Ê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 de Heawood
Résumé
En théorie des graphes, le graphe de Heawood est un graphe cubique symétrique possédant 14 sommets et 21 arêtes. Il doit son nom à Percy John Heawood, un mathématicien britannique né en 1861 et mort en 1955.
Le graphe de Heawood est une (3,6)-cage, c'est-à-dire un graphe minimal en nombres de sommets ayant une maille de 6 et étant cubique. En fait, il s'agit de l'unique (3,6)-cage et sa taille coïncide avec la borne de Moore, une borne inférieure sur le nombre de sommets que peut avoir une cage. Un tel graphe est qualifié de graphe de Moore.
Le diamètre du graphe de Heawood et son rayon sont tous deux égaux à 3. Cela entraîne que tous ses sommets appartiennent à son centre.
Le graphe de Heawood est 3-sommet-connexe et 3-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 3 sommets ou de 3 arêtes. Comme il est régulier de degrés 3 ce nombre est optimal. Le graphe de Heawood est donc un graphe optimalement connecté.
Il est également hamiltonien, c'est-à-dire qu'il possède un cycle passant par tous les sommets une et une seule fois.
Le graphe de Heawood n'est pas planaire. En fait pour le dessiner sur un plan il faut nécessairement que plusieurs arêtes se croisent. Il est possible de le dessiner avec seulement 3 croisements et ce nombre est minimal. En fait, d'après Pegg et Exoo, le graphe de Heawood, avec ses 14 sommets, serait le plus petit graphe cubique nécessitant 3 croisements pour être dessiné sur le plan.
Le graphe de Heawood peut par contre être plongé sur le tore, c'est donc un graphe toroïdal.
Le nombre chromatique du graphe de Heawood est 2. C'est-à-dire qu'il est possible de le colorer avec 2 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes. Ce nombre est minimal.
L'indice chromatique du graphe de Heawood est 3. Il existe donc une 3-coloration des arêtes du graphe telle que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.
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.