Sauter au contenu

Mathématiques discrètes Version préliminaire

Section 7.3 Chaîne, cycle et graphe eulérien

Sous-section 7.3.1 Chaîne et cycle

On veut étudier les différentes façons dont il est possible de se déplacer à l’intérieur d’un graphe, d’un sommet à l’autre en empruntant les arêtes. Non seulement les graphes sont justement utiles afin de représenter des chemins (trajets routiers, aériens et autres), mais l’étude des différents chemins présents à l’intérieur d’un graphe permet souvent de mieux comprendre ceux-ci.
🔗
Par exemple, on pourra donner une nouvelle caractérisation des graphes bipartis en termes de chemins présents dans ces graphes. Aussi, en étudiant les chemins présents dans un graphe, il nous sera entre autres possible de montrer que deux graphes ne sont pas isomorphes.
🔗
D’un autre côté, de nombreuses applications des graphes proviennent du fait que l’on trouve le chemin le plus court entre différents sommets. On peut évidemment penser à trouver le chemin le plus court entre deux endroits dans une ville, mais on pourra également mesurer la complexité de certains algorithmes, comme des algorithmes de tri, grandement utilisés en informatique.
🔗
Puisque la définition d’un graphe a été donnée en termes d’ensembles, on doit donner la définition d’un chemin de façon similaire. Aussi, lorsqu’on travaille avec des graphes non orientés, comme c’est notre cas, on parlera d’une chaîne plutôt que d’un chemin. Le terme chemin étant habituellement utilisé pour les graphes orientés
🔗

Définition 7.3.1.

Soit \(G=(S,A)\) un graphe simple, une chaîne de longueur \(n\in \N^\ast\) reliant les sommets \(s, t\in S\text{,}\) ou encore une chaîne entre \(s\) et \(t\text{,}\) est une suite de sommets \(s_0, s_1, \dots, s_n\) de \(G\) tel que \(\{s_i, s_{i+1}\}\in A\) pour \(i=0, 1, \dots, n-1\text{,}\) avec \(s_0=s\) et \(s_n=t\text{.}\)
🔗
Si toutes les arêtes formant la chaîne sont uniques, c’est-à-dire si \(\{s_i, s_{i+1}\}\neq \{s_j, s_{j+1}\}\) lorsque \(i\neq j\text{,}\) on dira que la chaîne est une chaîne simple.
🔗
Si \(s_0=s_n\text{,}\) on parlera d’un cycle plutôt que d’une chaîne.
🔗
🔗

Exemple 7.3.2. Quelsques chaînes.

On considère le graphe \(G\) ci-dessous.
Un graphe pour introduire les définitions de chaînes.
Figure 7.3.3. \(G\)
🔗
🔗
On remarque qu’il existe de nombreuses chaînes reliant \(a\) et \(h\text{.}\) Par exemple, il y a la chaîne \(a, e, d, a, e, b, c, f, g, h\) est une chaîne de longueur \(9\text{.}\) Celle-ci n’est pas simple, car elle passe deux fois par \(\{a,e\}\text{.}\)
🔗
Si on se limite aux chaînes simples, on peut trouver des chaînes de longueur \(6\text{.}\) Par exemple, les chaînes \(a, e, b, c, g, i, h\) et \(a, b, d, c, f, g, h\text{.}\)
🔗
On remarque également que la chaîne \(a, b, c, f, g, h\) est parmi les chaînes les plus courtes (de longueur \(5\)) reliant \(a\) et \(h\text{.}\)
🔗
Finalement, \(G\) possède plusieurs cycles. Par exemple, la chaîne \(a, b, d, a\) est un cycle simple de longueur \(3\text{,}\) alors que la chaîne \(f, g, h, i, f\) est un cycle simple de longueur \(4\text{.}\)
🔗
🔗
🔗

Sous-section 7.3.2 Graphes connexes

Jusqu’à maintenant, pour la grande majorité des graphes étudiés, il était toujours possible de trouver une chaîne reliant deux sommets quelconques du graphe. Ceci n’est pas toujours vrai, et les graphes ayant cette propriété seront nommés des graphes connexes. Si un graphe n’est pas connexe, il sera toujours possible de se restreindre à des sous-graphes connexes, c’est-à-dire ses composantes connexes.
🔗

Définition 7.3.4.

