Exercices — Théorie des graphes

On considère le graphe non orienté $G=(S,\mathcal{A})$ représenté ci-dessous. Ses sommets sont A, B, C, D, E et F.

Toutes les réponses demandées se lisent sur cette figure. On rappelle deux définitions de vocabulaire : un sommet est dit isolé lorsque son degré est nul, et un graphe est dit régulier lorsque tous ses sommets ont le même degré.

1. Donner l'ordre $n$ du graphe $G$.

2. Dresser la liste, en extension, de l'ensemble $\mathcal{A}$ des arêtes de $G$, puis donner le nombre $m$ d'arêtes.

3. Citer les sommets adjacents à B, puis les sommets adjacents à F.

4. Déterminer le degré de chacun des six sommets.

5. Vérifier sur cet exemple la formule d'Euler dite des poignées de main.

6. Quel est le degré maximal des sommets de $G$, et ce degré est-il atteint par un seul sommet ? Le graphe possède-t-il un sommet isolé ? Justifier les deux réponses.

7. Le graphe $G$ est-il complet ? Est-il régulier ? Justifier chaque réponse.

Une zone d'activités est desservie par un réseau de navettes qui relie six arrêts, notés A, B, C, D, E et F. Le plan du réseau est représenté ci-dessous : chaque trait figure une liaison directe entre deux arrêts, c'est-à-dire un trajet de navette qui ne s'arrête pas entre les deux. Toutes les liaisons sont assurées dans les deux sens.

On modélise ce réseau par le graphe non orienté $G=(S,\mathcal{A})$ dont les sommets sont les six arrêts et dont les arêtes sont les liaisons directes. On note $A=(a_{i,j})$ sa matrice d'adjacence, les sommets étant rangés dans l'ordre alphabétique $(A,B,C,D,E,F)$.

1. Dresser la liste des liaisons directes lues sur le plan, puis écrire la matrice d'adjacence $A$.

2. Justifier, sans calcul supplémentaire, que la matrice $A$ est symétrique. Que traduit par ailleurs le fait que sa diagonale soit nulle ?

3. Calculer la somme des coefficients de chaque ligne de $A$ et vérifier que l'on retrouve le degré de l'arrêt correspondant. Interpréter ce degré pour un usager du réseau.

4. Calculer la somme de tous les coefficients de $A$ et interpréter le résultat obtenu.

5. Un usager souhaite savoir s'il peut aller directement de A à C, puis s'il peut aller directement de B à E. Répondre en lisant uniquement la matrice $A$, en précisant à chaque fois le coefficient utilisé.

On considère la matrice carrée d'ordre $5$ suivante :

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

On admet qu'il s'agit de la matrice d'adjacence d'un graphe $G$ dont les cinq sommets, rangés dans cet ordre, sont A, B, C, D et E. Toutes les questions se traitent à partir de cette seule matrice, le graphe n'étant pas dessiné.

1. Vérifier que $A$ possède les trois propriétés caractéristiques de la matrice d'adjacence d'un graphe simple non orienté : ses coefficients valent $0$ ou $1$, sa diagonale est nulle, et elle est symétrique. Préciser ce que traduit chacune de ces trois propriétés sur le graphe.

2. Dresser la liste, en extension, des arêtes de $G$.

3. Déterminer le degré de chacun des cinq sommets.

4. Déterminer le nombre $m$ d'arêtes de $G$ de deux façons : par un comptage direct sur la liste de la question 2, puis à l'aide de la formule d'Euler dite des poignées de main.

5. Dessiner le graphe $G$.

6. Le graphe $G$ est-il complet ? On justifiera la réponse en comparant $m$ au nombre d'arêtes d'un graphe complet d'ordre $5$, puis en citant deux sommets non adjacents.

On considère le graphe orienté $G=(S,\mathcal{A})$ représenté ci-dessous. Ses quatre sommets sont notés $1$, $2$, $3$ et $4$, et chaque flèche représente un arc, c'est-à-dire une liaison à sens unique : l'arc $(u,v)$ va de $u$ vers $v$ et ne permet pas d'aller de $v$ vers $u$.

On rappelle les définitions du cours pour un graphe orienté : le degré sortant $d^{+}(s)$ d'un sommet $s$ est le nombre d'arcs qui partent de $s$, et son degré entrant $d^{-}(s)$ est le nombre d'arcs qui arrivent en $s$.

1. Dresser la liste des arcs de $G$ et donner leur nombre.

2. Écrire la matrice d'adjacence $A$ de $G$, les sommets étant rangés dans l'ordre $(1,2,3,4)$.

3. La matrice $A$ est-elle symétrique ? Expliquer, en exhibant un couple de coefficients, pourquoi c'était prévisible.

4. Déterminer les degrés sortants et les degrés entrants des quatre sommets, en précisant à chaque fois quelle somme de la matrice $A$ on utilise. Présenter les résultats dans un tableau.

5. Calculer la somme de tous les degrés sortants, puis celle de tous les degrés entrants. Comparer ces deux nombres au nombre d'arcs et justifier le résultat observé.

6. Existe-t-il un sommet dans lequel n'arrive aucun arc ? Existe-t-il un sommet dont on ne peut pas sortir ? Répondre en lisant la matrice $A$, puis dire ce que l'on peut en conclure pour un déplacement le long des flèches.

On rappelle la formule d'Euler dite des poignées de main : pour tout graphe non orienté $G=(S,\mathcal{A})$ d'ordre $n$ possédant $m$ arêtes,

$$\sum _{s\in S}d(s)=2m\mathrm{.}$$

Dans tout l'exercice, les graphes considérés sont simples et non orientés, et les quatre situations de la question 1 sont indépendantes les unes des autres. Chaque réponse devra être justifiée par la formule ci-dessus, et non par un dessin.

1. Répondre à chacune des questions suivantes.

2. Lors d'une réunion de $7$ personnes, chaque participant serre la main d'exactement trois autres participants. Une telle situation est-elle possible ?

On rappelle qu'un graphe non orienté est dit complet lorsque deux sommets distincts quelconques y sont toujours adjacents. Le graphe complet d'ordre $n$ se note $K_n$. La figure ci-dessous représente $K_5$, dont les cinq sommets sont A, B, C, D et E.

1. Justifier que chaque sommet de $K_5$ est de degré $4$, puis déterminer le nombre $m$ d'arêtes de $K_5$ de deux façons : par une énumération organisée, puis par la formule d'Euler dite des poignées de main.

2. Écrire la matrice d'adjacence de $K_5$, les sommets étant rangés dans l'ordre alphabétique $(A,B,C,D,E)$.

On passe maintenant au cas général : dans les questions 3 à 5, $n$ désigne un entier supérieur ou égal à $2$ et on travaille sur le graphe complet $K_n$.

3. Déterminer le degré de chaque sommet de $K_n$.

4. En déduire, à l'aide de la formule des poignées de main, que $K_n$ possède ${\displaystyle \frac{n(n-1)}{2}}$ arêtes.

5. Décrire la matrice d'adjacence de $K_n$ et l'exprimer à l'aide de la matrice $J_n$, dont tous les coefficients valent $1$, et de la matrice identité $I_n$.

6. Application numérique. Combien $K_{12}$ possède-t-il d'arêtes ? Un tournoi rassemble $12$ équipes et se joue « toutes rondes », c'est-à-dire que chaque équipe rencontre exactement une fois chacune des autres. Combien de matchs comporte ce tournoi ?

On considère le graphe non orienté $G=(S,\mathcal{A})$ d'ordre $6$, dont les sommets sont $s_1$, $s_2$, $s_3$, $s_4$, $s_5$ et $s_6$, et dont les sept arêtes sont les suivantes :

On rappelle le vocabulaire du cours. Une chaîne de $u_0$ à $u_k$ est une suite de sommets $u_0-u_1-\cdots -u_k$ dans laquelle deux sommets consécutifs sont toujours reliés par une arête ; sa longueur est le nombre $k$ d'arêtes parcourues. Une chaîne est dite élémentaire lorsqu'elle ne passe pas deux fois par le même sommet. Un cycle est une chaîne de longueur non nulle dont les deux extrémités sont confondues et qui n'emprunte pas deux fois la même arête.

