Árbol de trémaux

Todo grafo no dirigido conexo finito tiene al menos un árbol de 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 desde el que se descubrió. El árbol construido de esta manera se conoce como árbol de búsqueda en profundidad. Si${\displaystyle uv}$es una arista arbitraria en el grafo, y${\displaystyle u}$es el primero de los dos vértices que se alcanzan mediante la búsqueda, entonces${\displaystyle v}$debe pertenecer al subárbol que desciende de${\displaystyle u}$en el árbol de búsqueda en profundidad, porque la búsqueda necesariamente descubrirá${\displaystyle v}$mientras explora este subárbol, ya sea desde uno de los otros vértices del subárbol o, en su defecto, desde${\displaystyle u}$directamente. Todo árbol de Trémaux finito puede generarse como un árbol de búsqueda en profundidad: Si${\displaystyle T}$es un árbol de Trémaux de un grafo finito, y una búsqueda en profundidad explora los hijos en${\displaystyle T}$de cada vértice antes de explorar cualquier otro vértice, necesariamente generará${\displaystyle T}$como su árbol de búsqueda en profundidad.

Es P-completo encontrar el árbol de Trémaux que se encontraría mediante un algoritmo de búsqueda en profundidad secuencial, en el que los vecinos de cada vértice se buscan en orden según sus identidades. ^{[ 5 ]} Sin embargo, es posible encontrar un árbol de Trémaux diferente mediante un algoritmo paralelo aleatorio , lo que demuestra que la construcción de árboles de 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 ]} Hasta 1997, se desconocía si la construcción de árboles de Trémaux podía realizarse mediante un algoritmo paralelo determinista, en la clase de complejidad NC . ^{[ 7 ]} Si se pueden encontrar emparejamientos en NC, también se pueden encontrar árboles de Trémaux. ^{[ 6 ]}

Es posible expresar la propiedad de que un conjunto${\displaystyle T}$de aristas con una elección de vértice raíz${\displaystyle r}$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 ₂ , que permite la cuantificación sobre conjuntos de vértices y aristas. Esta propiedad puede expresarse como la conjunción de las siguientes propiedades:

• El gráfico está conectado por las aristas en${\displaystyle 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 grafo, existe una arista en${\displaystyle T}$con exactamente un punto final en el subconjunto dado.
• ${\displaystyle T}$es acíclico. Esto se puede expresar lógicamente como la afirmación de que no existe un subconjunto no vacío.${\displaystyle C}$de${\displaystyle T}$para los cuales cada vértice es incidente a cero o dos aristas de${\displaystyle C}$.
• Cada borde${\displaystyle e}$no en${\displaystyle T}$conecta un par de vértices ancestro-descendiente en${\displaystyle T}$Esto es cierto cuando ambos extremos de${\displaystyle e}$pertenecer a un camino en${\displaystyle T}$Se puede expresar lógicamente como la afirmación de que, para todas las aristas${\displaystyle e}$, existe un subconjunto${\displaystyle P}$de${\displaystyle T}$de tal manera que exactamente dos vértices, uno de ellos${\displaystyle r}$, son incidentes a un único borde de${\displaystyle P}$y de tal manera que ambos extremos de${\displaystyle e}$son incidentes en al menos un borde de${\displaystyle P}$.

Una vez identificado un árbol de Trémaux de esta manera, se puede describir la 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 extremo ancestral hasta el extremo descendiente. Las aristas restantes fuera de este conjunto deben estar orientadas en la dirección opuesta. Esta técnica permite especificar 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 limitado utilizando el teorema de Courcelle . ^{[ 8 ]}

Si un grafo tiene un camino hamiltoniano , entonces ese camino (con raíz en uno de sus extremos) también es un árbol de Trémaux. Los grafos no dirigidos para los cuales todo árbol de Trémaux tiene esta forma son los grafos cíclicos , los grafos completos y los grafos bipartitos completos equilibrados . ^{[ 9 ]}

Los árboles de Trémaux están estrechamente relacionados con el concepto de profundidad de árbol . La profundidad de árbol de un grafo${\displaystyle G}$se puede definir como el número más pequeño${\displaystyle d}$para los cuales existe un gráfico${\displaystyle H}$, con un árbol de Trémaux${\displaystyle T}$de altura${\displaystyle d}$, de tal manera que${\displaystyle G}$es un subgrafo de${\displaystyle H}$La profundidad de árbol limitada, en una familia de grafos, es equivalente a la existencia de un camino que no puede aparecer como menor de grafos de la familia. Muchos problemas computacionales difíciles en grafos tienen algoritmos que son tratables con parámetros fijos cuando se parametrizan por la profundidad de árbol de sus entradas. ^{[ 10 ]}

Los árboles de Trémaux también juegan un papel clave en el criterio de planaridad de Fraysseix-Rosenstiehl para probar si un grafo dado es planar . Según este criterio, un grafo${\displaystyle G}$es planar si, para un árbol de Trémaux dado${\displaystyle T}$de${\displaystyle G}$, los bordes restantes se pueden colocar de manera consistente a la izquierda o a la derecha del árbol, sujetos a restricciones que impiden que los bordes con la misma posición se crucen entre sí. ^{[ 11 ]}

No todos los grafos infinitos tienen un árbol de expansión normal. Por ejemplo, un grafo completo con un conjunto no numerable de vértices no lo tiene: un árbol de expansión normal en un grafo completo solo puede ser un camino, pero un camino solo tiene un número numerable de vértices. Sin embargo, todo grafo conexo con un conjunto numerable de vértices sí tiene un árbol de expansión normal. ^{[ 3 ] [ 4 ]}

Incluso en grafos contables, una búsqueda en profundidad podría no tener éxito en explorar eventualmente todo el grafo, ^{[ 3 ]} y no todos los árboles de expansión normal pueden ser generados por una búsqueda en profundidad: para ser un árbol de búsqueda en profundidad, un árbol de expansión normal contable debe tener solo un camino infinito o un nodo con infinitos hijos (y no ambos).

Si un gráfico infinito${\displaystyle G}$tiene un árbol de expansión normal, al igual que cada grafo conectado menor de${\displaystyle G}$De esto se deduce que los grafos que poseen árboles de expansión normales tienen una caracterización mediante menores prohibidos . Una de las dos clases de menores prohibidos consiste en grafos bipartitos en los que un lado de la bipartición es numerable, el otro no, 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 conjuntista 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 reemplazarse 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, se extienden hasta el 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 considerando el grafo mismo como un complejo simplicial y añadiendo un punto en el infinito en cada extremo del mismo. 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 numerable 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 ]}