Graphe de Tutte

Graphe de Tutte
Graphe de Tutte
Représentation du 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

Le graphe de Tutte est, en théorie des graphes, un graphe 3-régulier possédant 46 sommets et 69 arêtes.

Sommaire

Histoire

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 une 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 contres-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 (en) 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].

Propriétés

Propriétés générales

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.

Coloriage

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 tels que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.

Propriétés algébriques

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 du graphe de Tutte est :

(x − 3)(x15 − 22x13 + x12 + 184x11 − 26x10 − 731x9 + 199x8 + 1383x7 − 576x6 − 1061x5 + 561x4 + 233x3 − 151x2 + 4x + 4)2
(x15 + 3x14 − 16x13 − 50x12 + 94x11 + 310x10 − 257x9 − 893x8 + 366x7 + 1218x6 − 347x5 − 717x4 + 236x3 + 128x2 − 56x + 4).

Voir aussi

Liens internes

Liens externes

Références

  1. (en) P. G. Tait, « Listing's Topologie », dans Philosophical Magazine (5th ser.), vol. 17, 1884, p. 30–46 . Reprinted in Scientific Papers, Vol. II, pp. 85–98.
  2. (en) W. T. Tutte, « On Hamiltonian circuits », dans Journal of the London Mathematical Society (2nd ser.), vol. 21, no 2, 1946, p. 98–101 [texte intégral] 
  3. (en) Faulkner, G. B. and Younger, D. H. "Non-Hamiltonian Cubic Planar Maps." Discr. Math. 7, 67-74, 1974.
  4. Claude Berge, Graphes et hypergraphes, Dunod, 1973.
  5. (en) Lederberg, J. "DENDRAL-64: A System for Computer Construction, Enumeration and Notation of Organic Molecules as Tree Structures and Cyclic Graphs. Part II. Topology of Cyclic Graphs." Interim Report to the National Aeronautics and Space Administration. Grant NsG 81-60. December 15, 1965. [1]
  6. (en) Eric W. Weisstein, Barnette-Bosák-Lederberg Graph (MathWorld)
  7. (en) Derek Holton and Robert E. L. Aldred. Planar Graphs, Regular Graphs, Bipartite Graphs and Hamiltonicity. Australasian Journal of Combinatorics, 20:111–131, 1999. [2]
  8. (en) D. A. Holton et B. D. McKay, « The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices », dans Journal of Combinatorial Theory, Series B, vol. 45, no 3, 1988, p. 305–319 [lien DOI] 

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe de Tutte de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Graphe de Tutte–Coxeter — Représentation hamiltonienne du graphe de Tutte–Coxeter. Nombre de sommets 30 Nombre d arêtes 45 Distribution des degrés 3 régulier Rayo …   Wikipédia en Français

  • Graphe de Barnette-Bosák-Lederberg — Représentation du graphe Barnette Bosák Lederberg Nombre de sommets 38 Nombre d arêtes 57 Distribution des degrés 3 régulier …   Wikipédia en Français

  • Graphe distance-régulier — En théorie des graphes, un graphe est distance régulier si pour tous sommets , le nombre de sommets voisins de u à distance i et le nombre de sommets voisins de v à distance j ne dépendent que de i,j et de la distance d(u,v) entre u et v.… …   Wikipédia en Français

  • Graphe de Moore — En théorie des graphes, un graphe de Moore est un graphe régulier dont le nombre de sommets, pour un degré et un diamètre donnés, est maximal. Les graphes de Moore ont été nommés par Alan Hoffman et Robert Singleton en 1960 en hommage à Edward F …   Wikipédia en Français

  • Graphe intégral — En théorie des graphes, un graphe intégral est un graphe dont le spectre de la matrice d adjacence ne contient que des entiers[1]. En d autres termes, les racines de son polynôme caractéristiques sont toutes entières. Leur étude fut introduite… …   Wikipédia en Français

  • Graphe de Horton — Représentation du graphe de Horton. Nombre de sommets 96 Nombre d arêtes 144 Distribution des degrés 3 régulier Rayon 10 …   Wikipédia en Français

  • Graphe de Petersen — Schéma classique du graphe de Petersen, sous la forme d un pentagone et d un pentagramme concentriques, reliés par cinq rayons. Nombre de sommets 10 Nombre d arêtes 15 Distribution des degrés 3 régulier …   Wikipédia en Français

  • Graphe (mathématiques) — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Graphe (théorie des graphes) — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • William Tutte — William Thomas Tutte (14 mai 1917 – 2 mai 2002) était un mathématicien et cryptanalyste britannique, puis canadien. Pendant la Seconde Guerre mondiale, il décrypta l un des principaux codes allemands, ce qui eut un impact significatif sur le… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”