Cours : Théorie des Graphes

Resp. Cours : Dr. Salma Elaoud

Filière : 2ème année LFInf - SI
Année Univ. : 2018 - 2019

Chapitre 4
Parcours sur un graphe

Introduction

Le problème des ponts de Königsberg est considéré comme le premier problème historique utilisant
explicitement les graphes.

L’histoire raconte que les habitants de Königsberg en Prusse

(maintenant Kaliningrad en Russie) souhaitaient savoir s’il
existait un moyen de partir de chez soi, emprunter tous les
7 ponts, une et une seule fois, et revenir dans sa demeure.

Leonhard Euler, montra que c’était impossible et fut amené pour cela à introduire les premiers rudi-
ments de théorie des graphes, dont celle de cycle eulérien qui va être définie à la suite.

1
 Chapitre 4. Parcours sur un graphe

1. Graphes eulériens
1.1. Chaı̂ne eulérienne, cycle eulérien

Soit G un graphe non orienté.

Définition
On appelle chaı̂ne eulérienne une chaı̂ne passant une et une seule fois par chacune des arêtes de G.

Remarque
On peut donc passer plusieurs fois par le même sommet, mais pas par la même arête.

Exemple
Dans le graphe suivant, la chaı̂ne 4 − 3 − 2 − 4 − 5 − 1 − 2
est une chaı̂ne eulérienne.

Définition
On appelle cycle eulérien un cycle passant une et une seule fois par chacune des arêtes de G.

Exemple
Dans le graphe suivant, le cycle 1 − 2 − 3 − 4 − 5
est un cycle eulérien.

Bien sûr, une chaı̂ne eulérienne ou un cycle eulérien ne peuvent exister que sur un graphe connexe.

Définitions
• un graphe est dit eulérien s’il possède un cycle eulérien.
• Un graphe ne possédant que des chaı̂nes eulériennes est semi-eulérien.

Plus simplement, on peut dire qu’un graphe est eulérien (ou semi-eulérien) s’il est possible de des-
siner le graphe sans lever le crayon et sans passer deux fois sur la même arête.

Exemple
Est-il possible de tracer les figures suivantes sans lever le crayon (et sans passer deux fois sur le même
trait !) ? Pourquoi ?

2
 Chapitre 4. Parcours sur un graphe

Question : Comment savoir si un graphe est eulérien ou non ?

Supposons qu’un graphe G admette un cycle eulérien.

Chaque fois que ce cycle passe par un sommet, il contribue pour 2 dans le degré de ce sommet.
Par conséquent, chaque sommet doit avoir un degré pair.

On retrouve ces différentes notions sur les graphes orientés :

Définitions
• On appelle chemin eulérien d’un graphe orienté G un chemin passant une et une seule fois par
chaque arc de G.
• On appelle circuit eulérien d’un graphe orienté G un circuit passant une et une seule fois par
chaque arc de G.

Remarque
L’existence d’un circuit eulérien dépend alors des demi-degrés extérieurs et intérieurs des différents
sommets : pour chaque sommet il doit y avoir autant d’arcs qui y arrivent que d’arcs qui en partent.

1.2. Théorème d’Euler

Euler a donné une caractérisation très forte des graphes eulériens :

Théorème . Euler - 1741

Soit G = (S, A) un graphe connexe alors :
• Si G est non orienté, alors G est eulérien si et seulement si tout sommet est de degré pair.

∀x ∈ S, ∃k ∈ N, d(x) = 2k

• Si G est orienté alors G est eulérien si et seulement si pour tout sommet le degré sortant est égal
au degré entrant.
∀x ∈ S, d+ (x) = d− (x)

Remarque
Ce théorème donne donc deux conditions nécessaires et suffisantes pour qu’un graphe soit eulérien.

Remarque
La connexité suffit pour étendre le cas non orienté au cas orienté, et un graphe eulérien est nécessai-
rement fortement connexe.

3
 Chapitre 4. Parcours sur un graphe

Application
Un camion de ramassage des ordures part du dépôt représenté en noir ci-dessous et doit passer sur
chaque route du réseau ci-dessous pour effectuer la collecte des déchets.
Comment doit-il s’y prendre ?

On cherche ici un cycle eulérien.

