Ressources · Terminale · Maths expertes (option Tle)

Matrice d’adjacence et chemins

Matrice d’adjacence d’un graphe orienté ou non ; degrés et nombre d’arêtes lus sur la matrice ; nombre de chemins de longueur k donné par Mᵏ, avec sa démonstration ; chemins fermés, triangles et coefficients nuls ; distance, diamètre et connexité.

À propos de cette page

Quatre problèmes corrigés dans l’esprit des sujets de maths expertes : recommandations dans un réseau professionnel et forte connexité, raccordement de six sites en fibre optique et pannes, déplacements d’un pion avec des fonctions Python, vols d’une compagnie en étoile avec une récurrence sur les puissances de M.

4 problèmes, du plus simple au plus difficile. Écris tes réponses, puis « Vérifier ».

Résoudre un problème : la méthode

J’écris la matrice en précisant l’ordre des sommets, et je la contrôle : symétrique si le graphe n’est pas orienté, sommes des lignes égales aux degrés.
Je traduis la question : « nombre de trajets en k étapes » = coefficient de $M^{k}$ ; « trajet fermé » = coefficient diagonal ; « au minimum combien d’étapes » = distance ; « peut-on toujours aller de… à… » = connexité.
Je calcule seulement ce qui sert : une ligne de $M^{k}$ , ou un coefficient par un produit ligne × colonne ; la calculatrice pour une matrice entière.
Je rédige la conclusion en citant le théorème et en interprétant le nombre dans la situation (comptes, sites, cases, vols).
Pour une formule générale ( $M^{3} = 4 M$ , $M^{2 n + 1} = 4^{n} M$ …), je raisonne sur les chemins ou par récurrence, en vérifiant l’initialisation.

Problème 1 · Recommandations dans un réseau professionnel★★★Moyen

Cinq comptes d’un réseau professionnel sont numérotés de

1

5

. On dit que «

i

recommande

j

» lorsqu’il existe un lien orienté de

i

vers

j

. Les recommandations sont :

1 \to 2

1 \to 4

2 \to 3

3 \to 1

3 \to 5

4 \to 3

5 \to 4

. Une recommandation se propage de proche en proche le long des liens. On note

M

la matrice d’adjacence de ce graphe orienté.