Soit \(G=(S,A)\) un graphe simple. Si, pour tout \(s, t \in S\text{,}\) il existe une chaîne reliant \(s\) et \(t\text{,}\) alors on dira que \(G\) est un graphe connexe.
🔗
Si on peut écrire \(G\) comme l’union de graphes \(G_i=(S_i,A_i)\) tels que \(G_i\) est connexe et \(S_i\cap S_j =\emptyset\) lorsque \(i\neq j\text{,}\) on dira que les graphes \(G_i\) sont les composantes connexes de \(G\text{.}\)
🔗
🔗
Si un graphe n’est pas connexe, il sera toujours possible de le séparer en ses composantes connexes. Cependant, le cas où le nombre de sommets du graphe est infini est un peu plus complexe. On se limitera donc au cas où le graphe possède un nombre fini de sommets.
🔗

Démonstration.

🔗

Sous-section 7.3.3 Chemins et circuits eulériens

On termine la section avec l’étude d’un type particulier de graphes connexes, les graphes eulériens. Ce type de graphes a été utilisé afin de modéliser le fameux problème du postier chinois.
🔗

Définition 7.3.6.

  • Une chaîne eulérienne d’un graphe \(G\) est une chaîne simple passant par toutes les arêtes de \(G\text{.}\)
    🔗
  • Un cycle eulérien d’un graphe \(G\) est un cycle simple passant par toutes les arêtes de \(G\text{.}\)
    🔗
  • Si un graphe \(G\) possède un cycle eulérien, on dira que \(G\) est un graphe eulérien.
    🔗
    🔗
🔗
🔗

Exemple 7.3.7.

  • La chaîne \(a,c,e,d,c,b,a,d,b\) est une chaîne eulérienne du graphe \(G_1\text{.}\)
    🔗
  • La chaîne \(a,b,c,d,b\) est une chaîne eulérien du graphe \(G_2\text{.}\)
    🔗
  • Le cycle \(a,b,e,d,c,e,a\) est un cycle eulérien du graphe \(G_3\text{.}\)
    🔗
  • Le graphe \(G_4\) ne possède aucune chaîne eulérienne, et aucun cycle eulérien.
    🔗
  • Le graphe \(G_5\) ne possède aucune chaîne eulérienne, et aucun cycle eulérien.
    🔗
🔗
(a) \(G_1\)
🔗
(b) \(G_2\)
🔗
(c) \(G_3\)
🔗
(d) \(G_4\)
🔗
(e) \(G_5\)
🔗
Figure 7.3.8. Chaînes et cycles eulériens
🔗
🔗
Pour montrer l’existence d’une chaîne ou d’un cycle eulérien, on peut essayer d’en trouver un. Pour montrer qu’il n’en existe pas, il faut argumenter un peu plus.
🔗
Le critère donne une condition suffisante et nécessaire pour l’existence d’une chaîne ou d’un cycle eulérien
🔗
🔗

Questions de compréhension de la lecture 7.3.4 Questions de compréhension de la lecture

Ces questions sont à faire avant de venir en classe et à remettre au début du cours.
🔗

1.

Noter toute question qui demeure suite à la lecture de la section et la résolution des exercices ci-dessus ou toute précision/clarification à apporter. Note: cette question est facultative.
🔗
🔗
🔗

Exercices 7.3.5 Exercices

1.

Soit \(G=(S,A)\) un graphe simple connexe. Montrer que si \(s, t\) sont des sommets quelconques de \(G\text{,}\) alors il existe une chaîne simple reliant \(s\) et \(t\text{.}\)
🔗
Solution.
Puisque \(G\) est connexe, alors il existe une chaîne \(s=s_0, s_1, \dots, s_n=t\text{.}\) Supposons que cette chaîne soit de longueur minimale. On veut montrer que cette chaîne est simple.
🔗
Supposons le contraire, alors il existe \(i, j\) des indices tels que \(0\leq i\lt j \leq n\) avec \(s_i=s_j\text{.}\) Ainsi, la chaîne
\begin{equation*} s_0, \dots s_{i-1}, s_i, s_{j+1}, s_{j+2}, \dots s_n \end{equation*}
est une chaîne reliant \(s\) et \(t\) de longueur \(n-(j-i)\lt n\text{.}\) Cette chaîne est donc plus courte que la chaîne initiale. Ceci est une contradiction, car on avait supposé que la chaîne était la plus courte possible.
🔗
La chaîne \(s=s_0, s_1, \dots, s_n=t\) est donc nécessairement une chaîne simple reliant \(s\) et \(t\text{.}\)
🔗
🔗
🔗

