Árbol de Trémaux - Trémaux tree

En teoría de grafos , un árbol Trémaux de un grafo no dirigido G es un árbol de expansión de G , enraizado en uno de sus vértices, con la propiedad de que cada dos vértices adyacentes en G están relacionados entre sí como antepasado y descendiente en el árbol. Todos los árboles de búsqueda en profundidad y todos los caminos hamiltonianos son árboles Trémaux. Los árboles de Trémaux llevan el 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 . También se les ha llamado árboles de expansión normales , especialmente en el contexto de gráficos infinitos.

En gráficos finitos, aunque la búsqueda en profundidad en sí misma es inherentemente secuencial, los árboles de Trémaux pueden construirse mediante un algoritmo paralelo aleatorio en la clase de complejidad RNC . Se pueden usar para definir la profundidad de árbol de un gráfico y como parte de la prueba de planaridad izquierda-derecha para probar si un gráfico es plano . Una caracterización de los árboles de Trémaux en la lógica monádica de segundo orden de los gráficos permite que las propiedades de los gráficos que involucran orientaciones sean reconocidas de manera eficiente para gráficos de ancho de árbol acotado usando el teorema de Courcelle .

No todos los gráficos infinitos conectados tienen un árbol de Trémaux, y los gráficos que los tienen pueden caracterizarse por sus menores prohibidos . Existe un árbol de Trémaux en cada grafo conectado con muchos vértices numerables, incluso cuando una forma infinita de búsqueda en profundidad no lograría explorar todos los vértices del grafo. En un gráfico infinito, un árbol de Trémaux debe tener exactamente un camino infinito para cada extremo del gráfico, y la existencia de un árbol de Trémaux caracteriza los gráficos cuyas terminaciones topológicas, formadas por la adición de un punto en el infinito para cada extremo, son espacios métricos .

Ejemplo

