Leçons de niveau 16

Introduction à la théorie des graphes/Quelques problèmes célèbres

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
Début de la boite de navigation du chapitre
Quelques problèmes célèbres
Icône de la faculté
Chapitre no 3
Leçon : Introduction à la théorie des graphes
Chap. préc. :Graphes et sous-graphes
fin de la boite de navigation du chapitre
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Introduction à la théorie des graphes : Quelques problèmes célèbres
Introduction à la théorie des graphes/Quelques problèmes célèbres
 », n'a pu être restituée correctement ci-dessus.


Les ponts de Königsberg[modifier | modifier le wikicode]

Le 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.

Schéma de Königsberg
Graphe représentant Königsberg

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.






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 parcours bien toutes les arêtes d'un graphe qui n'en a aucune.

Début d’un théorème


Fin du théorème


Début d'une démonstration


Fin de la démonstration

Problème du Voyageur de Commerce (PVC)[modifier | modifier le wikicode]

Le 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 sur de revenir à son domicile a 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 :




Voir aussi[modifier | modifier le wikicode]