Introduction à la théorie des graphes/Quelques problèmes célèbres
Les ponts de Königsberg
modifierLe problème des ponts de Königsberg est considéré historiquement comme le premier problème ayant permis de poser les bases de la théorie des graphes.
La question posée à Euler était la suivante :
- La ville de Königsberg, traversée par la rivière Prégolya, possède deux îles et sept ponts. Est-il possible de faire une promenade dans cette ville, en passant une unique fois sur chacun de ses ponts et en revenant à son point de départ à la fin de la promenade ?
La réponse est non.
Et c’est Euler qui en fit la preuve, et qui proposa même une généralisation de ce problème.
Une chaîne eulerienne d'un graphe est une chaîne qui passe une fois et une seule par chaque arête du graphe.
Un cycle eulerien d'un graphe est une chaîne eulerienne fermée.
On parle de graphe eulérien si un graphe contient un cycle eulérien.
Par définition, un stable est toujours eulérien. En effet, un cycle vide parcourt bien toutes les arêtes d'un graphe qui n'en a aucune.
Un graphe connexe admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair.
Si le graphe possède 0 ou 1 sommet, la preuve est triviale. Nous supposerons donc que le graphe possède au moins deux sommets. Dans ce cas et comme le graphe est connexe, nous remarquerons que chaque sommet est de degré au moins 1.
Si le graphe connexe est eulérien, alors en chaque sommet le cycle eulérien « entrant » dans le sommet doit « ressortir » et, comme les arêtes du cycle ne peuvent être utilisées qu'une fois, chaque sommet est de degré pair.
Si tous les sommets du graphe G connexe sont de degré pair et supposons que le graphe ne soit pas eulérien : comme le degré de chaque sommet est au moins 2, il existe un cycle non vide dans le graphe. Considérons un cycle C de longueur maximale (cycle ayant le plus d'arêtes possibles) du graphe, ce cycle ne peut pas être eulérien car le graphe ne l'est pas. Donc le graphe G'=G-E(C) (le graphe partiel de G où on a enlevé les arêtes du cycle C) possède au moins une arête. De plus, comme les sommets de C et de G sont tous de degré pair, les sommets de G' sont tous de degré pair. Comme précédemment, il existe donc un cycle C' non vide dans G', et comme G est connexe, on peut choisir C' tel qu’il ait un sommet en commun avec C. Donc est un cycle de G. Il y a donc contradiction sur la maximalité de C, et donc G est eulérien.
Problème du Voyageur de Commerce (PVC)
modifierLe problème du voyageur de commerce est le suivant :
- Un voyageur de commerce doit faire sa tournée en passant par une liste de villes prédéterminées, et il aimerait que son voyage soit le plus court possible.
Nous n'étudierons pas dans ce chapitre l'optimalité de la solution (nous ne chercherons pas le trajet le plus court), mais nous nous intéresserons plutôt à l’existence d'un itinéraire qui permettrait au voyageur de parcourir toutes les villes une seule fois et bien sûr de revenir à son domicile à la fin de son périple.
Nous pouvons représenter ce problème par un graphe, dont les sommets sont les villes à visiter et le domicile du voyageur, et les arêtes sont les routes reliant les villes entre elles.
Le problème devient donc :
- Existe-t-il un cycle parcourant tous les sommets du graphe une seule fois ?
Voici la définition d'un tel cycle :
Un cycle hamiltonien d'un graphe est un cycle parcourant une unique fois chaque sommet du graphe.
Un graphe hamiltonien est un graphe qui possède un tel cycle.
Voir aussi
modifier