1. Donner une chaîne reliant $s_1$ à $s_4$ et préciser sa longueur.

2. Donner une autre chaîne reliant $s_1$ à $s_4$, de longueur différente de celle de la question 1.

3. Pour chacune des deux suites de sommets suivantes, dire si c'est une chaîne de $G$, et dans l'affirmative donner sa longueur et préciser si elle est élémentaire.

4. Exhiber un cycle de $G$ et donner sa longueur. En exhiber ensuite un second, de longueur différente.

5. Déterminer toutes les chaînes élémentaires reliant $s_1$ à $s_4$ et donner leur nombre. On veillera à justifier que l'énumération est complète.

6. Déterminer la longueur minimale d'une chaîne reliant $s_6$ à $s_3$, c'est-à-dire la distance $\delta (s_6,s_3)$. On exhibera une chaîne réalisant ce minimum et on justifiera qu'il n'en existe pas de plus courte.

On considère un graphe non orienté $G$ dont les quatre sommets sont A, B, C et D. Rangés dans cet ordre alphabétique, sa matrice d'adjacence est

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

On rappelle le résultat du cours sur les puissances de la matrice d'adjacence : pour tout entier $d⩾1$, le coefficient en position $(i,j)$ de $A^d$ est égal au nombre de chaînes de longueur $d$ reliant le sommet numéro $i$ au sommet numéro $j$.

Pour alléger l'écriture, on note $(A^2{)}_{\mathrm{A},\mathrm{D}}$ le coefficient de $A^2$ situé sur la ligne du sommet A et sur la colonne du sommet D, c'est-à-dire $(A^2{)}_{1,4}$, et on adopte la même convention pour les autres sommets.

1. Calculer la matrice $A^2$. On détaillera le calcul d'au moins trois coefficients à l'aide de la formule du produit matriciel.

2. Que vaut $(A^2{)}_{\mathrm{A},\mathrm{D}}$ ? Interpréter ce nombre en termes de chaînes, puis énumérer effectivement les chaînes concernées pour vérifier le résultat.

3. Comparer les coefficients diagonaux de $A^2$ aux degrés des sommets de $G$. Expliquer le résultat observé.

4. Calculer la somme de tous les coefficients de $A^2$ et interpréter le nombre obtenu.

5. La matrice $A^2$ possède des coefficients nuls. En choisir un et expliquer concrètement ce qu'il signifie pour le graphe. Le fait qu'un coefficient de $A^2$ soit nul signifie-t-il que les deux sommets correspondants ne sont pas reliés ?

On considère le graphe orienté $G=(S,\mathcal{A})$ représenté ci-dessous, dont les sommets sont A, B, C et D.

Les sommets sont rangés une fois pour toutes dans l'ordre A, B, C, D, et on note $A$ la matrice d'adjacence de $G$ dans cet ordre. La matrice $A$, écrite en italique, ne doit pas être confondue avec le sommet A : le contexte lèvera toujours l'ambiguïté.

On rappelle le résultat du cours : pour tout entier $d⩾1$, le coefficient $(A^d{)}_{i,j}$ est le nombre de chemins de longueur $d$ allant du sommet numéro $i$ au sommet numéro $j$, étant entendu qu'un tel chemin a le droit de repasser plusieurs fois par un même sommet.

1. Écrire la matrice d'adjacence $A$, puis contrôler le résultat en comparant les sommes des lignes et des colonnes au nombre d'arcs.

2. Calculer $A^2$, puis $A^3$, en détaillant les calculs.

3. a. Lire sur $A^2$ le nombre de chemins de longueur $2$ allant de A à B, puis retrouver ce nombre en énumérant tous les chemins de longueur $2$ partant de A.

3. b. Reprendre la même question pour les chemins de longueur $2$ allant de C à B.

4. Lire sur $A^3$ le nombre de chemins de longueur $3$ allant de A à B, puis énumérer ces chemins.

5. Le coefficient $(A^3{)}_{2,2}$ n'est pas nul. Que compte-t-il exactement ? Écrire les chemins correspondants.

6. Exhiber un couple de sommets $(u,v)$ pour lequel il n'existe aucun chemin de longueur $3$ de $u$ vers $v$. Justifier ce fait directement sur le graphe, sans se servir de $A^3$.

On considère le graphe non orienté $G=(S,\mathcal{A})$ d'ordre $4$, dont les sommets sont A, B, C et D, et dont les arêtes sont

$$\mathcal{A}=\{\{A,B\},\{B,C\},\{C,D\},\{D,A\},\{A,C\}\}\mathrm{.}$$

C'est un carré $A-B-C-D-A$ auquel on a ajouté la diagonale $\{A,C\}$. Les sommets sont rangés dans l'ordre A, B, C, D et on note $A$ la matrice d'adjacence de $G$ dans cet ordre ; la matrice $A$, en italique, ne doit pas être confondue avec le sommet A.

On rappelle que $(A^d{)}_{i,j}$ est le nombre de chaînes de longueur $d$ reliant le sommet numéro $i$ au sommet numéro $j$, une chaîne pouvant repasser plusieurs fois par un même sommet ou emprunter deux fois la même arête.

1. Écrire la matrice $A$ et vérifier qu'elle est symétrique. Donner le degré de chaque sommet et vérifier la formule d'Euler dite des poignées de main.

2. Calculer $A^2$, puis $A^3$, en détaillant les calculs.

3. a. Vérifier le coefficient $(A^2{)}_{1,3}$ en énumérant les chaînes correspondantes.

3. b. Vérifier de même le coefficient $(A^3{)}_{2,4}$.

4. Déterminer le nombre total de chaînes de longueur $2$ du graphe, puis le nombre total de chaînes de longueur $3$, en additionnant tous les coefficients de la matrice concernée.

5. Expliquer pourquoi ces totaux comptent deux fois chaque chaîne, une fois dans chaque sens. Y a-t-il des exceptions ?

6. Que vaut la somme des coefficients diagonaux de $A^2$ ? Démontrer le résultat général correspondant et l'interpréter.

Un petit site est composé de quatre pages $P_1$, $P_2$, $P_3$ et $P_4$. On modélise le site par un graphe orienté dont les sommets sont les quatre pages, avec un arc $P_i\to P_j$ lorsque la page $P_i$ contient un lien hypertexte vers la page $P_j$. Emprunter un arc, c'est cliquer sur un lien.

Les pages sont rangées dans l'ordre $P_1$, $P_2$, $P_3$, $P_4$ et on note $A$ la matrice d'adjacence du graphe dans cet ordre.

1. Écrire la matrice $A$.

2. Déterminer, dans un tableau, le degré entrant $d^{-}$ et le degré sortant $d^{+}$ de chaque page. Vérifier que la somme des degrés entrants et la somme des degrés sortants valent toutes deux le nombre d'arcs.

3. Quelle page reçoit le plus de liens ? Quelle page en émet le plus ?

4. Calculer $A^2$, puis $A^3$. En déduire le nombre de façons d'aller de $P_1$ à $P_4$ en exactement $3$ clics, puis vérifier ce nombre en énumérant les chemins correspondants.

5. Un internaute arrive sur la page $P_1$.

a. Quelles pages peut-il atteindre en un seul clic ? En existe-t-il une qu'il ne peut pas atteindre ainsi ?

b. Quelles pages peut-il atteindre en exactement deux clics ? Commenter.

6. Sur un graphe du web, que mesure le degré entrant d'une page ? Pourquoi un moteur de recherche s'y intéresse-t-il ? Dire enfin un mot de ce que devient cette matrice pour le web réel.

Soit $n$ un entier supérieur ou égal à $3$. On définit deux graphes non orientés ayant les mêmes sommets $s_1,s_2,\dots ,s_n$, rangés dans cet ordre.

