Graphes

Sommets • arêtes • chemins • graphes orientés • liens avec les matrices (matrice d’adjacence) • parcours et applications (niveau Maths Expertes).

Cours Exercices Fiche Quiz
Prévisualiser (PDF) Télécharger
Exercices — Graphes (niveau 19–20/20)
Matrice d’adjacence • puissances • comptage de chemins • interprétation • pièges Bac.
Exercice 1 — Construire la matrice d’adjacence (piège ligne/colonne)
On considère le graphe orienté \(G\) de sommets \(S=\{1,2,3,4,5\}\) dont les arcs sont : \[ 1\to2,\; 1\to4,\; 2\to3,\; 2\to5,\; 3\to1,\; 3\to4,\; 4\to2,\; 5\to4. \]
  1. Construire la matrice d’adjacence \(A\) (ordre \(1,2,3,4,5\)).
  2. Déterminer le degré sortant et le degré entrant du sommet \(4\).
  3. Le graphe est-il symétrique ? justifier.
Correction Afficher / Masquer
\[ A= \begin{pmatrix} 0&1&0&1&0\\ 0&0&1&0&1\\ 1&0&0&1&0\\ 0&1&0&0&0\\ 0&0&0&1&0 \end{pmatrix} \]
  • Degré sortant de \(4\) = nombre de 1 sur la ligne 4 : \(1\) (arc \(4\to2\)).
  • Degré entrant de \(4\) = nombre de 1 sur la colonne 4 : \(3\) (arcs \(1\to4,3\to4,5\to4\)).
  • Non : par exemple \(a_{14}=1\) mais \(a_{41}=0\), donc \(A\) n’est pas symétrique.
⚠️ Piège Bac : ligne = départ, colonne = arrivée.
Exercice 2 — \(A^2\) : compter les chemins de longueur 2
On reprend la matrice \(A\) de l’exercice 1.
  1. Calculer \((A^2)_{1,3}\) et interpréter.
  2. Calculer \((A^2)_{2,4}\) et interpréter.
  3. Sans calculer toute la matrice \(A^2\), déterminer \((A^2)_{4,5}\).
Correction Afficher / Masquer
Rappel : \[ (A^2)_{ij}=\sum_{k=1}^5 a_{ik}a_{kj} \] et \((A^2)_{ij}\) = nombre de chemins de longueur 2 de \(i\) vers \(j\).
  • \[ (A^2)_{1,3}=\sum_k a_{1k}a_{k3} =a_{12}a_{23}+a_{14}a_{43} =1\cdot1+1\cdot0=1. \] Interprétation : un chemin de longueur 2 de \(1\) vers \(3\) : \(1\to2\to3\).
  • \[ (A^2)_{2,4}=\sum_k a_{2k}a_{k4} =a_{23}a_{34}+a_{25}a_{54} =1\cdot1+1\cdot1=2. \] Interprétation : deux chemins de longueur 2 de \(2\) vers \(4\) : \(2\to3\to4\) et \(2\to5\to4\).
  • De \(4\), on ne peut aller qu’à \(2\). Donc tout chemin de longueur 2 partant de \(4\) est \(4\to2\to(\cdots)\). Or \(2\to5\) existe, donc \[ (A^2)_{4,5}=1. \]
⚠️ Piège Bac : \((A^2)_{ij}\) ne donne pas la connectivité directe, mais les chemins de longueur 2.
Exercice 3 — \(A^3\) : chemins de longueur 3 et distinction des chemins
Toujours avec le graphe de l’exercice 1 :
  1. Déterminer \((A^3)_{1,4}\) et interpréter.
  2. Donner explicitement tous les chemins de longueur 3 de \(1\) vers \(4\).
  3. Expliquer pourquoi « passer par les mêmes sommets dans un autre ordre » change le chemin.
Correction Afficher / Masquer
On peut écrire : \[ (A^3)_{1,4}=\sum_{k=1}^5 (A^2)_{1k}a_{k4}. \] Ici, on raisonne vite par comptage.
Depuis \(1\), on va vers \(2\) ou \(4\).
  • Si \(1\to4\), il reste 2 arcs depuis \(4\). Or depuis \(4\), on doit faire \(4\to2\to\cdots\). Pour revenir en \(4\) en 2 arcs, il faudrait \(4\to2\to4\), mais \(2\to4\) n’existe pas. Donc 0 chemin via ce départ.
  • Si \(1\to2\), il reste des chemins de longueur 2 de \(2\) vers \(4\), et d’après l’exo 2, il y en a 2.
