Graphe chenille

Un graphe chenille.

En théorie des graphes, un graphe chenille ou plus simplement une chenille est un arbre dans lequel tous les sommets sont à distance au plus 1 d'un chemin central.

Caractérisations équivalentes

Les graphes chenilles ont d'abord été étudiés dans une série d'articles de Harary et Schwenk. Le nom a été suggéré par A. HobbsModèle:,. Harary & Schwenk écrivent de façon colorée : « une chenille est un arbre qui se métamorphose en un chemin lorsque son cocon de points d'extrémité est supprimé ». Les graphes chenille possèdent un étiquetage gracieux.

Les caractérisations suivantes décrivent les chenilles: Les chenilles sont

• les arbres pour lesquels la suppression des feuilles et des arêtes incidentes produit un graphe cheminModèle:,.
• les arbres dans lesquels il existe un chemin qui contient tous les sommets de degré deux ou plusModèle:,.
• les arbres dans lesquels chaque sommet de degré au moins trois a au plus deux voisins qui ne sont pas des feuilles.
• les arbres qui ne contiennent pas comme sous-graphe le graphe obtenu en remplaçant chaque arête du graphe étoile K _1,3 par un chemin de longueur deux.
• les graphes connexes qui peuvent être tracés avec leurs sommets sur deux droites parallèles, avec des arêtes représentées par des segments de droites sans croisement qui ont un point d'extrémité sur chacune des droites.
• les arbres dont le carré est une chaîne hamiltonienne. En d'autres termes dans une chenille, il existe une séquence cyclique de tous les sommets dans laquelle chaque paire de sommets consécutifs est à distance un ou deux l'une de l'autre, et les arbres qui ne sont pas des chenilles ne possèdent pas une telle séquence. Un cycle de ce type peut être obtenu en traçant la chenille sur deux droites parallèles et en concaténant la séquence de sommets sur une droite avec l'inverse de la séquence sur l'autre droite .
• les arbres dont le line graph contient une chaîne hamiltonienne ; une telle chaîne peut être obtenu en ordonnant les arêtes dans un dessin à deux droites de l'arbre. Plus généralement, le nombre d'arêtes qui doivent être ajoutées au line graph d'un arbre arbitraire pour qu'il contienne une chaîne hamiltonienne (la taille de sa complétion hamiltonienne ) est égal au nombre minimum de décompositions de l'arbre en chenilles à arêtes disjointes.
• les graphes connexes de largeur de chemin égale à un.
• les graphes d'intervalle sans triangle et connexes.

Généralisations

Un k-arbre est un graphe cordal avec exactement n-k cliques maximales, chacune contenant k+1 sommets; dans un k-arbre qui n'est pas lui-même une clique de k+1 sommets, chaque clique maximale sépare le graphe en deux ou plusieurs composantes, ou alors elle contient un seul sommet feuille, un sommet qui n'appartient qu'à une seule clique maximale. Une k-chaîne est un k-arbre avec au plus deux feuilles, et une k- chenille est un k-arbre qui peut être décomposé en une k-chaîne et des k-feuilles, chacune adjacente à un séparateur qui est une k-clique de la k-chaîne. Dans cette terminologie, une 1-chenille est la même chose qu'un arbre à chenilles, et les k-chenilles sont les graphes maximaux en nombre d'arêtes avec largeur de chemin égale à k.

Un graphe homard est un arbre dans lequel tous les sommets sont à distance 2 d'un chemin central.

Énumération

Les chenilles forment une famille de graphes pour laquelle une formule exacte peut être donnée : pour n ≥ 3, le nombre de chenilles à n sommets non étiquetés est :

$2^{n-4}+2^{\lfloor (n-4)/2\rfloor }.$

Pour n = 1, 2, 3, ... les nombres de chenilles à n sommets est

1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, ...

C'est la Modèle:OEIS .

Complexité informatique

Trouver une chenille couvrant un graphe est NP-complet. Un problème d'optimisation lié est le problème de couverture minimale par une chenille (MSCP pour Minimum Spanning Caterpillar Problem), où un graphe a deux coûts associés à ses arêtes et le but est de trouver un arbre chenilles qui couvre le graphe donné et qui a le plus petit coût total. Ici, le coût de la chenille est défini comme la somme des coûts de ses arêtes, où chaque arête a pour coût l'un des deux coûts attribués en fonction de son rôle en tant que arête d'une feuille ou arête interne. Il n'y a pas d'algorithme d'approximation en f(n) pour le MSCP à moins que P = NP; ici f (n) est toute fonction calculable en temps polynomial de n, le nombre de sommets d'un graphe.

Il existe un algorithme paramétré qui trouve une solution optimale pour le MSCP dans les graphes à largeur arborescente bornée. Ainsi, le problème de couverture par une chenille et le MSCP possèdent tous deux des algorithmes de temps linéaire si le graphe est un graphe planaire extérieur, un graphe série-parallèle ou un graphe de Halin.

Applications

Les graphes chenilles ont été utilisées dans la théorie des graphes chimiques pour représenter la structure des molécules d'hydrocarbures aromatiques. Dans cette représentation, on forme une chenille dans laquelle chaque arête correspond à un cycle à 6 atomes de carbone de la structure moléculaire, et deux arêtes sont incidentes à un sommet chaque fois que les anneaux correspondants appartiennent à une séquence d'anneaux connectés bout à bout dans le structure. El-Basil note : « Il est étonnant que presque tous les graphes qui ont joué un rôle important dans ce qui est maintenant appelé la théorie chimique des graphes puissent être reliés aux graphes chenilles. »" Dans ce contexte, les chenilles sont également connues sous le nom dModèle:'arbres benzéniques et dModèle:'arbres Gutman, d'après les travaux d'Ivan Gutman dans ce domaineModèle:,Modèle:,.