• Le graphe cycle $C_n$ a pour arêtes $\{s_1,s_2\},\{s_2,s_3\},\dots ,\{s_{n-1},s_n\}$ et $\{s_n,s_1\}$ : les sommets sont disposés en anneau, chacun relié au suivant, le dernier étant relié au premier.
• Le graphe chaîne $L_n$ a les mêmes arêtes, sauf $\{s_n,s_1\}$ : c'est le cycle « ouvert », une file de sommets reliés de proche en proche.

On note $A$ la matrice d'adjacence de $C_5$ et $B$ celle de $L_5$, les sommets étant toujours rangés dans l'ordre $s_1,s_2,s_3,s_4,s_5$.

On rappelle qu'un graphe est dit régulier de degré $r$ lorsque tous ses sommets sont de degré $r$.

1. Écrire les matrices $A$ et $B$.

2. Soit $n⩾3$. Décrire les coefficients de la matrice d'adjacence de $C_n$, puis ceux de la matrice d'adjacence de $L_n$ : on donnera dans chaque cas la condition portant sur les indices $i$ et $j$ qui caractérise $a_{i,j}=1$.

3. Déterminer le degré de chaque sommet de $C_n$, puis de $L_n$. Vérifier la formule d'Euler dite des poignées de main dans les deux cas pour $n=5$.

4. En déduire le nombre d'arêtes de $C_n$ et celui de $L_n$.

5. Calculer $A^2$, puis interpréter les trois valeurs prises par ses coefficients.

6. Pour quelles valeurs de $n$ le graphe $C_n$ est-il régulier de degré $2$ ? On examinera avec soin ce que deviendrait la définition pour les petites valeurs de $n$. Le graphe $L_n$ est-il régulier ?

Cinq joueurs $J_1$, $J_2$, $J_3$, $J_4$ et $J_5$ disputent un tournoi. Chaque match désigne un vainqueur, il n'y a pas de match nul. On modélise les résultats par le graphe orienté ci-dessous : il y a un arc $J_i\to J_j$ lorsque $J_i$ a battu $J_j$.

Les joueurs sont rangés dans l'ordre $J_1$, $J_2$, $J_3$, $J_4$, $J_5$ et on note $A$ la matrice d'adjacence du graphe dans cet ordre.

1. Vérifier sur la figure que chaque paire de joueurs s'est rencontrée exactement une fois. En déduire le nombre total de matchs disputés, et retrouver ce nombre par la formule ${\displaystyle \frac{n(n-1)}{2}}$ pour $n=5$.

2. Écrire la matrice $A$.

3. Dresser dans un tableau le degré sortant $d^{+}$ et le degré entrant $d^{-}$ de chaque joueur, c'est-à-dire son nombre de victoires et son nombre de défaites. Vérifier que la somme des victoires est égale au nombre de matchs.

4. a. Calculer $A^2$.

4. b. Interpréter le coefficient $(A^2{)}_{i,j}$ en termes de résultats sportifs. Lire $(A^2{)}_{1,4}$ et détailler les deux enchaînements qu'il compte.

4. c. Justifier, sans calcul, que tous les coefficients diagonaux de $A^2$ sont nuls.

5. L'organisateur veut établir un classement.

a. Le nombre de victoires suffit-il à départager les joueurs ?

b. Il propose alors de compter, pour chaque joueur, ses victoires et ses victoires indirectes, c'est-à-dire la somme des coefficients de sa ligne dans $A+A^2$. Calculer ces sommes et conclure.

c. Expliquer le phénomène observé, puis proposer une façon de départager les joueurs.

Six personnes sont inscrites sur un réseau social : Alice, Bilal, Chloé, David, Emma et Farid. L'amitié y est réciproque : si $x$ est ami avec $y$, alors $y$ est ami avec $x$. Les couples d'amis sont les suivants :

$$\{\text{Alice},\text{Bilal}\},\{\text{Alice},\text{Chlo}\acute{\text{e}}\},\{\text{Alice},\text{David}\},\{\text{Bilal},\text{Chlo}\acute{\text{e}}\},$$ $$\{\text{Bilal},\text{Emma}\},\{\text{Chlo}\acute{\text{e}},\text{David}\},\{\text{David},\text{Emma}\},\{\text{Emma},\text{Farid}\}\mathrm{.}$$

On modélise la situation par le graphe non orienté $G$ dont les sommets sont les six personnes et dont les arêtes sont les couples d'amis. Les sommets sont rangés dans l'ordre Alice, Bilal, Chloé, David, Emma, Farid, et on note $A$ la matrice d'adjacence de $G$ dans cet ordre.

1. Écrire la matrice $A$, puis donner le degré de chaque personne. Vérifier la formule d'Euler dite des poignées de main.

2. Calculer $A^2$ en détaillant les calculs.

3. Soient $i$ et $j$ deux indices distincts. Démontrer que $(A^2{)}_{i,j}$ est le nombre d'amis communs aux personnes $i$ et $j$.

4. a. Combien Alice et Chloé ont-elles d'amis communs ? Les nommer.

4. b. Même question pour Bilal et David.

4. c. Le coefficient $(A^2{)}_{5,6}$ est nul alors qu'Emma et Farid sont amis. Expliquer.

5. Que vaut $(A^2{)}_{i,i}$ ? Justifier, et donner l'interprétation.

6. Le réseau veut suggérer une nouvelle relation à ses membres : il propose de mettre en contact deux personnes qui ne sont pas amies et qui ont le plus grand nombre d'amis communs. Quelle paire le réseau doit-il retenir ? Que peut-on suggérer à Farid ?

On appelle triangle d'un graphe non orienté tout ensemble de trois sommets deux à deux adjacents. On rappelle que la trace d'une matrice carrée $M$ d'ordre $n$, notée $\mathrm{tr}(M)$, est la somme de ses coefficients diagonaux :

$$\mathrm{tr}(M)=\sum _{i=1}^n{M}_{i,i}\mathrm{.}$$

On considère le graphe non orienté $G$ d'ordre $5$, de sommets A, B, C, D, E, dont les arêtes sont

$$\mathcal{A}=\{\{A,B\},\{A,C\},\{A,D\},\{B,C\},\{C,D\},\{C,E\},\{D,E\}\}\mathrm{.}$$

Les sommets sont rangés dans l'ordre A, B, C, D, E et on note $A$ la matrice d'adjacence de $G$ dans cet ordre ; la matrice $A$, en italique, ne doit pas être confondue avec le sommet A.

1. Écrire la matrice $A$, donner les degrés et vérifier la formule d'Euler dite des poignées de main.

2. Calculer $A^2$ en détaillant les calculs.

3. Calculer les cinq coefficients diagonaux de $A^3$, en détaillant, puis en déduire $\mathrm{tr}(A^3)$.

4. Énumérer à la main tous les triangles de $G$. Combien y en a-t-il ?

5. a. Comparer $\mathrm{tr}(A^3)$ au nombre de triangles trouvé.

5. b. Démontrer le résultat général : si $T$ désigne le nombre de triangles d'un graphe non orienté de matrice d'adjacence $A$, alors $\mathrm{tr}(A^3)=6T$. On expliquera précisément d'où viennent le facteur $2$, puis le facteur $3$.

6. On considère un second graphe $H$, d'ordre $5$, de sommets $t_1,t_2,t_3,t_4,t_5$, dont la matrice d'adjacence dans cet ordre est

$$B=\left(\begin{array}{ccccc}0& 1& 1& 0& 0\\ 1& 0& 1& 0& 0\\ 1& 1& 0& 1& 1\\ 0& 0& 1& 0& 1\\ 0& 0& 1& 1& 0\end{array}\right)$$

Déterminer le nombre de triangles de $H$ par la formule de la question 5. b., puis les identifier.

On considère le graphe complet $K_3$, c'est-à-dire le triangle : ses sommets sont A, B et C, et ses arêtes sont $\{A,B\}$, $\{A,C\}$ et $\{B,C\}$, de sorte que deux sommets distincts quelconques sont toujours adjacents.

