Devoir surveillé — Théorie des graphes

Calculatrice interdite. Les cinq exercices sont indépendants. Commencez tôt l'exercice 5, le problème : il pèse plus que tout autre et ses premières questions sont parmi les plus abordables du sujet. Une matrice écrite sans le calcul demandé ne rapporte aucun point.

Un parc naturel relie cinq relais, numérotés $1$ à $5$. Deux réseaux de sentiers y coexistent, et aucun sentier n'est des deux types à la fois.

• Sentiers pédestres : $\{1,2\}$, $\{1,3\}$, $\{2,4\}$, $\{3,4\}$, $\{4,5\}$.
• Sentiers équestres : $\{1,4\}$, $\{2,3\}$, $\{2,5\}$, $\{3,5\}$.

Le plan du parc reprend ces deux listes sur un même dessin : trait plein pour un sentier pédestre, trait tireté pour un sentier équestre. Les deux réseaux partagent les cinq relais, et c'est ce qui rendra possibles les itinéraires mixtes de la question 3.

Chaque relais est un point de changement de mode : on peut y laisser sa monture ou en reprendre une.

On note $P$ la matrice d'adjacence du graphe des sentiers pédestres et $E$ celle du graphe des sentiers équestres, les relais étant rangés une fois pour toutes dans l'ordre $(1,2,3,4,5)$.

1. Écrire les matrices $P$ et $E$. Donner le degré de chaque relais dans chacun des deux réseaux, puis vérifier la formule d'Euler dite des poignées de main sur chacun d'eux. (0,5 point)

2. On appelle réseau complet du parc le graphe dont les sommets sont les cinq relais et dont les arêtes sont tous les sentiers, pédestres ou équestres. Justifier que sa matrice d'adjacence est $P+E$, et écrire cette matrice. On dira précisément où intervient l'hypothèse « aucun sentier n'est à la fois pédestre et équestre », et ce que deviendrait la matrice $P+E$ si cette hypothèse tombait. (0,75 point)

3. On appelle itinéraire mixte de longueur $2$ allant du relais $i$ au relais $j$ la donnée d'un relais intermédiaire $k$ tel que $\{i,k\}$ soit un sentier pédestre et $\{k,j\}$ un sentier équestre. Démontrer que le nombre d'itinéraires mixtes de $i$ à $j$ est égal au coefficient $(PE{)}_{i,j}$, puis calculer la matrice $PE$. (1 point)

4. Interpréter le coefficient $(EP{)}_{i,j}$. On rappelle que la transposée d'un produit vérifie ${}^t(MN)={}^{t}N{}^{t}M$ : en déduire l'égalité $EP={}^t(PE)$, puis écrire la matrice $EP$ sans effectuer aucun produit. Les matrices $PE$ et $EP$ sont-elles égales ? (0,5 point)

5. On rappelle le résultat du chapitre de calcul matriciel : pour deux matrices carrées de même ordre,

$$(P+E{)}^2=P^2+PE+EP+E^2\mathrm{.}$$

Sans calculer le produit $(P+E)(P+E)$, déterminer le coefficient en position $(1,5)$ de $(P+E{)}^2$. Vérifier le résultat en énumérant toutes les chaînes de longueur $2$ du réseau complet allant du relais $1$ au relais $5$, puis dire en une phrase ce que compte chacun des quatre termes de la somme. (0,5 point)

Un jeu de piste comporte six énigmes numérotées de $1$ à $6$. Chaque énigme, une fois résolue, désigne une seule énigme suivante, d'après le tableau ci-dessous.

On modélise la situation par le graphe orienté $G$ dont les sommets sont les six énigmes, avec un arc $i\to j$ lorsque l'énigme $i$ désigne l'énigme $j$. On note $A$ sa matrice d'adjacence, les énigmes étant rangées dans l'ordre $(1,2,3,4,5,6)$.

Un joueur qui part de l'énigme $i$ et en résout $d$ successivement parcourt un chemin de longueur $d$ d'origine $i$ ; on dit qu'il se trouve après $d$ étapes au sommet où ce chemin aboutit.

1. Dresser la liste des six arcs de $G$. Écrire la matrice $A$. Donner le degré sortant $d^{+}$ et le degré entrant $d^{-}$ de chaque énigme, et vérifier que les deux sommes valent le nombre d'arcs. (0,25 point)

