TP : Représentation par matrice d'adjacence 
Si nécessaire, revoir le cours sur les graphes et notamment les notions de sommet, arête, voisin, degré, matrice d'adjacence...
Représentation par matrice d'adjacence¶
Dans cette partie, on utilise uniquement des graphes non orientés.
Exercice
Définir une fonction make_matrix telle que make_matrix(n, p) renvoie une matrice $n\times p$ avec que des $0$. On rappelle qu'une matrice est définie par une liste de listes, où chaque sous-liste représente une ligne de la matrice.
Solution
# version "basique" :
def make_matrix(n, p):
M = []
for i in range(n):
L = [] # ième ligne
for i in range(p):
L.append(0)
M.append(L)
return M
# version rapide :
def make_matrix(n, p):
return [[0]*p for i in range(n)]
make_matrix(3, 4)
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Exercice
Ecrire une fonction add_edge telle que add_edge(G, u, v) ajoute l'arête entre les sommets u et v dans un graphe G non-orienté représenté par matrice d'adjacence.
Solution
def add_edge(G, u, v):
G[u][v] = 1
G[v][u] = 1
Exercice
Définir dans une variable G la matrice d'adjacence du graphe suivant (on pourra éventuellement utiliser les fonctions précédentes) :
Solution
G = make_matrix(7, 7)
for u, v in [(3, 4), (3, 1), (1, 2), (4, 1), (4, 2), (2, 5), (4, 5), (0, 6)]:
add_edge(G, u, v)
G
[[0, 0, 0, 0, 0, 0, 1], [0, 0, 1, 1, 1, 0, 0], [0, 1, 0, 0, 1, 1, 0], [0, 1, 0, 0, 1, 0, 0], [0, 1, 1, 1, 0, 1, 0], [0, 0, 1, 0, 1, 0, 0], [1, 0, 0, 0, 0, 0, 0]]
Exercice
Définir une fonction voisins telle que voisins(G, v) renvoie la liste des voisins du sommet v.
Vérifier que les voisins du sommet $2$ dans le graphe ci-dessus sont les sommets $1$, $4$, $5$.
Solution
def voisins(G, v):
L = []
for j in range(len(G[v])): # parcours de la ligne v
if G[v][j] == 1:
L.append(j)
return L
voisins(G, 2)
[1, 4, 5]
Exercice
En déduire une fonction deg telle que deg(G, v) renvoie le degré du sommet v.
Solution
def deg(G, v):
return len(voisins(G, v))
deg(G, 2)
3
Exercice
Écrire une fonction n_aretes pour calculer le nombre d'arêtes d'un graphe donné par matrice d'adjacence. Tester avec le graphe G précédent. On pourra soit réutiliser deg, soit deux boucles for pour parcourir les éléments de la matrice.
Solution
def n_aretes(G):
n = 0
for i in range(len(G)): # lignes
for j in range(len(G[0])): # colonnes
if G[i][j] == 1:
n += 1
return n//2 # chaque arête apparaît deux fois dans un graphe non-orienté
n_aretes(G)
8
Puissance de la matrice d'adjacence¶
Exercice
Écrire une fonction produit telle que, si A et B sont deux matrices compatibles, produit(A, B) renvoie une matrice contenant le produit AB de A et B.
On rappelle que, si $A = (a_{i, k})$ est de taille $n\times p$ et $B = (b_{k, j})$ de taille $p\times q$ alors $AB$ est de taille $n\times q$ et :
$$AB = (c_{i, k}), ~\text{ où } c_{i, k} = \sum_{j = 0}^{p - 1} a_{i, j} b_{j, k}$$
On pourra utiliser make_matrix pour créer la matrice du résultat et remplir ses éléments un par un.
Tester avec deux matrices $2\times 3$ et $3\times 2$ de votre choix et vérifier en faisant aussi le produit à la main.
Solution
def produit(A, B):
n, p, q = len(A), len(B), len(B[0])
C = make_matrix(n, q)
for i in range(n):
for k in range(q):
for j in range(p):
C[i][k] += A[i][j]*B[j][k] # calcul de la somme
return C
A = [[1, 2, 3], [4, 5, 6]]
B = [[1, 2], [1, 2], [1, 2]]
produit(A, B)
[[6, 12], [15, 30]]
Exercice
En déduire une fonction puissance telle que puissance(A, k) renvoie $A^k$. Vérifier sur un exemple.
Solution
def puissance(A, k):
M = A
for i in range(k - 1):
M = produit(M, A)
return M
A = [[1, 1], [0, 1]]
puissance(A, 4)
[[1, 4], [0, 1]]
Exercice
Quelle est la complexité de puissance(A, k), pour une matrice A de taille $n\times n$ ?
M'appeler pour que je puisse vérifier.
Solution
Si A est de taille $p\times q$ et B de taille $q\times n$, produit(A, B) est en O($pqn$). En effet, produit(A, B) doit remplir les $p\times n$ cases de C, chaque case demandant le calcul d'une somme de $q$ éléments. Ici, les matrices sont carrés donc $n = p = q$.
Comme puissance(A, k) appelle $k$ fois produit sur deux matrices $n\times n$, d'où une complexité $\boxed{\text{O}(kn^3)}$.
Exercice
Soit $A = (a_{i, j})$ la matrice d'adjacence d'un graphe $G$ (orienté ou non). Soit $A^k = A\times ... \times A$. On note $a^k_{i, j}$ le coefficient ligne $i$, colonne $j$ de $A^k$.
Montrer par récurrence sur $k$ que $a^k_{i, j}$ est égal au nombre de chemins de longueur $k$ du graphe $G$.
On pourra commencer par donner une équation de récurrence sur $a^k_{i, j}$.
Merci de m'appeler pour que je vérifie votre raisonnement.
Exercice
En utilisant la question précédente et la fonction puissance, trouver le nombre de chemins de longueur $100$ du sommet $0$ au sommet $2$ dans le graphe suivant :
Solution
G = [[1, 1, 0], [0, 1, 1], [0, 0, 1]] # matrice d'adjacence
puissance(G, 100) # le nombre de chemins est 4950
[[1, 100, 4950], [0, 1, 100], [0, 0, 1]]
Exercice
Retrouver mathématiquement le résultat précédent, en utilisant seulement du dénombrement (pas de matrice d'adjacence).
Solution
Pour choisir un chemin de longueur $100$ de $0$ à $2$, il faut choisir les deux étapes parmi $100$ qui vont changer de sommets. Le nombre cherché est donc :$$\boxed{\binom{100}{2} = 4950}$$
Exercice
Réécrire puissance(A, k) de façon à avoir une complexité O($n^3\log(k)$), où A est de taille $n\times n$.
On pourra utiliser la technique de l'exponentiation rapide du TP dichotomie du 1er semestre.
Exercice
Pour ceux qui auraient fini le TP, voici d'autres questions plus théoriques/difficiles :
- Montrer que dans tout graphe avec au moins 2 sommets, il existe 2 sommets de même degré.
- Si $G = (V, E)$ est un graphe on définit ${}^c G = (V, {}^c{E})$ (le graphe complémentaire, contenant les arêtes qui n'existent pas dans $G$). Montrer que $G$ ou ${}^c G$ est connexe. Est-il possible que les deux soient connexes?