Exercice
Trouver tous les graphes simples eulériens d’ordre 5, à isomorphisme près.

Exercice
Quels sont les graphes complets Kn qui admettent un cycle eulérien ?

Problème des sept ponts de Königsberg

On peut alors représenter notre problème par un graphe avec 4 sommets,
où chaque arête représente l’un des 7 ponts de Koenigsberg.
Sur cet exemple le graphe n’est pas un graphe simple.

Résoudre le problème revient à trouver un cycle eulérien.

Avec caractérisation d’Euler, les sommets A, B, C et D étant de degré impair, on sait immédiate-
ment qu’il est imposible de parcourir tous les ponts de Kônigsberg seulement une fois au cours d’une
promenade.

Exercice
Soit G un graphe non eulérien.
Est-il toujours possible de rendre G eulérien en lui rajoutant un sommet et quelques arêtes ?

Problème des neuf ponts de Kaliningrad

À Kaliningrad, il y a aujourd’hui deux ponts de plus que les sept qui ont été construits au XVIIIème
siècle. Ces deux nouveaux ponts font la jonction respectivement entre les régions B et C et les régions
B et D.
Est-il possible à un promeneur de traverser les neuf ponts de Kaliningrad une fois seulement dans une
promenade ?

4
 Chapitre 4. Parcours sur un graphe

Théorème .
• Un graphe non orienté connexe possède une chaı̂ne eulérienne si et seulement si le nombre de ses
sommets de degré impair est 0 ou 2.
• Un graphe orienté connexe possède un chemin eulérien (mais pas de circuit eulérien) si et seulement
si, pour tout sommet sauf deux a et b, le degré entrant est égal au degré sortant et

d+ (a) = d− (a) + 1 d+ (b) = d− (b) − 1

Remarque
Si le graphe possède exactement deux sommets de degré impair alors toute chaı̂ne eulérienne commence
en un de ces sommets et se termine à l’autre.

Exercice
Un facteur désire faire sa tournée sans passer deux fois dans la même rue.

Est-ce possible si sa tournée a les profils suivants

(où chaque rue est représentée par une arête) :

Application
Est-il possible de dessiner cette maison sans lever le crayon,
et bien sûr sans repasser par le même trait ?

1.3. Algorithme d’Euler

L’algorithme d’Euler permet de trouver explicitement, lorsque cela est possible, une chaı̂ne eulérienne
dans un graphe.

Algorithme d’Euler
Etape 1.
• S’il y a exactement deux sommets de degré impair,
on construit une chaı̂ne quelconque joignant ces deux sommets.
• Si tous les sommets sont de degré pair,
on construit un cycle à partir d’un sommet.
Dans les deux cas, on marque toutes les arêtes utilisées.
Si toutes les arêtes sont marquées, la chaı̂ne est eulérienne.
Sinon on passe à l’étape 2.

5
 Chapitre 4. Parcours sur un graphe

Etape 2.
On insère dans cette chaı̂ne, un cycle (une chaı̂ne fermée) ayant pour origine
l’un des sommets déja utilisés, ne contenant pas deux fois la même
arête et ne contenant acune arête déja parcourue.
Les arêtes utilisées sont marquées.
L’insertion consiste à remplacer un sommet x par une cahı̂ne x . . . x.
Etape 3.
S’il reste des arêtes non marquées, revenir à l’étape 2.

Remarque
Pour un cycle eulérien, il suffit de suivre la même méthode en partant à l’étape 1 d’un cycle à partir
d’un des sommets quelconque du graphe.

Détermination pratique d’une chaı̂ne eulérienne

On considère le graphe de la maison.

Il a seulement deux sommets de degré impair :

le sommet a et le sommet b.
Il existe donc une chaı̂ne eulérienne entre les sommets a et b.
Pour la déterminer, on suit les étapes suivantes :

cycle chaı̂ne eulérienne

Etpae 1 ab
Etpae 2
Etpae 3
Etpae 4
Etpae 5
..
.

Remarque
Cet algorithme ne conduit pas à une solution unique : le choix de la chaı̂ne de départ et des chaı̂nes
fermées est arbitraire.

6
 Chapitre 4. Parcours sur un graphe

