10.3: Árboles enraizados

En las dos secciones siguientes, discutiremos los árboles enraizados. Nuestros focos primarios estarán en árboles enraizados generales y en un caso especial, árboles binarios ordenados.

Definición y Terminología

Figura\(\PageIndex{1}\): Un árbol enraizado

Lista\(\PageIndex{1}\): Informal Definition and Terminology

Lo que diferencia a los árboles enraizados de los árboles no dirigidos es que un árbol enraizado contiene un vértice distinguido, llamado raíz. Considera el árbol en la Figura\(\PageIndex{1}\). Vértice\(A\) ha sido designado la raíz del árbol. Si elegimos cualquier otro vértice en el árbol, tal como\(M\text{,}\) sabemos que hay un camino único desde\(A\) hasta\(M\text{.}\) Los vértices en este camino, se\((A, D, K, M)\text{,}\) describen en términos genealógicos:

• \(M\)es hijo de\(K\) (así es\(L\))
• \(K\)es\(M\) el padre.
• \(A\text{,}\)\(D\text{,}\)y\(K\) son\(M\) ancestros.
• \(D\text{,}\)\(K\text{,}\)y\(M\) son descendientes de\(A\text{.}\)

Estas relaciones genealógicas suelen ser más fáciles de visualizar si el árbol se reescribe para que los niños se posicionen por debajo de sus padres, como en la Figura\(\PageIndex{2}\).

Con este formato, es fácil ver que cada vértice del árbol puede pensarse como la raíz de un árbol que contiene, además de sí mismo, a todos sus descendientes. Por ejemplo,\(D\) es la raíz de un árbol que contiene\(D\text{,}\)\(K\text{,}\)\(L\text{,}\) y\(M\text{.}\) además,\(K\) es la raíz de un árbol que contiene\(K\text{,}\)\(L\text{,}\) y\(M\text{.}\) finalmente,\(L\) y\(M\) son raíces de árboles que solo contienen a sí mismas. A partir de esta observación, podemos dar una definición formal de árbol enraizado.

Figura\(\PageIndex{2}\): Un árbol enraizado, redibujado

Definición\(\PageIndex{1}\): Rooted Tree

1. Base: Un árbol sin vértices es un árbol enraizado (el árbol vacío).
2. Un solo vértice sin hijos es un árbol enraizado.
3. Recursión: Dejar\(T_1, T_2,\ldots,T_r\text{,}\)\(r\geq 1\text{,}\) ser árboles enraizados disjuntos con raíces\(v_1\text{,}\)\(v_2, \ldots \text{,}\)\(v_r\text{,}\) respectivamente, y dejar\(v_0\) ser un vértice que no pertenece a ninguno de estos árboles. Entonces\(v_0\text{,}\) se obtiene un árbol enraizado, enraizado\(v_0\) al hacer el padre de los vértices\(v_1\text{,}\)\(v_2, \ldots\text{,}\) y\(v_r\text{.}\) llamamos\(T_1, T_2, \ldots, T_r\) subárboles del árbol más grande.

El nivel de un vértice de un árbol enraizado es el número de bordes que separan el vértice de la raíz. El nivel de la raíz es cero. La profundidad de un árbol es el nivel máximo de los vértices en el árbol. La profundidad de un árbol en la Figura\(\PageIndex{2}\) es tres, que es el nivel de los vértices\(L\) y\(M\text{.}\) Los vértices\(E\text{,}\)\(F\text{,}\)\(G\text{,}\)\(H\text{,}\)\(I\text{,}\)\(J\text{,}\) y\(K\) tienen el nivel dos. \(B\text{,}\)\(C\text{,}\)y\(D\) están en el nivel uno y\(A\) tiene nivel cero.

Ejemplo\(\PageIndex{1}\): A Decision Tree

La Figura 2.1.1 es un árbol enraizado con Start como raíz. Es un ejemplo de lo que se llama un árbol de decisiones.

Ejemplo\(\PageIndex{2}\): Tree Structure of Data

Una de las claves para trabajar con grandes cantidades de información es organizarla de manera consistente y lógica. Una estructura de datos es un esquema para organizar datos. Un ejemplo simple de una estructura de datos podría ser la información que un departamento de admisiones universitarias podría mantener sobre sus solicitantes. Los artículos pueden verse así:

\ begin {equation*}\ begin {split} applicantItem & = (FirstName, MiddleInitial, LastName, StreetAddress,\\ & Ciudad, Estado, Código Postal, HomePhone, Celular, EmailAddress,\\ & HighSchool, Major, applicationPaid, MathSat, VerbalSat,\\ & Recomendación1, Recomendación2, Recomendación3)\ end {split}\ end {equación *}

