Concept

Snark fleur

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.

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.