Snark (graphe)

De testwiki
Aller à la navigation Aller à la recherche

Modèle:Voir homonymes

Le snark fleur J5 est l'un des 6 snarks à 20 sommets.
Une coloration des arêtes de J5 avec 4 couleurs.

En théorie des graphes, une branche des mathématiques, un snark est un graphe cubique connexe, sans isthme et d'indice chromatique égal à 4. En d'autres termes, c'est un graphe dans lequel chaque sommet a trois voisins, et dont les arêtes ne peuvent pas être colorées avec seulement 3 couleurs sans que deux arêtes de même couleur ne se rencontrent en un même sommet (d'après le théorème de Vizing, l'indice chromatique d'un graphe cubique est 3 ou 4).

Pour éviter les cas triviaux, on exige souvent de plus que les snarks aient une maille d'au moins 5.

Les snarks ont été nommés ainsi par le mathématicien américain Martin Gardner en 1976, d'après l'objet mystérieux et insaisissable du poème La Chasse au Snark de Lewis Carroll[1].

Historique

Peter Guthrie Tait a initié l'étude des snarks en 1880, quand il a prouvé que démontrer le théorème des quatre couleurs revenait à démontrer que tout graphe cubique planaire pouvait avoir ses arêtes colorées avec trois couleurs. Ou dit autrement, qu'aucun snark n'est planaire[2].

Le premier snark connu était le graphe de Petersen, découvert en 1898. En 1946, le mathématicien croate Danilo Blanuša découvrit deux autres snarks, tous deux à 18 sommets, à présent appelés les snarks de Blanuša[3]. Le quatrième snark connu a été découvert deux ans plus tard par Bill Tutte, sous le pseudonyme de Blanche Descartes, et comportait 210 sommets[4]Modèle:,[5]. En 1973, George Szekeres a découvert le cinquième snark connu, le snark de Szekeres[6]. En 1975, Rufus Isaacs a généralisé la méthode de Blanuša afin de construire deux familles infinies de snarks : les snarks fleurs et les BDS ou snarks de Blanuša-Descartes-Szekeres, une famille qui comprend les deux snarks de Blanuša, le snark de Descartes et le snark de Szekeres[7]. Isaacs découvrit aussi un snark à 30 sommets qui n'appartient pas à la famille BDS et qui n'est pas un snark fleur : le snark double étoile.

Écrivant dans The Electronic Journal of Combinatorics, Miroslav Chladný affirme que Modèle:Citation

Propriétés

Tous les snarks sont non-hamiltoniens, et plusieurs snarks connus sont hypohamiltoniens : en supprimant n'importe quel sommet, le graphe devient hamiltonien. Un snark hypohamiltonien est forcément bicritique : en supprimant n'importe quelle paire de sommets, les arêtes du graphes peuvent être colorées avec 3 couleurs[8]Modèle:,[9].

On a pu démontrer que le nombre de snarks ayant un nombre pair donné de sommets est minoré par une fonction exponentielle de ce nombre de sommets[10] (comme les snarks sont des graphes cubiques, ils ont forcément un nombre de sommets pair). La Modèle:OEIS donne le nombre de snarks non triviaux à 2n sommets pour les petites valeurs de n : 0, 0, 0, 0, 1, 0, 0, 0, 2, 6, 20, 38, 280, 2900, 28399, 293059, 3833587, 60167732.

Conjecture du double revêtement

Un double revêtement du graphe de Petersen à l'aide de cycles.

La Modèle:Lien affirme que dans tout graphe sans isthme, on peut trouver un ensemble de cycles passant deux fois par chaque arête. Une formulation équivalente est que le graphe peut être plongé dans une surface de telle sorte que toutes les faces du plongement soient des cycles simples.

Les snarks forment le cas difficile dans cette conjecture : si elle est vraie pour les snarks, elle le sera pour tous les graphes[11].

En rapport avec ce problème, Branko Grünbaum a émis la conjecture qu'il était impossible de plonger un graphe sur une surface de sorte que toutes les faces soient des cycles simples et que deux faces quelconques soit soient disjointes soit partagent une seule arête commune. Cette conjecture s'est révélée fausse, Martin Kochol ayant trouvé un contre-exemple[12]Modèle:,[13]Modèle:,[14].

Théorème du snark

Modèle:Article connexe W. T. Tutte a émis la conjecture que tout snark a le graphe de Petersen comme mineur. En d'autres termes, il a émis l'hypothèse que l'on pouvait obtenir le plus petit snark, le graphe de Petersen, à partir de n'importe quel autre snark en contractant certaines arêtes et en supprimant des sommets isolés ou des arêtes.

Une hypothèse équivalente est que tout snark peut être formé à partir du graphe de Petersen en subdivisant certaines de ses arêtes par homéomorphisme.

En 1999, Neil Robertson, Daniel Sanders, Paul Seymour et Robin Thomas ont annoncé une démonstration de la conjecture de Tutte[15]. Sarah-Marie Belcastro fait néanmoins remarquer qu'en 2012, leur démonstration reste en grande partie non publiée.

Tutte a également émis une conjecture généralisant le théorème du snark à des graphes arbitraires : tout graphe sans isthme et sans graphe de Petersen comme mineur un Modèle:Lien. Cela signifie que les arêtes du graphe peuvent se voir affecter une orientation et un nombre égal à 1, 2 ou 3, de façon que la somme des nombres entrants moins la somme des nombres sortants soit divisible par 4 quel que soit le sommet. Comme Tutte l'a montré, pour les graphes cubiques une telle affectation existe si et seulement si les arêtes peuvent être colorées avec 3 couleurs, donc la conjecture découle du théorème du snark dans le cas des graphes cubiques. Néanmoins, la conjecture reste ouverte pour les autres graphes[16].

Liste de snarks

En 2012, Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund et Klas Markström ont généré tous les snarks jusqu'à 36 sommets grâce à une recherche par ordinateur[17].

Notes et références

Modèle:Références

Voir aussi

Crédit d'auteurs

Modèle:Traduction/Référence

Liens externes

Modèle:Portail

  1. ↑ Modèle:Article
  2. ↑ Modèle:Article
  3. ↑ Modèle:Article
  4. ↑ Modèle:Article
  5. ↑ Modèle:Ouvrage.
  6. ↑ Modèle:Article
  7. ↑ Modèle:Article
  8. ↑ Modèle:Article
  9. ↑ Modèle:Article
  10. ↑ Modèle:Chapitre
  11. ↑ Modèle:Chapitre.
  12. ↑ Modèle:Article.
  13. ↑ Modèle:Chapitre.
  14. ↑ Modèle:Chapitre.
  15. ↑ Modèle:Chapitre
  16. ↑ Modèle:En 4-flow conjecture, Open Problem Garden.
  17. ↑ Modèle:Article
Récupérée de "https://fr.wiki.beta.math.wmflabs.org/w/index.php?title=Snark_(graphe)&oldid=13773"