Índice Hosoya
Número de coincidencias en un gráfico
El gráfico completo K 4 tiene las diez coincidencias mostradas, por lo que su índice de Hosoya es diez, el máximo para cualquier gráfico de cuatro vértices.

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 siempre es 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 .

Historia

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]

Ejemplo

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 . a {\estilo de visualización k} a − 1 {\estilo de visualización k-1} a − 2 {\estilo de visualización k-2}

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 norte {\estilo de visualización n} K norte Estilo de visualización K_{n}

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... (secuencia A000085 en la OEIS ).

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 más pequeño que este límite superior . [4] ∑ a = 0 ⌊ norte / 2 ⌋ norte ! 2 a ⋅ a ! ⋅ ( norte − 2 a ) ! . {\displaystyle \sum _{k=0}^{\lfloor n/2\rfloor }{\frac {n!}{2^{k}\cdot k!\cdot \left(n-2k\right)!}}.}

Algoritmos

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]

Notas

  1. ^ Hosoya, Haruo (1971), "Índice topológico. Una cantidad propuesta recientemente que caracteriza la naturaleza topológica de los isómeros estructurales de los hidrocarburos saturados", Boletín de la Sociedad Química de Japón , 44 (9): 2332–2339, doi : 10.1246/bcsj.44.2332.
  2. ^ ab Hosoya, Haruo (2002), "El índice topológico Z antes y después de 1971", Internet Electronic Journal of Molecular Design , 1 (9): 428–442.
  3. ^ Internet Electronic Journal of Molecular Design, números especiales dedicados al Profesor Haruo Hosoya con motivo de su 65º cumpleaños: Volumen 1 (2002), Número 9 — Volumen 2 (2003), Número 6.
  4. ^ Tichy, Robert F.; Wagner, Stephan (2005), "Problemas extremos para índices topológicos en química combinatoria" (PDF) , Journal of Computational Biology , 12 (7): 1004–1013, doi :10.1089/cmb.2005.12.1004, PMID  16201918.
  5. ^ Jerrum, Mark (1987), "Los sistemas bidimensionales monómero-dímero son computacionalmente intratables", Journal of Statistical Physics , 48 (1): 121–134, Bibcode :1987JSP....48..121J, doi :10.1007/BF01010403, S2CID  189854401.
  6. ^ Gutman, Ivan (1991), "Polinomios en la teoría de grafos", en Bonchev, D.; Rouvray, DH (eds.), Teoría de grafos químicos: Introducción y fundamentos , Química matemática, vol. 1, Taylor & Francis, págs. 133-176, ISBN 978-0-85626-454-2.
  7. ^ Courcelle, B. ; Makowsky, JA; Rotics, U. (2001), "Sobre la complejidad de parámetros fijos de problemas de enumeración de grafos definibles en lógica monádica de segundo orden" (PDF) , Discrete Applied Mathematics , 108 (1–2): 23–52, doi :10.1016/S0166-218X(00)00221-3.
  8. ^ Makowsky, JA; Rotics, Udi; Averbouch, Ilya; Godlin, Benny (2006), "Cálculo de polinomios de grafos en grafos de ancho de camarilla acotado", Proc. 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG '06) (PDF) , Apuntes de clase en informática, vol. 4271, Springer-Verlag, pp. 191–204, doi :10.1007/11917496_18, ISBN 978-3-540-48381-6.
  9. ^ Jerrum, Mark ; Sinclair, Alistair (1996), "Capítulo 12: El método de Monte Carlo de la cadena de Markov: un enfoque para el recuento y la integración aproximados", Algoritmos de aproximación para problemas NP-hard (PDF) , PWS Publishing, págs. 482–520

Referencias

Obtenido de "https://es.wikipedia.org/w/index.php?title=Índice_de_Hosoya&oldid=1119368502"