2.

Soit \(G=(S,A)\) un graphe simple, et soit \(s, t, u \in S\text{.}\)
🔗
(a)
Montrer que s’il existe une chaîne de longueur \(n\) entre \(s\) et \(t\text{,}\) et s’il existe une chaîne de longueur \(m\) entre \(t\) et \(u\text{,}\) alors il existe une chaîne de longueur \(m+n\) entre \(s\) et \(u\text{.}\)
🔗
🔗
(b)
Montrer que s’il existe une chaîne de longueur \(n\) entre \(s\) et \(t\text{,}\) une arête entre \(t\) et \(u\text{,}\) et ’il existe une chaîne de longueur \(m\) entre \(s\) et \(u\text{,}\) alors il existe un cycle de longueur \(m+n+1\) qui commence à \(s\text{.}\)
🔗
🔗
🔗

3.

Soit \(G=(S_1\cup S_2,A)\) un graphe biparti (avec \(S_1\) et \(S_2\) les parties de \(G\)). Soit \(s_0, s_1, \dots, s_n\) une chaîne de \(G\text{,}\) et supposons que \(s_1\in S_1\text{.}\) Montrer que pour les sommets d’indice impair dans cette chaîne sont des éléments de \(S_1\text{.}\) Plus formellement, montrer que si \(k\in \N\) tel que \(1\leq 2k+1 \leq n\text{,}\) alors \(s_{2k+1}\in S_1\text{.}\)
🔗
Solution.
Supposons par contradiction qu’il existe un des sommets d’indice impair qui est un élément de \(S_2\text{,}\) alors on peut choisir \(s_{2k+1}\in S_2\) avec l’indice le plus petit possible. Puisque \(s_1\in S_1\text{,}\) on a que \(3\leq 2k+1\leq n\text{.}\)
🔗
Or, \(\{s_{2k-1},s_{2k}\}\) et \(\{s_{2k}, s_{2k+1}\}\) sont des arêtes de \(G\text{.}\) Puisque \(2k+1\) est minimal, on doit avoir \(s_{2k-1}\in S_1\text{,}\) mais alors \(s_{2k}\in S_2\) et donc \(s_{2k+1}\in S_1\text{.}\) Puisque \(S_1\cap S_2 = \emptyset\text{,}\) on obtient une contradiction.
🔗
Par ce qui précède, il ne peut pas y avoir de sommet de la chaîne d’indice impair dans \(S_2\text{.}\)
🔗
Remarque 7.3.10.
Par ce qui précède, on obtient directement que \(s_{2k}\in S_2\) lorsque \(0\leq 2k \leq n\text{.}\)
🔗
🔗
🔗
🔗

4.

Montrer qu’un graphe \(G=(S,A)\) est un graphe biparti si et seulement si \(G\) ne possède aucun cycle de longueur impaire.
🔗
Solution.
Supposons que \(G\) soit un graphe biparti avec \(S_1\) et \(S_2\) les parties de \(G\text{.}\) Supposons qu’il existe un cycle de longueur impair \(s_0, s_1, \dots, s_{2k+1}\) avec \(s_1\in S_1\text{.}\) On a alors \(s_0\in S_2\text{.}\) De plus, par l’exercice 7.3.5.3, on a également que \(s_{2k+1}\in S_1\text{.}\) Cependant, puisque \(s_0, s_1, \dots, s_{2k+1}\) ext un cycle, on a \(s_0=s_{2k+1}\text{.}\) Ceci est impossible, car \(S_1\cap S_2 =\emptyset\text{.}\)
🔗
Supposons maintenant que \(G\) ne possède aucun cycle de longueur impaire. On suppose que \(G\) est connexe. Sinon, on utilise l’argument ci-dessous sur chaque composante connexe de \(G\text{.}\) On choisit un sommet \(s_0\) quelconque de \(G\text{,}\) et on pose \(S_1\) l’ensemble des sommets relié à \(s_0\) par une chaîne de longueur impaire, et \(S_2\) l’ensemble des sommets relié à \(s_0\) par une chaîne de longueur paire. Puisque \(G\) est connexe, on a bien \(S=S_1\cup S_2\text{.}\)
🔗
On commence par montrer que \(S_1\cap S_2=\emptyset\text{.}\) Si \(t\in S_1\cap S_2\text{,}\) alors il existe une chaîne de longueur impaire ainsi qu’une chaîne de longueur paire entre \(s_0\) et \(t\text{.}\) Ainsi, par l’exercice 7.3.5.2, il existe un cycle de longueur impaire dans \(G\text{,}\) ce qui est une contradiction.
🔗
Il reste maintenant à montrer qu’il n’y a pas d’arête entre deux sommets de \(S_i\text{,}\) pour \(i=1\) et pour \(i=2\text{.}\) Supposons le contraire. Ainsi, il existe une arête entre \(t_1, t_2\in S_i\) pour \(i=1\) ou \(i=2\text{.}\) De plus, on sait qu’il existe une chaîne de longueur \(n\equiv i \mod 2\) entre \(s_0\) et \(t_1\text{,}\) ainsi qu’une chaîne de longueur \(m\equiv i \mod 2\text{.}\) Encore par l’exercice 7.3.5.2, il existe un cycle de longueur \(n+m+1\equiv i+i+1\mod 2 \equiv 1 \mod 2\text{,}\) c’est-à-dire qu’il existe un cycle de longueur impaire, ce qui est en contradiction avec notre hypothèse.
🔗
🔗
🔗