Les sommets sont rangés dans l'ordre A, B, C et on note $A$ la matrice d'adjacence du graphe dans cet ordre ; la matrice $A$, en italique, ne doit pas être confondue avec le sommet A.

Le but de l'exercice est de calculer les puissances de $A$ sans effectuer de produit matriciel à chaque étape, en exploitant une relation vérifiée par $A^2$, comme on l'a fait au chapitre sur le calcul matriciel avec les polynômes annulateurs.

1. Écrire la matrice $A$.

2. Calculer $A^2$, puis vérifier la relation

$$A^2=A+2I_3\mathrm{.}$$

3. Démontrer par récurrence que, pour tout entier $d⩾1$, il existe deux réels ${\alpha }_d$ et ${\beta }_d$ tels que

$$A^d={\alpha }_{d}A+{\beta }_d{I}_3,$$

et que ces réels vérifient ${\alpha }_1=1$, ${\beta }_1=0$ ainsi que les relations

$${\alpha }_{d+1}={\alpha }_d+{\beta }_d\text{et}{\beta }_{d+1}=2{\alpha }_d\mathrm{.}$$

4. Dresser le tableau des valeurs de ${\alpha }_d$ et ${\beta }_d$ pour $d$ allant de $1$ à $4$, puis en déduire les matrices $A^3$ et $A^4$.

5. Vérifier le résultat obtenu pour $A^3$ en calculant directement le produit $A^2\times A$.

6. Interpréter les coefficients de $A^4$ en termes de chaînes de longueur $4$ dans le triangle. Contrôler le résultat en comptant autrement le nombre total de chaînes de longueur $4$ issues d'un sommet.

On considère le graphe non orienté $G=(S,\mathcal{A})$ représenté ci-dessous, dont les sept sommets sont numérotés de $1$ à $7$.

On rappelle le vocabulaire du cours. Deux sommets $u$ et $v$ sont reliés lorsqu'il existe une chaîne d'extrémités $u$ et $v$ ; le graphe est connexe lorsque deux sommets quelconques sont toujours reliés ; une composante connexe est un ensemble de sommets deux à deux reliés, et maximal pour cette propriété, c'est-à-dire qu'aucune arête ne joint un sommet de cet ensemble à un sommet extérieur.

1. Dresser la liste des arêtes de $G$. Préciser l'ordre $n$ du graphe et son nombre d'arêtes $m$.

2. Le graphe $G$ est-il connexe ? Justifier soigneusement la réponse.

3. Déterminer les composantes connexes de $G$. Pour chacune, on exhibera des chaînes montrant que ses sommets sont deux à deux reliés ; on justifiera aussi qu'aucune chaîne ne mène d'une composante à l'autre.

4. Écrire la matrice d'adjacence $A$ de $G$, les sommets étant rangés dans l'ordre $1$, $2$, $3$, $4$, $5$, $6$, $7$. Que remarque-t-on sur la forme de cette matrice ? Quel lien avec la question précédente ?

5. Déterminer le degré de chaque sommet, puis vérifier la formule d'Euler dite des poignées de main.

6. Quel est le nombre minimal d'arêtes à ajouter à $G$ pour obtenir un graphe connexe ? On donnera une construction explicite et on justifiera qu'on ne peut pas faire moins.

7. On revient au graphe $G$ de départ et on supprime l'arête $\{4,7\}$. Combien de composantes connexes le graphe obtenu possède-t-il ? Les décrire.

Partie A. On considère un graphe non orienté $G$ dont les quatre sommets sont numérotés de $1$ à $4$. Dans cet ordre, sa matrice d'adjacence est

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

1. Énoncer le critère matriciel de connexité vu en cours, pour un graphe d'ordre $n$ de matrice d'adjacence $A$. Rappeler également ce que représente le coefficient $(A^d{)}_{i,j}$.

2. Dresser la liste des arêtes de $G$.

3. Calculer $A^2$, puis $A^3$. On détaillera au moins un coefficient de chaque produit.

4. Former la matrice $M=I_4+A+A^2+A^3$, puis conclure quant à la connexité de $G$.

5. Vérifier directement la conclusion de la question précédente en exhibant, pour chaque paire de sommets, une chaîne les reliant.

Partie B. On considère maintenant un second graphe non orienté $H$, également à quatre sommets numérotés de $1$ à $4$, de matrice d'adjacence

$$B=\left(\begin{array}{cccc}0& 0& 1& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\\ 0& 1& 0& 0\end{array}\right)$$

6. Dresser la liste des arêtes de $H$, puis calculer $B^2$ et $B^3$.

7. Former la matrice $N=I_4+B+B^2+B^3$. Le critère est-il vérifié ? Identifier un coefficient nul de $N$ et interpréter cette nullité en termes de chaînes.

8. Déterminer les composantes connexes de $H$.

Partie C.

9. Pour un graphe d'ordre $n$, le critère s'arrête à la puissance $A^{n-1}$. Expliquer pourquoi il est inutile d'aller plus loin, et pourquoi il serait en revanche insuffisant de s'arrêter plus tôt. On s'appuiera sur la partie A pour ce second point.

Un petit réseau informatique est représenté par le graphe non orienté ci-dessous. Ses sept sommets sont les machines A, B, C, D, E, F et G, et une arête signifie que les deux machines sont reliées par un câble direct.

Pour éviter toute confusion avec le sommet G, on note $R=(S,\mathcal{A})$ ce graphe.

On rappelle les définitions du cours. La distance $\delta (u,v)$ entre deux sommets $u$ et $v$ d'un graphe connexe est la longueur de la plus courte chaîne d'extrémités $u$ et $v$. L'excentricité d'un sommet $s$ est

$$e(s)=\underset{v\in S}{\max }\delta (s,v),$$

et le diamètre du graphe est $\mathrm{diam}(R)={\max }_{s\in S}e(s)$, c'est-à-dire la plus grande distance entre deux sommets.

1. Dresser la liste des arêtes de $R$ et donner le degré de chaque sommet. Vérifier la formule d'Euler dite des poignées de main.

2. Calculer $\delta (G,v)$ pour chacun des six autres sommets $v$. On donnera pour chaque sommet une chaîne témoin, et on justifiera qu'aucune chaîne plus courte n'existe.

3. En déduire l'excentricité $e(G)$.

4. Calculer de même l'excentricité $e(A)$.

5. Déterminer le diamètre de $R$. On justifiera que la valeur trouvée est bien atteinte, et qu'aucune paire de sommets n'est plus éloignée.

6. Quel sommet est le plus « central », au sens de la plus petite excentricité ? Commenter.

7. L'administrateur du réseau ajoute un câble entre les machines G et D. Le diamètre du réseau est-il modifié ? Justifier.

Huit membres d'un réseau d'entraide, notés A, B, C, D, E, F, G et H, sont représentés par le graphe non orienté ci-dessous. Une arête entre deux membres signifie qu'ils sont en contact régulier.

Pour éviter toute confusion avec le sommet G, on note $R=(S,\mathcal{A})$ ce graphe, d'ordre $n=8$.

On introduit la mesure suivante, utilisée en analyse des réseaux sociaux. Le degré de centralité d'un membre $s$ est

$$C_D(s)=\frac{d(s)}{n-1}\mathrm{.}$$

C'est la proportion des autres membres du réseau avec lesquels $s$ est directement en contact. Cette mesure vaut $1$ pour un membre en contact avec tout le monde, et $0$ pour un membre isolé. On précise que les mesures de centralité ne sont pas au programme : elles sont introduites ici sur un exemple, comme le fait le texte officiel.

1. Dresser la liste des arêtes de $R$, puis donner le degré de chaque membre dans un tableau. Vérifier la formule d'Euler dite des poignées de main.

2. Justifier que, pour tout membre $s$, on a $0⩽C_D(s)⩽1$. Dans quel cas la valeur $1$ serait-elle atteinte ?

3. Calculer le degré de centralité de chacun des huit membres, sous forme d'une fraction puis d'un pourcentage arrondi au dixième.

