Exercice 14

Reprenons la figure de l'énoncé, en la redessinant pour la lecture :

Les $15$ arcs sont donc : $$G\to A \; ; \; G\to B \; ; \; G\to C \; ; \; F\to A \; ; \; F\to B \; ; \; F\to E \; ; \; A\to B \; ; \; A\to C \; ; \; A\to D$$

1. L'ordre d'un graphe est son nombre de sommets. Ici les sommets sont $A$, $B$, $C$, $D$, $E$, $F$ et $G$ : $$\boxed{\text{le graphe est d'ordre } 7}$$

2. Le degré d'un sommet est le nombre d'arcs qui lui sont incidents, une boucle comptant deux fois (elle part du sommet et y arrive).

3. Chaque arc possède deux extrémités : il est donc compté exactement deux fois dans la somme des degrés. Cette somme vaut : $$5+6+4+4+4+4+3=30 \qquad \text{d'où} \qquad \boxed{\text{nombre d'arcs}=\frac{30}{2}=15}$$

4. Un chemin de longueur $5$ comporte $5$ arcs. La boucle en $B$ en fournit un immédiatement : $$\boxed{A\to B\to B\to B\to B\to C}$$ Il en existe d'autres, comme $A\to D\to F\to A\to B\to C$ ou encore $A\to D\to F\to A\to D\to C$. On peut d'ailleurs les compter : le coefficient $(A\,;C)$ de $M^{5}$ vaut $5$, il y a donc exactement cinq tels chemins.

5. Il faut revenir en $A$. Or les seuls arcs arrivant en $A$ viennent de $G$ et de $F$ ; comme aucun arc n'arrive en $G$, il faut passer par $F$, où l'on ne peut arriver que depuis $D$. Cela conduit directement au circuit : $$\boxed{A\to D\to F\to A \quad \text{convient : c'est un circuit de longueur } 3}$$

6. On lit sur le tableau de la question 2 que le degré sortant de $C$ est nul : aucun arc ne part de $C$. $$\boxed{\text{Non : il n'existe aucun circuit d'origine } C}$$ Le sommet $C$ est un puits : une fois qu'on y est arrivé, on ne peut plus en repartir.

7. En rangeant les sommets dans l'ordre $A$, $B$, $C$, $D$, $E$, $F$, $G$, le coefficient en ligne $i$ et colonne $j$ vaut $1$ s'il existe un arc du sommet $i$ vers le sommet $j$, et $0$ sinon : $$\boxed{M=\begin{pmatrix} 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}}$$ Deux contrôles : la somme de tous les coefficients vaut $15$, le nombre d'arcs ; et la ligne de $C$ est entièrement nulle, ce qui traduit bien que $C$ est un puits. Les deux boucles se lisent sur la diagonale, en $(B\,;B)$ et en $(E\,;E)$. Cette matrice n'est pas symétrique : le graphe est bien orienté.