2. Justifier que, pour tout sommet $i$ et tout entier $d⩾1$, il existe exactement un chemin de longueur $d$ d'origine $i$. En déduire que chaque ligne de $A^d$ contient exactement un coefficient égal à $1$, tous ses autres coefficients étant nuls, puis que la somme de tous les coefficients de $A^d$ vaut $6$, et ce pour tout $d⩾1$. (0,75 point)

3. On donne la matrice

$$A^2=\left(\begin{array}{cccccc}0& 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0\\ 1& 0& 0& 0& 0& 0\end{array}\right)$$

En vérifier un coefficient non nul en détaillant le produit, puis calculer $A^3$. Présenter enfin dans un tableau, pour chaque énigme de départ, l'énigme atteinte après $2$ étapes puis après $3$ étapes. (0,5 point)

4. Montrer que la colonne numéro $6$ de $A$ est nulle, puis que la colonne numéro $6$ de $A^d$ est nulle pour tout entier $d⩾1$. Traduire ce fait en une phrase sur le jeu de piste, et en déduire que $G$ n'est pas fortement connexe sans calculer aucune somme de puissances de $A$. (0,5 point)

5. Que compte la somme des coefficients de la colonne $j$ de $A^d$ ? Calculer ces six sommes pour $d=3$, et commenter le cas de l'énigme $1$ en le comparant à son degré entrant. (0,5 point)

6. Vérifier que les énigmes $1$, $2$, $3$ et $4$ forment un circuit de longueur $4$. Déterminer, pour chaque énigme de départ, le plus petit nombre d'étapes au bout duquel le joueur se trouve sur ce circuit, puis en déduire le plus petit entier $d_0$ tel que, quel que soit le point de départ, le joueur soit sur le circuit après $d_0$ étapes. (0,25 point)

7. En déduire que $A^{d+4}=A^d$ pour tout entier $d⩾2$, puis montrer que $A^5\mathrm{\ne }A$, c'est-à-dire que l'égalité est fausse pour $d=1$. On suivra pour cela le joueur parti de l'énigme $6$. On justifiera le résultat par un raisonnement sur le graphe, et non par un calcul de puissances. (0,75 point)

On considère le graphe non orienté $G$ d'ordre $5$, de sommets $s_1$, $s_2$, $s_3$, $s_4$ et $s_5$, dont les sept arêtes sont

On note $A=(a_{i,j})$ sa matrice d'adjacence, les sommets étant rangés dans l'ordre $(s_1,s_2,s_3,s_4,s_5)$, et $d_i$ le degré du sommet $s_i$.

On rappelle que $(A^d{)}_{i,j}$ compte les chaînes de longueur $d$ de $s_i$ à $s_j$, une telle chaîne ayant le droit de repasser plusieurs fois par un même sommet, et qu'une chaîne est dite élémentaire lorsqu'elle ne passe pas deux fois par le même sommet. Le but de l'exercice est de mesurer exactement l'écart entre les deux comptages, pour les chaînes de longueur $3$.

On donne la matrice $A^2$, qu'il est donc inutile de recalculer :

$$A^2=\left(\begin{array}{ccccc}3& 1& 2& 1& 2\\ 1& 3& 1& 3& 0\\ 2& 1& 3& 1& 2\\ 1& 3& 1& 3& 0\\ 2& 0& 2& 0& 2\end{array}\right)$$

1. Écrire la matrice $A$ et donner les cinq degrés. Vérifier deux coefficients de la matrice $A^2$ fournie, dont un coefficient diagonal, en disant à chaque fois ce que le résultat signifie. Calculer ensuite $A^3$, en détaillant au moins deux coefficients. (1,25 points)

2. Lire le coefficient $(A^3{)}_{1,2}$. Énumérer les chaînes de longueur $3$ allant de $s_1$ à $s_2$, et dire pour chacune si elle est élémentaire. Combien y en a-t-il d'élémentaires ? (0,5 point)

3. Soient $i$ et $j$ deux indices distincts. Une chaîne de longueur $3$ de $s_i$ à $s_j$ s'écrit $s_i-u-v-s_j$. Démontrer que le nombre de ces chaînes qui ne sont pas élémentaires vaut

$$a_{i,j}(d_i+d_j-1)\mathrm{.}$$

On montrera d'abord que les seules répétitions possibles sont $u=s_j$ et $v=s_i$, puis on dénombrera séparément les deux cas avant de retirer les chaînes comptées deux fois. (0,75 point)

4. En déduire que le nombre ${\mathcal{E}}_{i,j}$ de chaînes élémentaires de longueur $3$ de $s_i$ à $s_j$ vaut

