Árbol binario sin raíz

Un cladograma en forma de árbol binario sin raíz, que representa las similitudes y la historia evolutiva entre las especies de actinobacterias .

En matemáticas y ciencias de la computación, un árbol binario sin raíz es un árbol sin raíz en el que cada vértice tiene uno o tres vecinos.

Definiciones

Un árbol libre o árbol sin raíz es un grafo no dirigido conectado y sin ciclos . Los vértices con un vecino son las hojas del árbol y los vértices restantes son los nodos internos del árbol. El grado de un vértice es su número de vecinos; en un árbol con más de un nodo, las hojas son los vértices de grado uno. Un árbol binario sin raíz es un árbol libre en el que todos los nodos internos tienen exactamente grado tres.

En algunas aplicaciones puede tener sentido distinguir subtipos de árboles binarios sin raíz: una incrustación planar del árbol puede ser fijada especificando un orden cíclico para los bordes en cada vértice, convirtiéndolo en un árbol plano . En informática, los árboles binarios suelen tener raíz y estar ordenados cuando se utilizan como estructuras de datos , pero en las aplicaciones de árboles binarios sin raíz en la agrupación jerárquica y la reconstrucción evolutiva de árboles , los árboles desordenados son más comunes. ^[1]

Además, se puede distinguir entre árboles en los que todos los vértices tienen etiquetas distintas, árboles en los que sólo las hojas están etiquetadas y árboles en los que los nodos no están etiquetados. En un árbol binario sin raíz con n hojas, habrá n  − 2 nodos internos, por lo que las etiquetas se pueden tomar del conjunto de números enteros de 1 a 2 n  − 1 cuando se deben etiquetar todos los nodos, o del conjunto de números enteros de 1 a n cuando sólo se deben etiquetar las hojas. ^[1]

Estructuras relacionadas

Árboles binarios enraizados

Un árbol binario sin raíz T puede transformarse en un árbol binario con raíz completa (es decir, un árbol con raíz en el que cada nodo que no es una hoja tiene exactamente dos hijos) eligiendo una arista raíz e de T , colocando un nuevo nodo raíz en el medio de e y dirigiendo cada arista del árbol subdividido resultante lejos del nodo raíz. A la inversa, cualquier árbol binario con raíz completa puede transformarse en un árbol binario sin raíz eliminando el nodo raíz, reemplazando el camino entre sus dos hijos por una única arista sin dirección y suprimiendo la orientación de las aristas restantes en el grafo. Por esta razón, hay exactamente 2 n  −3 veces más árboles binarios con raíz completa con n hojas que árboles binarios sin raíz con n hojas. ^[1]

Agrupamiento jerárquico

Una agrupación jerárquica de una colección de objetos puede formalizarse como una familia máxima de conjuntos de los objetos en la que no se cruzan dos conjuntos. Es decir, por cada dos conjuntos S y T en la familia, o bien S y T son disjuntos o bien uno es un subconjunto del otro, y no se pueden añadir más conjuntos a la familia mientras se preserve esta propiedad. Si T es un árbol binario sin raíz, define una agrupación jerárquica de sus hojas: para cada arista ( u , v ) en T hay una agrupación que consiste en las hojas que están más cerca de u que de v , y estos conjuntos junto con el conjunto vacío y el conjunto de todas las hojas forman una familia máxima sin cruces. A la inversa, a partir de cualquier familia máxima sin cruces de conjuntos sobre un conjunto de n elementos, se puede formar un árbol binario único sin raíz que tiene un nodo para cada triple ( A , B , C ) de conjuntos disjuntos en la familia que juntos cubren todos los elementos. ^[2]

Árboles evolutivos

Según las formas simples de la teoría de la evolución , la historia de la vida se puede resumir como un árbol filogenético en el que cada nodo describe una especie, las hojas representan las especies que existen en la actualidad y los bordes representan las relaciones ancestro-descendiente entre especies. Este árbol tiene una orientación natural de ancestros a descendientes y una raíz en el ancestro común de las especies, por lo que es un árbol enraizado. Sin embargo, algunos métodos de reconstrucción de árboles binarios pueden reconstruir solo los nodos y los bordes de este árbol, pero no sus orientaciones.

Por ejemplo, los métodos cladísticos como la parsimonia máxima utilizan como datos un conjunto de atributos binarios que describen características de las especies. Estos métodos buscan un árbol con las especies dadas como hojas en el que los nodos internos también estén etiquetados con características, e intentan minimizar el número de veces que alguna característica está presente en solo uno de los dos puntos finales de un borde en el árbol. Idealmente, cada característica debería tener solo un borde para el cual este sea el caso. Cambiar la raíz de un árbol no cambia este número de diferencias de bordes, por lo que los métodos basados ​​en la parsimonia no son capaces de determinar la ubicación de la raíz del árbol y producirán un árbol sin raíz, a menudo un árbol binario sin raíz. ^[3]

