Exercices

TP1 — Bases

Sélection courte des exercices à refaire : les exercices 1 et 2 sur leurs sous-questions les plus utiles, une question ciblée sur l’hypercube, puis l’exercice 4 sur les tournois.

TP1 — Exercice 1

Source	Numéro	Importance	Notion
TP1	1	⭐⭐⭐	Degrés, isomorphisme, contradiction

Énoncé

Vrai ou faux ? Démontrez ou donnez un contre-exemple.

a) L’élimination d’un sommet de degré maximum peut augmenter le degré moyen d’un graphe.

b) Deux graphes simples qui possèdent un même nombre de sommets et dont les listes de degrés sont identiques sont isomorphes. Même énoncé avec la condition supplémentaire que les graphes sont connexes.

c) Un graphe simple de deux sommets au moins possède toujours deux sommets de degrés identiques.

Indice

a) Écrivez le degré moyen sous la forme $\bar d=2|E|/|V|$ et comparez le degré maximum à cette moyenne.

b) Une liste de degrés ne décrit pas complètement les adjacences. Cherchez deux graphes connexes, 3-réguliers, à 6 sommets, dont l’un est biparti et l’autre non.

c) Supposez par contradiction que tous les degrés sont différents. Dans un graphe simple à $n$ sommets, ils devraient alors être exactement $0,1,\ldots,n-1$. Regardez les degrés $0$ et $n-1$.

Voir la correction ↓

---

TP1 — Exercice 2

Source	Numéro	Importance	Notion
TP1	2	⭐⭐⭐	Connexité, degrés, bornes

Énoncé

Démontrez les propositions suivantes.

a) D’un sommet de degré impair, il existe toujours un chemin jusqu’à un autre sommet de degré impair.

b) Pour un graphe simple connexe de $n$ sommets,

$$n-1\le |E|\le \frac{n(n-1)}2.$$

c) Un graphe simple qui possède plus de

$$\frac{(n-1)(n-2)}2$$

arêtes est connexe.

Indice

a) Travaillez uniquement dans la composante connexe du sommet de degré impair et appliquez le théorème des poignées de main à cette composante.

b) Séparez les deux bornes. Pour la borne inférieure, demandez-vous combien d’arêtes il faut au minimum pour relier $n$ sommets. Pour la borne supérieure, comptez le nombre de paires de sommets possibles dans un graphe simple.

c) Raisonnez par contraposée : quel est le plus grand nombre d’arêtes qu’un graphe peut posséder tout en restant non connexe ? Pensez à un sommet isolé et à rendre tous les autres sommets adjacents deux à deux.

Voir la correction ↓

---

TP1 — Exercice 3 — version ciblée

Source	Numéro	Importance	Notion
TP1	3	⭐⭐	Hypercube, bipartition

Énoncé

Dans le graphe de l’hypercube, les sommets sont les $k$-tuples de $0$ et de $1$, et deux sommets sont adjacents s’ils diffèrent en exactement une position.

Proposez une bipartition naturelle des sommets et justifiez qu’elle convient.

Indice

Ne regardez pas d’abord la position des $1$, mais seulement leur nombre. Que devient la parité du nombre de $1$ lorsqu’on modifie exactement une coordonnée ?

Voir la correction ↓

---

TP1 — Exercice 4

Source	Numéro	Importance	Notion
TP1	4	⭐⭐⭐	Tournoi, degré sortant maximal, contradiction

Énoncé

Un tournoi de $n$ joueurs est un graphe complet $K_n$ dans lequel on a choisi une direction pour chaque arête. Il y a une arête $(u,v)$ lorsque $u$ a remporté sa partie contre $v$.

Un sommet $u$ d’un tournoi est un roi si, quel que soit le sommet $v$ du graphe, il y a une arête $(u,v)$, ou il y a un sommet intermédiaire $w$ et des arêtes $(u,w)$ et $(w,v)$.

Démontrez qu’un tournoi possède toujours un roi.

Indice

Choisissez un sommet $\beta$ de degré sortant maximal. Supposons qu’il ne soit pas roi : il existe alors un sommet $u$ qui bat $\beta$ et qui ne peut être atteint depuis $\beta$ en deux étapes. Comparez alors les degrés sortants de $u$ et de $\beta$.

Voir la correction ↓

---

TP2 — Graphes connexes, eulériens et bipartis

Sélection : exercices 2, 3a–b et 5a–b. Les corrections sont regroupées à la fin du document.

