En teoría de grafos , un árbol Trémaux de un grafo no dirigido es un tipo de árbol de expansión , que generaliza los árboles de búsqueda en profundidad . Se definen por la propiedad de que cada arista de conecta un par ancestro-descendiente en el árbol. Los árboles Trémaux reciben su nombre de Charles Pierre Trémaux, un autor francés del siglo XIX que utilizó una forma de búsqueda en profundidad como estrategia para resolver laberintos . [1] [2] También se les ha llamado árboles de expansión normales , especialmente en el contexto de grafos infinitos. [3] [4]
Todos los árboles de búsqueda en profundidad y todos los caminos hamiltonianos son árboles Trémaux. En los grafos finitos, cada árbol Trémaux es un árbol de búsqueda en profundidad, pero aunque la búsqueda en profundidad en sí misma es inherentemente secuencial, los árboles Trémaux pueden construirse mediante un algoritmo paralelo aleatorio en la clase de complejidad RNC . Pueden usarse para definir la profundidad del árbol de un grafo y como parte de la prueba de planaridad izquierda-derecha para probar si un grafo es un grafo planar . Una caracterización de los árboles Trémaux en la lógica monádica de segundo orden de los grafos permite que las propiedades de los grafos que involucran orientaciones se reconozcan de manera eficiente para grafos de ancho de árbol acotado utilizando el teorema de Courcelle .
No todo grafo infinito conexo tiene un árbol de Trémaux, y no todo árbol de Trémaux infinito es un árbol de búsqueda en profundidad. Los grafos que tienen árboles de Trémaux pueden caracterizarse por menores prohibidos . Un árbol de Trémaux infinito debe tener exactamente un camino infinito para cada extremo del grafo, y la existencia de un árbol de Trémaux caracteriza a los grafos cuyas terminaciones topológicas, formadas añadiendo un punto en el infinito para cada extremo, son espacios métricos .
Un árbol Trémaux, para un grafo , es un árbol de expansión con la propiedad de que, para cada arista en , uno de los dos puntos finales y es un ancestro del otro. Para ser un árbol de expansión, solo debe usar aristas de , e incluir cada vértice, con un camino finito único entre cada par de vértices. Además, para definir la relación ancestro-descendiente en este árbol, uno de sus vértices debe designarse como su raíz.
Si un grafo finito tiene un camino hamiltoniano , entonces al enraizar ese camino en uno de sus dos puntos finales se obtiene un árbol de Trémaux. Para un camino de este tipo, cada par de vértices es un par ancestro-descendiente.
En el gráfico que se muestra a continuación, el árbol con aristas 1–3, 2–3 y 3–4 es un árbol Trémaux cuando tiene su raíz en el vértice 1 o en el vértice 2: cada arista del gráfico pertenece al árbol excepto la arista 1–2, que (para estas elecciones de raíz) conecta un par ancestro-descendiente.
Sin embargo, enraizar el mismo árbol en el vértice 3 o en el vértice 4 produce un árbol enraizado que no es un árbol Trémaux, porque con esta raíz 1 y 2 ya no son ancestro y descendiente uno del otro.
Todo grafo no dirigido y conexo finito tiene al menos un árbol Trémaux. [4] Se puede construir un árbol de este tipo realizando una búsqueda en profundidad y conectando cada vértice (excepto el vértice inicial de la búsqueda) con el vértice anterior a partir del cual se descubrió. El árbol construido de esta manera se conoce como árbol de búsqueda en profundidad. Si es una arista arbitraria en el grafo, y es el anterior de los dos vértices a alcanzar por la búsqueda, entonces debe pertenecer al subárbol que desciende de en el árbol de búsqueda en profundidad, porque la búsqueda descubrirá necesariamente mientras explora este subárbol, ya sea a partir de uno de los otros vértices en el subárbol o, en su defecto, directamente. Todo árbol Trémaux finito se puede generar como un árbol de búsqueda en profundidad: Si es un árbol Trémaux de un grafo finito, y una búsqueda en profundidad explora los hijos en de cada vértice antes de explorar cualquier otro vértice, necesariamente se generará como su árbol de búsqueda en profundidad.
Es P-completo encontrar el árbol Trémaux que se encontraría mediante un algoritmo de búsqueda secuencial en profundidad, en el que los vecinos de cada vértice se buscan en orden por sus identidades. [5] Sin embargo, es posible encontrar un árbol Trémaux diferente mediante un algoritmo paralelo aleatorio , lo que demuestra que la construcción de árboles Trémaux pertenece a la clase de complejidad RNC . El algoritmo se basa en otro algoritmo paralelo aleatorio, para encontrar emparejamientos perfectos de peso mínimo en grafos ponderados 0-1. [6] A partir de 1997, seguía siendo desconocido si la construcción del árbol Trémaux podía realizarse mediante un algoritmo paralelo determinista, en la clase de complejidad NC . [7] Si se pueden encontrar emparejamientos en NC, entonces también se pueden encontrar árboles Trémaux. [6]
Es posible expresar la propiedad de que un conjunto de aristas con una elección de vértice raíz forma un árbol de Trémaux, en la lógica monádica de segundo orden de grafos , y más específicamente en la forma de esta lógica llamada MSO 2 , que permite la cuantificación tanto sobre conjuntos de vértices como de aristas. Esta propiedad puede expresarse como la conjunción de las siguientes propiedades:
Una vez que se ha identificado un árbol Trémaux de esta manera, se puede describir una orientación del grafo dado, también en lógica monádica de segundo orden, especificando el conjunto de aristas cuya orientación va desde el punto final ancestral hasta el punto final descendiente. Las aristas restantes fuera de este conjunto deben estar orientadas en la otra dirección. Esta técnica permite especificar las propiedades de grafos que involucran orientaciones en lógica monádica de segundo orden, lo que permite probar estas propiedades de manera eficiente en grafos de ancho de árbol acotado utilizando el teorema de Courcelle . [8]
Si un grafo tiene un camino hamiltoniano , entonces ese camino (con raíz en uno de sus puntos finales) también es un árbol de Trémaux. Los grafos no dirigidos para los cuales cada árbol de Trémaux tiene esta forma son los grafos cíclicos , los grafos completos y los grafos bipartitos completos balanceados . [9]
Los árboles Trémaux están estrechamente relacionados con el concepto de profundidad de árbol . La profundidad de árbol de un grafo se puede definir como el número más pequeño para el cual existe un grafo , con un árbol Trémaux de altura , tal que es un subgrafo de . La profundidad de árbol acotada, en una familia de grafos, es equivalente a la existencia de un camino que no puede ocurrir como un grafo menor de los grafos de la familia. Muchos problemas computacionales difíciles en grafos tienen algoritmos que son manejables con parámetros fijos cuando se parametrizan por la profundidad de árbol de sus entradas. [10]
Los árboles Trémaux también desempeñan un papel clave en el criterio de planaridad de Fraysseix–Rosenstiehl para comprobar si un grafo dado es planar . Según este criterio, un grafo es planar si, para un árbol Trémaux dado de , las aristas restantes se pueden colocar de forma consistente a la izquierda o a la derecha del árbol, sujetas a restricciones que impidan que las aristas con la misma ubicación se crucen entre sí. [11]
No todos los grafos infinitos tienen un árbol de expansión normal. Por ejemplo, un grafo completo sobre un conjunto incontable de vértices no tiene uno: un árbol de expansión normal en un grafo completo solo puede ser un camino, pero un camino solo tiene un número contable de vértices. Sin embargo, todo grafo conexo sobre un conjunto contable de vértices sí tiene un árbol de expansión normal. [3] [4]
Incluso en gráficos contables, una búsqueda en profundidad podría no tener éxito en explorar finalmente todo el gráfico, [3] y no todos los árboles de expansión normales pueden generarse mediante una búsqueda en profundidad: para ser un árbol de búsqueda en profundidad, un árbol de expansión normal contable debe tener solo una ruta infinita o un nodo con infinitos hijos (y no ambos).
Si un grafo infinito tiene un árbol de expansión normal, también lo tiene todo grafo conexo menor de . De esto se deduce que los grafos que tienen árboles de expansión normales tienen una caracterización por menores prohibidos . Una de las dos clases de menores prohibidos consiste en grafos bipartitos en los que un lado de la bipartición es contable, el otro lado es incontable y cada vértice tiene grado infinito. La otra clase de menores prohibidos consiste en ciertos grafos derivados de árboles de Aronszajn . [12]
Los detalles de esta caracterización dependen de la elección de la axiomatización de la teoría de conjuntos utilizada para formalizar las matemáticas. En particular, en los modelos de teoría de conjuntos para los que el axioma de Martin es verdadero y la hipótesis del continuo es falsa, la clase de grafos bipartitos en esta caracterización puede ser reemplazada por un único menor prohibido. Sin embargo, para los modelos en los que la hipótesis del continuo es verdadera, esta clase contiene grafos que son incomparables entre sí en el orden de los menores. [13]
Los árboles de expansión normales también están estrechamente relacionados con los extremos de un grafo infinito, clases de equivalencia de caminos infinitos que, intuitivamente, van al infinito en la misma dirección. Si un grafo tiene un árbol de expansión normal, este árbol debe tener exactamente un camino infinito para cada uno de los extremos del grafo. [14]
Un grafo infinito puede utilizarse para formar un espacio topológico al considerar el grafo en sí como un complejo simplicial y agregar un punto en el infinito para cada extremo del grafo. Con esta topología, un grafo tiene un árbol de expansión normal si y solo si su conjunto de vértices puede descomponerse en una unión contable de conjuntos cerrados . Además, este espacio topológico puede representarse mediante un espacio métrico si y solo si el grafo tiene un árbol de expansión normal. [14]
