árbol oruga

En teoría de grafos , una oruga o árbol oruga es un árbol en el que todos los vértices están a una distancia de 1 de un camino central .

Las orugas fueron estudiadas por primera vez en una serie de artículos de Harary y Schwenk. El nombre fue sugerido por Arthur Hobbs . ^{[ 1 ] [ 2 ]} Como escriben Harary y Schwenk (1973) de forma elocuente: «Una oruga es un árbol que se transforma en un camino cuando se le quita su capullo de extremos». ^{[ 1 ]}

Las siguientes caracterizaciones describen a los árboles oruga:

• Son los árboles para los cuales la eliminación de las hojas y las aristas incidentes produce un grafo de caminos . ^{[ 2 ] [ 3 ]}
• Son los árboles en los que existe un camino que contiene todos los vértices de grado dos o superior.
• Son árboles en los que cada vértice de grado al menos tres tiene como máximo dos vecinos que no son hojas.
• Son los árboles que no contienen como subgrafo el grafo formado al reemplazar cada arista en el grafo estrella K _1,3 por un camino de longitud dos. ^{[ 3 ]}
• Son grafos conexos que se pueden dibujar con sus vértices en dos líneas paralelas, con aristas representadas como segmentos de línea que no se cruzan y que tienen un extremo en cada línea. ^{[ 3 ] [ 4 ]}
• Son árboles cuyo cuadrado es un grafo hamiltoniano . Es decir, en una oruga, existe una secuencia cíclica de todos los vértices en la que cada par de vértices adyacentes se encuentra a una distancia de uno o dos entre sí, y los árboles que no son orugas no tienen dicha secuencia. Un ciclo de este tipo se puede obtener dibujando la oruga en dos líneas paralelas y concatenando la secuencia de vértices de una línea con la secuencia inversa de la otra. ^{[ 3 ]}
• Son los árboles cuyos grafos de líneas contienen un camino hamiltoniano ; dicho camino se puede obtener ordenando las aristas en un dibujo de dos líneas del árbol. De forma más general, el número de aristas que deben añadirse al grafo de líneas de un árbol arbitrario para que contenga un camino hamiltoniano (el tamaño de su completitud hamiltoniana ) es igual al número mínimo de orugas disjuntas en las que se pueden descomponer las aristas del árbol. ^{[ 5 ]}
• Son los grafos conectados de ancho de camino uno. ^{[ 6 ]}
• Son los grafos de intervalos libres de triángulos conectados . ^{[ 7 ]}
• Son grafos de n vértices cuyas matrices de adyacencia se pueden escribir de tal manera que las de la parte triangular superior formen un camino de longitud n − 1 que comienza en la esquina superior derecha y va hacia abajo o hacia la izquierda. ^{[ 8 ]}

Un k -árbol es un grafo cordal con exactamente n − k camarillas maximales , cada una con k + 1 vértices; en un k -árbol que no es una ( k + 1)-camarilla , cada camarilla maximal separa el grafo en dos o más componentes, o contiene un único vértice hoja, un vértice que pertenece a una sola camarilla maximal. Un k -camino es un k -árbol con como máximo dos hojas, y una k -oruga es un k -árbol que se puede particionar en un k -camino y algunas k -hojas, cada una adyacente a una k -camarilla separadora del k -camino. En esta terminología, una 1-oruga es lo mismo que un árbol oruga, y las k -orugas son los grafos con aristas máximas y ancho de camino k . ^{[ 6 ]}

Un grafo de langosta es un árbol en el que todos los vértices están a una distancia de  2 de un camino central . ^{[ 9 ]}

Las orugas proporcionan uno de los raros problemas de enumeración de grafos para los que se puede dar una fórmula precisa: cuando n  ≥  3, el número de orugas con n vértices sin etiquetar es ^{[ 1 ]}

${\displaystyle 2^{n-4}+2^{\lfloor (n-4)/2\rfloor }.}$

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

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

Encontrar una oruga que abarque todo el grafo es un problema NP-completo . Un problema de optimización relacionado es el Problema de la Oruga de Expansión Mínima (MSCP), donde un grafo tiene costos duales en sus aristas y el objetivo es encontrar un árbol oruga que abarque todo el grafo de entrada y tenga el menor costo total. Aquí, el costo de la oruga se define como la suma de los costos de sus aristas, donde cada arista toma uno de los dos costos según su rol como arista hoja o interna. No existe un algoritmo de aproximación f(n) para el MSCP a menos que P = NP . Aquí, f(n) es cualquier función computable en tiempo polinomial de n, el número de vértices de un grafo. ^{[ 10 ]}

Existe un algoritmo parametrizado que encuentra una solución óptima para el MSCP en grafos de ancho de árbol limitado . Por lo tanto, tanto el Problema de la Oruga Expansora como el MSCP tienen algoritmos de tiempo lineal si un grafo es un grafo planar exterior, un grafo serie-paralelo o un grafo de Halin . ^{[ 10 ]}

Los árboles oruga se han utilizado en la teoría de grafos químicos para representar la estructura de las moléculas de hidrocarburos bencenoides . En esta representación, se forma una oruga en la que cada arista corresponde a un anillo de 6 carbonos en la estructura molecular, y dos aristas inciden en un vértice cuando los anillos correspondientes pertenecen a una secuencia de anillos conectados extremo con extremo en la estructura. El-Basil (1987) escribe: «Es sorprendente que casi todos los grafos que desempeñaron un papel importante en lo que ahora se llama "teoría de grafos químicos" puedan estar relacionados con los árboles oruga». En este contexto, los árboles oruga también se conocen como árboles bencenoides y árboles de Gutman , en honor al trabajo de Ivan Gutman en esta área. ^{[ 2 ] [ 11 ] [ 12 ]}

• Weisstein, Eric W. "Oruga" . MathWorld .