$${\mathcal{E}}_{i,j}=(A^3{)}_{i,j}-a_{i,j}(d_i+d_j-1)\mathrm{.}$$

Vérifier la formule sur le couple $(1,2)$ à l'aide de la question 2, puis l'appliquer au couple $(2,4)$ en contrôlant le résultat par énumération directe. (0,75 point)

5. Exhiber deux sommets adjacents reliés par au moins une chaîne de longueur $3$ mais par aucune chaîne élémentaire de longueur $3$. Démontrer ensuite que cette situation est impossible dès que les deux sommets ne sont pas adjacents. (0,5 point)

On considère le graphe non orienté $G$ dont les sommets sont les douze entiers $1,2,\dots ,12$, deux entiers distincts étant reliés par une arête lorsque leur somme est le carré d'un entier.

Le graphe n'est donc donné ni par un dessin ni par une matrice : c'est la règle ci-dessus qui le définit, et la première tâche consiste à le construire.

1. Justifier que la somme de deux sommets distincts est comprise entre $3$ et $23$, et en déduire que les seuls carrés à examiner sont $4$, $9$ et $16$. Dresser ensuite la liste des arêtes de $G$ et donner son nombre $m$ d'arêtes. (0,5 point)

2. Donner le degré de chaque sommet. Démontrer ensuite, sans utiliser la liste des arêtes, que le degré d'un sommet ne peut jamais dépasser $3$. (0,5 point)

3. Déterminer les composantes connexes de $G$. Le graphe est-il connexe ? On justifiera soigneusement qu'aucune arête ne joint deux composantes différentes. (0,5 point)

4. Vérifier que chaque composante connexe de $G$ est une file de sommets, c'est-à-dire de la forme $t_1-t_2-\cdots -t_k$ dont les seules arêtes relient deux termes consécutifs. En déduire, sans calculer aucune puissance de la matrice d'adjacence, la plus grande distance séparant deux sommets dans chacune des trois composantes. (0,5 point)

5. On souhaite rendre le graphe connexe en lui ajoutant de nouvelles arêtes. Démontrer qu'il en faut au moins deux. (0,5 point)

6. On ajoute les deux arêtes $\{3,4\}$ et $\{3,7\}$, et l'on note $G^{\mathrm{\prime }}$ le graphe obtenu. Vérifier que $G^{\mathrm{\prime }}$ est connexe, puis déterminer son diamètre en précisant toutes les paires de sommets qui le réalisent. (1 point)

7. Démontrer que, quelles que soient les deux arêtes ajoutées rendant le graphe connexe, le diamètre du graphe obtenu est toujours supérieur ou égal à $4$. On pourra s'intéresser aux sommets $8$ et $10$. (0,5 point)

Certains graphes ont leurs sommets répartis en deux catégories, les arêtes ne joignant jamais deux sommets d'une même catégorie. Ce problème étudie cette situation, en tire une conséquence inattendue sur les chaînes, et en déduit un critère permettant d'affirmer qu'un graphe n'est pas de ce type.

Partie A. Un exemple : les emprunts d'une bibliothèque.

Une bibliothèque suit les emprunts de trois lecteurs $L_1$, $L_2$, $L_3$ sur trois ouvrages $O_1$, $O_2$, $O_3$. Le lecteur $L_1$ a emprunté $O_1$ et $O_2$ ; le lecteur $L_2$ a emprunté $O_1$ et $O_3$ ; le lecteur $L_3$ a emprunté $O_1$, $O_2$ et $O_3$.

On note $G$ le graphe dont les six sommets sont les trois lecteurs et les trois ouvrages, une arête reliant un lecteur à un ouvrage lorsque celui-là a emprunté celui-ci. Les sommets sont rangés dans l'ordre $(L_1,L_2,L_3,O_1,O_2,O_3)$ et $A$ désigne la matrice d'adjacence de $G$ dans cet ordre.

Vocabulaire employé dans tout le problème. On appelle blocs de $A$ les quatre tableaux carrés d'ordre $3$ obtenus en coupant $A$ entre ses troisième et quatrième lignes, puis entre ses troisième et quatrième colonnes. Les deux blocs diagonaux sont celui des couples formés de deux lecteurs et celui des couples formés de deux ouvrages ; les deux autres sont les blocs hors diagonale. Aucune question ne demandera de multiplier des matrices par blocs : ce découpage sert uniquement à désigner des zones de la matrice.

1. Écrire la matrice $A$. Vérifier qu'en la découpant en quatre blocs carrés d'ordre $3$, les deux blocs de la diagonale sont nuls, et dire ce que traduit cette nullité. (0,5 point)

