Snark (graphe)

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. 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. 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. 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. En 1973, George Szekeres a découvert le cinquième snark connu, le snark de Szekeres. 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. 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 Tous les snarks sont non-hamiltoniens, et plusieurs snarks connus sont hypohamiltoniens : en supprimant n'importe quel sommet, le graphe devient hamiltonien.

À 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.

Concepts associés (25)

Cours associés (1)

Séances de cours associées (3)

PHYS-512: Statistical physics of computation

This course covers the statistical physics approach to computer science problems ranging from graph theory and constraint satisfaction to inference and machine learning. In particular the replica and

En théorie des graphes, une branche des mathématiques, un graphe cubique est un graphe régulier de degré 3. En d'autres termes, c'est un graphe dans lequel il y a exactement trois arêtes incidentes à chaque sommet. Le graphe complet K4 est le plus petit graphe cubique. Le graphe biparti complet K3,3 est le plus petit graphe cubique non-planaire. Le graphe de Petersen est le plus petit graphe cubique de maille 5. Le graphe de Heawood est le plus petit graphe cubique de maille 6.

Le graphe de Tietze est, en théorie des graphes, un graphe 3-régulier possédant 12 sommets et 18 arêtes. Il est remarquable notamment pour ses propriétés de coloration. Le diamètre du graphe de Tietze, l'excentricité maximale de ses sommets, est 3, son rayon, l'excentricité minimale de ses sommets, est 3 et sa maille, la longueur de son plus court cycle, est 3. 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.

Comparer la coloration aléatoire et symétrique des graphiques en termes de coloration et d'équilibre des amas.

Explore la physique statistique des clusters, en se concentrant sur la complexité et le comportement d'équilibre.

Couvre les méthodes probabilistes en combinatoire, les bords monochromatiques, les graphiques à 2 couleurs et les bons 2 couleurs.