Índice Hosoyya

El índice (topológico) de Hosoya , también conocido como índice Z , de un gráfico es el número total de coincidencias en él. El índice de Hosoya siempre es mayor o igual a uno, ya que el conjunto vacío de aristas cuenta como una coincidencia. De manera equivalente, el índice de Hosoya es el número de emparejamientos no vacíos más uno.

Historia

Este gráfico invariante fue introducido por Haro Hosoya en 1971 [1] . A menudo se utiliza en quimioinformática para estudiar sustancias orgánicas [2] [3] .

En el artículo "El índice topológico Z antes y después de 1971" sobre la historia del concepto e historias relacionadas, Hosoya escribe que introdujo el índice Z para indicar una alta correlación entre el punto de ebullición de los isómeros de alcanos y sus índices Z, basado en en un artículo inédito de 1957 cuando era estudiante de pregrado en la Universidad de Tokio [2] .

Ejemplo

Los alcanos lineales en el contexto del índice de Hosoyya se pueden representar como caminos no ramificados . Un camino con un vértice sin aristas (correspondiente a una molécula de metano ) tiene una coincidencia (vacía), por lo que su índice de Hosoyya es uno. Un camino con un borde ( etan ) tiene dos coincidencias (una con un conjunto vacío de bordes, la otra con un borde), por lo que su índice Hosoyya es dos. El propano (un camino de longitud dos) tiene tres coincidencias: cualquiera de sus aristas, más un conjunto vacío de aristas. n - El butano (un camino de longitud tres) tiene cinco emparejamientos, lo que lo distingue del isobutano , que tiene cuatro. En general, las coincidencias en un camino con k aristas forman una coincidencia con las aristas iniciales o forman una coincidencia desde las primeras aristas más una arista que conecta los dos últimos vértices. Así, los índices de Hosoya de los alcanos lineales satisfacen la relación recurrente de los números de Fibonacci . Las estructuras coincidentes en estos gráficos se pueden visualizar utilizando el cubo de Fibonacci .

El mayor valor posible del índice de Hosoyya en un gráfico con n vértices viene dado por gráficos completos , y los índices de Hosoyya para gráficos completos números de teléfono entre sí (no llamadas de conferencia).

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

Algoritmos

Se refiere a índices topológicos difíciles de calcular. Calcular el índice de Hosoya es #P-completo incluso para gráficos planos [5] . Sin embargo, se puede calcular calculando el polinomio coincidente con el argumento 1 [6] . Basado en este cálculo del índice de Hosoya, el problema tiene solución paramétrica fija para gráficos de ancho de árbol acotado [ 7] y polinomial (con un exponente que depende linealmente del ancho) para gráficos de ancho de camarilla acotado [8] .

El artículo de Trofimov da una estimación de la complejidad computacional como , donde es el número de aristas [9] .

Notas

  1. ↑ Hosoya, 1971 , pág. 2332–2339.
  2. ↑ 1 2 Hosoya, 2002 , pág. 428–442.
  3. ↑ 65 años de Haruo Hosoya, 2002/2003 .
  4. ↑ Tichy, Wagner, 2005 , pág. 1004–1013.
  5. ↑ Jerrum, 1987 , pág. 121–134.
  6. ↑ Gutman, 1991 , pág. 133–176.
  7. ↑ Courcelle, Makowsky, Rotics, 2001 , p. 23–52.
  8. ↑ Makowsky, Rotics, Averbouch, Godlin, 2006 , p. 191–204.
  9. ↑ Trofimov, 1991 , pág. 327.

Literatura