1. Écrire $M$ . Nombre de recommandations reçues par le compte $3$ :
$M$ $= (\begin{matrix} 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{matrix}) .$ Les recommandations reçues par le compte $3$ se lisent dans la colonne $3$ : $(0 1 0 1 0)$ , de somme $2$ (des comptes $2$ et $4$ ). C’est le degré entrant de $3$ .
2. Calculer $M^{2}$ et $M^{3}$ . Nombre de chemins de longueur $2$ du compte $1$ au compte $3$ :
$M^{2}$ $= (\begin{matrix} 0 & 0 & 2 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 2 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \end{matrix}), M^{3}$ $= (\begin{matrix} 2 & 0 & 0 & 0 & 2 \\ 0 & 1 & 0 & 2 & 0 \\ 0 & 0 & 3 & 0 & 0 \\ 0 & 1 & 0 & 2 & 0 \\ 1 & 0 & 0 & 0 & 1 \end{matrix}) .$ D’après le théorème, $(M^{2})_{13} = 2$ : il y a deux chemins de longueur $2$ de $1$ à $3$ , 1 → 2 → 3, 1 → 4 → 3. Le compte $1$ atteint le compte $3$ par deux intermédiaires différents.
3. Calculer la somme des coefficients diagonaux de $M^{3}$ et en déduire le nombre de circuits de longueur $3$ du réseau :
Rédaction attendue. La somme des coefficients diagonaux de $M^{3}$ vaut $2 + 1 + 3 + 2 + 1 = 9$ . Chaque circuit de longueur $3$ est compté une fois depuis chacun de ses trois sommets : il y a $9 \div 3 = 3$ circuits, $1 \to 2 \to 3 \to 1$ , $1 \to 4 \to 3 \to 1$ et $3 \to 5 \to 4 \to 3$ .
4. Coefficient ligne $5$ , colonne $2$ de $M + M^{2} + M^{3}$ : . Que peut-on en déduire sur la forte connexité du graphe ?
La ligne $5$ de la somme vaut $(0 0 0 1 0) + (0 0 1 0 0) + (1 0 0 0 1)$ $= (1 0 1 1 1)$ : son coefficient en colonne $2$ est nul, aucun chemin de longueur $1$ , $2$ ou $3$ ne va de $5$ à $2$ . On ne peut pas en conclure que le graphe n’est pas fortement connexe : il a $n = 5$ sommets, la propriété du cours porte sur $M + M^{2} + M^{3} + M^{4}$ , et un chemin de longueur $4$ reste possible.
5. Distance du compte $5$ au compte $2$ :
La ligne $5$ de $M^{4} = M^{3} \times M$ s’obtient à partir de la ligne $5$ de $M^{3}$ , $(1 0 0 0 1)$ : c’est la somme des lignes $1$ et $5$ de $M$ , $(0 1 0 2 0)$ . Le coefficient $(5; 2)$ vaut $1$ , alors qu’il était nul dans $M$ , $M^{2}$ et $M^{3}$ : $d (5; 2) = 4$ , et le seul chemin est 5 → 4 → 3 → 1 → 2.
6. Démontrer que le graphe est fortement connexe. Plus petit coefficient hors de la diagonale de $M + M^{2} + M^{3} + M^{4}$ :
Rédaction attendue. $M + M^{2} + M^{3} + M^{4}$ $= (\begin{matrix} 2 & 3 & 2 & 5 & 2 \\ 1 & 1 & 4 & 2 & 1 \\ 4 & 1 & 3 & 2 & 4 \\ 1 & 1 & 4 & 2 & 1 \\ 1 & 1 & 1 & 3 & 1 \end{matrix}) .$ Le graphe est d’ordre $5$ et tous les coefficients hors de la diagonale de cette somme sont non nuls (le plus petit vaut $1$ ) : le graphe est fortement connexe. Une recommandation partie de n’importe quel compte peut atteindre tous les autres, en quatre étapes au plus.

Problème 2 · Raccordement d’un réseau de fibre optique★★★Moyen

Un opérateur peut relier six sites, notés S₁ à S₆ (dans cet ordre), par les liaisons du tableau ci-dessous ; chaque liaison fonctionne dans les deux sens, et un signal peut transiter par plusieurs sites successifs. On note

M

la matrice d’adjacence du graphe non orienté associé.

Site	Liaisons possibles vers
S₁	S₂, S₃
S₂	S₁, S₃, S₄
S₃	S₁, S₂, S₅
S₄	S₂, S₅, S₆
S₅	S₃, S₄, S₆
S₆	S₄, S₅