Los árboles binarios sin raíz también se producen mediante métodos para inferir árboles evolutivos basados ​​en datos de cuarteto que especifican, para cada especie de cuatro hojas, el árbol binario sin raíz que describe la evolución de esas cuatro especies, y mediante métodos que utilizan la distancia de cuarteto para medir la distancia entre árboles. ^[4]

Descomposición de ramas

Los árboles binarios sin raíz también se utilizan para definir descomposiciones de ramas de grafos, formando un árbol binario sin raíz cuyas hojas representan los bordes del grafo dado. Es decir, una descomposición de ramas puede verse como una agrupación jerárquica de los bordes del grafo. Las descomposiciones de ramas y una cantidad numérica asociada, el ancho de rama, están estrechamente relacionadas con el ancho de árbol y forman la base para algoritmos de programación dinámica eficientes en grafos. ^[5]

Enumeración

Debido a sus aplicaciones en la agrupación jerárquica, el problema de enumeración de grafos más natural en árboles binarios sin raíz es contar el número de árboles con n hojas etiquetadas y nodos internos sin etiquetar. Un árbol binario sin raíz en n hojas etiquetadas se puede formar conectando la n- ésima hoja a un nuevo nodo en el medio de cualquiera de las aristas de un árbol binario sin raíz en n  − 1 hojas etiquetadas. Hay 2 n  − 5 aristas en las que se puede unir el n -ésimo nodo; por lo tanto, el número de árboles en n hojas es mayor que el número de árboles en n  − 1 hojas por un factor de 2 n  − 5. Por lo tanto, el número de árboles en n hojas etiquetadas es el factorial doble

${\displaystyle (2n-5)!!={\frac {(2n-4)!}{(n-2)!2^{n-2}}}.}$^[6]

Los números de árboles en hojas etiquetadas 2, 3, 4, 5, ... son

1, 1, 3, 15, 105, 945, 10395, 135135, 2027025, 34459425, ... (secuencia A001147 en la OEIS ).

Igualdades fundamentales

La longitud de la ruta de hoja a hoja en un árbol binario sin raíz (UBT) fijo T codifica el número de aristas que pertenecen a la ruta única en T que conecta una hoja dada con otra hoja. Por ejemplo, haciendo referencia al UBT que se muestra en la imagen de la derecha, la longitud de la ruta entre las hojas 1 y 2 es igual a 2, mientras que la longitud de la ruta entre las hojas 1 y 3 es igual a 3. La secuencia de longitud de ruta desde una hoja dada en un UBT fijo T codifica las longitudes de las rutas desde la hoja dada hasta todas las restantes. Por ejemplo, haciendo referencia al UBT que se muestra en la imagen de la derecha, la secuencia de longitud de ruta desde la hoja 1 es . El conjunto de secuencias de longitud de ruta asociadas a las hojas de T se suele denominar colección de secuencias de longitud de ruta de T ^[7] . ${\displaystyle p_{1,2}}$ ${\displaystyle p_{1,3}}$ ${\displaystyle p_{1}=(p_{1,2},p_{1,3},p_{1,4})=(2,3,3)}$

Un ejemplo de un árbol binario sin raíz con cuatro hojas

Daniele Catanzaro, Raffaele Pesenti y Laurence Wolsey demostraron ^[7] que la colección de secuencias de longitud de ruta que codifica un UBT dado con n hojas debe satisfacer igualdades específicas, a saber:

• ${\displaystyle p_{i,i}=0}$a pesar de ${\displaystyle i\in [1,n]}$
• ${\displaystyle p_{i,j}=p_{j,i}}$a pesar de ${\displaystyle i,j\in [1,n]:i\neq j}$
• ${\displaystyle p_{i,j}\leq p_{i,k}+p_{k,j}}$a pesar de ${\displaystyle i,j,k\in [1,n]:i\neq j\neq k}$
• ${\displaystyle \sum _{j=1}^{n}1/2^{p_{i,j}}=1/2}$para todos (que es una adaptación de la desigualdad de Kraft-McMillan ) ${\displaystyle i\in [1,n]}$
• ${\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{n}p_{i,j}/2^{p_{i,j}}=2n-3}$, también conocida como variedad filogenética . ^[7]

