Terminale⏱ 1 heure

Graphes et matrices d'adjacence — Entraînement type évaluation

Pour un entraînement qui sert vraiment à quelque chose : pas de cours sous les yeux, une feuille et un crayon. Note-toi ensuite avec le corrigé.

Barème indicatif : 20 points. Exercice 1 sans calculatrice ; calculatrice autorisée ensuite.

Exercice 1 (4 points) — Automatismes

Réponds directement (0,5 point par question).

Nombre d'arêtes de $K_4$ ?
Un graphe a $10$ arêtes : somme des degrés ?
Peut-il y avoir exactement $3$ sommets de degré impair dans un graphe ?
La matrice d'adjacence d'un graphe non orienté est-elle toujours symétrique ?
Que représente le coefficient $(2, 5)$ de $A^4$ ?
Degré d'un sommet dans $K_7$ ?
$\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}^2$ ?
Un graphe connexe a tous ses sommets de degré pair : que peut-on affirmer ?

Voir le corrigé

$\dfrac{4 \times 3}{2} = 6$ .
$20$ .
Non : le nombre de sommets de degré impair est pair.
Oui.
Le nombre de chemins de longueur $4$ du sommet $2$ au sommet $5$ .
$6$ .
$I_2 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ .
Il admet un cycle eulérien.

Exercice 2 (4 points) — Démonstration de cours

Soit $A$ la matrice d'adjacence d'un graphe orienté à $p$ sommets. Démontre par récurrence que, pour tout $n \geqslant 1$ , le coefficient $(i, j)$ de $A^n$ est le nombre de chemins de longueur $n$ de $i$ à $j$ .

Voir le corrigé

Notons $a_{ij}^{(n)}$ le coefficient $(i, j)$ de $A^n$ et $c_{ij}^{(n)}$ le nombre de chemins de longueur $n$ de $i$ à $j$ . Initialisation : $c_{ij}^{(1)}$ est le nombre d'arcs de $i$ à $j$ , c'est-à-dire $a_{ij}$ . Hérédité : supposons $c_{ik}^{(n)} = a_{ik}^{(n)}$ pour tous $i$ , $k$ . Un chemin de longueur $n + 1$ de $i$ à $j$ est formé d'un chemin de longueur $n$ de $i$ à un sommet $k$ , puis d'un arc de $k$ à $j$ . Donc $c_{ij}^{(n+1)} = \sum_{k=1}^{p}c_{ik}^{(n)}a_{kj} = \sum_{k=1}^{p}a_{ik}^{(n)}a_{kj}$ , qui est le coefficient $(i, j)$ de $A^nA = A^{n+1}$ . La propriété est vraie pour tout $n \geqslant 1$ .

Exercice 3 (7 points) — Réseau de pistes cyclables

Une ville relie cinq quartiers $A$ , $B$ , $C$ , $D$ , $E$ par des pistes cyclables à double sens : $A - B$ , $A - C$ , $B - C$ , $B - D$ , $C - D$ , $C - E$ , $D - E$ .

Dessine le graphe et donne le degré de chaque sommet. (1,5 point)
Le graphe est-il connexe ? complet ? (1 point)
Un agent d'entretien veut parcourir chaque piste une seule fois. Est-ce possible ? Si oui, d'où doit-il partir, et où arrive-t-il ? Donne un tel parcours. (2 points)
Écris la matrice d'adjacence $M$ (ordre $A$ , $B$ , $C$ , $D$ , $E$ ) et, à la calculatrice, le coefficient $(A, E)$ de $M^3$ . Interprète. (2,5 points)

Voir le corrigé

Degrés : $A : 2$ , $B : 3$ , $C : 4$ , $D : 3$ , $E : 2$ .
Connexe (on va de tout quartier à tout autre). Non complet ( $A$ et $D$ ne sont pas reliés, par exemple).
Exactement deux sommets de degré impair ( $B$ et $D$ ) dans un graphe connexe : il existe une chaîne eulérienne, qui part de $B$ et arrive en $D$ (ou l'inverse). Exemple : $B - A - C - B - D - C - E - D$ .
$M = \begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 \end{pmatrix}$ . Le coefficient $(A, E)$ de $M^3$ vaut $3$ : il y a trois trajets empruntant exactement $3$ pistes de $A$ à $E$ ( $A - B - C - E$ , $A - B - D - E$ , $A - C - D - E$ ).

Exercice 4 (5 points) — Réseau social

Sur un réseau social, $1$ suit $2$ et $3$ , $2$ suit $3$ , $3$ suit $1$ .

Représente la situation par un graphe orienté et écris sa matrice d'adjacence $N$ . (1,5 point)
Calcule $N^2$ . Interprète le coefficient $(2, 1)$ . (1,5 point)
Calcule $N + N^2$ . Que représente le coefficient $(i, j)$ de cette matrice ? Quels comptes $i$ ne peuvent atteindre $j$ ni directement ni en passant par un intermédiaire ? (2 points)

Voir le corrigé

Arcs $1 \to 2$ , $1 \to 3$ , $2 \to 3$ , $3 \to 1$ . $N = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$ .
$N^2 = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{pmatrix}$ . Le coefficient $(2, 1)$ vaut $1$ : $2$ atteint $1$ en deux étapes ( $2 \to 3 \to 1$ ).
$N + N^2 = \begin{pmatrix} 1 & 1 & 2 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{pmatrix}$ : le coefficient $(i, j)$ est le nombre de chemins de longueur $1$ ou $2$ de $i$ à $j$ . Seul le coefficient $(2, 2)$ est nul : le compte $2$ ne « revient » pas sur lui-même en une ou deux étapes ; tous les autres couples sont reliés en au plus deux étapes.