Circuits eulériens

Sept ponts enjambent Königsberg (fig1) reliant quatre quartiers de l a ville ,les habitants se demandent s’il existe un t rajet leur permettant d’emprunter une seule fois tous les ponts. Euler modélise le problème (fig2) et œuvre ainsi une théorie en 1736. figure 1 figure 2 Les quartiers sont les sommets du gr aphe , les ponts les arêtes .on a quat re sommets de degré 3 et l’ordre du graphe est de 4. Le problème posé induit deux questions : – Existe t ‘il un trajet partant d’un point donné, passant par toutes les arêtes (arcs)une et une seule fois dans un même sens (chemin eulérien). – Existe –t ’ il un chemin eulérien revenant au point de parte (circuit eulérien) La réponse a été fournit en 1736 par le mathématicien Euler à travers le théorème 2.1, qui suffit pour détecter un chemin ou circuit eulérien dans un graphe. Définition 1.1. Une chaîne d’un graphe orienté G=(S,A) est une séquence d’arcs : {a1 , a2 , a3 ,…, an} ; ai ∈A ∀ i=1,2,…., n; telle que c haque arc ai ait une ex trémité commune avec l’arc précédent ai-1.Le premier arc a1 est l’arc initial tandis que le dernier arc an est le final.

Théorèmes de caractérisation de circuit Eulérien.

Théorème 2.1. Soit G : (A,S) un graphe à n s ommets, alors G admet un chemin eulérien si et seulement si G est connexe et possède 2 sommets de degrés impaire ; ou alors admet un c ircuit eulérien si G est connexe et possède 0 s ommet degré impair. Preuve. Nous montrons la première implication (⇒) Comme G est eulérien, il contient un chemin Ne passant une seule fois par tous les arcs (arêtes) et au m oins une fois par tous les sommets. En conséquences, il est connexe. Dans ce chemin Ne, tout sommet intermédiaire est de degr é impaire pour chaque passage au niveau d’un tel sommet implique 2 arcs, l’aller et le retour. Les sommets intermédiaires sont de degré paire. Les extrémités initiale et finale du chemin Ne sont de degré 0. Le chemin est un circuit et de degré impaire si le chemin est non fermé. Pour montrer l’implication (⇐) nous raisonnons par induction : pour n=2, le cas est trivial. Les deux sommets sont de degré impaire . pour n =3 ,soit G est un triangle donc tous les sommets degré 2. Et soit G possède deux arcs avec deux sommets de degré impaire Supposons l’hypothèse d’ induction vraie pour tout graphe n-1 sommets ,et démontrons la pour n sommets . Soit vo un sommet du graphe G qui un des deux sommets de degré impaire si G en possède Considérons tous les ares allant de{vo} à S -{vo}et un c hemin c ontenant tous ces arcs . Ce chemin existe car G est connexe. Le chemin es t un c ircuit si vo et degré pair .Enlevons ce chemin No du graphe ; le graphe résultant Go est connexe et possède 0 ou 2 s ommets de degré impaire. Il satisfait l’hypothèse d’induction car possède moins de n -1 sommets.En conséquence ; Go possède un c hemin eulerien .Il suffit d’y adjoindre le chemin No pour obtenir un chemin eurelien de G.Ce chemin est un circuit s’il est ferme et possède 0 sommet de degré impaire.

Liens entre cycles Hamiltoniens et Eulériens

Définition 4.1. Soit G = (S,A) un gr aphe non orienté, on appelle graphe ligne de G noté par L(G) un gr aphe dont les sommets correspondent un à un av ec des arêtes de G. Exemple 4.1. G1 L(G1) G2 L( G 2) Proposition 4.1. Soit G est eulérien alors L(G) est hamiltonien et eulérien Preuve. Soit G = (S, A) et L (G) = (S’,A’) Si G est eulérien tous ces arêtes sont parcourues une et une seule fois d’où tous les sommets de L(G) sont parcourus une et une seule fois donc L(G) est hamiltonien. ∀ u ∈A ∃ a ,b ∈ S tel que u =(a , b) ∀ u ∈ A ∃ v∈ S ’ et ∀v ∈ S ’ ∃ u ∈ A on a d(v) = d(a) + d(b) G est eulérien donc d(a) =2k (k Є ∈N) ; d(b)=2k’ (k ’Є ∈ N) donc v Є S’ on a d(v) =2 (k+k’) d’où L (G) est eulérien . Remarque .La réciproque de ce théorème est fausse, car dans l’exemple suivant L (G) est eulérien et G ne l’est pas . Exemple4.2. L (G) est eulérien et hamiltonien mais G est non hamiltonien G L(G) .

L’étude des problèmes eulériens ou hamiltoniens remonte aux origines de la théorie des graphes. L’intérêt porté aujourd’hui à c es problèmes s’explique par leurs applications nombreuses comme les tournées de di stribution (« postier chinois », « voyageur de commerce » ), tracet automatique sur l’ordinateur, problèmes d’ordonnances d’ateliers, etc.… Les domaines d’applications seraient plus intéressants dans le chapitre des couplages et des problèmes polynomiaux . On peut dire que cette partie est un outil essentiel, presque indispensable dans la résolution des problèmes en t héorie des graphes . On remarque que la plupart des conditions suffisantes pour qu’un graphe soit hamiltonien f ont i ntervenir les degrés, néanmoins on a c iter d’autres sur le nombre de c onnexité et le nombre de s tabilité .Dans cet mémoire après avoir cité ces dernières nous avons travailler directement s ur les arêtes avec une méthode constructive en fin d’obtenir des propositions nécessaires et suffisants très simples. Ces propositions ouvre une nouvelle méthode appelée << théorie des opposés >> qui ne se limite pas seulement sur la caractérisation oui ou non d’un graphe hamiltonien mais va jusqu’à la détermination du nombre de cycle hamiltonien contenu dans un graphe. Sur les graphes eulérien différemment des graphes hamiltoniens le travail a été bouclé par le père de la théorie des graphes Euler en 1736 en donnant un théorème nécessaire et suffisant. Mais l’algorithme de dét ermination étais trop générale et ne permettais pas d’obtenir rapidement un c ircuit eulérien contenu dans un graphe cause pour laquelle on a proposé dans la mémoire une autre algorithme très facile à manier avec laide des matrices d’incidences. Il reste maintenant à développer cette matière dans l’enseignement général .