Caterpillar (teoría de grafos)

Una oruga o árbol de oruga  es un árbol en el que todos los vértices están a una distancia de como máximo 1 del camino central.

Los gráficos de oruga se estudiaron por primera vez en una serie de artículos de Harari y Schwenk. El nombre fue sugerido por Arthur Hobbs [1] [2] . Como Harari y Schwenk [3] escribieron elocuentemente , "Una oruga es un árbol que se convierte en un camino si se quita el capullo de los vértices terminales" [1] .

Descripciones equivalentes

Las siguientes características describen los gráficos de oruga:

Generalizaciones

Un árbol K es un gráfico cordal que contiene exactamente n − k camarillas máximas , cada una de las cuales contiene k + 1 vértices. En un árbol k , que no es en sí mismo una camarilla ( k + 1) , cada camarilla máxima divide el gráfico en dos o más componentes o contiene un vértice de hoja ( k- ) que pertenece solo a una camarilla máxima. Un camino k es un árbol k con dos hojas como máximo, y una oruga k es un árbol k que se puede dividir en caminos k y varias hojas k , cada una adyacente al separador de camarilla k del k - camino. En esta terminología, una oruga 1 es lo mismo que un gráfico de oruga, y las orugas k son gráficos de borde máximo con ancho de ruta k [ 7] .

Un cangrejo  es un árbol en el que todos los vértices están a una distancia no superior a 2 del camino central [9]

Enumeración

Las orugas son un caso raro de problemas de enumeración de gráficos cuando se conoce la fórmula exacta: si n  ≥ 3, el número de orugas con n vértices es [1] .

Para n = 1, 2, 3, … el número de orugas con n vértices es

1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160,… (secuencia A005418 en OEIS ).

Complejidad computacional

Encontrar una oruga que se contrae es un problema NP-completo . El problema de optimización correspondiente es el problema de oruga de contracción mínima (MPCT), en el que los precios se dan en los bordes y el objetivo es encontrar una oruga que minimice los precios. Aquí el precio de una oruga se define como la suma de los precios de sus aristas, y cada arista tiene dos precios, según sea hoja o arista interna. No existe un algoritmo de aproximación f(n) para SMSH a menos que se satisfaga P = NP . Aquí f(n) es cualquier función de n calculada en tiempo polinomial, y n es el número de vértices del gráfico [10] .

Hay un algoritmo parametrizado que encuentra la solución óptima al GSGM en un gráfico con un ancho de árbol acotado . Por lo tanto, tanto el problema de la oruga que se contrae como el problema de la oruga que se contrae mínimamente tienen algoritmos de tiempo lineal si el gráfico es plano externo , secuencial paralelo o el gráfico de Halin [10] .

Aplicaciones

Las orugas se utilizan en la teoría de grafos químicos para representar la estructura molecular de los hidrocarburos bencenoides . En esta representación, las moléculas forman orugas, en las que cada arista corresponde a un anillo de 6 átomos de carbono, y dos aristas inciden en un vértice si los anillos de benceno correspondientes pertenecen a una secuencia de anillos conectados linealmente. El-Bazil escribe: "Es sorprendente que casi todos los gráficos que juegan un papel importante en lo que ahora se llama "teoría de gráficos químicos" estén asociados con gráficos de oruga". En este contexto, los gráficos de oruga también se conocen como árboles benzoides o árboles de Gutmann , por el trabajo de Ivan Gutman en esta área [2] [11] [12] .

Notas

  1. ↑ 1 2 3 Harary, Schwenk, 1973 , pág. 359–365.
  2. ↑ 1 2 3 El-Basil, 1987 , p. 153–174.
  3. ↑ Harary, Schwenk, 1973 .
  4. ↑ 1 2 3 4 5 Harary, Schwenk, 1971 , pág. 138–140.
  5. ↑ Harary, Schwenk, 1972 , pág. 203–209.
  6. ↑ Raychaudhuri, 1995 , pág. 299–306.
  7. ↑ 1 2 Proskurowski, Telle, 1999 , p. 167–176.
  8. ↑ Eckhoff, 1993 , pág. 117–127.
  9. ↑ Weisstein, Eric W. Lobster  en el sitio web de Wolfram MathWorld .
  10. ↑ 12 Josravani , 2011 .
  11. ↑ Gutman, 1977 , pág. 309–315.
  12. ↑ El-Basil, 1990 , p. 273–289.

Literatura

Enlaces