2. Donner le degré de chacun des six sommets. Vérifier que la somme des degrés des trois lecteurs et la somme des degrés des trois ouvrages valent toutes deux le nombre $m$ d'arêtes, puis démontrer ce fait par un double comptage. (0,5 point)

3. On donne la matrice

$$A^2=\left(\begin{array}{cccccc}2& 1& 2& 0& 0& 0\\ 1& 2& 2& 0& 0& 0\\ 2& 2& 3& 0& 0& 0\\ 0& 0& 0& 3& 2& 2\\ 0& 0& 0& 2& 2& 1\\ 0& 0& 0& 2& 1& 2\end{array}\right)$$

En vérifier deux coefficients, dont un coefficient diagonal, en détaillant les produits. Constater ensuite que les deux blocs hors diagonale sont nuls et interpréter ce fait en termes de chaînes de longueur $2$. (0,25 point)

4. Sans calculer $A^3$, conjecturer lesquels de ses quatre blocs sont nuls. On donnera l'argument en une ou deux phrases : la partie B le transformera en démonstration. (0,25 point)

Partie B. Le cas général.

Dans toute cette partie, $G$ est un graphe biparti d'ordre $n$, de bipartition $(S_1,S_2)$. Les sommets sont numérotés de sorte que ceux de $S_1$ viennent en premier, et $A$ désigne la matrice d'adjacence dans cette numérotation.

5. Justifier que deux sommets d'une même partie ne sont jamais adjacents. En déduire la position des coefficients nuls de $A$. (0,25 point)

6. Lemme d'alternance. Démontrer par récurrence sur $d$ que, pour tout entier naturel $d$, toute chaîne de longueur $d$ dont l'origine appartient à $S_1$ a son extrémité dans $S_1$ si $d$ est pair, et dans $S_2$ si $d$ est impair. Justifier ensuite, sans nouveau calcul, que l'énoncé obtenu en échangeant les rôles de $S_1$ et $S_2$ est également vrai. (0,75 point)

7. Soient $u$ et $v$ deux sommets. Déduire du lemme que $(A^d{)}_{u,v}=0$ dans chacun des deux cas suivants : $u$ et $v$ sont dans une même partie et $d$ est impair ; $u$ et $v$ sont dans deux parties différentes et $d$ est pair. Confirmer alors la conjecture de la question 4. (0,5 point)

8. En déduire que $G$ ne possède aucune chaîne fermée de longueur impaire, c'est-à-dire aucune chaîne de longueur impaire dont les deux extrémités coïncident. En particulier, $G$ ne contient ni triangle, ni plus généralement de cycle de longueur impaire. (0,25 point)

Partie C. Reconnaître un graphe biparti.

9. Soit $n⩾1$. Démontrer que le graphe complet $K_n$ est biparti si et seulement si $n=2$. On traitera séparément les cas $n=1$, $n=2$ et $n⩾3$. (0,5 point)

10. Soit $n⩾3$. On note $C_n$ le graphe cycle d'ordre $n$, de sommets $t_1,t_2,\dots ,t_n$ et d'arêtes $\{t_1,t_2\},\{t_2,t_3\},\dots ,\{t_{n-1},t_n\}$ et $\{t_n,t_1\}$. Démontrer que $C_n$ est biparti si et seulement si $n$ est pair. (0,5 point)

11. On considère le graphe $H$ d'ordre $6$, de sommets numérotés de $1$ à $6$, dont les six arêtes sont

Le graphe $H$ est-il biparti ? Justifier la réponse en exhibant, selon le cas, une bipartition ou une chaîne fermée de longueur impaire. Expliquer enfin pourquoi le seul test « $H$ contient-il un triangle ? » n'aurait pas permis de conclure. (0,5 point)

Partie D. Combien d'arêtes ?

12. Soit $G$ un graphe biparti de bipartition $(S_1,S_2)$, avec $p=\mathrm{card}(S_1)$, $q=\mathrm{card}(S_2)$ et $m$ arêtes. Démontrer que $m⩽pq$. Décrire les graphes bipartis pour lesquels l'égalité a lieu. (0,5 point)

13. Une bibliothèque suit $5$ lecteurs et $7$ ouvrages. Majorer le nombre de couples distincts formés d'un lecteur et d'un ouvrage qu'il a emprunté. Comparer cette majoration au nombre maximal d'arêtes d'un graphe simple quelconque d'ordre $12$, puis conclure en une phrase sur ce que la bipartition coûte en arêtes. (0,25 point)