Mathématiques 2: Géométrie
Les graphes
Euler & Hamilton

1. Euler

Leonhard Euler est un mathématicien, physicien, ingénieur et philosophe. Né à Bâle en suisse, 1707 et décédé à Saint-Pétersbourg en Russie, 1783. Il a vécu en Allemeagne, à Berlin Mais c'est en Russie qu'il a passé la plus grande partie de sa vie.

Euler résidait à Königsberg en Prusse, Kaliningrad en Russie actuelle. En en 1736, il a prouvé dans un article, qu'il était impossible de trouver un chemin qui traverserait une et une seule fois chacun des sept ponts de cette ville.

Ce problème est connu sous le nom du problème des sept ponts de Königsberg. souvent, on le trouve sous cette forme:

Partant d'un point de la ville, peut-on se promener, en revenant à son point de départ, en passant une seule fois par tous les ponts ?


Pour résoudre ce problème, Euler a construit un graphe dont les sommets sont les différentes régions, et où chaque arête représente un pont. Il s'agit de donc de parcourir le graphe d'un seul trait.

Pour que ce problème soit possible, il faut que tous les sommets de ce graphe soient de degré pair. Ce qui n’est pas le cas car le graphe contient 4 sommets de degré impair.

Euler a démontré , dans le cas général, qu'un graphe ne pouvait être parcouru d'un seul trait s'il avait plus de deux sommets avec des degrés impairs.

On accorde à Leonhard Euler l'origine de la théorie des graphes. Il fut le premier à proposer un traitement mathématique pour résoudre ce genre de proplèmes.

Actuellement, on utilise la thérie des graphes en recherche opérationnelle, une branche des Mathématiques et en reseaux, une application en informatique.

En théorie des graphes, lorsqu'un parcours n'utilise qu'une seule fois la même arête, on dit qu'il est eulérien. C'est le cas du chemin eulérien, circuit eulérien, chaîne eulérienne, cycle eulérien, ou graphe eulérien. L'adjectif eulérien est un hommage à Euler.

2. Hamilton

Le problème similaire à celui de traverser des arêtes exactement une fois, consiste à passer par chaque sommet exactement une fois.

Ce parcours a pris le nom de chemin hamiltonien d'après le mathématicien William Rowan Hamilton.

William Rowan Hamilton est un mathématicien, physicien et astronome irlandais (né et mort à Dublin: 1805 - 1865).

En théorie des graphes, lorsqu'un parcours n'utilise qu'une seule fois le même sommet, on dit qu'il est hamiltonien. C'est le cas du chemin hamiltonien, circuit hamiltonien, chaîne hamiltonienne, cycle hamiltonien, ou graphe hamiltonien.

Si une distance est associée à chaque arête, le problème de la détermination d’un cycle hamiltonien de distance totale minimale s’appelle le problème du voyageur de commerce .