4. Classer les membres par degré de centralité décroissant. Qui est l'influenceur du réseau, au sens de cette mesure ?

5. Les membres B et D ont le même degré, donc le même degré de centralité, mais ils n'occupent visiblement pas la même position dans le réseau. Décrire la différence entre ces deux positions, puis dire laquelle vous semble la plus stratégique. On rédigera la réponse.

On reprend le réseau d'entraide à huit membres A, B, C, D, E, F, G, H déjà rencontré, représenté ci-dessous. Une arête signifie que les deux membres sont en contact régulier. On rappelle sa description : A, B et C forment un triangle, E, F et G forment un autre triangle, le membre H n'est en contact qu'avec G, et le membre D est en contact avec A et avec E.

Pour éviter toute confusion avec le sommet G, on note $R=(S,\mathcal{A})$ ce graphe, d'ordre $n=8$. Ses arêtes sont donc

On introduit la seconde mesure classique d'analyse des réseaux sociaux, qui n'est pas non plus au programme. Le degré d'intermédiarité d'un membre $s$ est

$$C_B(s)=\sum _{\{u,v\}}\frac{{\sigma }_{u,v}(s)}{{\sigma }_{u,v}},$$

où la somme porte sur toutes les paires de membres distincts $u$ et $v$, tous deux différents de $s$, où ${\sigma }_{u,v}$ désigne le nombre de plus courtes chaînes de $u$ à $v$, et où ${\sigma }_{u,v}(s)$ désigne le nombre de ces plus courtes chaînes qui passent par $s$, celui-ci étant alors un sommet intermédiaire de la chaîne, ni l'une ni l'autre de ses extrémités. Autrement dit, $C_B(s)$ mesure à quel point $s$ est un point de passage obligé du réseau.

On rappelle enfin le degré de centralité $C_D(s)={\displaystyle \frac{d(s)}{n-1}}$, étudié sur ce même réseau dans l'exercice précédent.

1. Combien y a-t-il de paires $\{u,v\}$ à examiner dans le calcul de $C_B(s)$, pour un membre $s$ fixé de ce réseau ?

2. Justifier que la suppression du membre D coupe le réseau en deux, et préciser les deux groupes obtenus.

3. a. Soient $u$ un membre du groupe $\{A,B,C\}$ et $v$ un membre du groupe $\{E,F,G,H\}$. Justifier que toute chaîne de $u$ à $v$ emprunte successivement A, puis D, puis E, et en déduire que ces deux membres sont reliés par une unique plus courte chaîne.

3. b. Calculer $C_B(D)$. On organisera le décompte dans un tableau donnant, pour chaque paire concernée, la valeur de ${\sigma }_{u,v}$ et celle de ${\sigma }_{u,v}(D)$, et on justifiera que les autres paires ne contribuent pas.

4. Calculer $C_B(B)$, puis comparer les couples $(C_D(B),C_B(B))$ et $(C_D(D),C_B(D))$.

5. Que conclure sur la différence entre « être très connecté » et « être un point de passage » ?

6. L'entreprise qui anime ce réseau veut éviter qu'un départ ne le coupe en deux. Quel membre doit-elle absolument doubler ? Proposer également une liaison à créer qui règle le problème d'un seul coup.

Une entreprise possède quatre sites, numérotés $1$, $2$, $3$ et $4$, reliés par des navettes à sens unique. On modélise la situation par un graphe orienté dont les sommets sont les quatre sites, et dont les arcs sont les navettes : il y a un arc $i\to j$ lorsqu'une navette conduit du site $i$ au site $j$. Dans l'ordre $1$, $2$, $3$, $4$, la matrice d'adjacence de ce graphe est

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

On rappelle que le coefficient $(A^d{)}_{i,j}$ est le nombre de chemins de longueur $d$ allant du site $i$ au site $j$ en respectant le sens des arcs. On admet que le critère matriciel du cours s'adapte au cas orienté sous la forme suivante : dans un graphe orienté d'ordre $n$, on peut aller de n'importe quel sommet à n'importe quel autre en suivant le sens des arcs si et seulement si tous les coefficients de

$$I_n+A+A^2+\cdots +A^{n-1}$$

sont strictement positifs. On dit alors que le graphe orienté est fortement connexe.

1. Dresser la liste des arcs du graphe. Donner le degré sortant $d^{+}(s)$ et le degré entrant $d^{-}(s)$ de chaque site, et vérifier la cohérence de ces deux comptages.

2. Calculer $A^2$, puis $A^3$. On détaillera au moins un coefficient de chaque produit et on l'interprétera en termes de chemins.

3. Former la matrice $M=I_4+A+A^2+A^3$. Un employé peut-il rejoindre n'importe quel site depuis n'importe quel autre en empruntant les navettes ?

4. Déterminer les couples de sites $(i,j)$ pour lesquels le trajet le plus court comporte le plus grand nombre de navettes, et écrire ce trajet.

5. L'entreprise envisage de faire circuler toutes ses navettes dans les deux sens. Que devient la matrice d'adjacence ? Le critère de connexité est-il plus facile ou plus difficile à satisfaire ? On justifiera la réponse, d'abord en général, puis sur cet exemple.

Une entreprise de logistique exploite six entrepôts, désignés par les lettres A, B, C, D, E et F. Chaque jour, des camions assurent des liaisons directes entre certains d'entre eux, toujours dans les deux sens. Le plan de transport est le suivant.

• L'entrepôt A est l'entrepôt central : il est relié directement à B, à C et à D.
• Les entrepôts B et C sont également reliés directement entre eux.
• L'entrepôt D est relié directement à E.
• L'entrepôt E est relié directement à F.
• Il n'existe aucune autre liaison directe.

Un colis peut être acheminé d'un entrepôt à un autre en enchaînant plusieurs liaisons : à chaque étape, il change de camion. On dit alors qu'il y a transbordement.

1. Modéliser cette situation par un graphe $G=(S,\mathcal{A})$ : préciser ce que sont les sommets et les arêtes, dresser la liste des arêtes, et donner l'ordre $n$ du graphe ainsi que son nombre d'arêtes $m$. Justifier que le graphe est non orienté.

2. Écrire la matrice d'adjacence $A$ de $G$, les entrepôts étant rangés dans l'ordre A, B, C, D, E, F. Donner le degré de chaque entrepôt et vérifier la formule d'Euler dite des poignées de main.

3. Justifier que le réseau est connexe, c'est-à-dire que tout colis peut être acheminé de n'importe quel entrepôt vers n'importe quel autre.

4. Calculer la distance $\delta (A,v)$ de l'entrepôt central à chacun des autres entrepôts.

5. Déterminer le diamètre du réseau. Interpréter cette valeur en nombre de camions à enchaîner, et préciser entre quels entrepôts le trajet est le plus pénible.

6. Une liaison peut être fermée pour travaux. Identifier une liaison dont la fermeture couperait le réseau en deux, et le démontrer. Existe-t-il d'autres liaisons de ce type ?

7. L'entreprise a les moyens de créer une liaison directe supplémentaire, et souhaite faire baisser le diamètre du réseau. Proposer une liaison et démontrer la valeur du nouveau diamètre. Peut-on espérer descendre à $2$ avec une seule liaison ?

Soit $G=(S,\mathcal{A})$ un graphe simple d'ordre $n$, c'est-à-dire non orienté, sans boucle et sans arête multiple. On appelle graphe complémentaire de $G$, et l'on note $\bar{G}$, le graphe qui possède les mêmes sommets que $G$, et dans lequel deux sommets distincts sont reliés par une arête si et seulement s'ils ne le sont pas dans $G$.

On note $A$ la matrice d'adjacence de $G$ et $\bar{A}$ celle de $\bar{G}$, les sommets étant rangés dans le même ordre dans les deux cas. On note enfin $J_n$ la matrice carrée d'ordre $n$ dont tous les coefficients valent $1$.

Les degrés et les nombres d'arêtes sont indicés par le graphe considéré : $d_G(s)$ et $m_G$ pour $G$, $d_{\bar{G}}(s)$ et $m_{\bar{G}}$ pour $\bar{G}$.