1. Écrire $M$ . Nombre de liaisons possibles, déduit de la somme des coefficients de $M$ :
$M$ $= (\begin{matrix} 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 \end{matrix}) .$ Les sommes des lignes valent $2$ , $3$ , $3$ , $3$ , $3$ , $2$ ; la somme totale vaut $16 = 2 m$ : il y a $8$ liaisons possibles.
2. Calculer la première ligne de $M^{2}$ , puis celle de $M^{3}$ . Nombre de chaînes de longueur $3$ de S₁ à S₆ :
S₁ a pour voisins S₂ et S₃ : la première ligne de $M^{2}$ est la somme des lignes $2$ et $3$ de $M$ , $(1 0 1 1 0 0) + (1 1 0 0 1 0)$ $= (2 1 1 1 1 0)$ . La première ligne de $M^{3} = M^{2} \times M$ combine les lignes de $M$ avec ces coefficients : $2 L_{1} + L_{2} + L_{3} + L_{4} + L_{5}$ $= (2 4 4 2 2 2)$ . Le dernier coefficient vaut $2$ : il y a deux chaînes de longueur $3$ de S₁ à S₆, S₁–S₂–S₄–S₆, S₁–S₃–S₅–S₆.
3. Justifier que $d (S_{1}; S_{6}) =$
Rédaction attendue. Le coefficient $(1; 6)$ vaut $0$ dans $M$ (pas de liaison directe), $0$ dans $M^{2}$ (question précédente) et $2$ dans $M^{3}$ . La plus petite puissance qui donne un coefficient non nul est $3$ : $d (S_{1}; S_{6}) = 3$ .
4. La diagonale de $M^{3}$ vaut $(2, 2, 2, 2, 2, 2)$ . Nombre de triangles du réseau :
La somme des coefficients diagonaux vaut $12$ ; chaque triangle est compté $6$ fois : $12 \div 6 = 2$ triangles, S₁–S₂–S₃ et S₄–S₅–S₆. Chaque site appartient à un seul triangle ( $(M^{3})_{i i} = 2$ ) : dans chaque groupe de trois sites, deux sites restent reliés si la liaison directe entre eux tombe en panne.
5. Démontrer que le réseau reste connexe quand une seule liaison tombe en panne. Déterminer le nombre minimal de liaisons en panne qui coupent le réseau :
Rédaction attendue. Si une liaison d’un triangle tombe en panne (par exemple S₁–S₂), ses deux extrémités restent reliées par le troisième sommet du triangle (S₁–S₃–S₂), et toutes les autres liaisons fonctionnent : le réseau reste connexe. Si S₂–S₄ tombe en panne, la liaison S₃–S₅ relie encore les deux triangles, et réciproquement. Une seule panne ne coupe donc jamais le réseau. Si S₂–S₄ et S₃–S₅ tombent toutes les deux en panne, plus aucune liaison ne relie ${S_{1}, S_{2}, S_{3}}$ à ${S_{4}, S_{5}, S_{6}}$ : le réseau est coupé (deux pannes isolant S₁, sur S₁–S₂ et S₁–S₃, le couperaient aussi). Le nombre minimal est $2$ .
6. Le diamètre du réseau vaut $3$ . On ajoute la liaison S₁–S₆. Diamètre du nouveau réseau :
Seule la distance de S₁ à S₆ valait $3$ ; elle devient $1$ . Les autres paires de sites non reliés directement sont à distance $2$ : S₁–S₂–S₄, S₁–S₃–S₅, S₂–S₃–S₅, S₂–S₄–S₆, S₃–S₅–S₄ et S₃–S₅–S₆. Le nouveau diamètre vaut $2$ : deux sites quelconques communiquent en passant par au plus un site intermédiaire.

Problème 3 · Déplacements d’un pion et programme Python★★★Difficile

Un plateau de jeu comporte quatre cases numérotées de

1

4

. Un pion passe d’une case à une autre en suivant uniquement les déplacements autorisés :

1 \to 2

2 \to 1

2 \to 3

3 \to 4

4 \to 1

4 \to 2

. Un parcours de longueur

k

est une suite de

k

déplacements autorisés. On note

M

