El índice de Hosoya , también conocido como índice Z , de un grafo es el número total de coincidencias en él. 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 recibe su nombre de Haruo Hosoya . Se utiliza como índice topológico en la teoría de grafos químicos .
Los gráficos completos tienen el índice de Hosoya más grande para cualquier número dado de vértices; sus índices de Hosoya son los números de teléfono .
Este invariante gráfico fue introducido por Haruo Hosoya en 1971. [1] Se utiliza a menudo en quimioinformática para investigaciones de compuestos orgánicos . [2] [3]
En su artículo, "El índice topológico Z antes y después de 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 alcanos y sus índices Z, basándose en su trabajo inédito de 1957 realizado mientras era estudiante universitario en la Universidad de Tokio . [2]
Un alcano lineal , para los propósitos del índice de Hosoya, puede representarse como un grafo de trayectoria sin ninguna ramificación. Una trayectoria con un vértice y sin aristas (que corresponde a la molécula de metano ) tiene una coincidencia (vacía), por lo que su índice de Hosoya es uno; una trayectoria 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 (una trayectoria de longitud dos) tiene tres coincidencias: cualquiera de sus aristas o la coincidencia vacía. El n - butano (una trayectoria de longitud tres) tiene cinco coincidencias, lo que lo distingue del isobutano que tiene cuatro. De manera más general, una coincidencia en una trayectoria con aristas forma una coincidencia en las primeras aristas, o forma una coincidencia en las primeras aristas junto con la arista final de la trayectoria. 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 debido a que también tienen el mismo caso base, deben ser iguales a los números de Fibonacci. La estructura de las correspondencias en estos gráficos se puede visualizar utilizando un cubo de Fibonacci .
El valor máximo posible del índice de Hosoya, en un grafo con vértices, viene dado por el grafo completo . Los índices de Hosoya para los grafos completos son los números de teléfono
Estos números se pueden expresar mediante una fórmula de suma que involucra factoriales , ya que cada gráfico que no esté completo tiene un índice de Hosoya menor que este límite superior . [4]
El índice de Hosoya es #P-completo para calcular, incluso para grafos planares . [5] Sin embargo, se puede calcular evaluando el polinomio correspondiente 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 grafos de ancho de árbol acotado [7] y polinomial (con un exponente que depende linealmente del ancho) para grafos de ancho de camarilla acotado . [8] El índice de Hosoya se puede aproximar eficientemente a cualquier razón de aproximación constante deseada utilizando un esquema de aproximación aleatorio completamente polinomial . [9]
