El índice de Hosoya , también conocido como índice Z , de un gráfico es el número total de coincidencias en el mismo. El índice de Hosoya es siempre al menos uno, porque el conjunto vacío de aristas se cuenta como una coincidencia para este propósito. De manera equivalente, el índice de Hosoya es el número de coincidencias no vacías más uno. El índice lleva el nombre de Haruo Hosoya . Se utiliza como índice topológico en la teoría química de grafos .
Los gráficos completos tienen el índice de Hosoya más grande para cualquier número de vértices; sus índices Hosoya son los números de teléfono .
Este gráfico invariante fue introducido por Haruo Hosoya en 1971. [1] A menudo se utiliza en quimioinformática para investigaciones de compuestos orgánicos . [2] [3]
En su artículo, "The Topological Index Z Before and After 1971", sobre la historia de la noción y las historias internas asociadas, Hosoya escribe que introdujo el índice Z para informar una buena correlación de los puntos de ebullición de los isómeros de alcano y su Z. índices, basándose en su trabajo inédito de 1957 realizado mientras era estudiante universitario en la Universidad de Tokio . [2]
Un alcano lineal , a los efectos del índice de Hosoya, se puede representar como un gráfico de ruta sin ninguna ramificación. Un camino con un vértice y sin aristas (correspondiente a la molécula de metano ) tiene una coincidencia (vacía), por lo que su índice de Hosoya es uno; un camino con una arista ( etano ) tiene dos coincidencias (una con cero aristas y otra con una arista), por lo que su índice de Hosoya es dos. El propano (un camino de longitud dos) tiene tres coincidencias: cualquiera de sus bordes o la coincidencia vacía. El n - butano (un camino de longitud tres) tiene cinco coincidencias, lo que lo distingue del isobutano que tiene cuatro. De manera más general, una coincidencia en un camino con bordes forma una coincidencia en los primeros bordes o forma una coincidencia en los primeros bordes junto con el borde final del camino. Este análisis de caso muestra que los índices de Hosoya de los alcanos lineales obedecen a la recurrencia que rige los números de Fibonacci y, como también tienen el mismo caso base, deben ser iguales a los números de Fibonacci. La estructura de las coincidencias en estos gráficos se puede visualizar utilizando un cubo de Fibonacci .
El mayor valor posible del índice de Hosoya, en un gráfico con vértices, viene dado por el gráfico completo . Los índices de Hosoya para los gráficos completos son los números de teléfono.
Estos números se pueden expresar mediante una fórmula de suma que incluya factoriales , como
El índice de Hosoya es #P-completo para calcular, incluso para gráficos planos . [5] Sin embargo, se puede calcular evaluando el polinomio coincidente m G en el argumento 1. [6] Con base en esta evaluación, el cálculo del índice de Hosoya es manejable con parámetros fijos para gráficos de ancho de árbol acotado [7] y polinomio (con un exponente que depende linealmente del ancho) para gráficas de ancho de camarilla acotado . [8] El índice de Hosoya se puede aproximar eficientemente a cualquier relación de aproximación constante deseada utilizando un esquema de aproximación aleatorio totalmente polinomial . [9]
