Graphe cactus

vignette|upright=1.4| Un graphe cactus. En théorie des graphes, un graphe cactus (parfois appelé arbre cactus) est un graphe connexe dans lequel deux cycles simples quelconques ont au plus un sommet en commun. De manière équivalente, c'est un graphe connexe dans lequel chaque arête appartient à au plus un cycle simple, ou (pour les cactus non triviaux) dans lequel chaque bloc (sous-graphe maximal sans point d'articulation) est une arête ou un cycle. Les graphes cactus ont d'abord été étudiés sous le nom darbres de Husimi, nom qui leur a été attribué par Frank Harary et George Eugene Uhlenbeck en l'honneur des travaux antérieurs sur ces graphes de Kôdi Husimi. Dans l'article de Harary et Uhlenbeck, le nom de « cactus » est réservé aux seuls graphes dans lesquels chaque cycle est un triangle ; depuis, cette restriction a été levée. Entretemps, le nom d'arbre de Husimi en est venu à désigner des graphes dans lesquels chaque bloc est un graphe complet (de manière équivalente, les graphes d'intersection des blocs dans un autre graphe). Cet usage avait peu à voir avec les travaux de Husimi, et le terme plus pertinent de graphe de blocs est maintenant utilisé pour cette famille. Les cactus sont des graphes planaires extérieurs. Toute pseudo-forêt est un cactus. Un graphe non trivial est un cactus si et seulement si chaque bloc est soit un cycle simple, soit une arête unique. La famille de graphes dans laquelle chaque composante est un cactus est fermée sous des opérations de mineurs du graphe. Cette famille de graphes peut être caractérisée par un seul mineur exclu, à savoir le graphe diamant à quatre sommets formé en supprimant une arête du graphe complet K4. vignette| Les graphes d'amitié sont des cactus triangulaires Un cactus triangulaire est un graphe cactus dans lequel tout cycle a longueur trois et toute arête appartient à un cycle. Par exemple, les graphes d'amitié (qui sont des graphes formés à partir d'une collection de triangles réunis en un seul sommet partagé) sont des cactus triangulaires.