Donc \[ (A^3)_{1,4}=2. \]
  • Chemins de longueur 3 de \(1\) vers \(4\) : \[ 1\to2\to3\to4 \quad \text{et} \quad 1\to2\to5\to4. \]
  • Un chemin est une suite ordonnée de sommets : changer l’ordre change le chemin.
⚠️ Piège : « même ensemble de sommets » ne suffit pas ; l’ordre et les arcs comptent.
Exercice 4 — Accessibilité : “peut-on atteindre ?”
On conserve le graphe de l’exercice 1.
  1. Montrer que \(1\) peut atteindre \(5\) (donner un chemin).
  2. Le sommet \(5\) peut-il atteindre \(1\) ? (justifier)
  3. Déterminer si le graphe est fortement connexe.
Correction Afficher / Masquer
  • \(1\to2\to5\) : donc oui.
  • \(5\to4\to2\to3\to1\) : donc oui.
  • Comme on peut atteindre \(1\leftrightarrow5\) et que les arcs donnent aussi \(2\to3\to1\to4\to2\), on peut atteindre chaque sommet depuis chaque autre : le graphe est fortement connexe.
⚠️ Piège Bac : “connexe” (non orienté) ≠ “fortement connexe” (orienté).
Exercice 5 — Graphe non orienté : symétrie et degrés
On considère un graphe non orienté à 6 sommets \(S=\{1,2,3,4,5,6\}\) dont les arêtes sont : \[ \{1,2\},\{1,3\},\{1,6\},\{2,3\},\{2,4\},\{3,5\},\{4,5\},\{5,6\}. \]
  1. Construire la matrice d’adjacence \(B\).
  2. Calculer les degrés de tous les sommets.
  3. Vérifier la relation \(\sum \deg = 2m\) où \(m\) est le nombre d’arêtes.
Correction Afficher / Masquer
\[ B= \begin{pmatrix} 0&1&1&0&0&1\\ 1&0&1&1&0&0\\ 1&1&0&0&1&0\\ 0&1&0&0&1&0\\ 0&0&1&1&0&1\\ 1&0&0&0&1&0 \end{pmatrix} \]
  • \(\deg(1)=3\), \(\deg(2)=3\), \(\deg(3)=3\), \(\deg(4)=2\), \(\deg(5)=3\), \(\deg(6)=2\).
  • Somme \(=3+3+3+2+3+2=16\).
  • Nombre d’arêtes \(m=8\) donc \(2m=16\). OK.
⚠️ Piège : en non orienté, la matrice d’adjacence est symétrique.
Exercice 6 — Interprétation type “processus” (états → transitions)
Un système possède 4 états \(\{1,2,3,4\}\). Les transitions possibles à chaque étape sont : \[ 1\to2,\; 1\to3,\; 2\to2,\; 2\to4,\; 3\to1,\; 3\to4,\; 4\to3. \]
  1. Écrire la matrice d’adjacence \(A\) (ordre \(1,2,3,4\)).
  2. Calculer \((A^2)_{3,4}\) et interpréter.
  3. Le coefficient \((A^3)_{2,2}\) est-il nécessairement \(\ge 1\) ? expliquer.
Correction Afficher / Masquer
\[ A= \begin{pmatrix} 0&1&1&0\\ 0&1&0&1\\ 1&0&0&1\\ 0&0&1&0 \end{pmatrix} \]
  • \[ (A^2)_{3,4}=\sum_{k=1}^4 a_{3k}a_{k4} =a_{31}a_{14}+a_{34}a_{44}+a_{33}a_{34}+a_{32}a_{24} =1\cdot0+1\cdot0+0\cdot1+0\cdot1=0. \] Donc aucun chemin de longueur 2 de \(3\) vers \(4\).
  • En général, \((A^3)_{2,2}\) n’est pas forcément \(\ge 1\) : cela dépend de l’existence d’au moins un circuit de longueur 3 revenant en \(2\).
    Ici, comme il y a une boucle \(2\to2\), on a par exemple \(2\to2\to2\to2\), donc \((A^3)_{2,2}\ge 1\).
⚠️ Piège : une boucle \(2\to2\) crée des chemins de toutes longueurs revenant en \(2\).
Fin des exercices
Si tu veux, je te donne maintenant le Quiz HARD (20 questions) (matrices d’adjacence, chemins, pièges Bac).
Chemins → Puissances → Interprétation →