TP2 — Exercice 2

Source	Numéro	Importance	Notion
TP2	2	⭐⭐⭐	Degrés et suppression d’un sommet

Énoncé

Pour un graphe simple $G$ de sommets $v_1,\ldots,v_n$ avec $n\ge3$, démontrez les deux identités :

$e(G)=\frac{\sum_{i=1}^{n}e(G-v_i)}{n-2}, \qquad d_G(v_i)=\frac{\sum_{j=1}^{n}e(G-v_j)}{n-2}-e(G-v_i).$

Ici $e(G)$ est le nombre d’arêtes et $G-v_i$ supprime le sommet $v_i$ et ses arêtes incidentes.

Voir la correction ↓

---

TP2 — Exercice 3 (a et b)

Source	Numéro	Importance	Notion
TP2	3	⭐⭐⭐	Parcours fermés, questions a et b

Énoncé

a) Combien y a-t-il de parcours fermés de longueur $2n$ dans le graphe biparti complet $K_{n,n}$ ?

b) Combien y a-t-il de parcours fermés de longueur $n$ dans le graphe complet $K_n$ ?

Un parcours fermé revient à son départ, mais peut répéter des sommets et des arêtes.

Voir la correction ↓

---

TP2 — Exercice 5 (a et b)

Source	Numéro	Importance	Notion
TP2	5	⭐⭐⭐	Séquences de de Bruijn, questions a et b

Énoncé

On veut construire la plus longue séquence circulaire de lettres d’un alphabet de $k$ lettres sans répéter de sous-séquence de longueur $n$.

a) Donner une borne supérieure sur la longueur de la séquence.

b) Peut-on atteindre cette borne ? Traduire en problème de parcours eulérien orienté. Indice : sommets = mots de longueur $n-1$, arêtes = mots de longueur $n$.

Voir la correction ↓

---

Corrections

Correction — TP1, exercice 1

a) Faux. Soit $G$ un graphe à $n$ sommets, de degré moyen $\mu$, et soit $v$ un sommet de degré maximum $\Delta$. On a nécessairement $\Delta\ge\mu$.

Après suppression de $v$, les degrés des autres sommets ne peuvent qu’être inférieurs ou égaux à leurs anciens degrés. Ainsi, si $\mu'$ est le nouveau degré moyen,

$$\mu' \le \frac{n\mu-\Delta}{n-1} \le \frac{n\mu-\mu}{n-1} =\mu.$$

Le degré moyen ne peut donc pas augmenter.

b) Faux, même si les deux graphes sont connexes. On peut prendre deux graphes simples connexes à 6 sommets, tous de degré 3, tels que l’un soit biparti et l’autre contienne un triangle. Ils ont la même liste de degrés

$$(3,3,3,3,3,3),$$

mais ne sont pas isomorphes, car l’isomorphisme préserve notamment la bipartition et la présence de cycles impairs.

c) Vrai. Supposons par contradiction que les $n$ sommets aient tous des degrés différents. Comme le graphe est simple, les degrés possibles sont $0,1,\ldots,n-1$. Les $n$ sommets devraient donc réaliser exactement ces $n$ valeurs.

Il existerait alors un sommet de degré $0$ et un sommet de degré $n-1$. Mais un sommet de degré $n-1$ est adjacent à tous les autres sommets, en particulier au sommet supposé de degré $0$, contradiction.

Donc au moins deux sommets ont le même degré.

Retour à l’exercice ↑

---

Correction — TP1, exercice 2

a) Considérons la composante connexe $C$ contenant un sommet $u$ de degré impair. Le théorème des poignées de main appliqué à $C$ donne

$$\sum_{v\in C}\deg(v)=2|E(C)|,$$

donc cette somme est paire. Le nombre de sommets de degré impair dans $C$ est donc pair. Puisque $u$ en est un, il en existe au moins un autre, noté $v$. Comme $u$ et $v$ appartiennent à la même composante connexe, il existe un chemin entre eux.

b) Borne inférieure. Un graphe connexe à $n$ sommets possède au moins $n-1$ arêtes. En retirant successivement toutes ses arêtes, on passe d’une seule composante connexe à $n$ sommets isolés. Il faut donc créer $n-1$ composantes supplémentaires, et retirer une arête ne peut augmenter le nombre de composantes que d’au plus 1. Ainsi,

$$|E|\ge n-1.$$

Borne supérieure. Dans un graphe simple, il y a au plus une arête pour chaque paire de sommets distincts. Il y a

