Gráfico de árbol con todos los nodos dentro de la distancia 1 desde la ruta central
Una oruga
En teoría de grafos , una oruga o árbol de orugas es un árbol en el que todos los vértices están dentro de la distancia 1 de un camino central .
Las orugas se estudiaron por primera vez en una serie de artículos de Harary y Schwenk. El nombre fue sugerido por Arthur Hobbs . [1] [2] Como escriben coloridamente Harary y Schwenk (1973): "Una oruga es un árbol que se metamorfosea en un camino cuando se le quita el capullo de sus extremos". [1]
Caracterizaciones equivalentes
Todas las siguientes caracterizaciones describen los árboles de orugas:
Son los árboles para los cuales la eliminación de las hojas y los bordes incidentes produce 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 que no son hojas.
Son los árboles que no contienen como subgrafo el grafo formado al reemplazar cada arista del grafo estrella K 1,3 por un camino de longitud dos. [3]
Son los gráficos conectados que se pueden dibujar con sus vértices en dos rectas paralelas, con aristas representadas como segmentos de recta que no se cruzan y que tienen un punto final en cada recta. [3] [4]
Son los á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 en la secuencia está a una distancia de uno o dos entre sí, y los árboles que no son orugas no tienen tal secuencia. Se puede obtener un ciclo de este tipo dibujando la oruga en dos líneas paralelas y concatenando la secuencia de vértices en una línea con el inverso de la secuencia en la otra línea. [3]
Son los árboles cuyos gráficos lineales contienen una trayectoria hamiltoniana ; dicho camino se puede obtener ordenando los bordes 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 terminación hamiltoniana ) es igual al número mínimo de orugas de bordes disjuntos que los bordes del árbol pueden ser descompuesto en. [5]
Son los gráficos conectados de ancho de ruta uno. [6]
Son gráficos 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 gráfico cordal con exactamente n - k camarillas máximas , cada una de las cuales contiene k + 1 vértices; en un k -árbol que no es en sí mismo una camarilla ( k + 1 ) , cada camarilla máxima separa el gráfico en dos o más componentes, o contiene un vértice de una sola hoja, un vértice que pertenece a una sola camarilla máxima. Un k -camino es un k -árbol con como máximo dos hojas, y una k -oruga es un k -árbol que puede dividirse en un k -camino y algunas k -hojas, cada una adyacente a un separador k -clique del k -camino. En esta terminología, una 1 oruga es lo mismo que un árbol de oruga, y k -orugas son los gráficos de borde máximo con ancho de ruta k . [6]
Un gráfico de langosta es un árbol en el que todos los vértices están a una distancia de 2 de un camino central . [9]
Enumeración
Las orugas proporcionan uno de los raros problemas de enumeración de gráficos para los cuales 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, ... el número de orugas de n vértices es
Encontrar una oruga que se expanda en un gráfico es NP-completo . Un problema de optimización relacionado es el problema de Caterpillar de expansión mínima (MSCP), donde un gráfico tiene costos duales en sus bordes y el objetivo es encontrar un árbol de oruga que abarque el gráfico de entrada y tenga el costo general más pequeño. 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 rol como arista de 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 gráfico. [10]
Existe un algoritmo parametrizado que encuentra una solución óptima para el MSCP en gráficos de ancho de árbol acotados . Entonces, tanto el problema de Spanning Caterpillar como el MSCP tienen algoritmos de tiempo lineal si un gráfico es un plano externo, una serie paralela o un gráfico de Halin . [10]
Aplicaciones
Los árboles de oruga se han utilizado en la teoría química de grafos para representar la estructura de las moléculas de hidrocarburos bencenoide . 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 pertenecen a una secuencia de anillos conectados de extremo a extremo en la estructura molecular. estructura. El-Basil (1987) escribe: "Es sorprendente que casi todos los grafos que jugaron un papel importante en lo que hoy se llama "teoría química de grafos" puedan estar relacionados con árboles de orugas". En este contexto, los árboles de oruga también se conocen como árboles bencenoideos y árboles de Gutman , por los trabajos de Iván Gutman en esta zona. [2] [11] [12]
Referencias
^ abc Harary, Frank ; Schwenk, Allen J. (1973), "El número de orugas" (PDF) , Matemáticas discretas , 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 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 finalización 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 e informática 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 elegantes [1]
^ ab Khosravani, Masoud (2011). Búsqueda de orugas óptimas en general y gráficos de ancho de árbol acotados (Ph.D.). Universidad de Auckland.
^ Gutman, Ivan (1977), "Propiedades topológicas de los sistemas bencenoideos", Theoretica Chimica Acta , 45 (4): 309–315, doi :10.1007/BF00554539.
^ El-Basil, Sherif (1990), "Árboles Caterpillar (Gutman) en la teoría química de grafos", en Gutman, I.; Cyvin, SJ (eds.), Avances en la teoría de los hidrocarburos bencenoideos , Temas de la química actual, vol. 153, págs. 273–289, doi :10.1007/3-540-51505-4_28, S2CID 91687862.
