TNSI : Quelques Graphes Classiques⚓︎
Graphes Complets \(K_n\)⚓︎
Graphe Complet
- Un
graphe Complet (Non Orienté) est un graphe simple dans lequel deux sommets quelconques sont forcément adjacents (reliés par une arête et une seulement). - Un
graphe Complet (Orienté) est un graphe simple dans lequel deux sommets \(s\) et \(v\) quelconques sont forcément reliés par exacteemnt deux arcs orientés (un dans chaque sens) : \(s \rightarrow v\) et \(v \rightarrow s\)
Le graphe complet à \(n\) sommets est noté
Graphes Eulériens⚓︎
Chaînes/Chemins Eulérien(ne)s⚓︎
Chaîne/Chemin Eulérien(ne)
Pte
Une chaîne/chemin eulérienne est une chaîne/chemin simple maximale (passant par toutes les arêtes du graphe)
Ex
Ex
Pour chacun des graphes suivants, trouver lorsque c'est possible une chaîne eulérienne / un parcours eulérien, càd tracer le graphe sans lever le stylo, en ne passant qu'une et une seule fois par chaque arête :
Pliée
Ouverte
Cycles/Circuits Eulériens & Graphes Eulériens⚓︎
Circuit Eulérien & Graphe Eulérien
- Un
Cycle/Circuit Eulérien , ouTournée Eulérienne , est un cycle qui parcoure toutes les arêtes/arcs du graphe une et une seule fois (en revenant au sommet initial) - Un
graphe Eulérien est un graphe contenant un cycle Eulérien Remarque: On appelle graphe semi-eulérien les graphes admettant :- un parcours eulérien,
- mais pas de cycle eulérien
Pte
Un cycle Eulérien est un cycle simple maximal (qui passe par toutes les arêtes/arcs)
Ex
Dans l'exercice précédent, quels sont les graphes Eulériens?
Caractérisation des Graphes Eulériens⚓︎
d'Euler, ou d'Euler-Hierholzer : Caractérisation des Graphes Eulériens, 1736
Un graphe connexe non orienté admet un circuit Eulérien
\(\Leftrightarrow\) tous ses sommets sont de degré pair
Ex
Pour quelles valeurs \(n\) peut-on dire que le graphe complet \(K_n\) est Eulérien?
Histoire / Jeu : Les 7 ponts de Königsberg⚓︎
La ville de Königsberg 
(aujourd'hui Kaliningrad 
) est construite autour de deux îles situées sur le Pregel et reliées entre elles par un pont. Six autres ponts relient les rives de la rivière à l'une ou l'autre des deux îles, comme représentés sur le plan ci-dessus.
Le problème consiste à déterminer s'il existe, ou non, une promenade dans les rues de Königsberg permettant, à partir d'un point de départ au choix, de passer une et une seule fois par chaque pont, et de revenir à son point de départ, étant entendu qu'on ne peut traverser le Pregel qu'en passant sur les ponts.
- D'après vous : Cette promenade est-elle réalisable? OUI? ou NON?
- Montrer que l'on peut modéliser la situation par un graphe connexe non orienté. Lequel?
- Ce graphe est-il Eulérien?
Concluez : Est-il possible de partir d'un point de départ, de parcourir tous les ponts une et une seule fois exactement, et de revenir au point de départ ? Justifiez : Si oui, détaillez la solution. Si non, expliquez pourquoi.
On a \(deg(2)=3\) (ou \(deg(3)=3\), ou \(deg(4)=3\)), donc en particulier est impair. Le
Une caractérisation un peu moins forte existe pour les parcours eulériens :
d'Euler pour les parcours Eulériens
Un graphe connexe admet un parcours Eulérien
\(\Leftrightarrow\) ses sommets sont tous de degré pair sauf au plus deux.
Est-il possible de partir d'un point de départ, de parcourir tous les ponts une et une seule fois exactement, quitte à finir sur un autre point d'arrivée (différent de celui de départ) ? Justifiez : Si oui, détaillez la solution. Si non, expliquez pourquoi.
Il existe \(3\) sommets ayant un degré impair (\(s=2\), \(s=3\) et \(s=4\)), donc cela en fait 1 de trop!
Le
Graphes Hamiltoniens⚓︎
Chaînes/Chemins Hamiltonien(ne)s⚓︎
Def
Une
Pte
Une chaîne/chemin hamiltonien(ne) est une chaîne/chemin élémentaire maximal(e) (passant par tous les sommets du graphe)
Ex
Pour chacun des graphes suivants, trouver lorsque c'est possible une chaîne hamiltonien / un parcours hamiltonien, càd tracer le graphe sans lever le stylo, en ne passant qu'une et une seule fois par chaque sommet :
Pliée
Ouverte
Cycles/Circuits Hamiltoniens & Graphes Hamiltoniens⚓︎
Cycle/Circuit Hamiltonien ou Tournée Hamiltonienne
Un
!! def "Graphe Hamiltonien"
Un
Pte
Un cycle Hamiltonien est un cycle élémentaire maximal (qui passe par tous les sommets) Un cycle Hamiltonien est une chaîne/chemin hamiltonien qui est un cycle.
Ex
Dans l'exercice précédent, quels sont les graphes Hamiltoniens?
Caractérisation des Graphes Hamiltoniens⚓︎
Il n'existe pas, comme pour les graphes Eulériens, de caractérisation (condition nécessaire et suffisante) connue pour les graphes Hamiltoniens : c'est un problème difficile. On connaît néanmoins plusieurs résultats donnant des conditions suffisantes pour que le graphe soit Hamiltonien :
Théorème de Ore (1960) (CULTURE: HORS-PROGRAMME)
Soit \(G\) un graphe simple à \(n\) sommets, avec \(n\ge3\)
Si \(deg(u)+deg(v)\ge n\) pour toute paire \((u, v)\) de sommets non adjacents,
Alors le graphe \(G\) est Hamiltonien
et une conséquence (un cas particulier)
Théorème de Dirac (1952): (CULTURE: HORS-PROGRAMME)
Soit \(G\) un graphe simple à \(n\) sommets, avec \(n\ge3\)
Si \(\displaystyle deg(s)\ge \frac n2\) pour chaque sommet \(s\),
Alors le graphe \(G\) est Hamiltonien
Histoire & Jeux : Le problème du Cavalier aux Échecs⚓︎
Au \(IX\)e siècle, le poète indien Rudrata a été l'un des tous premiers, dans son traité poétique (Kavyalankara), à parler des échecs en Inde..., et le premier à énoncer le problème des cavaliers aux échecs, ou cavalier d'Euler, qui peut se voir comme un problème de recherche de cycles/chemins hamiltoniens sur un échiquier à \(64\) cases : Un cavalier doit parcourir chaque case une et seule fois en n'utilisant que les mouvements de cette pièce, (et revenir sur la même case, si on souhaite un cycle). Une première solution à ce problème sera proposée par le joueur et théoricien arabe des échecs Al-Adli dès \(840\) ap. J.C.
Histoire & Jeux : Le Dodécaèdre de Hamilton⚓︎
Plus tardivement, en \(1857\), William Rowan Hamilton inventa un un jeu mathématique, appelé icosian game, dont le but est de parcourir tous les sommets d'un dodécaèdre en \(3D\), une et une seule fois, en partant et en revenant au même sommet.