$$\binom n2=\frac{n(n-1)}2$$

paires de sommets. Donc

$$|E|\le \frac{n(n-1)}2.$$

On obtient bien

$$n-1\le |E|\le \frac{n(n-1)}2.$$

c) Raisonnons par contraposée. Supposons $G$ non connexe. Pour maximiser le nombre d’arêtes sans rendre le graphe connexe, on peut prendre deux composantes de tailles $i$ et $n-i$, chacune complète. Le nombre d’arêtes est alors au plus

$$e(i)=\binom i2+\binom{n-i}{2}.$$

Cette fonction quadratique atteint son maximum, pour $1\le i\le n-1$, en $i=1$ ou $i=n-1$. Le graphe non connexe le plus dense est donc un sommet isolé accompagné d’un $K_{n-1}$, avec

$$|E|\le \binom{n-1}{2} =\frac{(n-1)(n-2)}2.$$

Par contraposée, si

$$|E|>\frac{(n-1)(n-2)}2,$$

alors $G$ est connexe.

Retour à l’exercice ↑

---

Correction — TP1, exercice 3

Définissons

$$A=\{x:x\text{ contient un nombre pair de }1\}, \qquad B=\{x:x\text{ contient un nombre impair de }1\}.$$

Deux sommets adjacents diffèrent en exactement une position. Passer de l’un à l’autre remplace donc soit un $0$ par un $1$, soit un $1$ par un $0$. Dans les deux cas, la parité du nombre de $1$ change.

Toute arête relie donc un sommet de $A$ à un sommet de $B$. Ainsi $(A,B)$ est une bipartition du graphe.

Retour à l’exercice ↑

---

Correction — TP1, exercice 4

Soit $G=(V,E)$ un tournoi. Pour un sommet $u$, notons $\deg^+(u)$ son degré sortant. Choisissons un sommet $\beta$ de degré sortant maximal.

Posons

$$V_\beta=\{x\in V:(\beta,x)\in E\}, \qquad D_\beta=\{x\in V:(x,\beta)\in E\}.$$

Par définition,

$$\deg^+(\beta)=|V_\beta|.$$

Supposons par contradiction que $\beta$ ne soit pas roi. Il existe alors un sommet $u\in D_\beta$ que $\beta$ ne peut pas atteindre en deux étapes.

Cela signifie qu’aucun sommet $w\in V_\beta$ ne bat $u$. Comme on est dans un tournoi, pour chaque $w\in V_\beta$, on a nécessairement

$$u\to w.$$

De plus, $u\in D_\beta$, donc

$$u\to\beta.$$

Ainsi $u$ bat tous les sommets de $V_\beta$ ainsi que $\beta$, d’où

$$\deg^+(u)\ge |V_\beta|+1 =\deg^+(\beta)+1.$$

Donc $\deg^+(u)>\deg^+(\beta)$, contradiction avec le choix de $\beta$ comme sommet de degré sortant maximal.

Ainsi $\beta$ est un roi. Tout tournoi possède donc au moins un roi.

Retour à l’exercice ↑

---

Correction — TP2, exercice 2

Supprimer $v_i$ enlève exactement ses $d_G(v_i)$ arêtes incidentes :

$$e(G-v_i)=e(G)-d_G(v_i).$$

Sommons sur tous les sommets :

$$\begin{aligned} \sum_{i=1}^{n}e(G-v_i) &=ne(G)-\sum_{i=1}^{n}d_G(v_i)\\ &=ne(G)-2e(G)\\ &=(n-2)e(G). \end{aligned}$$

La deuxième égalité utilise le théorème des poignées de main. Puisque $n\ge3$, on divise par $n-2$ et on obtient la première formule. Enfin,

$$d_G(v_i)=e(G)-e(G-v_i) =\frac{\sum_{j=1}^{n}e(G-v_j)}{n-2}-e(G-v_i).$$

Réflexe : compter les arêtes supprimées puis sommer sur tous les sommets.

Retour à l’exercice ↑

---

Correction — TP2, exercice 3

a) Dans $K_{n,n}$. Chaque sommet possède $n$ voisins dans l’autre partition. Pour un sommet de départ fixé, chacun des $2n-1$ premiers déplacements offre $n$ choix ; le dernier pas doit revenir au départ.

Dans $K_{2,2}$, on voit les quatre arêtes entre les deux partitions :

