Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Graphe polyédrique
Résumé
En théorie des graphes, une branche des mathématiques, un graphe polyédrique est un graphe non orienté défini en termes géométriques : il représente les sommets et les arêtes d'un polyèdre convexe.
On peut aussi définir un graphe polyédrique en termes purement issus de la théorie des graphes : c'est un graphe planaire 3 sommet-connexe.
Le diagramme de Schlegel d'un polyèdre convexe représente ses sommets et ses arêtes par des points et des segments de droite dans le plan euclidien. La figure résultante est un polygone convexe subdivisé en polygones plus petits. On peut associer à cette figure un graphe. Cette figure n'a pas de croisements, de telle sorte qu'un graphe polyédrique est un graphe planaire. De plus, le affirme que c'est un graphe 3 sommet-connexe, c'est-à-dire qu'il faut en retirer trois sommets avant qu'ils ne soient plus connexes.
En sens inverse, d'après le , un graphe planaire 3 sommet-connexe caractérise complètement un polyèdre. Plus précisément, quand un graphe est à la fois planaire et 3-connexe, il existe un polyèdre dont les sommets et les arêtes forment un graphe isomorphe au graphe de départ.
thumb|Le graphe de Herschel, polyédrique mais non hamiltonien. On peut se rendre compte qu'il est planaire en déplaçant le sommet central à l'extérieur.
Selon la conjecture de Tait, tout graphe polyédrique cubique (c'est-à-dire tout graphe polyédrique où chaque sommet voit arriver exactement trois arêtes) posséderait un cycle hamiltonien. Cette conjecture a été infirmée par un contre-exemple de William Tutte, le graphe de Tutte, qui est polyédrique et cubique, mais pas hamiltonien.
Si l'on ne demande plus au graphe d'être cubique, il y a des graphes polyédriques non hamiltoniens bien plus petits. Celui avec le moins de sommets et d'arêtes est le graphe de Herschel à 11 sommets et à 18 arêtes. Il existe également un graphe polyédrique non hamiltonien à 11 sommets dont toutes les faces sont des triangles, le graphe de Goldner-Harary.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.