Indice de Hosoya

En théorie des graphes, l'indice de Hosoya d'un graphe, également connu sous le nom d'indice Z, est le nombre total de couplages que possède ce graphe. L'indice de Hosoya est toujours au moins égal à 1, parce que par convention l'ensemble vide d'arêtes est compté comme un couplage dans ce contexte. De manière équivalente, l'indice de Hosoya est le nombre de couplages non vides plus un. L'indice porte le nom de Haruo Hosoya (en).

Le graphe complet K₄ possède dix couplages, indiqués en rouge, donc son indice de Hosoya est dix, qui est le maximum pour un graphe à quatre sommets.

Histoire

Cet invariant de graphe a été introduit par Haruo Hosoya en 1971. Outre ses aspects théoriques, il est souvent utilisé en chémoinformatique pour l'étude des composés organiques.

Dans son article « The topological index Z before and after 1971 », Hosoya note qu'il a introduit dès 1957 l'indice Z en observant une bonne corrélation entre les points d'ébullition des isomères d'alcanes et de leur indice Z.

Exemple

Un alcane linéaire, dans le cadre concerné par l'indice de Hosoya, peut être représenté sous la forme d'un graphe chemin sans ramification. Un chemin formé d'un sommet et sans arête (correspondant à la molécule de méthane) possède seulement un couplage vide, donc son indice de Hosoya est 1 ; un chemin formé d'une arête (éthane) a deux couplages (un avec zéro arêtes et un avec une arête), donc son indice de Hosoya est 2. Le propane (un chemin de longueur deux) a trois couplages : l'une de ses deux arêtes et le couplage vide. Le butane (un chemin de longueur trois) a cinq couplage, et l'isobutane en a quatre. Plus généralement, un couplage dans un chemin à k arêtes est soit un couplage de ses k-1 premières arêtes, soit formé d'un couplage de ses k-2 premières arêtes avec l'arête finale du chemin. Ainsi, les indices de Hosoya des alcanes linéaires obéissent à la récurrence régissant les nombres de Fibonacci. La structure des couplages dans ces graphes peut être visualisée à l'aide d'un cube de Fibonacci (en) .

La plus grande valeur possible de l'indice de Hosoya, pour un graphe à n sommets, est fournie par le graphe complet, et les indices de Hosoya pour les graphes complets sont les nombres d'involutions (en) :

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... suite A000085 de l'OEIS.

Deux définitions formelles

Une définition formelle est donnée dans MathWorld ; l'indice d'un graphe $G$ à $n$ sommets est défini par :

$Z(G)=\sum _{k=0}^{n}|a_{k}|=\sum _{k=0}^{n}b_{k}$

où $a_{k}$ est le coefficient du monôme d'exposant $k$ du polynôme des couplages (en)

$M_{G}(x):=\sum _{k\geq 0}(-1)^{k}a_{k}x^{n-2k}.$

et $b_{k}$ celui du polynôme générateur des couplages :

$m_{G}(x):=\sum _{k\geq 0}b_{k}x^{k}$,

et $b_{k}$ est le nombre de couplages composés de $k$ arêtes. En d'autres termes, cet indice est juste le nombre de couplages dans le graphe. Une autre définition est donnée par Devillers and Balaban, à savoir

$Z^{'}(G)=\sum _{k=0}^{\lfloor {n/2}\rfloor }|a_{2k}|$.

Cette définition coïncide avec la précédente pour les graphes ayant un nombre pair de sommets, pour les autres elle donne 0.

Algorithmes

Le calcul de l'indice de Hosoya est dans la classe #P-complet, même pour les graphes planaires. Cependant, il peut être calculé en évaluant le polynôme de couplage m _G pour la valeur 1 de la variable. Avec cette évaluation, le calcul de l'indice de Hosoya est traitable en complexité paramétrée pour les graphes de largeur arborescente bornée et en temps polynomial (avec un exposant qui dépend linéairement de la largeur) pour les graphes de largeur de clique bornée.

Pour certaines familles de graphes, l'indice se calcule par une relation de récurrence linéaire. Il en est ainsi par exemple pour le graphe chemin ou l'échelle de Möbius, pour lesquels on a la relation : $a(n)=2a(n-1)+4a(n-2)-a(n-4)$ (suite A020877 de l'OEIS).

Bibliographie

• Roberto Todeschini, Viviana Consonni (2000) Handbook of Molecular Descriptors, Wiley-VCH, (ISBN 3-527-29913-0)