Graphe eulérien
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche à compléter concernant les mathématiques, vous pouvez partager vos connaissances en le modifiant. |
En théorie des graphes, un graphe eulérien est un graphe non orienté tel qu'il peut être parcouru de telle manière de passer une et une seule fois par chaque arête. Un tel parcours s'appelle un cycle eulérien. Bien que la question de l'existence de cycles eulériens a pu être posée à plusieurs occasion, cette propriété a été formalisée par Leonhard Euler en 1736. La question de caractériser les graphes eulériens a été résolue vers 1840 par Hierholzer.
Sommaire |
[modifier] Formulation
Un graphe est la donnée d'un ensemble (supposé fini) S dont les éléments sont appelés les sommets, et d'un ensemble A de parties à deux éléments de S, appelées arêtes[1]. Un cycle de S est une énumération finie x1, ..., xn d'éléments de S telle que les parties {x1,x2}, ..., {xn-1,xn}, et {xn,x1}, soient des arêtes. Lorsque toutes les arêtes sont obtenues une et une seule fois, le cycle est dit eulérien.
Lorsqu'il existe au moins un cycle eulérien, le graphe (S,A) est dit eulérien. Il se peut qu'un graphe eulérien possède plusieurs cycles eulériens.
Pour un sommet s, on appelle degré de s le nombre d'arêtes ayant pour extrémité s, ou, dit autrement, le nombre d'arêtes auquel s appartient. D'après un théorème de Hierholzer, un graphe est eulérien ssi il ne possède que des sommets de degré pair.
[modifier] Histoire
[modifier] Motivations
[modifier] Sept ponts de Königsberg
Voir l’article problème des sept ponts de Königsberg.Le problème des sept ponts de Königsberg est un problème mathématique historique, qui fit la célébrité de la ville de Königsberg (aujourd'hui Kaliningrad). Sa résolution fut recherchée par ses habitants tout au long du XVIIIe siècle.
Le problème est le suivant :
- Étant donné que la ville est construite sur deux îles reliées au continent par six ponts, et entre elles par un pont, trouver un chemin quelconque permettant, à partir d'un point de départ au choix, de passer une et une seule fois par chaque pont, et de revenir à son point de départ, étant entendu qu'on ne peut traverser l'eau qu'en passant par les ponts.
[modifier] La preuve de Hierholzer
[modifier] Applications
[modifier] Voir aussi
[modifier] Références
[modifier] Notes et références
|
Portail des mathématiques – Accédez aux articles de Wikipédia concernant les mathématiques. |
