Indice de Hosoya

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.

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).

Histoire

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.

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

Deux définitions formelles

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.

Algorithmes

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).

Notes et références

1. Haruo Hosoya, « Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons », Bulletin of the Chemical Society of Japan, vol. 44, n^o 9,‎ 1971, p. 2332–2339 (DOI 10.1246/bcsj.44.2332 ).
2. Haruo Hosoya, « The topological index Z before and after 1971 », Internet Electronic Journal of Molecular Design, vol. 1, n^o 9,‎ 2002, p. 428–442 (lire en ligne).
3. Internet Electronic Journal of Molecular Design, special issues dedicated to Professor Haruo Hosoya on the occasion of the 65th birthday : Volume 1 (2002), Number 9 — Volume 2 (2003), Number 6.
4. Robert F. Tichy et Stephan Wagner, « Extremal problems for topological indices in combinatorial chemistry », Journal of Computational Biology, vol. 12, n^o 7,‎ 2005, p. 1004–1013 (PMID 16201918, DOI 10.1089/cmb.2005.12.1004, lire en ligne).
5. (en) Eric W. Weisstein, « Hosoya Index », sur MathWorld.
6. James Devillers et Alexandru T. Balaban (éditeurs), Topological Indices and Related Descriptors in QSAR and QSPR, Amsterdam, Gordon and Breach, 1999, p. 27-28 et 105.
7. Mark Jerrum, « Two-dimensional monomer-dimer systems are computationally intractable », Journal of Statistical Physics, vol. 48, n^o 1,‎ 1987, p. 121–134 (DOI 10.1007/BF01010403).
8. Ivan Gutman, « Polynomials in graph theory », dans D. Bonchev et D. H. Rouvray, Chemical Graph Theory: Introduction and Fundamentals, vol. 1, coll. « Mathematical Chemistry », 1991 (ISBN 978-0-85626-454-2), p. 133–176
   {{Article encyclopédique}} : l'usage du paramètre |périodique = Taylor & Francis laisse présager

   • soit d'une confusion entre les modèles {{article encyclopédique}} et {{article}}
   • soit d'une confusion entre les paramètres périodique et éditeur.
   Merci de consulter la documentation des modèles et de corriger l'article.
   .
9. Bruno Courcelle, Johann A. Makowsky et Udi Rotics, « On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic », Discrete Applied Mathematics, vol. 108, n^os 1–2,‎ 2001, p. 23–52 (DOI 10.1016/S0166-218X(00)00221-3, lire en ligne).
10. J. A. Makowsky, Udi Rotics, Ilya Averbouch et Benny Godlin, « Computing graph polynomials on graphs of bounded clique-width », Proc. 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG '06), Springer-Verlag,‎ 2006, p. 191–204 (ISBN 978-3-540-48381-6, DOI 10.1007/11917496_18, lire en ligne).

Bibliographie

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