Se ha demostrado que estas igualdades son necesarias e independientes para que una colección de longitudes de ruta codifique un UBT con n hojas. ^[7] Actualmente se desconoce si también son suficientes.

Nombres alternativos

Los árboles binarios sin raíz también se han denominado árboles binarios libres , ^[8] árboles cúbicos , ^[9] árboles ternarios ^[5] y árboles ternarios sin raíz . ^[10] Sin embargo, el nombre de "árbol binario libre" también se ha aplicado a árboles sin raíz que pueden tener nodos de grado dos ^[11] y a árboles binarios con raíz con hijos no ordenados, ^[12] y el nombre de "árbol ternario" se utiliza con más frecuencia para significar un árbol con raíz con tres hijos por nodo .

Notas

1. Furnas (1984).
2. Véase, por ejemplo, Eppstein (2009) para la misma correspondencia entre agrupamientos y árboles, pero utilizando árboles binarios con raíz en lugar de árboles sin raíz y, por lo tanto, incluyendo una elección arbitraria del nodo raíz.
3. Hendy y Penny (1989).
4. San Juan y otros (2003).
5. Robertson y Seymour (1991).
6. Balding, Bishop y Cannings (2007).
7. Catanzaro D, Pesenti R, Wolsey L (2020). "Sobre el politopo de evolución mínima equilibrada". Optimización discreta . 36 : 100570. doi : 10.1016/j.disopt.2020.100570 . S2CID  213389485.
8. Czumaj y Gibbons (1996).
9. Exoo (1996).
10. Cilibrasi y Vitanyi (2006).
11. Harary, Palmer y Robinson (1992).
12. Przytycka y Larmore (1994).

Referencias

• Balding, DJ; Bishop, Martin J.; Cannings, Christopher (2007), Manual de genética estadística , vol. 1 (3.ª ed.), Wiley-Interscience, pág. 502, ISBN 978-0-470-05830-5.
• Cilibrasi, Rudi; Vitanyi, Paul MB (2006). "Una nueva heurística de árbol de cuarteto para agrupamiento jerárquico". arXiv : cs/0606048 ..
• Czumaj, Artur; Gibbons, Alan (1996), "El problema de Guthrie: nuevas equivalencias y reducciones rápidas", Theoretical Computer Science , 154 (1): 3–22, doi : 10.1016/0304-3975(95)00126-3.
• Eppstein, David (2009), "Pantalones cuadrados en un árbol: agrupamiento de la suma de subárboles y descomposición de pantalones hiperbólicos", ACM Transactions on Algorithms , 5 (3): 1–24, arXiv : cs.CG/0604034 , doi :10.1145/1541885.1541890, S2CID  2434.
• Exoo, Geoffrey (1996), "Un método simple para construir pequeños gráficos cúbicos de circunferencias 14, 15 y 16" (PDF) , Electronic Journal of Combinatorics , 3 (1): R30, doi : 10.37236/1254.
• Furnas, George W. (1984), "La generación de árboles aleatorios, binarios y desordenados", Journal of Classification , 1 (1): 187–233, doi :10.1007/BF01890123, S2CID  121121529.
• Harary, Frank ; Palmer, EM; Robinson, RW (1992), "Contar árboles binarios libres que admitan una altura dada" (PDF) , Journal of Combinatorics, Information, and System Sciences , 17 : 175–181.
• Hendy, Michael D.; Penny, David (1989), "Un marco para el estudio cuantitativo de árboles evolutivos", Biología Sistemática , 38 (4): 297–309, doi :10.2307/2992396, JSTOR  2992396
• Przytycka, Teresa M. ; Larmore, Lawrence L. (1994), "El problema del árbol alfabético óptimo revisitado", Proc. 21st International Colloquium on Automata, Languages ​​and Programming (ICALP '94) , Apuntes de clase en informática, vol. 820, Springer-Verlag, págs. 251–262, doi :10.1007/3-540-58201-0_73, ISBN 978-3-540-58201-4.
• Robertson, Neil ; Seymour, Paul D. (1991), "Grafos menores. X. Obstrucciones a la descomposición en árboles", Journal of Combinatorial Theory , 52 (2): 153–190, doi : 10.1016/0095-8956(91)90061-N.
• St. John, Katherine; Warnow, Tandy ; Moret, Bernard ME ; Vawterd, Lisa (2003), "Estudio de rendimiento de métodos filogenéticos: métodos de cuarteto (no ponderados) y unión de vecinos" (PDF) , Journal of Algorithms , 48 (1): 173–193, doi :10.1016/S0196-6774(03)00049-X, S2CID  5550338.