Terminale

Graphes et matrices d'adjacence — Exercices d'application

1. Graphes, degrés

Exercice 1 — ⭐

On considère le graphe de la figure 1 du cours (sommets $A$ , $B$ , $C$ , $D$ , $E$ ; arêtes $AB$ , $AD$ , $BC$ , $BD$ , $CD$ , $CE$ , $DE$ ).

Donne l’ordre du graphe et le degré de chaque sommet. Vérifie le lemme des poignées de main.
Le graphe est-il complet ? Combien d’arêtes faudrait-il ajouter pour qu’il le soit ?
Cite un sommet adjacent à tous les autres.

Voir le corrigé

Ordre $5$ . Degrés : $A : 2$ , $B : 3$ , $C : 3$ , $D : 4$ , $E : 2$ . Somme $14 = 2 \times 7$ arêtes. ✓
Non ( $A$ et $C$ ne sont pas adjacents, par exemple). $K_5$ a $\dfrac{5 \times 4}{2} = 10$ arêtes : il faut en ajouter $3$ ( $AC$ , $AE$ , $BE$ ).
$D$ (degré $4$ ).

Exercice 2 — ⭐⭐

Un graphe a $8$ sommets, tous de degré $3$ . Combien a-t-il d’arêtes ?
Existe-t-il un graphe à $5$ sommets de degrés $1$ , $2$ , $2$ , $3$ , $3$ ? Et de degrés $1$ , $1$ , $2$ , $3$ , $3$ ?
Dans un groupe de $9$ amis, chacun envoie un message à exactement $5$ autres membres, et les messages sont réciproques (si $X$ écrit à $Y$ , $Y$ écrit à $X$ ). Est-ce possible ?

Voir le corrigé

Somme des degrés $24 = 2 \times$ arêtes : $12$ arêtes.
Somme $11$ , impaire : impossible. Somme $10$ : c’est possible (par exemple sommets $a$ , $b$ de degré 1, $c$ de degré 2, $d$ , $e$ de degré 3 avec les arêtes $ad$ , $be$ , $cd$ , $ce$ , $de$ ).
On aurait un graphe à $9$ sommets tous de degré $5$ : somme $45$ , impaire. Impossible.

2. Chaînes et connexité

↩ Revoir le cours

Exercice 3 — ⭐⭐

Un réseau de métro compte $6$ stations. Les lignes relient $S_1 - S_2$ , $S_2 - S_3$ , $S_3 - S_1$ , $S_4 - S_5$ et $S_5 - S_6$ .

Dessine le graphe. Est-il connexe ?
Donne une chaîne de longueur $3$ partant de $S_1$ et y revenant.
Quelle ligne suffit-il d’ajouter pour que le réseau devienne connexe ? Après cet ajout, quelle est la plus grande distance (nombre minimal de liaisons) entre deux stations ?

Voir le corrigé

Deux « morceaux » : $\{S_1, S_2, S_3\}$ et $\{S_4, S_5, S_6\}$ ; il n’est pas connexe.
$S_1 - S_2 - S_3 - S_1$ .
Une ligne entre un sommet du premier groupe et un du second, par exemple $S_3 - S_4$ . Alors la plus grande distance est entre $S_1$ (ou $S_2$ ) et $S_6$ : $S_1 - S_3 - S_4 - S_5 - S_6$ , soit $4$ liaisons.

3. Matrice d’adjacence

↩ Revoir le cours

Exercice 4 — ⭐

Écris la matrice d’adjacence du graphe de la figure 1 (ordre $A$ , $B$ , $C$ , $D$ , $E$ ). Vérifie qu’elle est symétrique et que la somme de chaque ligne est le degré du sommet.
Dessine le graphe orienté de matrice $M = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}$ (sommets $1$ , $2$ , $3$ ).

Voir le corrigé

$\begin{pmatrix} 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 \end{pmatrix}$ ; sommes des lignes : $2$ , $3$ , $3$ , $4$ , $2$ .
Arcs : $1 \to 2$ , $2 \to 3$ , $3 \to 1$ , $3 \to 2$ .

4. Compter les chemins avec les puissances de A

↩ Revoir le cours

Exercice 5 — ⭐⭐

On reprend la matrice $M$ de l’exercice 4.

Calcule $M^2$ et $M^3$ .
Combien y a-t-il de chemins de longueur $3$ allant de $3$ à $3$ ? Décris-les.
Combien y a-t-il de chemins de longueur $3$ au total ?

Voir le corrigé

$M^2 = \begin{pmatrix} 0 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}$ et $M^3 = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix}$ .
Coefficient $(3, 3)$ de $M^3$ : $1$ . C’est le chemin $3 \to 1 \to 2 \to 3$ .
Somme des coefficients de $M^3$ : $7$ .

Exercice 6 — ⭐⭐⭐

Réseau aérien. Quatre aéroports $P$ , $L$ , $M$ , $N$ sont reliés par des vols directs dans les deux sens : $P - L$ , $P - M$ , $P - N$ et $L - M$ .

Écris la matrice d’adjacence $A$ (ordre $P$ , $L$ , $M$ , $N$ ).
À l’aide de la calculatrice ou de Python, calcule $A^2$ et $A^3$ .
Combien de trajets en exactement $2$ vols relient $N$ à $M$ ? Lesquels ?
Combien de trajets en exactement $3$ vols partent de $P$ et y reviennent ?

Voir le corrigé

$A = \begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix}$ .
$A^2 = \begin{pmatrix} 3 & 1 & 1 & 0 \\ 1 & 2 & 1 & 1 \\ 1 & 1 & 2 & 1 \\ 0 & 1 & 1 & 1 \end{pmatrix}$ et $A^3 = \begin{pmatrix} 2 & 4 & 4 & 3 \\ 4 & 2 & 3 & 1 \\ 4 & 3 & 2 & 1 \\ 3 & 1 & 1 & 0 \end{pmatrix}$ .
Coefficient $(N, M)$ de $A^2$ : $1$ ; c’est $N - P - M$ .
Coefficient $(P, P)$ de $A^3$ : $2$ ; ce sont $P - L - M - P$ et $P - M - L - P$ .

5. Graphes eulériens (pour aller plus loin)

↩ Revoir le cours

Exercice 7 — ⭐⭐

Le graphe de la figure 1 admet-il une chaîne eulérienne ? un cycle eulérien ? Si oui, donne-en une.
Peut-on dessiner une « enveloppe ouverte » (un carré avec ses deux diagonales et un triangle posé dessus) sans lever le crayon ni repasser sur un trait ? On comptera les degrés des $5$ sommets.

Voir le corrigé

Degrés $2$ , $3$ , $3$ , $4$ , $2$ : exactement deux sommets impairs ( $B$ et $C$ ), graphe connexe. Il existe une chaîne eulérienne de $B$ à $C$ mais pas de cycle eulérien. Exemple : $B - A - D - B - C - D - E - C$ (7 arêtes, chacune une fois).
Le carré $ABCD$ avec ses diagonales et le sommet $E$ du toit relié à $A$ et $B$ : degrés $A : 4$ , $B : 4$ , $C : 3$ , $D : 3$ , $E : 2$ . Deux sommets impairs : c’est possible, en partant de $C$ (ou de $D$ ) et en finissant à l’autre.