5.

Soit \(G=(S,A)\) un graphe simple connexe tel que \(S=S_1\cup S_2\text{,}\) \(S_1\cap S_2=\emptyset\text{,}\) \(s_1\in S_1\) et \(s_2\in S_2\text{.}\) Montrer qu’il existe \(u_1\in S_1\) et \(u_2\in S_2\) tels que \(\{u_1,u_2\}\) est une arête de \(G\text{,}\) c’est-à-dire que \(\{u_1,u_2\}\in A\text{.}\)
🔗
🔗

6.

Soit \(G, H\) deux graphes simples tels qu’il existe un isomorphisme \(f\) entre eux, c’est-à-dire que \(G\cong H\text{,}\) montrer que si \(s_0, s_1, \dots, s_n\) est une chaîne de \(G\text{,}\) alors \(f(s_1), f(s_2), \dots, f(s_n)\) est une chaîne de \(H\text{.}\)
🔗
🔗

7.

On veut démontrer la proposition 7.3.5. Soit \(G=(S,A)\) un graphe simple tel que \(|S|\in \N^\ast\text{,}\) on définit \(G_i=(S_i,A_i)\) successivement de la façon suivante.
🔗
On choisit un sommet quelconque \(s_1\in S\text{.}\) On pose \(S_1\) l’ensemble des sommets de \(G\) reliés à \(s_1\) par une chaîne. On pose \(G_1\) comme étant le sous-graphe de \(G\) induit par \(S_1\).
🔗
Supposons maintenant qu’on ait défini les sous-graphes \(G_1=(S_1,A_1)\) jusqu’à \(G_k=(S_k,A_k)\) pour un certain entier positif \(k\text{.}\) Si \(S=\bigcup_{i=1}^k S_i=S_1\cup S_2\cup \cdots \cup S_k\text{,}\) alors on a terminé. Sinon, il existe un sommet \(s_{k+1}\in S-\bigl(S_1\cup\cdots \cup S_k \bigr)\text{.}\) On veut définir \(G_{k+1}\) à l’aide de ce sommet.
🔗
On pose \(S_{k+1}\) l’ensemble des sommets qui sont reliés à \(s_{k+1}\) par une chaîne de \(G\text{.}\) Finalement on pose \(G_{k+1}\) le sous-graphe de \(G\) induit par \(S_{k+1}\text{.}\)
🔗
(a)
Montrer que les graphes \(G_i\) obtenus dans le processus précédent sont connexes.
🔗
🔗
(b)
Montrer que si \(i \lt j\text{,}\) et si \(S_i\) et \(S_j\) sont les ensembles obtenus dans le processus précédent, alors \(S_i\cap S_j=\emptyset\text{.}\)
🔗
🔗
(c)
Montrer que le processus précédent se termine en un nombre fini d’étapes, c’est-à-dire qu’il existe un entier positif \(k\) tel que \(S=S_1\cup\cdots \cup S_k\text{.}\)
🔗
🔗
(d)
Vérifier que \(G=G_1\cup \cdot \cup G_k\text{.}\)
🔗
🔗
🔗
🔗
🔗
PrécédentTopSuivant