Université François Rabelais de Tours
Laboratoire de Mathématiques et Physique Théorique
Mathématiques Discrètes et Algorithmique
Mimats
Semestre 9
2. Quelques graphes remarquables
2.1. Graphes bipartis et couplages. Tous les graphes considérés dans cette partie sont simples et
non-orientés.
Définition 2.1. Un graphe G = (V, E) est biparti s’il existe une partition V1 ∪ V2 de V telle que il n’existe
pas d’arête reliant deux sommets de V1 ou deux sommets de V2 .
On vérifie facilement qu’un graphe est biparti si on peut colorier ses sommets avec deux couleurs de telle
manière qu’aucun sommet de même couleur ne soit relié.
Exemple 2.2. Le graphe G est biparti de partition associée {a, b, d} et {c, e, f, g}. Le graphe H n’est pas
biparti.
Figure 1. Graphes G et H.
On désigne par Kn,m = (V, E) le graphe simple tel que :
• V = V1 t V2 , |V1 | = n et |V2 | = m,
• Pour tous (u, v) ∈ V1 × V2 , {u, v} ∈ E.
On a par exemple
Figure 2. Exemples de graphes complets bipartis.
Définition 2.3. Soit G = (V, E) un graphe simple.
• Un couplage C est un sous-ensemble de E tel que pour tout (a, a0 ) ∈ C 2 on a a ∩ a0 = ∅. En d’autres
termes, les sommets de a et a0 sont disjoints.
• Un couplage de X ⊂ V est un couplage C tel que
(a) ∀x ∈ X, ∃a ∈ C, x ∈ a ;
(b) ∀a ∈ C, a ∩ X 6= ∅.
• Un couplage parfait est un couplage de V .
Exemple 2.4. Le graphe de gauche admet un couplage parfait de V1 dans V2 (les arêtes bleues). Pas celui
de droite.
V2
V2
1
2
Théorème 2.5 (Lemme des mariages de Hall). Soit G = (V, E) un graphe biparti de partition associée
V = V1 ∪ V2 . Alors G admet un couplage de V1 si et seulement si
(∗)
∀A ⊂ V1 , |N (A)| ≥ |A|.
Démonstration. Si G possède un couplage de V1 , il est clair que pour tout A ⊂ V1 , on a |N (A)| ≥ |A|
puisque, par définition d’un couplage de V1 , chaque sommet de A est relié à un sommet différent de V2 par
une arête de C.
Supposons maintenant que pour tout A ⊂ V1 on a |N (A)| ≥ |A| et montrons que G possède un couplage
de V1 . On procède par récurrence forte sur le nombre de sommets dans V1 .
Initialisation. Si |V1 | = 1 alors V1 contient exactement 1 sommet v et comme |N (v)| ≥ |V1 | = 1, v est
connecté à au moins un sommet de V2 . Il suffit alors de choisir une arête adjacente à v pour obtenir un
couplage de V1 .
Hypothèse de récurrence. Soit k ≥ 1. Tout graphe biparti G = (V, E) de partition V1 t V2 tel que (1)
|V1 | ≤ k et (2) pour tout A ⊂ V1 on a |N (A)| ≥ |A|, possède un couplage de V1 .
Hérédité. Soit maintenant un graphe biparti G = (V, E) de partition associée V1 t V2 avec |V1 | = k + 1
et tel que pour tout A ⊂ V1 on a |N (A)| ≥ |A|. On veut montrer que G possède un couplage de V1 . On
distingue deux cas :
(a) Pour tout 1 ≤ j ≤ k, tout sous-ensemble A ⊂ V1 tel que |A| = j vérifie N (A) ≥ |A| + 1 = j + 1.
(b) Il existe 1 ≤ j ≤ k et A0 ⊂ V1 tel que |A0 | = j ≤ k et N (A) = j.
(On remarque que ces deux cas couvrent toutes les possibilités puisque (b) est la négation de (a).)
Cas (a). Soit v ∈ V1 et soit w ∈ N (v). On a w ∈ V2 . Soit G0 = (V 0 , E 0 ) le graphe induit par V 0 = V \{v, w}.
On voit que G0 est biparti de partition V10 t V20 où V10 = V1 \{v} et V20 = V2 \{w}. De plus |V10 | = k. Soit
A0 ⊂ V10 , on désigne par NG0 (A0 ) l’ensemble des voisins de A0 dans G0 . On voit facilement que
NG0 (A0 ) ≥ N (A0 ) − 1 ≥ (|A0 | + 1) − 1 = |A0 |
et on peut donc utiliser l’hypothèse de récurrence pour construire un couplage C 0 de V10 . On obtient un
couplage de V en ajoutant l’arête [v, w] à C 0 .
Cas (b). Soit A0 ⊂ V1 telle que |N (A0 )| = |A0 | = j ≤ k. Par hypothèse de récurrence, on peut construire un
couplage CA0 de A0 (dans le graphe induit par A0 ∪ N (A0 )). Soit G0 le graphe induit par V \(A0 ∪ N (A0 )).
On obtient un graphe biparti H de partition associée V10 t V20 ou V10 = V1 \A0 et V20 = V2 \N (A0 ). Montrons
que H satisfait les conditions (1) et (2) de l’hypothèse de récurrence. Pour (1) c’est clair. Si G0 ne satisfait
pas la condition (2), alors il existe un ensemble A à t éléments tel que 1 ≤ t ≤ k + 1 − j et N (A) < t. Mais
alors dans G, l’ensemble A ∪ A0 contiendrait strictement moins de j + t voisins, ce qui est impossible. Ainsi,
G0 satisfait (1) et (2) et par récurrence on peut trouver un couplage C 0 de V10 . On vérifie alors facilement
que C 0 ∪ CA0 est un couplage de V1 , ce qui complète la preuve.
Corollaire 2.6. G admet un couplage parfait si et seulement si
(†)
∀A ⊂ V tel que A ⊂ V1 ou A ⊂ V2 , on a |N (A)| ≥ |A|.
Démonstration. Supposons que G admet un couplage parfait C. Alors, puisque G est biparti on voit que
toute arête dans C a une extrémité dans V1 et l’autre dans V2 . Ainsi, C est à la fois un couplage de V1
et un couplage de V2 . En appliquant (∗) du théorème précédent deux fois, on obtient directement (†).
Réciproquement supposons que G satisfait (†). Alors, d’après (1), on voit que G possède un couplage C1
de V1 et un couplage C2 de V2 . On a à la fois |V1 | = |C1 | ≤ |V2 | et |V2 | = |C2 | ≤ |V1 |. Finalement |V1 | = |V2 |
et C1 et C2 sont en fait des couplages parfaits.
Corollaire 2.7. Soit G = (V, E) un graphe biparti k-régulier de partition V1 ∪ V2 . Alors G admet un
couplage parfait.
Démonstration. Soit X ⊂ V1 tel que |X| = t. Par régularité du graphe, il y a kt arêtes incidentes à un
sommet de X. On note A l’ensemble de ces arêtes. Chacune de ces arêtes est incidente à un sommet de
V2 . On rappelle que
N (X) = {v ∈ V2 | ∃a ∈ A tel que v ∈ a}.
Or le nombres d’arêtes incidentes à N (X) est k|N (X)| ≥ A = kt, d’où |N (X)| ≥ t = |X|.
3
2.2. Graphes et chemins eulériens. Dans cette partie nous ne considèrerons que des graphes nonorientés. Cependant les résultats peuvent s’étendre au cas des graphes orientés.
Soit G = (V, E, N ) un graphe non-orienté. On rappelle que
∗ Une chaîne est simple si elle ne contient pas deux fois la même arête.
∗ Une chaîne est fermée si ses deux extrémités coïncident.
∗ Un cycle est une chaine fermée simple.
Définition 2.8. Soit G = (V, E) un graphe. Une chaîne (resp. cycle) eulérienne de G est une chaîne (resp.
cycle) simple qui passe par toutes les arêtes de G. Un graphe eulérien est un graphe qui possède un cycle
eulérien.
Exemple 2.9. Les ouvrages de théorie des graphes reprennent toujours le célèbre exemple des ponts de
Königsberg. Nous ne dérogerons pas à cette règle. Au XVII-ième siècle, les habitants de Königsberg (actuel
Kaliningrad, ville de Russie proche de la Lituanie et de la Pologne où coule la rivière Pregel) voulaient se
promener le dimanche en passant une et une seule fois par chacun des sept ponts de la ville. Les ponts
étaient disposés comme dans la figure suivante :
Figure 3. Les ponts de Königsberg
Une modélisation du problème revient à considérer un graphe ayant comme sommets, les deux rives et les
deux îles et comme arêtes, les sept ponts. Puisqu’il n’y a aucune contrainte sur le sens de parcours des
ponts, on considère un graphe non orienté :
Figure 4. Modélisation du problème des ponts de Königsberg
La question générale sous-jacente est donc de déterminer pour un graphe donné s’il existe un cycle eulérien.
Lemme 2.10. Soit G = (V, E) un graphe connexe dont tous les sommets sont de degres supérieurs ou
égales à 2. Alors G contient un cycle.
Démonstration. La preuve utilise un algorithme de marquage. Initialement tous les sommets sont non
marqués. Un sommet x1 est marqué arbitrairement. On construit alors une séquence x1 , ..., xk de sommets
marqués en choisissant arbitrairement pour xi+1 un sommet non marqué adjacent à xi . L’algorithme
s’arrête lorsque xk ne possède plus de voisin non marqué. Puisque ce sommet est de degré au moins 2, il
possède, outre xk−1 , un autre voisin xj dans la séquence, j < k − 1. Alors (xk , xj , xj+1 , . . . , xk−1 , xk ) est
un cycle.
Théorème 2.11. Un graphe connexe G = (V, E, N ) d’ordre n est eulérien si et seulement si tous les
degrés de ses sommets sont pairs.
Démonstration. Supposons qu’un graphe G soit eulérien. Il existe alors un cycle c parcourant une et
une seule fois chaque arête. Le graphe G est donc connexe, puisque c relie tous les sommets entre eux.
Considérons un sommet x. Lors du parcours du cycle, à chaque fois qu’une arête est incidente à x, il faut
une autre arête incidente à x pour quitter x. Le sommet x est donc de degré pair.
Réciproquement considérons un graphe G connexe dont tous les sommets de degré pair. Montrons par
récurrence sur le nombre d’arêtes que G est eulérien.
Si G se réduit à un unique sommet isolé, il est évidemment eulérien.
Sinon tous les sommets de G sont de degré supérieur ou égal à 2. Ceci implique qu’il existe un cycle sur
4
G d’après le lemme précédent. Considérons le graphe partiel H constitué des arêtes en dehors du cycle.
Les sommets de H sont également de degré pair, le cycle contenant un nombre pair d’arêtes incidentes
pour chaque sommet. Par induction chaque composante connexe Hi de H est un graphe eulérien, et admet
donc un cycle eulérien . Pour reconstruire un cycle eulérien sur G, il suffit de fusionner le cycle avec les
différents cycles . Pour cela on parcours le cycle depuis un sommet arbitraire ; lorsque l’on rencontre pour
la première fois un sommet x appartenant à Hi , on lui substitue le cycle. Le cycle obtenu est un cycle
eulérien pour G, le cycle et les cycles formant une partition des arêtes.
Figure 5. Construction d’un cycle eulérien
On adapte facilement la preuve pour trouver le corollaire suivant.
Corollaire 2.12. Un graphe connexe possède une chaîne eulérienne joignant deux sommets a et b si et
seulement si a et b sont les deux seuls sommets de degré impair.
2.3. Graphes hamiltoniens. Dans cette section, on s’intéresse à la question (posée initialement par Sir
W. R. Hamilton) de l’existence d’un cycle élémentaire passant par tous les sommet d’un graphe donné.
Etonnamment il n’existe pas de méthode efficace permettant de répondre à cette question. Il est clair qu’il
est suffisant d’étudier les graphes simples.
Définition 2.13. Soit G = (V, E) un graphe simple. Un graphe hamiltonien est un graphe possédant un
cycle élémentaire.
Exemple 2.14. La question orginale de Hamilton était de trouver un chemin “hamiltonien” le long des
arêtes d’un Dodécaèdre. On peut se ramener au problème de trouver un chemin hamiltonien sur un graphe :
On commence par une condition nécessaire pour qu’un graphe soit hamiltonien.
Proposition 2.15. Soit G = (V, E) un graphe (simple et non orienté) hamiltonien. Alors pour tout sousensemble non vide S ⊂ V , le nombre de composantes connexes du graphe induit par V \{S} est inférieur
ou égal à |S|.
Démonstration. Soit S un sous-ensemble non vide de V et u un sommet de S et G0 le graphe induit par
V \{S}. Considérons un cycle hamiltonien C passant par u. On peut voir C comme une suite ordonnée de
sommets (u, w1 , . . . , wn−1 , u). Soient G1 , . . . , Gk , les k composantes connexes de G0 . Si k = 1, le résultat
est trivial. Supposons donc k > 1. Pour i = 1, . . . , k, désignons par ui le dernier sommet de Gi dans le
cycle C et vi , le sommet suivant ui dans ce même cycle.
Montrons que les sommets v1 , . . . , vk appartiennent à S. Raisonnons par l’absurde. Si vi n’appartient pas
à S, il n’est pas supprimé dans le graphe G0 . Les sommets ui et vi sont voisins (en effet, ils sont consécutifs
dans le chemin C). Par conséquent, vi doit appartenir à Gi . Or par définition de ui et de vi , ui est le dernier sommet de Gi dans la suite donnée par C donc vi ne peut pas appartenir à Gi . C’est une contradiction.
On conclut donc que v1 , . . . , vk sont des sommets distincts de S (ils appartiennent à C) et |S| ≥ k.
5
Exemple 2.16. On vérife avec cette proposition que le graphe suivant n’est pas hamiltonien. En effet en
choisissant la partie S composée des sommets encerclés dans le graphe ci-dessous, on obtient 3 composantes
connexes et |S| = 2.
Figure 6. Exemple d’utilisation de la Proposition 2.15
Théorème 2.17 (Dirac). Tout graphe simple G = (V, E) ayant n ≥ 3 sommets et tel que le degré de
chaque sommet est au moins égal à n/2 possède un cycle hamiltonien.
Démonstration. Notons δ = inf v∈V deg(v). Puisque δ ≥ dn/2e, on en conclut que G est connexe. En effet,
si ce n’était pas le cas, G possèderait au moins deux composantes connexes distinctes dont une contient
moins de bn/2c sommets. Or si δ ≥ dn/2e, alors un des sommets de cette composante doit être voisin d’un
sommet d’une autre composante, ce qui est impossible.
Soit C une chaîne élémentaire de longueur maximale. Puisque G est simple, C est entièrement définie par
une suite de sommets x0 , . . . , xk . Par maximalité, tous les voisins de x0 et de xk appartiennent à C (en
effet, sinon, on pourrait étendre C en une chaîne plus longue). Par conséquent, au moins dn/2e sommets
parmi x0 , . . . , xk−1 sont voisins de xk et au moins dn/2e sommets parmi x1 , . . . , xk sont voisins de x0 . De
plus, k + 1 ≤ n. On pose
I := {i | (x0 , xi+1 ) ∈ E}
et
J := {i | (xi , xk ) ∈ E}.
On a I, J ⊂ {0, . . . , k − 1} et |I|, |J| ≥ dn/2e. Ainsi, I et J ne peuvent être disjoint et il existe un indice
i < k tel que (x0 , xi+1 ) ∈ E et (xi , xk ) ∈ E.
Ainsi, le cycle x0 , x1 , . . . , xi , xk , xk−1 , . . . , xi+1 , x0 est un cycle passant une seule fois par chacun des sommets x0 , . . . , xk :
Figure 7. Construction d’un cycle hamiltonien
Montrons que c’est un cycle hamiltonien. En effet, supposons qu’il existe un sommet y n’appartenant pas
à ce cycle. Puisque G est connexe, il existe j ∈ {0, ..., k} tel que (xj , y) ∈ E. De là, on peut construire un
chemin passant par k + 2 sommets distincts. C’est impossible vu le choix de C (de longueur maximale). Le théorème suivant sera l’objet d’un exercice dans le Td 3.
Théorème 2.18 (Ore). Tout graphe simple G = (V, E) ayant n ≥ 3 sommets et tel que le deg(u)+deg(v) ≥
n pour toute paire de sommets non adjacents possède un cycle hamiltonien.
© Copyright 2024 ExpyDoc
