$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Exercices corrigés - Théorie des graphes - exercices théoriques

Enoncé
Avez-vous jamais remarqué que dans un groupe de personnes, il y a toujours deux individus qui connaissent exactement le même nombre de membres du groupe?
  1. Formaliser la propriété à démontrer dans le vocabulaire des graphes.
  2. Démontrer cette propriété (on pourra raisonner par l'absurde et supposer que la propriété à prouver n'est pas vraie pour un graphe à $n$ sommets).
Corrigé
Enoncé
Un graphe est dit \emph{régulier} s'il est simple et si tous ses sommets ont le même degré. On s'intéresse dans cet exercice aux graphes réguliers dont les sommets sont de degré 3.
  1. Que dire du nombre de sommets d'un tel graphe?
  2. Démontrer que, pour tout $p\geq 2$, il existe un graphe régulier d'ordre $2p$ dont les sommets sont de degré 3.
Indication
Corrigé
Enoncé
Soit $G$ un graphe non-orienté simple d'ordre $2p$. On suppose que le degré de chaque sommet est au moins égal à $p$. Démontrer que ce graphe est connexe.
Indication
Corrigé
Enoncé
Soit $G$ un graphe \emph{simple}.
  1. On suppose que $G$ est connexe et que $x$ est un sommet de $G$ de degré 1. Prouvez que $G\backslash \{x\}$ est connexe.
  2. En déduire que si $G$ est connexe et d'ordre $n\geq 2$, alors $G$ comporte au moins $n-1$ arêtes.
  3. On suppose que $G$ est d'ordre $n\geq 3$ et qu'il comporte strictement plus de $(n-1)(n-2)/2$ arêtes.
    1. Démontrer que le degré de tout sommet est non-nul.
    2. Démontrer que $G$ est connexe.
Indication
Corrigé
Enoncé
On a construit des ponts entre les iles d'un archipel de sorte de pouvoir aller (directement ou indirectement) de toute ile à une autre. De plus, de chaque ile part un nombre pair de ponts. On a remarqué que, lorsqu'un pont est inaccessible pour cause de travaux, on peut encore aller de toute ile à une autre.
  1. Traduire ce problème en terme de théorie des graphes.
  2. Prouver le résultat!
Indication
Corrigé
Exercice 6 - Connexe moins un sommet [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
Soit $G$ un graphe connexe. Montrons qu'il existe un sommet $s$ du graphe tel que le sous-graphe obtenu à partir de $G$ en supprimant $s$ reste connexe.
Indication
Corrigé
Exercice 7 - Arbres et graphes bipartis [Signaler une erreur] [Ajouter à ma feuille d'exos]
Enoncé
On rappelle qu'un arbre est un graphe connexe et sans cycles, et qu'un graphe est biparti s'il est $2$-colorable (c'est-à-dire qu'on peut attribuer une couleur à chaque sommet de sorte que deux sommets liés par une arête ont une couleur différente en utilisant seulement deux couleurs). Montrer que tout arbre est un graphe biparti.
Indication
Corrigé
Enoncé
On souhaite démontrer dans cet exercice le théorème suivant, dû à König en 1916 :
Un graphe est 2-colorable si et seulement s'il ne possède pas de cycles de longueur impaire.
On rappelle que la longueur d'un cycle est le nombre d'arêtes qui le compose.
  1. Prouver l'implication directe.
  2. Réciproquement, on suppose que le graphe $G$ ne possède pas de cycles de longueur impaire, et on veut prouver qu'on peut le colorer en utilisant simplement deux couleurs.
    1. Expliquer pourquoi on peut supposer que le graphe est connexe.
    2. On suppose que le graphe est connexe, et on fixe $x$ un sommet de $G$. Pour $k\geq 1$, on note $G_k$ l'ensemble des sommets de $G$ qui sont à une distance exactement égale à $k$ de $x$. Démontrer que, s'il y a une arête entre un sommet $y$ dans $G_{2p}$ et un sommet $z$ dans $G_{2q}$, alors le graphe possède un cycle de longueur impaire.
    3. Conclure.
Indication
Corrigé
Graphes orientés
Enoncé
On appelle \emph{tournoi} un graphe orienté sans boucle tel que, entre deux sommets, il y a toujours exactement un arc. On dit qu'un sommet $x$ d'un tournoi $G$ \emph{domine} un sommet $y$ de $G$ si l'arc $(x,y)$ existe. On dit qu'un sommet $x$ est un roi si, pour tout autre sommet $y$, alors
  • ou bien $x$ domine $y$;
  • ou bien il existe un sommet $z$ tel que $x$ domine $z$ et $z$ domine $y$.
Démontrer que, dans un tournoi, il existe toujours un roi.
Indication
Corrigé
Enoncé
On appelle \emph{tournoi} un graphe orienté sans boucle tel que, entre deux sommets, il y a toujours exactement un arc. On dit qu'un sommet $x$ d'un tournoi $G$ \emph{domine} un sommet $y$ de $G$ si l'arc $(x,y)$ existe. Sinon, on dit que $x$ est dominé par $y$ (et c'est alors l'arc $(y,x)$ qui existe).
Le but de l'exercice est de démontrer le théorème de Moon suivant : dans un tournoi fortement connexe avec $n\geq 3$ sommets, pour tout sommet $x$ et tout $k\in\{3,\dots,n\}$, il existe toujours un circuit de longueur $k$ passant par $x$.
On fixe $G$ un tel tournoi fortement connexe.
  1. Question préliminaire : On suppose que les sommets de $G$ sont partagés en 3 parties non-vides $A$, $B$ et $C$ tels que, tous les sommets de $A$ dominent ceux de $C$ et tous les sommets de $C$ dominent ceux de $B$. Démontrer qu'il existe toujours un arc allant d'un sommet de $B$ à un sommet de $A$.
  2. Démontrer le résultat pour $k=3$. On pourra considérer $\Gamma^+(x)$ (resp. $\Gamma^-(x)$) l'ensemble des successeurs (resp. des prédécesseurs) de $x$.
  3. On suppose le résultat vrai pour $k\leq n-1$, et on souhaite construire un circuit de longueur $k+1$. Soit $C:=x_0=x\to x_1\to x_2\to\dots\to x_k=x_0$ un circuit de longueur $k-1$ passant par $x$.
    1. On suppose qu'il existe $y\in G\backslash C$ tel que $y$ domine un sommet de $C$ et $y$ est dominé par un sommet de $C$. Construire un circuit de longueur $k$ passant par $x$.
    2. Dans le cas contraire, on suppose que chaque sommet $y$ de $G\backslash C$ est dominé par tous les sommets de $C$, ou domine tous les sommets de $C$. On introduit $\mathcal R$ l'ensemble des sommets $y$ de $G\backslash C$ dominés par les sommets de $C$ et $\mathcal S$ l'ensemble des sommets $y$ de $G\backslash C$ dominant les sommets de $C$. Démontrer que $\mathcal R$ et $\mathcal S$ sont tous les deux non-vides, et conclure à l'existence d'un circuit de longueur $k$ passant par $x$.
Indication
Corrigé