20 Exercices de Graphes en Maths Expertes Corrigés (PDF)

Le graphe a 5 sommets : son ordre est 5.

On compte les arêtes partant de chaque sommet :

• A relié à B, C → \(d(A)=2\)
• B relié à A, C → \(d(B)=2\)
• C relié à A, B, D, E → \(d(C)=4\)
• D relié à C, E → \(d(D)=2\)
• E relié à C, D → \(d(E)=2\)

Ce qu’il faut rédiger : « Ordre 5 ; degrés \(d(A)=d(B)=d(D)=d(E)=2\) et \(d(C)=4\). »

Somme des degrés : \(2+2+4+2+2 = 12\).

D’après le lemme des poignées de main, \(\sum d(s_i) = 2m\), donc :

\(m = \displaystyle\frac{12}{2} = 6\).

Conclusion : le graphe possède 6 arêtes, ce qui confirme la lecture de la figure.

Chaque match est une arête d’un graphe complet d’ordre \(n=7\). Le nombre d’arêtes vaut :

\(\displaystyle\frac{n(n-1)}{2} = \displaystyle\frac{7\times 6}{2} = 21\).

Conclusion : 21 matchs sont joués. (On peut aussi voir ce nombre comme le nombre de paires de joueurs, c’est-à-dire une combinaison de 2 parmi 7.)

On met un 1 en case \((i,j)\) lorsque les sommets \(i\) et \(j\) sont reliés, 0 sinon. Le graphe étant non orienté, la matrice est symétrique :

\(A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\)

Vérification : la somme des coefficients de la ligne de C vaut \(1+1+0+1 = 3 = d(C)\) ✓. La diagonale est nulle (pas de boucle).

La matrice est symétrique : elle est compatible avec le graphe non orienté annoncé. La symétrie seule ne suffirait pas à exclure un graphe orienté à arcs réciproques.

Le degré d’un sommet est la somme des coefficients de sa ligne :

• \(d(1) = 0+1+0+1 = 2\)
• \(d(2) = 1+0+1+1 = 3\)
• \(d(3) = 0+1+0+0 = 1\)
• \(d(4) = 1+1+0+0 = 2\)

Somme des degrés : \(2+3+1+2 = 8\), donc \(m = \displaystyle\frac{8}{2} = 4\) arêtes.

Conclusion : graphe non orienté, 4 arêtes.

Méthode efficace sur un petit graphe : montrer que tout sommet est relié à un sommet pivot, par exemple A.

• A–B : chaîne directe.
• A–C : chaîne directe.
• A–C–D : A rejoint D.
• A–C–D–E : A rejoint E.

Tout sommet est donc relié à A par une chaîne. Par transitivité, deux sommets quelconques sont reliés en passant par A.

Ce qu’il faut rédiger : « Chaque sommet est relié à A par une chaîne, donc toute paire de sommets est reliée : le graphe est connexe. » Voir la méthode complète sur la page graphe connexe.

L’élève a tort. Aucun des quatre sommets n’est isolé : A et B ont pour degré 1, C et D aussi. Pourtant, il n’existe aucune chaîne reliant A à C : les arêtes A–B et C–D forment deux morceaux séparés.

Le graphe possède donc deux composantes connexes : {A, B} et {C, D}. Il n’est pas connexe.

À retenir : « aucun sommet isolé » n’implique jamais « connexe ». La seule définition correcte est : toute paire de sommets est reliée par une chaîne.

D’abord, le graphe est connexe (vérification immédiate). On applique le théorème d’Euler : un graphe connexe admet une chaîne eulérienne si et seulement s’il a exactement 0 ou 2 sommets de degré impair.

Degrés (ex. 1) : \(d(A)=2\), \(d(B)=2\), \(d(C)=4\), \(d(D)=2\), \(d(E)=2\). Tous sont pairs : il y a 0 sommet de degré impair.

Conclusion : il existe une chaîne eulérienne. Comme il y a 0 sommet de degré impair, c’est même un cycle eulérien : il peut commencer (et finir) en n’importe quel sommet.