Exercice
Si le graphe ci dessous admet une chaı̂ne ou un cycle Eulérien donner la ou donner le en appliquant
l’algorithme d’Euler.

cycle chaı̂ne eulérienne

Etpae 1
Etpae 2
Etpae 3
Etpae 4
Etpae 5
Etpae 6

Exercice
Est-il possible de dessiner sans lever la main
un lacet qui traverse chaque arête de ce graphe
planaire une et une seule fois ?

Solution
On considère le graphe dual qui associe
un sommet à chaque face,
et une arête à chaque arête du graphe initial.

Traverser l’ensemble des arêtes du graphe initial revient alors à trouver . . .

7
 Chapitre 4. Parcours sur un graphe

2. Graphes hamiltoniens
Un autre problème d’importance pour la théorie des graphes est dû à Sir Hamilton.
En 1859, il inventa le casse-tête « Tour du monde » qui consiste en un dodécaèdre
en bois (un polyèdre à 12 faces en forme de pentagone régulier et 20 sommets).

Trois arêtes sont donc issues de chaque sommet. Un clou est fiché sur chaque sommet marque du nom
de vingt grandes villes mondiales. Le casse-tête consiste à enrouler une ficelle passant une fois et une
seule fois par chacune des villes (sommets), puis revenir à son point de départ.

On considère la question équivalente suivante :

existe-t-il un cycle dans le graphe planaire du dodécaèdre
qui passe par tous les sommets une fois seulement ?

La réponse est positive :

Bien que la solution de ce problème soit aisée à obtenir, personne n’a encore trouvé de condition
nécessaire et suffisante de l’existence d’un tel chemin (appelé cycle hamiltonienne) dans un graphe
quelconque.

2.1. Chaı̂ne hamiltonienne, cycle hamiltonien

Soit G = (S, A) un graphe connexe d’ordre n.

Définitions
• On appelle chaı̂ne hamiltonienne/chemin hamiltonien du graphe G une chaı̂ne/chemin passant
une et une seule fois par chacun des sommets de G.
• On appelle cycle hamiltonien/circuit hamiltonien d’un graphe G un cycle/circuit passant une
et une seule fois par chacun des sommets de G.

Exemples
• chaı̂ne hamiltonienne : d − e − c − b − a
• cycle hamiltonien : d − e − b − a − c − d

Remarque
Dans un graphe connexe d’ordre n, une chaı̂ne hamiltonienne est donc une chaı̂ne élémentaire de
longueur n − 1.

8
 Chapitre 4. Parcours sur un graphe

Définitions
• Un graphe est dit hamiltonien s’il possède un cycle/circuit hamiltonien.
• Un graphe ne possédant que des chaı̂nes hamiltoniennes/chemins hamiltoniens est semi-hamiltonien.

Exemples

Graphe non-hamiltonien Graphe semi-hamiltonien Graphe hamiltonien

Exercice
Les graphes complets Kn sont-ils hamiltoniens ?

Application
Un voyageur de commerce part tous les matins de son domicile représenté en noir cidessous et doit
rendre visite à un ensemble de clients représentés en blanc, puis retourner à son domicile. Comment
doit-il s’y prendre pour minimiser la distance totale parcourue. (On suppose que les distances entre
toutes les paires de clients ainsi qu’entre les clients et le domicile du voyageur de commerce sont
connues).

On cherche ici un cycle hamiltonien

de longueur minimale.

Lorsque le point d’arrivée est différent du point de départ, le problème revient à rechercher une chaı̂ne
hamiltonienne de longueur totale minimale.

Autre application
Un autre problème classique concerne l’ordonancement de tâches.
On cherche un ordre dans lequel on peut effectuer n tâches données (deux tâches quelconques ne pou-
vant être effectuées simultanément) tout en respectant un certain nombre de contraintes d’antériorité.
Si l’on construit le graphe G dont l’ensemble des sommets correspond à l’ensemble des tâches, et où il
existe un arc (i, j) si la tâche i peut être effectuée avant la tâche j, le problème revient à déterminer
un chemin hamiltonien de G.

Dans beaucoup d’autres situations, on cherche un chemin hamiltonien dans un graphe qui minimise
une autre fonction économique que la longueur totale du chemin.

9
 Chapitre 4. Parcours sur un graphe

