Retour à la table des matières

Département de mathématiques de l'Université de La Rochelle

 

Chapitre 1 - Graphes eulériens

 

A - Un peu de vocabulaire

Un graphe est un ensemble fini de points A1, , An ainsi qu'un ensemble d'arêtes AiAj. Les arêtes ne sont pas supposées orientées (sinon, on parle de graphe orienté). Des arêtes AiAi sont autorisées (on les appelle des boucles), ainsi que la présence de plusieurs arêtes entre deux mêmes points (on parle alors d'arêtes multiples). Un graphe sans boucle ni arête multiple est appelé graphe simple.

Un point A est aussi appelé sommet. Le degré (ou la valence) d'un sommet est, par définition, égal au nombre d'arêtes qui partent de ce sommet. On fait la convention que, si d'un sommet part une boucle, la contribution de celle-ci au calcul du degré est égale à 2 (le degré se calcule donc, d'une certaine manière, en ``zoomant'' autour du sommet et en regardant combien on voit partir de traits : de cette manière, il est impossible de distinguer une boucle de deux arêtes ordinaires).

Théorème - (lemme des poignées de main)

(a) La somme de tous les degrés est un nombre pair. C'est le double du nombre d'arêtes.

(b) Le nombre de sommets de degré impair est pair.

Démonstration - (a) Dans cette somme, chaque arête est comptée deux fois, une au ``départ'' et une à l'``arrivée'' (y compris les boucles, vu la convention ci-dessus).

(b) Soit N le nombre de sommets de degré impair. Ces degrés valent 2k1+1, , 2kN+1. Les autres valent 2k'1, , 2k'm. La somme des degrés vaut

et cette somme est paire d'après (a) d'où le résultat.

On appelle chemin dans un graphe une suite d'arêtes contigües du graphe (A1A2), (A2A3), (An-2An-1), (An-1An). Lorsque ces arêtes sont deux à deux distinctes, on parle d'un chemin de Jordan, ou chemin simple. On dira, enfin, qu'un graphe G est connexe si, étant donné deux sommets quelconques A et B de G, il existe toujours au moins un chemin dans G ayant A pour origine et B pour extrémité.

Remarque -  Lorsqu'un graphe n'est pas simple, un chemin peut passer plusieurs fois de A à B, en utilisant les diverses arêtes qui relient A à B, tout en étant un chemin de Jordan.

Remarque -  Même lorsqu'un graphe est simple, rien n'interdit à un chemin de Jordan de passer plusieurs fois par le même sommet, du moment qu'il emprunte, lors de ces divers passages, des arêtes toujours distinctes.

Lorsque A1 = An (origine = extrémité), on dit que le chemin est un lacet (lacet de Jordan si le chemin est de Jordan).

Définition - On dit qu'un graphe est :

(a) eulérien s'il existe un lacet de Jordan contenant toutes les arêtes du graphe.

(b) semi-eulérien s'il existe un chemin de Jordan contenant toutes les arêtes du graphe (mais pas de lacet).

En d'autres termes, un graphe est eulérien lorsqu'il est possible de parcourir avec un crayon toutes ses arêtes sans lever le crayon et sans jamais passer deux fois sur la même arête.