On élève \(A\) au carré par produit matriciel :

\(A^2 = \begin{pmatrix} 2 & 1 & 1 & 1 \\ 1 & 2 & 1 & 1 \\ 1 & 1 & 3 & 0 \\ 1 & 1 & 0 & 1 \end{pmatrix}\)

D’après le théorème des chemins, le coefficient (ligne, colonne) de \(A^2\) donne le nombre de chaînes de longueur 2.

• Case (A, D) : coefficient \(1\) → une seule chaîne de longueur 2 : A–C–D.
• Case (C, C) : coefficient \(3\) → trois chaînes : C–A–C, C–B–C, C–D–C.

Conclusion : 1 chaîne A→D de longueur 2, et 3 chaînes fermées de longueur 2 issues de C.

La première ligne de \(A^3\) correspond au sommet A. Le coefficient en colonne D vaut \(1\) : il existe donc une seule chaîne de longueur 3 reliant A à D.

Vérification « à la main ». Une chaîne A → \(v_1\) → \(v_2\) → D doit finir par un voisin de D, donc \(v_2 = C\). Il faut \(v_1\) voisin de A et de C : parmi {B, C}, seul B convient. On obtient :

\(A \to B \to C \to D\)

Conclusion : une unique chaîne de longueur 3, ce qui confirme le coefficient. La démonstration générale du théorème des chemins se fait par récurrence.

Depuis A : reste en A avec 0,8, donc part vers B avec \(1-0{,}8 = 0{,}2\).

Depuis B : passe en A avec 0,1, donc reste en B avec \(1-0{,}1 = 0{,}9\).

Chaque ligne a bien pour somme 1 (convention des lignes) :

\(P = \begin{pmatrix} 0{,}8 & 0{,}2 \\ 0{,}1 & 0{,}9 \end{pmatrix}\)

Conclusion : cette matrice est la matrice de transition de la chaîne.

On utilise \(\pi(n+1) = \pi(n)\,P\) (vecteur ligne à gauche).

\(\pi(1)=(0{,}5\ ;\ 0{,}5)P\).
Première coordonnée : \(0{,}5\times0{,}8+0{,}5\times0{,}1=0{,}45\).
Seconde coordonnée : \(0{,}5\times0{,}2+0{,}5\times0{,}9=0{,}55\).

\(\pi(1) = (0{,}45\ ;\ 0{,}55)\)

\(\pi(2)=\pi(1)P\).
Première coordonnée : \(0{,}45\times0{,}8+0{,}55\times0{,}1=0{,}415\).
Seconde coordonnée : \(0{,}45\times0{,}2+0{,}55\times0{,}9=0{,}585\).

\(\pi(2) = (0{,}415\ ;\ 0{,}585)\)

Conclusion : la proportion d’abonnés diminue : 50 %, puis 45 %, puis 41,5 %.

On cherche \(\pi\) tel que \(\pi = \pi P\) avec \(a + b = 1\). La première coordonnée donne :

\(a = 0{,}8\,a + 0{,}1\,b\)

\(0{,}2\,a = 0{,}1\,b\) donc \(b = 2a\).

Avec \(a + b = 1\) : \(a + 2a = 1\), d’où \(a = \displaystyle\frac{1}{3}\) et \(b = \displaystyle\frac{2}{3}\).

Conclusion : \(\pi = \left(\displaystyle\frac{1}{3}\ ;\ \displaystyle\frac{2}{3}\right)\). À long terme, environ 33 % d’abonnés, indépendamment du point de départ.

\(\pi(1) = (1\ ;\ 0\ ;\ 0)\,P = (0{,}5\ ;\ 0{,}5\ ;\ 0)\) (on lit simplement la 1re ligne de \(P\)).

\(\pi(2) = (0{,}5\ ;\ 0{,}5\ ;\ 0)\,P\) :

• État 1 : \(0{,}5\times 0{,}5 + 0{,}5\times 0{,}25 = 0{,}375\)
• État 2 : \(0{,}5\times 0{,}5 + 0{,}5\times 0{,}5 = 0{,}5\)
• État 3 : \(0{,}5\times 0 + 0{,}5\times 0{,}25 = 0{,}125\)