Le parcours du cavalier sur un échiquier

On s’intéresse au parcours d’un cavalier sur un échiquier 8 × 8.
Sur l’échiquier, le cavalier se déplace de deux cases dans une direction
(horizontale ou verticale) puis d’une case dans une direction orthogonale.
Est-il possible qu’un cavalier passe par toutes les cases de l’échiquier
sans passer deux fois par la même case et revenir à son point de départ ?
Il s’agit encore de la recherche d’un cycle hamiltonien.
On peut considérer un graphe dont les sommets représentent les cases de l’échiquier et une arête joint
deux sommets si et seulement si un cavalier peut passer de l’une des cases correspondantes à la suivante
en un mouvement. (Ainsi, le degré de chaque sommet varie entre 2 et 8). A vous de jouer !

2.2. Critères et Théorèmes

Il n’existe pas de critères précis pour déterminer un graphe hamiltonien, contrairement aux graphes
eulériens. Il existe tout de même quelques propriétés et conditions.

Cependant, les conditions ne sont que suffisantes et non pas nécessaires. Nous pouvons donc, grâce à
cela, affirmer qu’un graphe est hamiltonien s’il répond à l’une des conditions mais il faut aussi savoir
qu’un graphe ne répondant pas aux conditions, peut tout de même être hamiltonien.

Propriété 1
Un graphe possédant un sommet de degré 1 ne peut être hamiltonien.

En effet,
On ne peut pas trouver un cycle passant une et une seule fois par chaque sommet.

Exemple
Dans ce graphe, le sommet 6 est de degré 1.
On peut en partir, mais sans pouvoir y revenir.
Ou à l’inverse, y arriver, sans pouvoir en repartir.

Propriété 2
Si un sommet dans un graphe est de degré 2, alors, les deux arêtes incidentes à ce sommet doivent
faire partie du cycle hamiltonien.

En effet,
Au sommet de degré 2, arrivent deux arêtes. Si on veut passer par ce sommet, il est donc nécessaire
d’emprunter une arête incidente pour l’atteindre et d’emprunter la seconde pour le quitter.

10
 Chapitre 4. Parcours sur un graphe

Exemple
Le sommet 1 est de degré 2.
Le cycle hamiltonien comprend donc les arêtes (5,1) et (1,2).

Propriété 3
Les graphes complets Kn , n ≥ 3 sont hamiltoniens.

En effet,
Puisque dans un graphe complet, les sommets sont reliés entre eux, il existera toujours un moyen de
passer d’un sommet à un autre sans repasser par un sommet déjà atteint.

Exemple
Ici, un graphe de type K5 .
Ce graphe est hamiltonien.
Un cycle hamiltonien parmi d’autres : 1 − 2 − 3 − 4 − 5.

Remarque
Ce critère est suffisant mais pas nécessaire puisqu’un graphe non complet peut être hamiltonien.

Exemple
Ce graphe n’est pas complet mais il est hamiltonien.

Propriété 4
Les graphes bipartis complets Kn,m sont hamiltoniens si et seulement si n > 1 et m = n.

En effet,
Kn,m est toujours un graphe connexe. L’ensemble des sommets de Kn,m est la réunion disjointe de
deux ensembles A et B tels que Card(A) = n, Card(B) = m, tout sommet de A est relié à tout
sommet de B et ce sont les seules arêtes de Kn,m
Un cycle élémentaire de Kn,m contient autant de sommets de A et de sommets de B.
Donc, si Kn,m contient un cycle hamiltonien, on doit avoir n = m.
- Pour n = m = 1, K1,1 ne possède pas de cycle, il ne peut être hamiltonien.
- Supposons que n > 1 et que m = n.
On numérote de 1 à n les sommets de A et de n + 1 à 2n les sommets de B.
Alors, le cycle (1, n + 1, 2, n + 2, . . . , n, 2n, 1) est un cycle hamiltonien de Kn,m .

Exercice
Donner les valeurs de n et de m pour lesquelles le graphe biparti complet Kn,m est eulérien.

11
 Chapitre 4. Parcours sur un graphe

