Snark fleur | EPFL Graph Search

Ê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 GraphSearch.

Découvrez-en plus sur les applications Graph.

En mathématiques, et plus particulièrement en théorie des graphes, les snarks fleurs forment une famille infinie de snarks introduite par Rufus Isaacs en 1975. Étant un snark, un snark fleur est un graphe cubique connexe et sans isthme d'indice chromatique égal à 4. Il est non-planaire et non-hamiltonien. Le snark fleur Jn peut être construit ainsi : Construire n copies du graphe étoile à 4 sommets. On note le sommet central de chaque étoile Ai et les sommets périphériques Bi, Ci et Di. On obtient un graphe non connexe à 4n sommets et 3n arêtes. Construire le cycle à n sommets (B1 B2... Bn) (au centre sur les figures). Cela ajoute n arêtes. Enfin construire le cycle à 2n sommets (C1C2... CnD1D2... Dn) (à l'extérieur sur les figures, les arêtes CnD1 et DnC1 sont en bas). Cela ajoute 2n arêtes. Par construction, le graphe obtenu Jn est un graphe cubique à 4n sommets et 6n arêtes. Pour être un snark fleur, n doit être impair. Le nom « snark fleur » désigne parfois plus particulièrement J5, un snark fleur à 20 sommets et 30 arêtes. C'est un des 6 snarks sur 20 sommets . Le snark fleur J5 est hypohamiltonien. Flower snark 3COL.svg|Le [[nombre chromatique]] du graphe fleur J5 vaut 3. Flower snark 4color edge.svg|L'[[indice chromatique]] du graphe fleur J5 vaut 4. Flower snark original.svg|La construction du graphe fleur J5. J3 est une variation sur le graphe de Petersen obtenue en appliquant une transformation Y-Δ au graphe de Petersen, en remplaçant un de ses sommets par un triangle. Ce graphe est également connu comme le graphe de Tietze. Pour éviter les cas triviaux, on demande souvent aux snarks d'avoir au moins une maille de 5. Avec cette restriction, J3 n'est pas un snark. Image:Tietze's graph.

À 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 (4)

Snark fleur

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.

Graphe cubique

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.