Avec les graphes eulériens on pourra trouver des chemins qui passent pour tous les sommets ou toutes les arêtes de la façon la plus convenable, lesquelles est souvent la plus courte. 

Le problème des sept ponts de Konigsberg se considère les origins de la théorie de graphes et ce probleme etait resolu avec des graphes eulériens, donc on va l’examiner pour comprendre ce qu' Euler avait fait pour resoudre ce probleme et donc comprendre les graphes eulériens. 

 

1. Les sept ponts de Königsberg 

 

                        

​

​

​

​

​

​

​

Ce problème marque le début et l’apparition de la théorie de Graphes. L’antique cité de Königsberg, appelée aujourd’hui Kaliningrad, était située à la Prusse Oriental. Le fleuve Pregolia traversait la cité et divisait le territoire en diverses zones et c’est pour cela qu’il y avait des ponts pour avoir une bonne communication. Plus concrètement il y avait sept ponts, d’ici le nom du problème. À force de cela, les citoyens se sont formulé une question comme jeu laquelle c’était :  

“Est-ce qu’on peut traverser tous les ponts en passant seulement une fois pour chacun?" 

 

C'est-à-dire, ils se sont demandés s'il existait un circuit dans le graphe G qui contient toutes les arêtes. 

Après beaucoup d’essais pour résoudre l’énigme, les citoyens sont arrivés à la conclusion que c’était impossible. Néanmoins cette explication n’était pas suffisante pour les mathématiciens et c’est alors que Leonhard Euler a proposé une résolution au problème. Il a mis en place la théorie des chemins eulériens pour résoudre cette question qui était formulée. 

Ce qu’il a fait premièrement c’était simplifier la carte avec une représentation que maintenant on appelle graphe : 

 

Le résultat de représenter la ville avec les ponts en forme de graphe est un multigraphe, donc pour obtenir un graphe simple il a mis des sommets à la moitié de chaque arête. 

 

​

​

​

​

​

​

Avant de continuer il faut définir quelques concepts: 

• Chemin eulérien: c’est un chemin qui contient toutes les arêtes d’un graphe G, et chacune apparaît seulement une fois. 

• Circuit eulérien: c’est un circuit qui contient toutes les arêtes d’un graphe G. Comme on l'avait déjà vu, les circuits sont des chemins fermés qui ne répètent pas d' arêtes. 

• Graphe eulérien: c’est un graphe qui admet un circuit eulérien. 

 

Cela s’applique seulement aux graphes connexes. Sinon on peut l’appliquer aux parties connexes dans un graphe qui ne le soit pas.

 

Dans ce cas, les sommets sont les zones qui étaient divisées et les arêtes les ponts. Il a donc résolu le problème en disant que c’était impossible traverser seulement une fois. Il conclut avec cette affirmation après avoir délimité quelques propositions à accomplir pour qu’un graphe puisse être eulérien. On va voir quels sont les requisites: 

 

• Proposition 1: un graphe G est eulérien si tous ses sommets sont de degré pair. 

• Proposition 2: un graphe G, aura un chemin eulérien si tous ses sommets sont de degré pair ou exactement deux de ses sommets sont de degré impair. 

 

Si on reprend l’exemple des sept ponts on peut voir que les degrés des sommets sont: 

grA=5  grB=3  grC=3  grD=3  grE=2  grF=2  grG=2  grH=2  grI=2  grJ=2  grK=2 

 

On peut voir que 4 de ses sommets ont un degré impair donc le graphe n’est pas eulérien, et alors les citoyens de Konigsberg avaient raison, il c'était impossible de traverser pour tous les ponts sans passer deux fois par le même. 

Maintenant, après avoir vu cet exemple qui est le plus connu, on va étudier la façon de trouver des chemins eulériens.