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 de manera pintoresca Harary y Schwenk (1973), "Una oruga es un árbol que se metamorfosea en un camino cuando se le quita el capullo de puntos finales". [1]
Caracterizaciones equivalentes
Las siguientes caracterizaciones describen todos los árboles de orugas:
Son los árboles a los que eliminando las hojas y los bordes incidentes se obtiene un gráfico de trayectoria . [2] [3]
Son los árboles en los que existe un camino que contiene cada vértice de grado dos o más.
Son los árboles en los que cada vértice de grado al menos tres tiene como máximo dos vecinos no hojas.
Son los árboles que no contienen como subgrafo el grafo formado al sustituir cada arista del grafo estrella K 1,3 por un camino de longitud dos. [3]
Son los 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 punto final en cada línea. [3] [4]
Son los árboles cuyo cuadrado es un grafo hamiltoniano . Es decir, en una oruga existe una sucesión cíclica de todos los vértices en la que cada par de vértices adyacentes de la sucesión se encuentra a una distancia de uno o dos entre sí, y los árboles que no son orugas no tienen tal sucesión. Un ciclo de este tipo puede obtenerse dibujando la oruga sobre dos líneas paralelas y concatenando la sucesión de vértices de una línea con la inversa de la sucesión de la otra línea. [3]
Son los árboles cuyos gráficos lineales contienen un camino hamiltoniano ; dicho camino puede obtenerse ordenando las aristas en un dibujo de dos líneas del árbol. De manera más general, el número de aristas que deben agregarse al gráfico lineal 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 aristas en las que se pueden descomponer las aristas del árbol. [5]
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]
Generalizaciones
Un k -árbol es un grafo cordal con exactamente n − k camarillas maximalistas , cada una conteniendo k + 1 vértices; en un k -árbol que no es en sí mismo una ( k + 1)-camarilla , cada camarilla maximalista o bien separa el grafo en dos o más componentes, o bien contiene un único vértice de hoja, un vértice que pertenece a una única camarilla maximalista. Un k -camino es un k -árbol con como máximo dos hojas, y una k -oruga es un k -árbol que puede ser dividido 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 de orugas, y las k -orugas son los grafos de aristas maximalistas con ancho de camino k . [6]
Un gráfico de langosta es un árbol en el que todos los vértices están dentro de la distancia 2 de un camino central . [9]
Enumeración
Las orugas proporcionan uno de los raros problemas de enumeración de gráficos 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]
Para n = 1, 2, 3, ... los números de orugas de n vértices son
Encontrar una oruga que se expande en un grafo es NP-completo . Un problema de optimización relacionado es el Problema de la Oruga que se Expande Mínimamente (MSCP), donde un grafo tiene costos duales sobre sus aristas y el objetivo es encontrar un árbol de oruga que se expanda al grafo de entrada y tenga el menor costo general. 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 en función de su papel como arista de hoja o una 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 acotado . Por lo tanto, tanto el problema de la oruga de expansión como el MSCP tienen algoritmos de tiempo lineal si un grafo es un plano exterior, un grafo serie-paralelo o un grafo de Halin . [10]
Aplicaciones
Los árboles de 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 siempre que los anillos correspondientes pertenezcan a una secuencia de anillos conectados de extremo a 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 de oruga". En este contexto, los árboles de 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]
Referencias
^ abc Harary, Frank ; Schwenk, Allen J. (1973), "El número de orugas" (PDF) , Discrete Mathematics , 6 (4): 359–365, doi : 10.1016/0012-365x(73)90067-8 , hdl : 2027.42/33977.
^ abc El-Basil, Sherif (1987), "Aplicaciones de los árboles de oruga en química y física", Journal of Mathematical Chemistry , 1 (2): 153–174, doi :10.1007/BF01205666, S2CID 121322252.
^ abcd Harary, Frank ; Schwenk, Allen J. (1971), "Árboles con cuadrado hamiltoniano", Mathematika , 18 : 138–140, doi :10.1112/S0025579300008494, hdl : 2027.42/153141.
^ Harary, Frank ; Schwenk, Allen J. (1972), "Un nuevo número de cruce para gráficos bipartitos", Utilitas Math. , 1 : 203–209.
^ Raychaudhuri, Arundhati (1995), "El número de intervalo total de un árbol y el número de completitud hamiltoniano de su gráfico lineal", Information Processing Letters , 56 (6): 299–306, doi :10.1016/0020-0190(95)00163-8.
^ ab Proskurowski, Andrzej; Telle, Jan Arne (1999), "Clases de gráficos con modelos de intervalo restringido" (PDF) , Matemáticas discretas y ciencias de la computación teórica , 3 : 167–176.
^ Eckhoff, Jürgen (1993), "Gráficos de intervalos extremos", Journal of Graph Theory , 17 (1): 117–127, doi :10.1002/jgt.3190170112.
^ E. Guseinov, Patrones de matrices de adyacencia y otra prueba más de que las orugas son gráciles [1]
^ ab Khosravani, Masoud (2011). Búsqueda de orugas óptimas en gráficos generales y de ancho de árbol acotado (Ph.D.). Universidad de Auckland.
^ Gutman, Ivan (1977), "Propiedades topológicas de los sistemas bencenoides", Theoretica Chimica Acta , 45 (4): 309–315, doi :10.1007/BF00554539.
^ El-Basil, Sherif (1990), "Árboles Caterpillar (Gutman) en la teoría de grafos químicos", en Gutman, I.; Cyvin, SJ (eds.), Avances en la teoría de hidrocarburos bencenoides , Temas de química actual, vol. 153, págs. 273–289, doi :10.1007/3-540-51505-4_28, ISBN978-3-540-51505-0, Número de identificación del sujeto 91687862.
