Parcours eulériens

Chaînes et cycles eulériens

Dans les années 1730, Leonhard Euler chercha à résoudre un problème pratique. Pouvait-on emprunter les sept ponts de Königsberg (aujourd'hui Kaliningrad) une fois et une seule au cours d'un parcours dans la ville ? Non seulement Euler résolut le problème, mais il jeta les bases d'une toute nouvelle branche des mathématiques, la théorie des graphes.

Étudions deux parcours eulériens. Qu’est-ce ? Il s’agit de propriétés que possèdent certains graphes non orientés. Après avoir compris les définitions et la méthode (très facile), vous pourrez appliquer ce que vous avez appris sur des questions extraites d’épreuves du bac.

Définitions

Une chaîne eulérienne d’un graphe connexe contient une fois et une seule toutes ses arêtes. Si une chaîne eulérienne est fermée (c’est-à-dire qu’elle revient à son point de départ), il s’agit d’un cycle eulérien.

Méthode

Soit un graphe connexe. S’il a deux sommets de degré impair, il admet une chaîne eulérienne (rappelons que le nombre de degrés est le nombre d’arêtes qui partent d'un sommet). Les deux sommets de degré impair sont les extrémités de la chaîne. Si tous les sommets sont de degré pair, il existe alors un cycle eulérien.

Exemple de graphe possédant une chaîne eulérienne

Le graphe en forme de fanion ci-dessous peut être dessiné sans lever le stylo et sans passer deux fois sur le même trait. Intuitivement, on perçoit donc qu’il admet une chaîne eulérienne.

Mais si vous justifiez un résultat par votre intuition, vous risquez d’avoir une note désastreuse. En revanche, vous pouvez constater que le graphe est connexe et que les sommets A et D sont de degré impair. Les autres sont de degré pair. Il s’ensuit qu’il existe une chaîne eulérienne. Par exemple (A ; D ; B ; C ; D). Vous remarquerez que la chaîne passe deux fois sur le même point mais ce n’est pas gênant puisque ce sont les arêtes qu’il faut prendre en compte. Vérifiez que le premier et le dernier sommet sont ceux qui ont un nombre impair de degrés.

Exemple de graphe possédant un cycle eulérien

Exercice 1 (Amérique du nord, mai 2011)

Un site internet comporte 8 pages, notées A, B, C, D, E, F, G, H reliées entre elles suivant le graphe ci-dessous.

Ainsi, par exemple, à partir de la page A on peut directement accéder aux pages B, C et D.

Par contre, la page A ne permet pas d’accéder à la page F.

Le technicien souhaite tester les liens de pages. En partant de la page A, est-il possible de trouver un parcours passant une seule fois par tous les liens de pages ? Justifier la réponse.

Exercice 2 (Polynésie, juin 2014)

Le graphe ci-dessous représente, dans un aéroport donné, toutes les voies empruntées par les avions au roulage. Ces voies, sur lesquelles circulent les avions avant ou après atterrissage, sont appelées taxiways. Les arêtes du graphe représentent les voies de circulation (les taxiways) et les sommets du graphe sont les intersections.

1. Déterminer le nombre de voies de circulation au total.
   
   
2. Afin que l’aéroport soit déneigé le plus rapidement possible, est-il possible de planifier un parcours pour que les chasse-neige passent par toutes les voies sans emprunter plusieurs fois la même route ? Justifier la réponse et donner un tel parcours.
   

Corrigé 1

Déterminons le degré de chaque sommet.

Le graphe est connexe. Cependant, il ne possède pas deux sommets de degré impair pair mais quatre. Il n’admet donc pas de chaîne eulérienne.

Il n’existe aucun parcours passant une seule fois par tous les liens de pages.

Corrigé 2

1- Le graphe a treize arêtes. L’aéroport possède donc treize voies de circulation.

2- Le graphe est connexe. Les degrés des sommets sont les suivants :

Deux sommets seulement sont de degré impair (A et T). Il existe donc une chaîne eulérienne.

Par conséquent, il est possible de parcourir toutes les voies une fois et une seule. Par exemple : (A ; B ; C ; A ; T ; F ; C ; D ; B ; E ; D ; F ; E ; T).