Graphes — matrice d'adjacence et chemins

Exercice 1 — Matrice d'adjacence d'un graphe non orienté
1. $A = \begin{pmatrix}0&1&0&1\\1&0&1&1\\0&1&0&1\\1&1&1&0\end{pmatrix}$
2. On vérifie que $a_{ij}=a_{ji}$ pour tous $i,j$ : la matrice est bien symétrique (graphe non orienté).
3. Somme des lignes : $\deg(A)=2$, $\deg(B)=3$, $\deg(C)=2$, $\deg(D)=3$. Vérification : $\sum \deg = 10 = 2 \times 5$ arêtes.

Exercice 2 — Calcul de $A^2$ et dénombrement de chemins
1. $A^2 = A \times A$. Calcul ligne par ligne :
$(A^2)_{13}=(0)(0)+(1)(1)+(0)(0)+(1)(1)=0+1+0+1=2$
$(A^2)_{11}=(0)(0)+(1)(1)+(0)(0)+(1)(1)=2$, $(A^2)_{22}=(1)(1)+(0)(0)+(1)(1)+(1)(1)=3$, etc.
$$A^2=\begin{pmatrix}2&1&2&1\\1&3&1&2\\2&1&2&1\\1&2&1&3\end{pmatrix}$$
2. $(A^2)_{13}=2$ : 2 chaînes de longueur 2 entre A et C. Ce sont A→B→C et A→D→C.
3. $(A^2)_{22}=3$ : 3 chaînes de longueur 2 partant et revenant à B. Ce sont B→A→B, B→C→B, B→D→B (via chaque voisin de B).

Exercice 3 — Graphe orienté et accessibilité
1. Arcs : $1\to2$, $2\to3$, $3\to1$, $3\to2$.
2. $A^2 = \begin{pmatrix}0&0&1\\1&1&0\\0&1&1\end{pmatrix}$. Vérification : $(A^2)_{13}=0\cdot0+1\cdot1+0\cdot0=1$ (chemin $1\to2\to3$).
3. $(A^2)_{12}=0$ : il n'existe pas de chemin de longueur 2 de $s_1$ à $s_2$. En effet, depuis $s_1$, on atteint $s_2$ directement (longueur 1) ou on va en $s_3$ puis en $s_2$ (longueur 2 via $s_3$... mais $(A^2)_{12}=0+0+0=0$). Non, $s_2$ n'est pas accessible depuis $s_1$ en exactement 2 étapes.
4. $B_2 = A + A^2 = \begin{pmatrix}0&1&1\\1&1&1\\1&2&1\end{pmatrix}$. Le coefficient $(1,2)=1$ : il existe 1 chemin de longueur 1 ou 2 de $s_1$ à $s_2$ (l'arc direct $1\to2$).

Exercice 4 — Connexité et fermeture transitive
1. On remplace tout coefficient $\geq1$ par 1 :
$T = \begin{pmatrix}0&1&1\\1&1&1\\1&1&1\end{pmatrix}$
2. $t_{22}=1$ : $s_2$ peut se retrouver lui-même en 1 ou 2 étapes. Cela signifie qu'il existe un circuit passant par $s_2$ (par exemple $2\to3\to2$ de longueur 2).
3. Les coefficients hors-diagonale de $T$ : $t_{12}=t_{13}=t_{21}=t_{23}=t_{31}=t_{32}=1$. Tous sont égaux à 1, donc tout sommet atteint tout autre : le graphe est fortement connexe.

Exercice 5 — Problème de synthèse — Réseau de communication
1. $(A^2)_{14}=a_{11}\cdot a_{14}+a_{12}\cdot a_{24}+a_{13}\cdot a_{34}+a_{14}\cdot a_{44}=0+1\cdot1+1\cdot0+0=1$. Exactement 1 chemin de longueur 2 : $R_1\to R_2\to R_4$.
2. $A^2 = \begin{pmatrix}0&1&0&1\\1&0&0&0\\0&0&0&1\\0&1&1&0\end{pmatrix}$. $(A^2)_{34}=1$ : $R_3$ atteint $R_4$ en 2 sauts ($R_3\to R_2\to R_4$). Donc $(B_3)_{34}\geq1$ : oui, $R_3$ atteint $R_4$.
3. On calcule $A^3$ et $B_3$. Pour vérifier la forte connexité, on vérifie que $B_3$ a tous ses coefficients strictement positifs. Après calcul, $(B_3)_{24}=2\geq1$, $(B_3)_{42}=1\geq1$, etc. : le réseau est fortement connexe (chaque routeur peut atteindre tous les autres en au plus 3 sauts).