On dispose néanmoins d’un certain nombre de critères, de plus en plus généraux, qui permettent
d’assurer que tel ou tel graphe est hamiltonien. C’est Gabriel Andrew Dirac qui ouvre le bal en 1952,
avec l’idée intuitive qu’un graphe est forcément hamiltonien lorsqu’il possède « suffisamment d’arêtes».

Théorème . (Dirac)
Soit G un graphe simple et non orienté d’ordre n ≥ 3.
n
Si pour tout sommet x de G, on a d(x) ≥ , alors G est hamiltonien.
2

Exemple
Les graphes bipartis complets Kn,n , n ≥ 2, sont hamiltoniens.

Ce théorème est dû à Oystein Ore, en 1960. Il s’énonce comme suit :

Théorème . (Ore)
Soit G un graphe simple et non orienté d’ordre n ≥ 3.
Si pour toute paire {x, y} de sommets non adjacents, on a d(x) + d(y) ≥ n, alors G est hamiltonien.

Remarque
Le théorème de Dirac est un cas particulier du théorème de Ore.
n
En effet, si chaque sommet est de degré au moins , alors la somme des degrés de n’importe quelle
2
paire de sommets, adjacents ou pas, est au moins n.

Remarque
Toutes ces conditions sont suffisantes, mais pas nécessaires.

Exemple
Voici un exemple de graphe hamiltonien.
On peut en dégager le cycle 1 - 2 - 3 - 4 - 5.
Pourtant
- il n’est pas complet
- il ne répond pas au critère de Dirac : d(5) = 2 < 5/2.
- il ne répond pas au critère de Ore : d(3) + d(5) = 4 < 5.

Exercice
Lesquels des graphes suivants est hamiltonien ?
Justifier.

12
 Chapitre 4. Parcours sur un graphe

On termine cette section par le résultat suivant présentant un certain intérêt pour le problème du
voyageur de commerce.

Variante le problème du voyageur de commerce.

Supposons disposer de n villes et de connections entre toutes ces villes. On supposera que tous les coûts
de connexion d’une ville à une autre sont identiques (ainsi, toute permutation des n villes fournit une
solution optimale). On est donc en présence du graphe complet Kn .
Le voyageur de commerce désire passer une et une seule fois par chacune des villes et revenir à son
point de départ (le siège de sa compagnie par exemple). Il est clair qu’une permutation quelconque
des n − 1 sommets du graphe (siège de la compagnie exclu) répond à la question. Cependant, on peut
imaginer qu’il ne désire pas repasser par une route déjà empruntée précédemment. De cette manière,
il pourra joindre l’utile à l’agréable en visitant la région de diverses manières. Ainsi, on désire non
seulement construire un circuit hamiltonien mais de plus, on voudrait trouver un nombre maximum
de tels circuits n’ayant aucune arête commune.

Propriété
n
• Si n est pair, alors Kn peut être partitionné en chaı̂nes hamiltoniennes disjointes.
2
n−1
• Si n ≥ 3 est impair, alors Kn peut être partitionné en cycles hamiltoniens disjoints.
2

Exemple
Dans K5 , les cycles 1 - 2 - 3 - 4 - 5 -1 et 1 - 3 - 5 - 2 - 4 -1
n’ont aucune arête commune.

Exercice
Il existe deux autres cycles hamiltoniens disjoints de K5 .
Trouver les.

Exemples
• Une tentative de partition de K7 .

• Chaı̂nes hamiltoniennes de K6 :

• Chaı̂nes hamiltoniennes de K8 :

13
 Chapitre 4. Parcours sur un graphe

Application
Un groupe de 9 élèves se réunit chaque jour autour d’une table ronde.
Combien de jours peuvent-ils se réunir si l’on souhaite que personne n’ait deux fois le même voisin ?
Même question avec 10 élèves, 11 élèves, . . . , n élèves.
Toujours avec 9 élèves, mais cette fois avec 2 tables, l’une de 4 places, l’autre de 5 . . .
Avec trois tables de 3 places ?

Application
Cette fois, ces réunions quotidiennes concernent un groupe de 12 élèves, 6 filles et 6 garçons.
On souhaite toujours que personne n’ait deux fois le même voisin, mais, cette fois, on souhaite égale-
ment que chaque fille soit entourée de deux garçons.
Combien de jours peuvent-ils se réunir ?

14