1. ¿Qué es Árbol y Bosque?
Árbol
- En la teoría de grafos, una árbol es un Gráfico no dirigido, conectado y acíclico. . En otras palabras, un gráfico conexo que no contiene ni un solo ciclo se llama árbol.
- Un árbol representa una estructura jerárquica en forma gráfica.
- Los elementos de los árboles se llaman nodos y los bordes del árbol se llaman ramas.
- Un árbol con n vértices tiene (n-1) aristas.
- Los árboles proporcionan muchas aplicaciones útiles, desde simples como un árbol genealógico hasta tan complejas como árboles en estructuras de datos de informática.
- A hoja en un árbol hay un vértice de grado 1 o cualquier vértice que no tenga hijos se llama hoja.
Ejemplo
En el ejemplo anterior, todos son árboles con menos de 6 vértices.
Bosque
En la teoría de grafos, una bosque es un gráfico acíclico, desconectado y no dirigido . En otras palabras, a un conjunto inconexo de árboles se le conoce como bosque. Cada componente de un bosque es un árbol.
Ejemplo
El gráfico anterior parece dos subgráficos, pero es un gráfico único desconectado. No hay ciclos en el gráfico anterior. Por tanto es un bosque.
2. Propiedades de los árboles
- Todo árbol que tenga al menos dos vértices debe tener al menos dos hojas.
- Los árboles tienen muchas caracterizaciones:
Sea T un gráfico con n vértices, entonces las siguientes afirmaciones son equivalentes:- T es un árbol.
- T no contiene ciclos y tiene n-1 aristas.
- T es conexo y tiene (n -1) arista.
- T es un gráfico conexo y cada arista es una arista de corte.
- Dos vértices cualesquiera del gráfico T están conectados exactamente por un camino.
- T no contiene ciclos, y para cualquier nueva arista e, el gráfico T+ e tiene exactamente un ciclo.
- Cada borde de un árbol es un borde cortado.
- Agregar un borde a un árbol define exactamente un ciclo.
- Cada gráfico conectado contiene un árbol de expansión.
- Todo árbol tiene al menos dos vértices de grado dos.
3. Árbol de expansión
A árbol de expansión en un gráfico conexo G es un subgráfico H de G que incluye todos los vértices de G y también es un árbol.
Ejemplo
Considere el siguiente gráfico G:
Del gráfico anterior G podemos implementar los siguientes tres árboles de expansión H:
Métodos para encontrar el árbol de expansión
Podemos encontrar el árbol de expansión sistemáticamente utilizando cualquiera de dos métodos:
- Método de reducción
- Método de construcción
1. Método de reducción
- Comience a elegir cualquier ciclo en el Gráfico G.
- Retire uno de los bordes del ciclo.
- Repita este proceso hasta que no queden ciclos.
Ejemplo
- Considere un gráfico G,
- Si eliminamos el borde ac que destruye el ciclo a-d-c-a en el gráfico anterior, obtenemos el siguiente gráfico:
- Eliminando el borde cb, que destruye el ciclo a-d-c-b-a del gráfico anterior, obtenemos el siguiente gráfico:
- Si eliminamos el borde ec, que destruye el ciclo d-e-c-d del gráfico anterior, obtenemos el siguiente árbol de expansión:
2. Método de construcción
- Seleccione los bordes del gráfico G uno a la vez. De tal manera que no se crean ciclos.
- Repita este proceso hasta que se incluyan todos los vértices.
Ejemplo
Considere el siguiente gráfico G,
- Elige el borde ab ,
- Elige el borde de ,
- Después de eso, elige el borde. CE ,
- A continuación, elige el borde. cb , finalmente obtenemos el siguiente árbol de expansión:
Rango de circuito
El número de aristas que necesitamos eliminar de G para obtener un árbol de expansión.
Árbol de expansión G = m- (n-1) , que se llama el rango de circuito de g.
Where, m = No. of edges. n = No. of vertices.
Ejemplo
En el gráfico anterior, aristas m = 7 y vértices n = 5
Entonces el rango del circuito es,
G = m - (n - 1) = 7 - (5 - 1) = 3