El árbol de Tremaux de un grafo no dirigido G es un árbol de expansión de raíces distinguidas de G con la propiedad de que dos vértices adyacentes cualesquiera en G están relacionados entre sí por una relación de ascendiente/descendiente. Todos los árboles de búsqueda primero en profundidad y todos los caminos hamiltonianos son árboles Tremo. Los árboles Tremaux llevan el nombre de Charles Pierre Tremaux, un autor francés del siglo XIX que usó una variación de la búsqueda en profundidad como estrategia de salida del laberinto [1] [2] . Los árboles de Tremaux también se denominan árboles de expansión normales , especialmente en el contexto de los gráficos infinitos [3] .
En gráficos finitos, aunque la búsqueda primero en profundidad es inherentemente secuencial, los árboles Tremo se pueden construir mediante un algoritmo paralelo aleatorio con clase de complejidad RNC . Los árboles tremo se pueden usar para determinar la profundidad del árbol de un gráfico y como parte de la prueba de planaridad para probar si un gráfico es plano . La descripción de los árboles de Tremo mediante una lógica de grafos unarios de segundo orden hace posible reconocer de manera eficiente las propiedades de los grafos dependientes de la orientación para grafos con un ancho de árbol limitado utilizando el teorema de Courcelle .
No todos los gráficos infinitos tienen un árbol Tremo, y los gráficos que no tienen dicho árbol pueden ser descritos por menores prohibidos . Existe un árbol Tremo en cualquier gráfico con un número contable de vértices, incluso si la variante de búsqueda infinita en profundidad no puede probar con éxito todos los vértices del gráfico. En un gráfico infinito, un árbol de Tremaux debe tener exactamente un camino infinito para cada rayo del gráfico, y la existencia de un árbol de Tremaux caracteriza a los gráficos cuyas terminaciones topológicas, formadas al agregar un punto en el infinito para cada rayo, son métricas . espacios _
En el gráfico que se muestra a continuación, un árbol con aristas 1 a 3, 2 a 3 y 3 a 4 es un árbol de Tremaux si su raíz es el vértice 1 o el vértice 2; cualquier arista del gráfico pertenece al árbol excepto la arista 1 a 2. , que (al seleccionar la raíz especificada) conecta un par antepasado-descendiente.
Sin embargo, si elegimos el nodo 3 o el nodo 4 como la raíz del mismo árbol, obtenemos un árbol enraizado que no es un árbol Tremo, porque con estas raíces los nodos 1 y 2 ya no serán un ancestro/descendiente.
Cualquier gráfico no dirigido finito conectado tiene al menos un árbol Tremo. Se puede construir un árbol de este tipo utilizando la búsqueda primero en profundidad y uniendo cada vértice (que no sea el vértice inicial de la búsqueda) con un vértice anterior desde el que se accedió al vértice actual. Un árbol construido de esta manera se conoce como árbol de búsqueda en profundidad. Si uv es un borde arbitrario en el gráfico y u es el primero de los dos vértices alcanzados por la búsqueda, entonces v debe pertenecer a un subárbol de los descendientes de u en el árbol de búsqueda en profundidad, ya que la búsqueda encontrará el vértice v según sea necesario observando ese árbol desde uno de los subárboles de vértices o directamente desde el vértice u . Cualquier árbol de Tremo finito se puede formar como un árbol primero en profundidad: si T es un árbol Tremo de un grafo finito, y Primero en profundidad Explore los descendientes de T de cada vértice antes de considerar cualquier otro vértice, esto necesariamente genera T como un árbol primero primero en profundidad del gráfico.
Un problema de búsqueda de árbol de Tremo es P-completo si se busca utilizando un algoritmo de búsqueda secuencial en profundidad en el que los vecinos de cada vértice se buscan en orden numérico [4] . Sin embargo, es posible encontrar otro árbol Tremo utilizando un algoritmo paralelo aleatorio , lo que muestra que la construcción de árboles Tremo pertenece a la clase de complejidad RNC [5] . Se desconoce si el árbol Tremo puede construirse mediante un algoritmo paralelo determinista perteneciente a la clase NC [6] .
Es posible expresar la propiedad de que el conjunto T de aristas con el vértice raíz elegido r forma un árbol de Tremaux, en la lógica de un lugar de grafos de segundo orden, y tal expresión se llama MSO 2 . Esta propiedad se puede expresar como una combinación de las siguientes propiedades:
Una vez que se ha identificado un árbol de Tremo de esta manera, se puede describir la orientación de un gráfico dado en una lógica de segundo orden de un lugar especificando un conjunto de bordes que están orientados de padre a hijo. Los bordes no incluidos en este conjunto deben estar orientados en la dirección opuesta. Esta técnica hace posible describir las propiedades de un gráfico usando la orientación en una lógica de segundo orden de un lugar, lo que hace posible probar estas propiedades de manera efectiva en gráficos con un ancho de árbol limitado usando el teorema de Courcelle [7] .
Si un gráfico tiene un camino hamiltoniano , entonces ese camino (con la raíz como uno de sus extremos) también es un árbol de Tremaux. El conjunto de grafos no dirigidos para los que cualquier árbol de Tremaux tiene esta forma consta de ciclos , grafos completos y grafos bipartitos completos balanceados [8] .
Los árboles de tremo están estrechamente relacionados con el concepto de profundidad de árbol . La profundidad del árbol de G se puede definir como el número más pequeño d tal que G se puede incrustar como un subgrafo de H que tiene un árbol de Tremaux T de profundidad d . La profundidad acotada de un árbol en una familia de grafos equivale a la existencia de un camino que no puede aparecer como grafo menor en la familia. Muchos problemas informáticos complejos en gráficos tienen algoritmos solucionables paramétricos fijos , si están parametrizados por la profundidad del árbol [9] .
Los árboles de Tremaux también juegan un papel clave en la prueba de planaridad de De Freysex-Rosenstil para probar si un gráfico es plano . De acuerdo con este criterio, un grafo G es plano si, para cualquier árbol Tremo T del grafo G , las aristas restantes se pueden colocar a la izquierda y a la derecha del árbol, lo que evita que las aristas se crucen (por esta razón, a veces se puede ver el nombre "algoritmo LP" - una abreviatura de Izquierda / Derecha) [10] [11] .
No todos los gráficos infinitos tienen un árbol de expansión normal. Por ejemplo, un gráfico completo en un conjunto incontable de vértices no tiene un árbol de expansión normal; dicho árbol en un gráfico completo solo puede ser una ruta, pero una ruta solo tiene un número contable de vértices. Sin embargo, cualquier gráfico en un conjunto contable de vértices tiene un árbol de expansión normal [3] .
Incluso en gráficos contables, la búsqueda primero en profundidad puede fallar al mirar el gráfico completo [3] , y no todos los árboles de expansión normales pueden generarse mediante la búsqueda primero en profundidad, para ser un árbol de búsqueda primero en profundidad, un árbol de expansión normal contable debe tener solo un camino infinito, o un nodo con un número infinito de vecinos (pero no ambos casos al mismo tiempo).
Si un gráfico infinito G tiene un árbol de expansión normal, también lo tiene cualquier menor conexo de G. Esto implica que los grafos con árboles de expansión normales pueden ser descritos por menores prohibidos . Una de las dos clases de menores prohibidos consiste en grafos bipartitos , en los que una parte es contable y la otra incontable, y cualquier vértice tiene grado infinito. Otra clase de menores prohibidos consiste en ciertos gráficos derivados de los árboles de Aronshine [12] .
Los detalles de esta descripción dependen de la elección de la axiomática de la teoría de conjuntos utilizada en la formalización de las matemáticas. En particular, en modelos de teoría de conjuntos en los que el axioma de Martin es verdadero pero la hipótesis del continuo no lo es, la clase de grafos bipartitos puede ser reemplazada por un solo menor prohibido. Sin embargo, para los modelos en los que la hipótesis del continuo es verdadera, esta clase contiene gráficos que son incomparables en el ordenamiento de los menores [13] .
Los árboles de expansión normales están estrechamente relacionados con los rayos un gráfico infinito, las clases de equivalencia de caminos infinitos que van en la misma dirección. Si un gráfico tiene un árbol de expansión normal, ese árbol debe tener exactamente un camino infinito para cada rayo del gráfico [14] .
Se puede usar un gráfico infinito para formar un espacio topológico tratando el gráfico en sí mismo como un complejo simplicial y agregando un punto en el infinito para cada rayo del gráfico. Con tal topología, un gráfico tiene un árbol de expansión normal si y solo si su conjunto de vértices se puede dividir en una unión contable de conjuntos cerrados . Además, este espacio topológico se puede representar mediante un espacio métrico si y solo si el gráfico tiene un árbol de expansión normal [14] .