Partie A. Un exemple. On considère le graphe $G$ d'ordre $5$ dont les sommets sont numérotés de $1$ à $5$ et dont les arêtes sont

1. Décrire la forme de $G$ en une phrase, puis dresser la liste des arêtes de $\bar{G}$. On justifiera le nombre d'arêtes trouvé.

2. Écrire les deux matrices d'adjacence $A$ et $\bar{A}$, les sommets étant rangés dans l'ordre $1$, $2$, $3$, $4$, $5$.

3. Calculer la matrice $J_5-I_5-A$ et vérifier qu'elle est égale à $\bar{A}$.

Partie B. Le cas général. Le graphe $G$ est maintenant un graphe simple quelconque, d'ordre $n$.

4. Démontrer que $\bar{A}=J_n-I_n-A$, en raisonnant coefficient par coefficient. On distinguera les coefficients diagonaux des autres.

5. En déduire que, pour tout sommet $s$, $d_{\bar{G}}(s)=n-1-d_G(s)$. Vérifier cette relation sur l'exemple de la partie A.

6. En déduire la relation $m_G+m_{\bar{G}}={\displaystyle \frac{n(n-1)}{2}}$, puis en donner une interprétation directe. Vérifier également cette relation sur l'exemple.

Partie C. Connexité.

7. Montrer que le graphe $G$ de la partie A n'est pas connexe, mais que son complémentaire $\bar{G}$, lui, l'est. On exhibera des chaînes explicites.

Un petit musée est organisé en cinq salles, notées A, B, C, D et E, reliées entre elles par des allées. Le conservateur souhaite proposer aux visiteurs un parcours qui emprunte chaque allée exactement une fois, sans jamais repasser deux fois dans la même allée. Un visiteur peut en revanche traverser plusieurs fois une même salle.

On modélise le musée par le graphe non orienté $G=(S,\mathcal{A})$ dont les sommets sont les cinq salles et dont les arêtes sont les allées.

Attention, deux salles peuvent être reliées par deux allées différentes : c'est le cas de A et B, ainsi que de D et E. Le graphe $G$ n'est donc pas un graphe simple, c'est un multigraphe. Pour pouvoir désigner chaque allée sans ambiguïté, on note $a_1$ et $a_2$ les deux allées reliant A à B, $e_1$ et $e_2$ les deux allées reliant D à E, et on désigne chacune des quatre autres allées par la paire de salles qu'elle relie. La liste complète des huit allées est donc :

Dans un multigraphe, le degré $d(s)$ d'un sommet est le nombre d'allées dont $s$ est une extrémité : une allée double compte donc pour $2$ dans le degré de chacune de ses deux extrémités.

On rappelle le théorème d'Euler, admis en cours, valable aussi bien pour un graphe simple que pour un multigraphe. Soit $G$ un graphe connexe.

• $G$ admet un cycle eulérien, c'est-à-dire une chaîne empruntant chaque arête exactement une fois et revenant à son point de départ, si et seulement si tous ses sommets sont de degré pair.
• $G$ admet une chaîne eulérienne non fermée si et seulement s'il possède exactement deux sommets de degré impair, et ces deux sommets en sont alors les extrémités.

1. Déterminer le degré de chacune des cinq salles et présenter les résultats dans un tableau.

2. Énoncer la formule d'Euler dite des poignées de main, expliquer pourquoi elle reste valable sur un multigraphe, puis la vérifier sur $G$.

3. Justifier que $G$ est connexe, préciser quelles sont les salles de degré impair, puis dire, en appliquant le théorème d'Euler, si le parcours souhaité par le conservateur existe. Dans l'affirmative, indiquer où il doit commencer et où il doit se terminer.

4. Exhiber un tel parcours et vérifier, allée par allée, qu'il emprunte bien chacune des huit allées exactement une fois.

5. Le conservateur aimerait que le parcours se termine dans la salle où il a commencé, afin que le visiteur retrouve la sortie. Est-ce possible avec le plan actuel ? Justifier.

6. Le musée peut percer une nouvelle allée entre deux salles. Déterminer toutes les possibilités qui rendraient réalisable un parcours fermé empruntant chaque allée exactement une fois, puis exhiber un tel parcours fermé.

On considère le graphe non orienté $G=(S,\mathcal{A})$ représenté ci-dessous. Ses huit sommets sont A, B, C, D, E, F, G et H.

Ce graphe est celui des sommets et des arêtes d'un cube : les quatre sommets A, B, C, D forment une face, les quatre sommets E, F, G, H la face opposée, et chaque sommet d'une face est relié à son vis-à-vis sur l'autre face. Ses douze arêtes sont donc :

On dit qu'un graphe est $k$-régulier lorsque tous ses sommets ont le même degré $k$.

1. Déterminer le degré de chacun des huit sommets et vérifier que $G$ est $3$-régulier.

2. Retrouver le nombre $m$ d'arêtes de $G$ à l'aide de la formule d'Euler dite des poignées de main, sans les compter une à une sur la figure. Énoncer, plus généralement, la formule donnant le nombre d'arêtes d'un graphe $k$-régulier d'ordre $n$.

3. Écrire la matrice d'adjacence $A$ de $G$, les sommets étant rangés dans l'ordre $(A,B,C,D,E,F,G,H)$. Indiquer deux contrôles simples permettant de vérifier cette matrice.

4. Déterminer la distance $\delta (A,s)$ de A à chacun des sept autres sommets. Pour chaque valeur, on exhibera une chaîne de longueur minimale et on justifiera qu'aucune chaîne plus courte n'existe.

5. En déduire l'excentricité $e(A)$ du sommet A.

6. Démontrer que $\mathrm{diam}(G)=3$. On pourra traiter séparément le cas de deux sommets situés sur une même face et celui de deux sommets situés sur des faces opposées.

7. Déterminer, par une énumération raisonnée et sans calculer de puissance de matrice, le nombre de chaînes de longueur $3$ reliant A à G. Que représente ce nombre dans la matrice $A^3$ ?

Dans tout l'exercice, les graphes considérés sont simples : non orientés, sans arête reliant un sommet à lui-même et sans arête double.

On dit qu'une liste d'entiers naturels $(d_1,d_2,\dots ,d_n)$ est réalisable lorsqu'il existe un graphe simple d'ordre $n$, de sommets $s_1,s_2,\dots ,s_n$, tel que

$$d(s_1)=d_1,d(s_2)=d_2,\dots ,d(s_n)=d_n\mathrm{.}$$

On considère les cinq listes suivantes.

Pour chacune des questions 1 à 5, dire si la liste proposée est réalisable. Si elle l'est, exhiber un graphe qui la réalise en donnant la liste de ses arêtes, et vérifier les degrés un à un. Si elle ne l'est pas, le démontrer. On pourra utiliser librement la formule d'Euler dite des poignées de main, ainsi que le fait qu'un sommet d'un graphe simple d'ordre $n$ a un degré compris entre $0$ et $n-1$ ; ces deux résultats sont redémontrés aux questions 6 et 7.

1. La liste $L_1$.

2. La liste $L_2$.

3. La liste $L_3$.

4. La liste $L_4$. Cette liste passe-t-elle les deux tests rappelés ci-dessus ? Que peut-on en conclure sur ces tests ?

5. La liste $L_5$.

6. Démontrer que, dans tout graphe simple, la somme des degrés de tous les sommets est un entier pair.

7. Soit $G$ un graphe simple d'ordre $n$, avec $n⩾2$.

a. Démontrer qu'un sommet de degré $n-1$ est adjacent à tous les autres sommets du graphe.

b. En déduire que $G$ ne peut pas posséder simultanément un sommet de degré $n-1$ et un autre sommet de degré $0$.

On considère un graphe non orienté $G$ dont les six sommets sont numérotés de $1$ à $6$. Dans cet ordre, sa matrice d'adjacence est

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

