Indice de Hosoya

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

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.

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[4].

Une définition formelle est donnée dans MathWorld[5] ; l'indice d'un graphe ${\displaystyle G}$ à ${\displaystyle n}$ sommets est défini par :

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

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

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

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

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

et ${\displaystyle b_{k}}$ est le nombre de couplages composés de ${\displaystyle 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[6], à savoir

${\displaystyle 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.

Le calcul de l'indice de Hosoya est dans la classe #P-complet, même pour les graphes planaires[7]. Cependant, il peut être calculé en évaluant le polynôme de couplage m _G pour la valeur 1 de la variable[8]. 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[9] et en temps polynomial (avec un exposant qui dépend linéairement de la largeur) pour les graphes de largeur de clique bornée[10].

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 : ${\displaystyle a(n)=2a(n-1)+4a(n-2)-a(n-4)}$ (suite A020877 de l'OEIS).

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