Loading AI tools
De Wikipédia, l'encyclopédie libre
Le graphe de Tutte est, en théorie des graphes, un graphe 3-régulier possédant 46 sommets et 69 arêtes.
| Graphe de Tutte | |
 Représentation du graphe de Tutte | |
| Nombre de sommets | 46 |
|---|---|
| Nombre d'arêtes | 69 |
| Distribution des degrés | 3-régulier |
| Rayon | 5 |
| Diamètre | 8 |
| Maille | 4 |
| Automorphismes | 3 (Z/3Z) |
| Nombre chromatique | 3 |
| Indice chromatique | 3 |
| Propriétés | Régulier Cubique Planaire |
modifier  |
|
Le graphe de Tutte est découvert par le mathématicien William Tutte en 1946. C'est le premier contre-exemple connu à la conjecture de Tait sur les graphes hamiltoniens, c'est-à-dire que c'est un graphe planaire non-hamiltonien étant 3-sommet-connexe[1],[2].
Le graphe de Tutte est suivi de la construction de plusieurs autres contre-exemples à cette conjecture. Notamment trois par Grinberg (le 46-graphe de Grinberg, le 44-graphe de Grinberg et le 42-graphe de Grinberg), et deux par Faulkner et Younger (le 44-graphe de Faulkner-Younger et le 42-graphe de Faulkner-Younger)[3],[4].
En 1965, Lederberg construit un contre-exemple à la conjecture de Tait doté de seulement 38 sommets : le graphe de Barnette-Bosák-Lederberg[5]. Lederberg émet l'hypothèse de sa minimalité mais est incapable de la prouver. Il démontre cependant qu'un contre-exemple minimal à la conjecture de Tait doit avoir strictement plus de 24 sommets.
À peu près à la même époque, David Barnette et Juraj Bosák (sk) construisent six contre-exemples d'ordre 38 à la conjecture de Tait, redécouvrant indépendamment le graphe de Barnette[6],[7].
En 1988, Derek Holton et Brendan McKay prouvent qu'il est impossible de construire un contre-exemple à la conjecture de Tait avec moins de 38 sommets. Dans le même article, ils démontrent que les 6 graphes décrits par D. Barnette et J. Bosák sont les seuls de cet ordre[8].
Le diamètre du graphe de Tutte, l'excentricité maximale de ses sommets, est 8, son rayon, l'excentricité minimale de ses sommets, est 5 et sa maille, la longueur de son plus court cycle, est 4. Il s'agit d'un graphe 3-sommet-connexe et d'un graphe 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.
Le nombre chromatique du graphe de Tutte est 3. C'est-à-dire qu'il est possible de le colorer avec 3 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes mais ce nombre est minimal. Il n'existe pas de 2-coloration valide du graphe.
L'indice chromatique du graphe de Tutte 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.
Le groupe d'automorphismes du graphe de Tutte est un groupe abélien d'ordre 3 isomorphe au groupe cyclique Z/3Z.
Le polynôme caractéristique de la matrice d'adjacence du graphe de Tutte est :
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