la matrice d’adjacence du graphe orienté associé, et on dispose des fonctions Python suivantes (les listes Python sont numérotées à partir de

0

def produit(A, B):
    n = len(A)
    C = [[0] * n for i in range(n)]
    for i in range(n):
        for j in range(n):
            s = 0
            for k in range(n):
                s = s + A[i][k] * B[k][j]
            C[i][j] = s
    return C

def puissance(M, k):
    P = M
    for i in range(k - 1):
        P = produit(P, M)
    return P

1. Écrire $M$ . Nombre de déplacements autorisés depuis la case $2$ :
$M$ $= (\begin{matrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \end{matrix}) .$ La ligne $2$ est $(1 0 1 0)$ : depuis la case $2$ , le pion peut aller en $1$ ou en $3$ .
2. Calculer $M^{2}$ et $M^{3}$ . Nombre de parcours de longueur $3$ de la case $2$ à la case $1$ :
$M^{2}$ $= (\begin{matrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \end{matrix}), M^{3}$ $= (\begin{matrix} 0 & 1 & 0 & 1 \\ 2 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{matrix}) .$ D’après le théorème, $(M^{3})_{21} = 2$ : ce sont 2 → 1 → 2 → 1, 2 → 3 → 4 → 1.
3. En remarquant que $M^{6} = M^{3} \times M^{3}$ , déterminer le nombre de parcours de longueur $6$ partant de la case $1$ et y revenant :
Rédaction attendue. Le nombre cherché est $(M^{6})_{11}$ , la ligne $1$ de $M^{3}$ multipliée par la colonne $1$ de $M^{3}$ : $(0 1 0 1)$ et $(0 2 1 1)$ donnent $0 \times 0 + 1 \times 2 + 0 \times 1 + 1 \times 1$ $= 3$ . Il y a $3$ parcours de longueur $6$ de la case $1$ à elle-même ; un seul produit ligne × colonne suffit.
4. Valeur renvoyée par puissance(M, 3)[1][0] : . Expliquer aussi pourquoi puissance(M, 1) renvoie bien $M$ .
Les indices Python commencent à $0$ : [1][0] désigne la deuxième ligne et la première colonne, c’est-à-dire le coefficient $(M^{3})_{21}$ , qui vaut $2$ . Avec $k = 1$ , la boucle for i in range(k - 1) parcourt range(0), qui est vide : P garde sa valeur initiale M, qui est renvoyée, ce qui correspond à $M^{1} = M$ .
5. Distance de la case $3$ à la case $2$ :
Le coefficient $(3; 2)$ vaut $0$ dans $M$ et $1$ dans $M^{2}$ : $d (3; 2) = 2$ , par $3 \to 4 \to 2$ .
6. Déterminer le diamètre du graphe et l’interpréter :
Rédaction attendue. Les coefficients de $M$ et de $M^{2}$ couvrent tous les couples de cases distinctes, sauf le couple $(1; 4)$ , nul dans les deux ; il vaut $1$ dans $M^{3}$ , donc $d (1; 4) = 3$ , par $1 \to 2 \to 3 \to 4$ . Toutes les autres distances valent $1$ ou $2$ : le diamètre vaut $3$ . Depuis n’importe quelle case, le pion atteint n’importe quelle autre en trois déplacements au plus, et il lui en faut trois pour aller de $1$ à $4$ .

Problème 4 · Les vols d’une compagnie en étoile★★★Difficile

Une compagnie aérienne relie un aéroport central O à quatre villes A, B, C, D : chaque ligne relie O à l’une des villes, dans les deux sens, et il n’y a aucune autre ligne. Un trajet de

k

vols est une chaîne de longueur

k

du graphe non orienté de sommets O, A, B, C, D (dans cet ordre) ; on note

M

sa matrice d’adjacence.

1. Écrire $M$ et calculer $M^{2}$ . Nombre de trajets de $2$ vols de A à B :
$M$ $= (\begin{matrix} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \end{matrix}), M^{2}$ $= (\begin{matrix} 4 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \end{matrix}) .$ $(M^{2})_{23} = 1$ : le seul trajet de deux vols de A à B est A–O–B.
2. Déterminer, en justifiant, le nombre de trajets de $5$ vols de A à B :
Rédaction attendue. Les sommets se partagent en deux groupes, ${O}$ et ${A, B, C, D}$ , et chaque ligne relie O à une ville : un trajet change de groupe à chaque vol. Après un nombre impair de vols, on n’est plus dans le groupe de départ ; partant d’une ville, on arrive donc en O, jamais dans une ville. Aucun trajet d’un nombre impair de vols ne relie deux villes : $(M^{5})_{23} = 0$ .
3. Démontrer que $M^{3} = 4 M$ . Nombre de trajets de $3$ vols de O à A :
Rédaction attendue. On a $M^{3}$ $= M^{2} \times M$ $= (\begin{matrix} 0 & 4 & 4 & 4 & 4 \\ 4 & 0 & 0 & 0 & 0 \\ 4 & 0 & 0 & 0 & 0 \\ 4 & 0 & 0 & 0 & 0 \\ 4 & 0 & 0 & 0 & 0 \end{matrix})$ $= 4 M .$ On le retrouve par les chemins : un trajet de $3$ vols de O vers une ville s’écrit O– $x$ –O–ville, avec $x$ l’une des $4$ villes, soit $4$ trajets, et de même d’une ville vers O ; entre deux sommets du même groupe, il n’y en a aucun (nombre impair de vols). Ce sont exactement les coefficients de $4 M$ .
4. Démontrer par récurrence que, pour tout entier $n ⩾ 1$ , $M^{2 n + 1} = 4^{n} M$ . Nombre de trajets de $7$ vols de O à A :
Rédaction attendue. Pour $n ⩾ 1$ , on note $P (n)$ : « $M^{2 n + 1} = 4^{n} M$ ». Initialisation : $M^{3} = 4 M = 4^{1} M$ , $P (1)$ est vraie. Hérédité : si $M^{2 n + 1} = 4^{n} M$ pour un entier $n ⩾ 1$ , alors $M^{2 n + 3}$ $= M^{2 n + 1} \times M^{2}$ $= 4^{n} M \times M^{2}$ $= 4^{n} M^{3}$ $= 4^{n} \times 4 M$ $= 4^{n + 1} M$ : $P (n + 1)$ est vraie. Conclusion : $P (n)$ est vraie pour tout $n ⩾ 1$ . Avec $7 = 2 \times 3 + 1$ : $(M^{7})_{12} = 4^{3} \times 1 = 64$ trajets.
5. En déduire que $M^{2 n} = 4^{n - 1} M^{2}$ pour tout $n ⩾ 1$ . Nombre de trajets de $6$ vols de A à C :
Rédaction attendue. Pour $n = 1$ , $M^{2} = 4^{0} M^{2}$ . Pour $n ⩾ 2$ , $M^{2 n}$ $= M^{2 (n - 1) + 1} \times M$ $= 4^{n - 1} M \times M$ $= 4^{n - 1} M^{2}$ , d’après la question précédente. Avec $n = 3$ : $(M^{6})_{24}$ $= 4^{2} \times (M^{2})_{24}$ $= 16 \times 1$ $= 16$ trajets.
6. Le programme ci-dessous cherche un nombre de vols. Valeur affichée :
```
k = 2
t = 4
while t <= 1000000:
    k = k + 2
    t = 4 * t
print(k)
```
D’après la question précédente, le nombre de trajets de $k = 2 n$ vols partant de O et y revenant vaut $(M^{2 n})_{11} = 4^{n - 1} \times 4 = 4^{n}$ ; la variable t contient ce nombre pour la valeur courante de k ( $k = 2$ , $t = 4$ ). Le programme affiche le plus petit nombre pair de vols pour lequel il y a plus d’un million de trajets fermés depuis O. Or $4^{9}$ $= 262 144 ⩽ 1 000 000 < 4^{10}$ $= 1 048 576$ : la boucle s’arrête pour $n = 10$ , et le programme affiche $k = 20$ .

Bloqué sur ce chapitre ?

Moi c'est Ben, j'ai créé ce site pour aider le plus d'élèves possible, partout en France. Je peux aussi reprendre avec toi ce qui coince en cours particulier : en visio, ou à domicile si tu es à Marseille.

Réserver un 1^er cours → Voir les tarifs

Prof de maths à Marseille · Cours particuliers au lycée · Aide aux devoirs