On rappelle le critère matriciel de connexité vu en cours : un graphe d'ordre $n$, de matrice d'adjacence $A$, est connexe si et seulement si tous les coefficients de la matrice

$$I_n+A+A^2+\cdots +A^{n-1}$$

sont strictement positifs.

On rappelle enfin que renuméroter les sommets d'un graphe consiste à les ranger dans un autre ordre : la nouvelle matrice d'adjacence s'obtient en permutant les lignes et les colonnes de $A$ de la même façon. Elle décrit exactement le même graphe.

1. Dresser la liste des arêtes de $G$, puis déterminer le degré de chaque sommet. Vérifier la formule d'Euler dite des poignées de main.

2. Déterminer les composantes connexes de $G$. Le graphe est-il connexe ?

3. Proposer une renumérotation des sommets pour laquelle la matrice d'adjacence est diagonale par blocs, c'est-à-dire de la forme

$$A^{\mathrm{\prime }}=\left(\begin{array}{cc}B& 0\\ 0& C\end{array}\right),$$

où $B$ et $C$ sont deux matrices carrées d'ordre $3$ et où les deux blocs notés $0$ sont des blocs nuls d'ordre $3$. Écrire la matrice $A^{\mathrm{\prime }}$.

4. a. Calculer $A^{\mathrm{\prime }2}$ en détaillant le calcul.

4. b. Démontrer que, pour tout entier $d⩾1$, la matrice $A^{\mathrm{\prime }d}$ est encore diagonale par blocs de même découpage, c'est-à-dire que ses coefficients situés hors des deux blocs diagonaux sont nuls. Donner ensuite une interprétation de ce résultat en termes de chaînes.

5. Montrer que le critère matriciel de connexité échoue pour $G$, en exhibant un coefficient nul de $I_6+A^{\mathrm{\prime }}+A^{\mathrm{\prime }2}+A^{\mathrm{\prime }3}+A^{\mathrm{\prime }4}+A^{\mathrm{\prime }5}$ sans calculer cette matrice.

6. Faire le bilan : quelles informations sur un graphe se lisent directement sur sa matrice d'adjacence, et lesquelles demandent un calcul ?

On appelle circuit d'un graphe orienté tout chemin de longueur au moins $1$ qui revient à son point de départ.

Partie A. Une entreprise doit mener à bien un projet composé de cinq tâches, notées $T_1$, $T_2$, $T_3$, $T_4$ et $T_5$ :

Le chef de projet recense six contraintes de précédence, chacune de la forme « la tâche $X$ doit être entièrement terminée avant que la tâche $Y$ ne commence » :

On modélise la situation par le graphe orienté $G$ dont les sommets sont les cinq tâches et dont les arcs sont les six contraintes : il y a un arc $X\to Y$ lorsque $X$ doit précéder $Y$.

1. Déterminer le degré entrant $d^{-}$ et le degré sortant $d^{+}$ de chaque tâche. Quelle est la seule tâche sans prérequis ? Quelle est la seule tâche qui n'en conditionne aucune autre ?

2. Déterminer un ordre d'exécution des cinq tâches compatible avec les six contraintes, c'est-à-dire un rangement des tâches tel que tout arc aille d'une tâche vers une tâche située plus loin dans l'ordre. Démontrer que cet ordre est le seul possible.

3. On range désormais les sommets dans l'ordre trouvé à la question 2 et on note $A$ la matrice d'adjacence de $G$ dans cet ordre. Écrire $A$ et constater qu'elle est triangulaire supérieure stricte, c'est-à-dire que tous ses coefficients situés sur la diagonale ou en dessous sont nuls.

4. Calculer $A^2$, $A^3$, $A^4$, puis $A^5$.

5. Interpréter le coefficient non nul de $A^4$ en termes de tâches, puis interpréter l'égalité $A^5=0$. Combien d'étapes successives le projet demande-t-il au minimum ?

Partie B. On considère maintenant un graphe orienté quelconque $G$, d'ordre $n$, dont les sommets sont numérotés de $1$ à $n$, et on note $A=(a_{i,j})$ sa matrice d'adjacence dans cette numérotation. On suppose que $A$ est triangulaire supérieure stricte :

$$a_{i,j}=0\text{pour tous indices }i\text{ et }j\text{ tels que }i⩾j\mathrm{.}$$

1. Justifier que s'il existe un arc allant du sommet $i$ vers le sommet $j$, alors $i<j$.

2. Soit $u_0\to u_1\to \cdots \to u_k$ un chemin de $G$, avec $k⩾1$. Démontrer que $u_0<u_1<\cdots <u_k$, puis en déduire que $G$ ne possède aucun circuit.

3. Démontrer que $A^n=0$. On pourra démontrer par récurrence sur $d⩾1$ la propriété suivante : « pour tous indices $i$ et $j$ tels que $j<i+d$, on a $(A^d{)}_{i,j}=0$ ».

4. On suppose $n⩾2$. Déterminer le coefficient en position $(n,1)$ de la matrice $I_n+A+A^2+\cdots +A^{n-1}$, et interpréter le résultat en termes de chemins.

5. On admet la réciproque de la Partie B : tout graphe orienté sans circuit peut être renuméroté de façon que sa matrice d'adjacence devienne triangulaire supérieure stricte. Qu'apporte ce résultat au chef de projet de la Partie A ?

Dans une salle se trouvent $n$ personnes, avec $n⩾2$. On admet que la relation « se connaître » est réciproque : si une personne en connaît une autre, alors cette autre la connaît aussi.

On veut démontrer le résultat suivant, qui peut sembler surprenant.

Quelle que soit l'assemblée, il existe toujours deux personnes qui connaissent exactement le même nombre de personnes présentes dans la salle.

On rappelle le principe des tiroirs : si l'on range $n$ objets dans $p$ tiroirs et si $p<n$, alors au moins un tiroir contient au moins deux objets.

1. Proposer un graphe $G$ modélisant la situation, en précisant ce que sont ses sommets et ses arêtes. Justifier que ce graphe est bien un graphe simple, c'est-à-dire non orienté, sans arête reliant un sommet à lui-même et sans arête double. Que représente le degré $d(s)$ d'un sommet $s$ ?

2. Démontrer que, pour tout sommet $s$ de $G$, on a $0⩽d(s)⩽n-1$. Que signifient concrètement les deux valeurs extrêmes $0$ et $n-1$ ?

3. Démontrer que $G$ ne peut pas posséder à la fois un sommet de degré $0$ et un sommet de degré $n-1$.

4. En déduire, à l'aide du principe des tiroirs, que deux sommets de $G$ ont le même degré. On pourra distinguer selon qu'un sommet de degré $n-1$ existe ou non.

5. Illustrer le résultat sur l'exemple suivant, où cinq personnes A, B, C, D, E sont présentes et où les couples de personnes qui se connaissent sont

On déterminera tous les degrés, on vérifiera la formule d'Euler dite des poignées de main, et on citera deux personnes qui connaissent le même nombre de gens. Expliquer ensuite pourquoi, avec cinq personnes, il est impossible que les cinq nombres de connaissances soient deux à deux distincts.

6. On suppose maintenant que l'on autorise les arêtes multiples, c'est-à-dire que le graphe modélise par exemple le nombre de projets menés en commun, deux personnes pouvant être reliées par plusieurs arêtes. La conclusion de la question 4 reste-t-elle vraie ? On justifiera la réponse par une démonstration ou par un contre-exemple, et on précisera quelle étape du raisonnement tombe en défaut.

Tous les graphes de cet exercice sont simples : non orientés, sans boucle et sans arête double. On note $n$ l'ordre d'un graphe et $m$ son nombre d'arêtes. L'objectif est de démontrer le résultat suivant, puis de l'exploiter.

Tout graphe connexe d'ordre $n$ possède au moins $n-1$ arêtes.

Partie A. Le résultat.

1. Vérifier l'inégalité $m⩾n-1$ sur les trois graphes suivants, en précisant à chaque fois $n$, $m$, et en justifiant brièvement la connexité.

