Graphes et matrices d’adjacence Terminale : 9 exercices corrigés

Le cours de Graphes et matrices d'adjacence permet de passer d'un graphe orienté au degré d'un sommet puis à une matrice d'adjacence, en fixant toujours l'ordre des sommets.

Chaque chemin de longueur donnée est ensuite relié à une puissance de matrice ou à un produit matriciel, tandis que la parité des degrés décide d'une chaîne eulérienne.

Lire et représenter un graphe

Fixer l'ordre des sommets.

Exercice 1 : Degrés d’un graphe

Facile

Un graphe non orienté a pour degrés 2, 3, 3, 4.

  1. Calculer le nombre d'arêtes.
  2. Pourquoi la somme doit-elle être paire ?
Voir le corrigé
  1. La somme vaut 12, donc le graphe possède 12/2=612/2=6 arêtes.
  2. Chaque arête contribue une unité au degré de chacune de ses deux extrémités.

Exercice 2 : Longueur d’une chaîne

Facile

On parcourt A, C, D, B, A.

  1. Quelle est la longueur de cette chaîne ?
  2. Est-ce un cycle ?
Voir le corrigé
  1. Elle utilise quatre arêtes, donc sa longueur vaut 4.
  2. Oui si les quatre arêtes existent : le parcours est fermé et ne répète pas d'arête.

Exercice 3 : Construire une matrice

Moyen

Dans l'ordre A, B, C, les arêtes sont AB, AC et BC, sans boucle.

  1. Écrire la matrice d'adjacence.
  2. Justifier sa symétrie.
Voir le corrigé
  1. A=(011101110)A=\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}.
  2. Le graphe est non orienté : chaque arête ij fournit aussi l'entrée ji.

Exercice 4 : Graphe orienté

Moyen

Les arcs sont A vers B, A vers C, C vers A et C vers B.

  1. Écrire la matrice dans l'ordre A, B, C.
  2. Donner les degrés sortants.
Voir le corrigé
  1. A=(011000110)A=\begin{pmatrix}0&1&1\\0&0&0\\1&1&0\end{pmatrix}.
  2. Ils valent respectivement 2, 0 et 2.

Calculer avec la matrice

Interpréter chaque coefficient.

Exercice 5 : Chemins de longueur deux

Moyen

On reprend le triangle complet sans boucle.

  1. Calculer A2A^2.
  2. Interpréter le coefficient diagonal 2.
Voir le corrigé
  1. A2=(211121112)A^2=\begin{pmatrix}2&1&1\\1&2&1\\1&1&2\end{pmatrix}.
  2. Depuis chaque sommet, deux chemins de longueur 2 reviennent au départ.

Exercice 6 : Produit non commutatif

Moyen

Soient A=(1101)A=\begin{pmatrix}1&1\\0&1\end{pmatrix} et B=(1011)B=\begin{pmatrix}1&0\\1&1\end{pmatrix}.

  1. Calculer AB.
  2. Calculer BA et comparer.
Voir le corrigé
  1. AB=(2111)AB=\begin{pmatrix}2&1\\1&1\end{pmatrix}.
  2. BA=(1112)BA=\begin{pmatrix}1&1\\1&2\end{pmatrix}, donc AB≠BAAB\neq BA.

Exercice 7 : Puissance d’une matrice triangulaire

Difficile

On pose M=(1101)M=\begin{pmatrix}1&1\\0&1\end{pmatrix}.

  1. Conjecturer MnM^n.
  2. Démontrer la formule par récurrence.
  3. Vérifier pour n = 5.
Indication
Calculer M² et M³ avant la récurrence.
Voir le corrigé
  1. Les premiers calculs suggèrent Mn=(1n01)M^n=\begin{pmatrix}1&n\\0&1\end{pmatrix}.
  2. Le produit par M transforme n en n + 1 dans le coefficient supérieur droit, les autres coefficients restant inchangés.
  3. M5=(1501)M^5=\begin{pmatrix}1&5\\0&1\end{pmatrix}.

Exercice 8 : Réseau de correspondances

Difficile

Une matrice d'adjacence A modélise des trajets directs entre quatre stations.

  1. Que compte (A3)2,4(A^3)_{2,4} ?
  2. Comment compter les trajets de longueur au plus 3 ?
  3. Pourquoi ajouter I ?
Indication
Associer chaque puissance à une longueur exacte.
Voir le corrigé
  1. Le nombre de trajets de longueur 3 allant de la station 2 à la station 4.
  2. On lit le coefficient correspondant dans I+A+A2+A3I+A+A^2+A^3.
  3. I compte le trajet de longueur 0, utile lorsque départ et arrivée coïncident.

Décider à partir des degrés

Relier une propriété globale à la parité des sommets.

Exercice 9 : Chaîne eulérienne ou cycle eulérien

Moyen

Un graphe connexe possède quatre sommets de degrés 3, 3, 2 et 2.

  1. Compter les sommets de degré impair.
  2. Décider si une chaîne eulérienne existe.
  3. Un cycle eulérien existe-t-il ?
Voir le corrigé
  1. Il y en a exactement deux, ceux de degré 3.
  2. Oui : un graphe connexe ayant exactement deux sommets de degré impair admet une chaîne eulérienne ouverte entre ces deux sommets.
  3. Non, car un cycle eulérien exigerait que tous les degrés soient pairs.
Partager