\(\pi(2) = (0{,}375\ ;\ 0{,}5\ ;\ 0{,}125)\)

Vérification : la somme des coordonnées vaut 1 ✓.

Chaque sommet a deux voisins, atteints avec probabilité \(\displaystyle\frac{1}{2}\) :

\(P = \begin{pmatrix} 0 & \displaystyle\frac{1}{2} & \displaystyle\frac{1}{2} \\ \displaystyle\frac{1}{2} & 0 & \displaystyle\frac{1}{2} \\ \displaystyle\frac{1}{2} & \displaystyle\frac{1}{2} & 0 \end{pmatrix}\)

Par symétrie, on cherche \(\pi = (a\ ;\ a\ ;\ a)\). La contrainte \(3a = 1\) donne \(a = \displaystyle\frac{1}{3}\).

On vérifie \(\pi = \pi P\) : la 1re coordonnée de \(\pi P\) vaut \(\displaystyle\frac{1}{3}\times 0 + \displaystyle\frac{1}{3}\times\displaystyle\frac{1}{2} + \displaystyle\frac{1}{3}\times\displaystyle\frac{1}{2} = \displaystyle\frac{1}{3}\) ✓.

Conclusion : \(\pi = \left(\displaystyle\frac{1}{3}\ ;\ \displaystyle\frac{1}{3}\ ;\ \displaystyle\frac{1}{3}\right)\) — le jeton visite les trois sommets de façon équilibrée.

Transitions. Depuis l’état 0 (0 à gauche) : la molécule choisie est forcément à droite, elle passe à gauche → état 1. Donc \(P_{0\to 1}=1\).

Depuis l’état 1 (1 à gauche, 1 à droite) : une chance sur deux de choisir celle de gauche (→ état 0) ou celle de droite (→ état 2). Donc \(P_{1\to 0}=P_{1\to 2}=\displaystyle\frac{1}{2}\).

Depuis l’état 2 : la molécule choisie est forcément à gauche → état 1. Donc \(P_{2\to 1}=1\).

\(P = \begin{pmatrix} 0 & 1 & 0 \\ \displaystyle\frac{1}{2} & 0 & \displaystyle\frac{1}{2} \\ 0 & 1 & 0 \end{pmatrix}\)

Invariance. On calcule \(\pi P\) avec \(\pi = \left(\displaystyle\frac{1}{4}\ ;\ \displaystyle\frac{1}{2}\ ;\ \displaystyle\frac{1}{4}\right)\) :

• Coord. 0 : \(\displaystyle\frac{1}{4}\times 0 + \displaystyle\frac{1}{2}\times\displaystyle\frac{1}{2} + \displaystyle\frac{1}{4}\times 0 = \displaystyle\frac{1}{4}\)
• Coord. 1 : \(\displaystyle\frac{1}{4}\times 1 + \displaystyle\frac{1}{2}\times 0 + \displaystyle\frac{1}{4}\times 1 = \displaystyle\frac{1}{2}\)
• Coord. 2 : \(\displaystyle\frac{1}{4}\times 0 + \displaystyle\frac{1}{2}\times\displaystyle\frac{1}{2} + \displaystyle\frac{1}{4}\times 0 = \displaystyle\frac{1}{4}\)

On retrouve \(\pi\) : la distribution est bien invariante. On reconnaît la loi binomiale \(\mathcal{B}\left(2\ ;\ \displaystyle\frac{1}{2}\right)\).

1. A–C–D relie A à D, A–B et A–C relient A aux autres : tout sommet est joignable depuis A, donc le graphe est connexe.

2. C’est exactement le graphe de l’exercice 4 :

\(A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\)

3. D’après l’exercice 10, le coefficient (A, D) de \(A^3\) vaut 1 : un seul trajet de longueur 3, A→B→C→D.