a. La chaîne $G_a$ de sommets $s_1$, $s_2$, $s_3$, $s_4$ et d'arêtes $\{s_1,s_2\}$, $\{s_2,s_3\}$, $\{s_3,s_4\}$.

b. Le triangle $G_b$ de sommets $s_1$, $s_2$, $s_3$ et d'arêtes $\{s_1,s_2\}$, $\{s_2,s_3\}$, $\{s_1,s_3\}$.

c. L'étoile $G_c$ de sommets $c$, $f_1$, $f_2$, $f_3$, $f_4$ et d'arêtes $\{c,f_1\}$, $\{c,f_2\}$, $\{c,f_3\}$, $\{c,f_4\}$.

Dans lesquels de ces exemples l'inégalité est-elle une égalité ?

2. Soit $G$ un graphe connexe d'ordre au moins $2$. Démontrer qu'aucun sommet de $G$ n'est de degré $0$.

3. Soit $G$ un graphe connexe dont tous les sommets sont de degré supérieur ou égal à $2$. Démontrer, à l'aide de la formule d'Euler dite des poignées de main, que $m⩾n$.

4. Soit $G$ un graphe connexe d'ordre au moins $2$ possédant un sommet $s_0$ de degré $1$. On note $G^{\mathrm{\prime }}$ le graphe obtenu en supprimant de $G$ le sommet $s_0$ ainsi que l'unique arête dont il est une extrémité.

a. Donner l'ordre et le nombre d'arêtes de $G^{\mathrm{\prime }}$ en fonction de ceux de $G$.

b. Démontrer que $G^{\mathrm{\prime }}$ est connexe. On pourra partir de deux sommets $u$ et $v$ de $G^{\mathrm{\prime }}$, considérer dans $G$ une chaîne de longueur minimale de $u$ à $v$, et montrer qu'elle ne passe pas par $s_0$.

5. Démontrer par récurrence sur $n$ que tout graphe connexe d'ordre $n$ possède au moins $n-1$ arêtes. On utilisera les questions 2, 3 et 4.

Partie B. Exploitation.

6. En déduire qu'un graphe d'ordre $n$ possédant strictement moins de $n-1$ arêtes n'est pas connexe.

7. Une entreprise possède $12$ sites informatiques et souhaite les relier par des câbles, de façon que l'information puisse circuler entre deux sites quelconques, éventuellement en transitant par d'autres sites. Déterminer le nombre minimal de câbles nécessaires, et décrire une installation atteignant ce minimum.

8. Le directeur technique affirme : « avec beaucoup de câbles, on est certain que tous les sites communiquent ». Montrer que cette affirmation est fausse en exhibant, sur les mêmes $12$ sites, une installation d'au moins $50$ câbles qui ne relie pourtant pas tous les sites.

9. On cherche le nombre de câbles qui garantit à coup sûr la communication entre les $12$ sites. Soit $G$ un graphe d'ordre $12$ non connexe. On note $C$ la composante connexe d'un sommet donné, $p$ son nombre de sommets et $q=12-p$ le nombre de sommets restants.

a. Justifier que $1⩽p⩽11$ et qu'aucune arête ne relie un sommet de $C$ à un sommet hors de $C$.

b. En admettant qu'un graphe simple d'ordre $k$ possède au plus ${\displaystyle \frac{k(k-1)}{2}}$ arêtes, démontrer que $m⩽{\displaystyle \frac{p^2+q^2-12}{2}}$, puis que $m⩽55$. On pourra écrire $p^2+q^2$ sous la forme $2(p-6{)}^2+72$.

c. Conclure : à partir de combien de câbles est-on certain que les $12$ sites communiquent ? Ce nombre est-il le plus petit possible ?

La matrice d'adjacence d'un graphe dépend de l'ordre dans lequel on range ses sommets. Cet exercice décrit précisément le lien entre deux matrices d'adjacence d'un même graphe, et en tire un critère pour reconnaître que deux graphes sont différents.

Vocabulaire donné. Soit $n$ un entier supérieur ou égal à $2$. Supposons les sommets d'un graphe numérotés de $1$ à $n$, puis rangés dans un nouvel ordre. Pour chaque position $i$ du nouvel ordre, on note $\sigma (i)$ l'ancien numéro du sommet qui occupe cette position ; l'application $\sigma$ est une bijection de $\{1,\dots ,n\}$ dans lui-même. On appelle matrice de permutation associée la matrice $P$ obtenue en permutant les colonnes de $I_n$ de la façon suivante :

$$\text{la colonne num}\acute{\text{e}}\text{ro }i\text{ de }P\text{ est la colonne num}\acute{\text{e}}\text{ro }\sigma (i)\text{ de }{I}_n\mathrm{.}$$

Autrement dit, $P$ ne contient que des $0$ et des $1$, avec exactement un $1$ par ligne et un $1$ par colonne, et $P_{k,i}=1$ si et seulement si $k=\sigma (i)$. On admettra que $P$ est inversible, d'inverse $P^{-1}={}^{t}P$, ce que la question 3 fait vérifier sur l'exemple.

On rappelle enfin que la trace d'une matrice carrée est la somme de ses coefficients diagonaux.

Partie A. Un exemple à quatre sommets.

On considère le graphe non orienté $G$ de sommets $s_1$, $s_2$, $s_3$, $s_4$ et d'arêtes

1. Écrire la matrice d'adjacence $A$ de $G$, les sommets étant rangés dans l'ordre $(s_1,s_2,s_3,s_4)$. Donner également le degré de chaque sommet.

2. Écrire la matrice d'adjacence $A^{\mathrm{\prime }}$ du même graphe $G$, les sommets étant cette fois rangés dans l'ordre $(s_2,s_4,s_1,s_3)$.

3. Déterminer la bijection $\sigma$ correspondant à ce changement d'ordre, puis écrire la matrice de permutation $P$ associée. Calculer ${}^{t}PP$ et en déduire que $P$ est inversible, d'inverse ${}^{t}P$.

4. Calculer $AP$, puis ${}^{t}P(AP)$, et vérifier que ${}^{t}PAP=A^{\mathrm{\prime }}$.

Partie B. Le cas général.

Soit $G$ un graphe non orienté d'ordre $n$, de matrice d'adjacence $A=(a_{i,j})$ pour une première numérotation. On renumérote ses sommets, on note $\sigma$ la bijection et $P$ la matrice de permutation associées, et $A^{\mathrm{\prime }}=(a_{i,j}^{\mathrm{\prime }})$ la matrice d'adjacence dans le nouvel ordre.

5. a. Démontrer que, pour tous indices $i$ et $j$, on a $({}^{t}PAP{)}_{i,j}=a_{\sigma (i),\sigma (j)}$. On explicitera la double somme définissant ce coefficient.

5. b. Justifier que $a_{i,j}^{\mathrm{\prime }}=a_{\sigma (i),\sigma (j)}$, puis conclure que $A^{\mathrm{\prime }}={}^{t}PAP$.

6. En déduire les trois propriétés suivantes.

a. Les matrices $A$ et $A^{\mathrm{\prime }}$ ont la même trace.

b. Les matrices $A$ et $A^{\mathrm{\prime }}$ ont la même somme de coefficients.

c. La liste des degrés lue sur $A^{\mathrm{\prime }}$ est celle lue sur $A$, à l'ordre près.

7. On considère les deux graphes suivants, tous deux d'ordre $4$ et possédant $3$ arêtes :

• $H_1$ a pour sommets $t_1$, $t_2$, $t_3$, $t_4$ et pour arêtes $\{t_1,t_2\}$, $\{t_2,t_3\}$, $\{t_3,t_4\}$ ;
• $H_2$ a pour sommets $t_1$, $t_2$, $t_3$, $t_4$ et pour arêtes $\{t_1,t_2\}$, $\{t_1,t_3\}$, $\{t_1,t_4\}$.

Démontrer qu'aucune renumérotation ne transforme la matrice d'adjacence de $H_1$ en celle de $H_2$ : ces deux graphes ne sont pas le même graphe renuméroté.