flowchart LR a1((a1)) --- b1((b1)) a1 --- b2((b2)) a2((a2)) --- b1 a2 --- b2

Depuis $a_1$, un parcours de longueur 4 est de la forme $a_1\to B\to A\to B\to a_1$. Il existe $2^3=8$ parcours, soit $4\cdot8=32$ en comptant tous les sommets de départ.

En général, il y a $2n$ sommets de départ :

$$\boxed{2n\cdot n^{2n-1}=2n^{2n}}.$$

b) Dans $K_n$ — méthode avec $1_{n\times n}$. Notons $J=1_{n\times n}$ la matrice dont toutes les entrées valent $1$, et $I_n$ la matrice identité. La matrice d’adjacence du graphe complet est

$$A=J-I_n.$$

Le coefficient $(A^r)_{ij}$ donne le nombre de parcours de longueur $r$ de $v_i$ à $v_j$. Les parcours fermés sont donc comptés sur la diagonale :

$$N=\operatorname{tr}(A^n).$$

Les valeurs propres de $J$ sont $n$ (une fois, pour le vecteur de tous les $1$) et $0$ (multiplicité $n-1$, pour les vecteurs dont la somme des composantes est nulle). Celles de $A=J-I_n$ sont donc $n-1$ et $-1$, respectivement. La trace de $A^n$ est la somme de leurs puissances $n$-ièmes :

$$\boxed{N=(n-1)^n+(n-1)(-1)^n}.$$

Exemple : $K_3$ est un triangle. Depuis chaque sommet, deux tours de longueur 3 sont possibles, un par sens. Cela donne $3\cdot2=6$, conformément à $2^3+2(-1)^3=6$.

flowchart TB A((A)) --- B((B)) B --- C((C)) C --- A

À retenir : parcours fermés de longueur $r$ $\Rightarrow \operatorname{tr}(A^r)$ ; pour $K_n$, la forme $J-I_n$ permet de calculer cette trace sans développer la puissance de matrice.

Retour à l’exercice ↑

---

Correction — TP2, exercice 5

a) Borne supérieure. Il existe $k^n$ mots de longueur $n$. Une séquence circulaire de longueur $L$ possède $L$ fenêtres de longueur $n$, une par position. Si aucune ne se répète :

$$\boxed{L\le k^n}.$$

b) Construction. On crée un graphe orienté dont chaque sommet représente un mot de longueur $n-1$. Chaque mot de longueur $n$ fournit une arête allant des $n-1$ premières lettres vers les $n-1$ dernières lettres.

Exemple $k=3,n=3$. L’alphabet est $\{0,1,2\}$. Les neuf sommets sont $00,01,02,10,11,12,20,21,22$. Un mot comme $201$ devient l’arête $20\to01$ ; les mots se chevauchent sur deux lettres. Extrait du graphe (trois arêtes parmi les 27) :

flowchart LR n20["20"] -->|"201"| n01["01"] n01 -->|"012"| n12["12"] n12 -->|"120"| n20

L’objectif « utiliser une seule fois chaque mot de longueur $n$ » revient à « parcourir une seule fois chaque arête » : on cherche un circuit eulérien puisque la séquence est circulaire.

Degrés. Depuis $20$, les mots $200,201,202$ définissent les arêtes sortantes, et $020,120,220$ les arêtes entrantes. Chaque sommet possède donc $k$ arêtes entrantes et $k$ sortantes : ajouter une lettre à gauche ou à droite offre toujours $k$ choix.

$$\boxed{\forall v,\quad d^-(v)=d^+(v)=k}.$$

Forte connexité. Pour aller d’un sommet-mot $u$ à un sommet-mot $v$, on ajoute successivement les $n-1$ lettres de $v$ : après ces décalages, le sommet atteint est $v$. C’est vrai pour tout couple ordonné $(u,v)$.

Le graphe est fortement connexe, avec degrés entrants et sortants égaux. Il possède donc un circuit eulérien. Il contient exactement $k^n$ arêtes (une par mot) : le circuit donne une séquence circulaire de longueur $k^n$ contenant chacun des mots une seule fois.

$$\boxed{L_{\max}=k^n}.$$

Vérification plus petite : pour $k=2,n=2$, la séquence circulaire $0011$ contient $00,01,11,10$ une seule fois chacun.

Réflexe : chaque mot à utiliser exactement une fois $\to$ une arête ; chevauchement $\to$ enchaînement des arêtes ; circularité $\to$ circuit eulérien.

Retour à l’exercice ↑