Esta estructura se llama “archivo plano”.

Una hoja de cálculo puede ser utilizada para organizar los datos de esta manera. Aunque una estructura de “archivo plano” suele ser adecuada, hay ventajas al agrupar parte de la información. Por ejemplo, la información del solicitante podría dividirse en cuatro partes: nombre, información de contacto, escuela secundaria y datos de solicitud:

\ begin {equation*}\ begin {split} applicantItem & = ((FirstName, MiddleInitial, LastName),\\ & ((StreetAddress, Ciudad, Estado, Código Postal),\\ & (HomePhone, Celular), EmailAddress),\\ &HighSchool,\\ & (Mayor, ApplicationPaid, (MathSat, VerbalSat),\\ & (Recomendación1, Recomendación2, Recomendación3))\ end { dividir}\ end {ecuación*}

El primer elemento de cada applicantItem es una lista\((FirstName, MiddleInitial, LastName)\text{,}\) con cada elemento de esa lista siendo un solo campo del archivo plano original. El tercer elemento es simplemente el artículo individual de la escuela secundaria del archivo plano. Los datos de la solicitud son una lista y uno de sus ítems, es en sí mismo una lista con los datos de recomendación para cada recomendación que tenga el solicitante.

La organización de estos datos se puede visualizar con un árbol enraizado como el de la Figura\(\PageIndex{3}\).

Figura\(\PageIndex{3}\): Datos del solicitante en un árbol enraizado

En general, se puede representar un elemento de datos,\(T\text{,}\) como un árbol enraizado con\(T\) como la raíz y un subárbol para cada campo. Esos campos que son más de un solo elemento son raíces de otros subárboles, mientras que los elementos individuales no tienen más hijos en el árbol.

Algoritmo de Kruskal

Un algoritmo alternativo para construir un árbol de expansión mínimo utiliza un bosque de árboles enraizados. Primero describiremos el algoritmo en sus términos más simples. Posteriormente, describiremos cómo se utilizan los árboles enraizados para implementar el algoritmo. Finalmente, demostraremos la implementación de SaeMath del algoritmo. En todas las versiones de este algoritmo, supongamos que\(G = (V, E, w)\) es un gráfico ponderado no dirigido con\(\lvert V\rvert = m\) y\(\lvert E\rvert = n\text{.}\)

Algorithm\(\PageIndex{1}\): Kruskal's Algorithm - Informal Version

1. Ordenar los bordes de\(G\) en orden ascendente según el peso. Es decir,
   \ begin {ecuación*} i\ leq j\ Leftrightarrow w\ left (e_j\ right)\ leq w\ left (e_j\ right)\ text {.} \ end {ecuación*}
2. Baja por la lista del Paso 1 y agrega bordes a un conjunto (inicialmente vacío) de bordes para que el conjunto no forme un ciclo. Cuando se encuentra un borde que crearía un ciclo, ignóralo. Continúe examinando aristas hasta que se hayan seleccionado las\(m - 1\) aristas o haya llegado al final de la lista de aristas. Si se seleccionan\(m - 1\) aristas, estas aristas forman un árbol de expansión mínimo para\(G\text{.}\) Si se seleccionan menos de\(m - 1\) aristas, no\(G\) está conectada.

El paso 1 se puede lograr usando una de cualquier número de rutinas de clasificación estándar. Usando la rutina de clasificación más eficiente, el tiempo requerido para realizar este paso es proporcional a\(n \log n\text{.}\) El segundo paso del algoritmo, también de complejidad de\(n \log n\) tiempo, es el que usa un bosque de árboles enraizados para probar si se debe agregar un borde al conjunto de expansión.

Algorithm\(\PageIndex{2}\): Kruskal's Algorithm

1. Ordenar los bordes de\(G\) en orden ascendente según el peso. Es decir,
   \ begin {ecuación*} i\ leq j\ Leftrightarrow w\ left (e_j\ right)\ leq w\ left (e_j\ right)\ text {.} \ end {ecuación*}
2. 1. Inicializar cada vértice en V para que sea la raíz de su propio árbol enraizado.
   2. Baja por la lista de aristas hasta que se complete un árbol de expansión o se haya agotado la lista de bordes. Para cada borde\(e =\left\{v_1,v_2\right\}\text{,}\) podemos determinar si e se puede agregar al conjunto de expansión sin formar un ciclo determinando si la raíz del\({v_1}'s\) árbol es igual a la raíz del\({v_2}'s\) árbol. Si las dos raíces son iguales, entonces ignora e. Si las raíces son diferentes, entonces podemos agregar e al conjunto de expansión. Además, fusionamos los árboles que\(v_1\) y a los que\(v_2\) pertenecen. Esto se logra ya sea haciendo\({v_1}'s\) root el padre de\({v_2}'s\) root o viceversa.

Nota\(\PageIndex{1}\)

1. Desde que iniciamos el algoritmo de Kruskal con\(m\) árboles y cada adición de un borde disminuye el número de árboles en uno, terminamos el algoritmo con un árbol enraizado, siempre que exista un árbol de expansión.
2. El árbol enraizado que desarrollamos en el algoritmo no es el árbol de expansión en sí.

Nota de Sage Math - Implementación del Algoritmo de Kruskal

El algoritmo de Kruskal ha sido implementado en Sage. Ilustramos cómo se puede generar el árbol de expansión para una gráfica ponderada en. Primero, creamos una gráfica de este tipo

Crearemos una gráfica usando una lista de triples de la forma\((\text{vertex},\text{vertex}, \text{label})\text{.}\) El\(weighted\) método le dice a Sage que considere las etiquetas como pesos.

edges=[(1, 2, 4), (2, 8, 4), (3, 8, 4), (4, 7, 5), (6, 8, 5), (1, 3, 6), (1, 7, 6), (4, 5, 6), (5, 10, 9), (2, 10, 7), (4, 6, 7), (2, 4, 8), (1,8, 9), (1, 9, 9), (5, 6, 9), (1, 10, 10), (2, 9, 10), (4, 9, 10), (5, 9, 10), (6, 9, 10)]
G=Graph(edges)
G.weighted(True)
G.graphplot(edge_labels=True,save_pos=True).show()

Figura\(\PageIndex{4}\): Gráfico ponderado, salida de SueMath

A continuación, cargamos la función kruskal y la usamos para generar la lista de bordes en un árbol de expansión de\(G\text{.}\)

from sage.graphs.spanning_tree import kruskal
E = kruskal(G, check=True);E

Para ver el árbol resultante con la misma incrustación\(G\text{,}\) que generamos una gráfica a partir de los bordes del árbol de expansión. A continuación, establecemos las posiciones de los vértices para que sean las mismas que en la gráfica. Finalmente, trazamos el árbol.

T=Graph(E)
T.set_pos(G.get_pos())
T.graphplot(edge_labels=True).show()

Figura\(\PageIndex{5}\): Árbol de expansión, salida de SueMath

Ejercicios

Ejercicio\(\PageIndex{1}\)

Supongamos que un árbol no dirigido tiene diámetro\(d\) y que le gustaría seleccionar un vértice del árbol como raíz para que el árbol enraizado resultante tenga la menor profundidad posible. ¿Cómo se seleccionaría tal raíz y cuál sería la profundidad del árbol (en términos de\(d\))?

Contestar

Localice cualquier camino simple de longitud\(d\) y ubique el vértice en posición\(\lceil d/2\rceil\) sobre el trazado. El árbol enraizado en ese vértice tendrá una profundidad de la\(\lceil d/2\rceil\text{,}\) cual es mínima.

Ejercicio\(\PageIndex{2}\)

Utilice el algoritmo de Kruskal para encontrar un árbol de expansión mínimo para las siguientes gráficas. Además del árbol de expansión, encuentra el árbol enraizado final en el algoritmo. Cuando fusione dos árboles en el algoritmo, haga que la raíz con el número menor sea la raíz del nuevo árbol.

Figura\(\PageIndex{6}\)

Figura\(\PageIndex{7}\)

Ejercicio\(\PageIndex{3}\)

Supongamos que la información sobre los edificios está dispuesta en registros con cinco campos: el nombre del edificio, su ubicación, su propietario, su altura y su espacio de piso. Los campos ubicación y propietario son registros que incluyen toda la información que esperaría, como calle, ciudad y estado, junto con el nombre del propietario (primero, medio, último) en el campo propietario. Dibuja un árbol enraizado para describir este tipo de registro

Contestar

Figura\(\PageIndex{8}\)

Ejercicio\(\PageIndex{4}\)

Atraviesa a mano el Algorthm de Kruskal para verificar que el ejemplo de un árbol de expansión mínimo usando Sage en la Subsección 10.3.3 es correcto.