En teoría de grafos , una oruga o un árbol de oruga 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 A. Hobbs . [1] [2] Como Harary y Schwenk (1973) escriben de manera colorida, "Una oruga es un árbol que se metamorfosea en un camino cuando se quita su capullo de extremos". [1]
Caracterizaciones equivalentes
Todas las siguientes caracterizaciones describen los árboles de oruga:
- Son los árboles para los que la eliminación de las hojas y los bordes incidentes produce un gráfico de ruta . [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 gráfico formado al reemplazar cada arista del gráfico estelar 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 líneas paralelas, con los bordes representados 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 gráfico 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 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 reverso de la secuencia en la otra línea. [3]
- Son los árboles cuyas gráficas lineales contienen un camino hamiltoniano ; tal trayectoria puede obtenerse ordenando los bordes en un dibujo de dos líneas del árbol. De manera más general, el número de bordes que deben agregarse al gráfico de líneas 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 disjuntas de bordes que los bordes del árbol pueden descomponerse en. [5]
- Son los gráficos conectados del ancho de ruta uno. [6]
- Son los gráficos de intervalos sin triángulos conectados . [7]
- Son grafos de n vértices cuyas matrices de adyacencia se pueden escribir de tal forma que las de la parte triangular superior formen un camino de longitud n-1 comenzando en la esquina superior derecha y yendo hacia abajo o hacia la izquierda. [8]
Generalizaciones
Un árbol k es un grafo cordal con 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 o separa la gráfica en dos o más componentes, o contiene un solo vértice de hoja, un vértice que pertenece a una sola camarilla máxima. Un k -path es un k -árbol con un máximo de dos hojas, y una k -caterpillar es un k -árbol que se puede dividir en un k -path y algunas k -hojas, cada una adyacente a un separador k -clique de la k -ruta. En esta terminología, una oruga 1 es lo mismo que un árbol 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 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, ... el número de orugas n- vértice es
Complejidad computacional
Encontrar una oruga en expansión 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 sobre sus bordes y el objetivo es encontrar un árbol de oruga que abarque el gráfico de entrada y tenga el costo total más pequeño. Aquí, el costo de la oruga se define como la suma de los costos de sus bordes, donde cada borde toma uno de los dos costos en función de su función como borde de la hoja o interno. 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 polinómico de n, el número de vértices de una gráfica. [10]
Existe un algoritmo parametrizado que encuentra una solución óptima para el MSCP en gráficos de ancho de árbol acotado . Por tanto, tanto el problema de Spanning Caterpillar como el MSCP tienen algoritmos de tiempo lineal si una gráfica es un plano exterior, una serie paralela o una gráfica 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 borde corresponde a un anillo de 6 carbonos en la estructura molecular, y dos bordes 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 gráficos que desempeñaron un papel importante en lo que ahora se llama" teoría de los gráficos químicos "puedan estar relacionados con los árboles de oruga". En este contexto, los árboles de oruga también se conocen como árboles de benzenoid y árboles de Gutman , por el trabajo de Ivan Gutman en esta área. [2] [11] [12]
Referencias
- ^ a b c 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.
- ^ a b c 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.
- ^ a b c d Harary, Frank ; Schwenk, Allen J. (1971), "Trees with hamiltonian square", 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 terminación hamiltoniana de su gráfico de líneas", Information Processing Letters , 56 (6): 299-306, doi : 10.1016 / 0020-0190 (95) 00163 -8.
- ^ a b 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óricas , 3 : 167-176, archivado desde el original (PDF) en 2011-06-06 , recuperado en 2010 -05-07.
- ^ Eckhoff, Jürgen (1993), "Gráficos de intervalo extremo", 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]
- ^ Weisstein, Eric W. "Gráfico de langosta" . MathWorld .
- ^ a b Khosravani, Masoud (2011). Búsqueda de orugas óptimas en general y gráficos de ancho de árbol acotado (Ph.D.). Universidad de Auckland.
- ^ Gutman, Ivan (1977), "Propiedades topológicas de los sistemas benzenoides", Theoretica Chimica Acta , 45 (4): 309–315, doi : 10.1007 / BF00554539.
- ^ El-Basil, Sherif (1990), "Árboles de Caterpillar (Gutman) en la teoría de grafos químicos", en Gutman, I .; Cyvin, SJ (eds.), Advances in the Theory of Benzenoid Hydrocarbons , Topics in Current Chemistry, 153 , págs. 273–289, doi : 10.1007 / 3-540-51505-4_28.
enlaces externos
- Weisstein, Eric W. "Caterpillar" . MathWorld .