En el gráfico que se muestra a continuación, el árbol con las aristas 1–3, 2–3 y 3–4 es un árbol de Trémaux cuando tiene sus raíces en el vértice 1 o en el vértice 2: todas las aristas de la gráfica pertenecen al árbol excepto la arista 1–2, que (para estas opciones 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 antepasados ​​y descendientes entre sí.

En gráficos finitos

Existencia

Cada grafo no dirigido conectado finito tiene al menos un árbol Trémaux. Se puede construir un árbol de este tipo realizando una búsqueda en profundidad y conectando cada vértice (que no sea el vértice inicial de la búsqueda) con el vértice anterior desde el que se descubrió. El á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 que alcanzará la búsqueda, entonces v debe pertenecer al subárbol que desciende de u en el árbol de búsqueda en profundidad, porque la búsqueda necesariamente descubrirá v mientras está explorando este subárbol, ya sea desde uno de los otros vértices del subárbol o, en su defecto, desde u directamente. Cada árbol de Trémaux finito se puede generar como un árbol de búsqueda de profundidad primero: si T es un árbol de Trémaux de un gráfico finito, y una búsqueda de profundidad primero explora los hijos en T de cada vértice antes de explorar cualquier otro vértice, necesariamente generar T como su árbol de búsqueda en profundidad.

Construcción paralela

Es P-completo encontrar el árbol de 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. 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 coincidencias perfectas de peso mínimo en gráficos ponderados 0-1. En 1997, se desconocía si la construcción del árbol de Trémaux podría realizarse mediante un algoritmo paralelo determinista, en la clase de complejidad NC . Si se pueden encontrar coincidencias en Carolina del Norte, también se pueden encontrar los árboles Trémaux.

Expresión lógica

Es posible expresar la propiedad de que un conjunto T de aristas con una elección de vértice raíz r forma un árbol de Trémaux, en la lógica monádica de segundo orden de los gráficos , y más específicamente en la forma de esta lógica denominada MSO ₂ , que permite cuantificación sobre conjuntos de vértices y aristas. Esta propiedad se puede expresar como la conjunción de las siguientes propiedades:

• El gráfico está conectado por los bordes en T . Esto se puede expresar lógicamente como la afirmación de que, para cada subconjunto propio no vacío de los vértices del gráfico, existe una arista en T con exactamente un punto final en el subconjunto dado.
• T es acíclico. Esto se puede expresar lógicamente como la afirmación de que no existe un subconjunto no vacío C de T para el que cada vértice es incidente a cero o dos bordes de C .
• Cada borde e no en T se conecta un par de vértices en ancestro-descendiente T . Esto es cierto cuando ambos extremos de correo pertenecen a una ruta en T . Puede expresarse lógicamente como el enunciado de que, para todos los bordes e , existe un subconjunto P de T tal que exactamente dos vértices, uno de ellos r , inciden en un solo borde de P , y tal que ambos extremos de e son incidente a al menos un borde de P .

Una vez que se ha identificado un árbol de Trémaux de esta manera, se puede describir una orientación del gráfico dado, también en lógica monádica de segundo orden, especificando el conjunto de aristas cuya orientación es desde el extremo ancestral al extremo descendiente. Los bordes restantes fuera de este conjunto deben orientarse en la otra dirección. Esta técnica permite especificar las propiedades de los gráficos que involucran orientaciones en la lógica monádica de segundo orden, lo que permite probar estas propiedades de manera eficiente en gráficos de ancho de árbol acotado utilizando el teorema de Courcelle .

Propiedades relacionadas

Si un gráfico tiene una ruta hamiltoniana , esa ruta (enraizada en uno de sus extremos) también es un árbol de Trémaux. Los gráficos no dirigidos para los que cada árbol de Trémaux tiene esta forma son los gráficos de ciclo , los gráficos completos y los gráficos bipartitos completos equilibrados .

Los árboles de Trémaux están estrechamente relacionados con el concepto de profundidad de árbol . La profundidad del árbol de un gráfico G se puede definir como el número más pequeño d, de modo que G se puede incrustar como un subgráfico de un gráfico H que tiene un árbol Trémaux T de profundidad d . La profundidad del árbol acotada, en una familia de gráficos, es equivalente a la existencia de un camino que no puede ocurrir como un gráfico menor de los gráficos de la familia. Muchos problemas computacionales difíciles en gráficos tienen algoritmos que son manejables con parámetros fijos cuando se parametrizan por la profundidad del árbol de sus entradas.

Los árboles de Trémaux también juegan un papel clave en el criterio de planaridad de Fraysseix-Rosenstiehl para probar si un gráfico dado es plano . De acuerdo con este criterio, un gráfico G es plano si, para un árbol Trémaux dado T de G , las aristas restantes se pueden colocar de manera consistente a la izquierda o la derecha del árbol, sujeto a restricciones que impiden aristas con la misma colocación de cruzarse entre sí.

En gráficos infinitos

Existencia

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 uno: un árbol de expansión normal en un gráfico completo solo puede ser una ruta, pero una ruta solo tiene un número contable de vértices. Sin embargo, cada gráfico en un conjunto contable de vértices tiene un árbol de expansión normal.

Incluso en gráficos contables, es posible que una búsqueda en profundidad primero no tenga éxito en la exploración de todo el gráfico, 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 elementos secundarios (y no ambos).

Menores

Si un gráfico infinito G tiene un árbol de expansión normal, lo mismo ocurre con todos los conectado menor gráfica de G . De esto se deduce que los gráficos que tienen árboles de expansión normales tienen una caracterización por menores prohibidos . Una de las dos clases de menores prohibidos consiste en gráficos bipartitos en los que un lado de la bipartición es contable, el otro lado es incontable y cada vértice tiene un grado infinito. La otra clase de menores prohibidos consiste en ciertos gráficos derivados de árboles Aronszajn .

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 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 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 entre sí en el orden menor.

Extremos y metrizabilidad

Los árboles de expansión normales también están estrechamente relacionados con los extremos de un gráfico infinito, clases de equivalencia de caminos infinitos que, intuitivamente, van al infinito en la misma dirección. Si un gráfico tiene un árbol de expansión normal, este árbol debe tener exactamente una ruta infinita para cada uno de los extremos del gráfico.

Se puede usar un gráfico infinito para formar un espacio topológico al ver el gráfico en sí como un complejo simple y agregar un punto en el infinito para cada extremo del gráfico. Con esta topología, un gráfico tiene un árbol de expansión normal si y solo si su conjunto de vértices se puede descomponer 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.

Referencias