4. Longueur 1 : A et D ne sont pas voisins (coefficient (A,D) de \(A\) nul). Longueur 2 : le coefficient (A, D) de \(A^2\) vaut aussi 1 (trajet A→C→D), donc il existe en réalité un trajet de longueur 2. L’énoncé insiste simplement sur l’absence de route directe (longueur 1).

Ce qu’il faut rédiger : toujours citer le théorème des chemins avant de lire un coefficient de \(A^n\).

Degrés sortants : P1 a 2 liens, P2 en a 1, P3 en a 2. On répartit uniformément :

\(P = \begin{pmatrix} 0 & \displaystyle\frac{1}{2} & \displaystyle\frac{1}{2} \\ 1 & 0 & 0 \\ \displaystyle\frac{1}{2} & \displaystyle\frac{1}{2} & 0 \end{pmatrix}\)

On cherche \(\pi = (a\ ;\ b\ ;\ c)\) avec \(\pi = \pi P\) et \(a+b+c=1\) :

\(a = 0\cdot a + 1\cdot b + \displaystyle\frac{1}{2} c = b + \displaystyle\frac{1}{2}c\) \(b = \displaystyle\frac{1}{2} a + 0 + \displaystyle\frac{1}{2} c\) \(c = \displaystyle\frac{1}{2} a + 0 + 0 = \displaystyle\frac{1}{2} a\)

De la 3e : \(c = \displaystyle\frac{a}{2}\). La 2e donne \(b = \displaystyle\frac{a}{2} + \displaystyle\frac{a}{4} = \displaystyle\frac{3a}{4}\). La contrainte \(a + \displaystyle\frac{3a}{4} + \displaystyle\frac{a}{2} = 1\) donne \(\displaystyle\frac{9a}{4}=1\), soit \(a = \displaystyle\frac{4}{9}\).

D’où \(\pi = \left(\displaystyle\frac{4}{9}\ ;\ \displaystyle\frac{3}{9}\ ;\ \displaystyle\frac{2}{9}\right)\).

Classement : P1 (4/9) > P2 (1/3) > P3 (2/9). La page la plus « importante » est P1, car elle est citée par les deux autres.

Le coefficient \(B_{ij}\) compte le nombre de chaînes de longueur \(0\) à \(n-1\) entre \(i\) et \(j\). S’il est strictement positif pour toute case, chaque paire de sommets est reliée : le graphe est connexe.

Le calcul complet donne \(B=\begin{pmatrix}5&5&6&2\\5&5&6&2\\6&6&6&4\\2&2&4&2\end{pmatrix}\). Chaque coefficient est strictement positif.

Conclusion : tous les coefficients de \(B\) sont strictement positifs, donc le graphe est connexe — ce qui confirme l’exercice 17. Ce critère est très utile quand le graphe est trop gros pour être parcouru à la main.

Avec la convention des lignes, \(\pi = \pi P\). En transposant cette égalité de vecteurs :

\({}^t(\pi P) = {}^t\pi \quad\Longrightarrow\quad {}^t P\,{}^t\pi = {}^t\pi\)

Donc \({}^t\pi\) est un vecteur propre de \({}^t P\) pour la valeur propre 1. Vérifions :

\({}^t P = \begin{pmatrix} 0{,}8 & 0{,}1 \\ 0{,}2 & 0{,}9 \end{pmatrix}, \qquad {}^t\pi = \begin{pmatrix} \displaystyle\frac{1}{3} \\ \displaystyle\frac{2}{3} \end{pmatrix}\) \({}^t P\,{}^t\pi = \begin{pmatrix} 0{,}8\times\displaystyle\frac{1}{3} + 0{,}1\times\displaystyle\frac{2}{3} \\ 0{,}2\times\displaystyle\frac{1}{3} + 0{,}9\times\displaystyle\frac{2}{3} \end{pmatrix} = \begin{pmatrix} \displaystyle\frac{1}{3} \\ \displaystyle\frac{2}{3} \end{pmatrix} = {}^t\pi\)

Conclusion : l’état stable est bien le vecteur propre de \({}^t P\) pour la valeur propre 1. C’est l’outil central des matrices stochastiques en prépa.