ÁRBOL DE EXPANSIÓN - TUTORIAL DS

En este artículo, analizaremos el árbol de expansión y el árbol de expansión mínimo. Pero antes de pasar directamente al árbol de expansión, veamos primero una breve descripción del gráfico y sus tipos.

Grafico

Un gráfico se puede definir como un grupo de vértices y aristas para conectar estos vértices. Los tipos de gráficos se dan de la siguiente manera:

Gráfico no dirigido:Un gráfico no dirigido es un gráfico en el que todas las aristas no apuntan a ninguna dirección particular, es decir, no son unidireccionales; son bidireccionales. También se puede definir como un gráfico con un conjunto de vértices V y un conjunto de aristas E, cada arista conecta dos vértices diferentes.Gráfico conectado:Un gráfico conexo es un gráfico en el que siempre existe un camino desde un vértice a cualquier otro vértice. Un gráfico es conexo si podemos llegar a cualquier vértice desde cualquier otro vértice siguiendo aristas en cualquier dirección.Gráfico dirigido:Los grafos dirigidos también se conocen como dígrafos. Un gráfico es un gráfico dirigido (o dígrafo) si todas las aristas presentes entre cualquier vértice o nodo del gráfico están dirigidas o tienen una dirección definida.

Ahora, avancemos hacia el árbol de expansión de temas.

¿Qué es un árbol de expansión?

Un árbol de expansión se puede definir como el subgrafo de un gráfico conectado no dirigido. Incluye todos los vértices junto con el menor número posible de aristas. Si falta algún vértice, no es un árbol de expansión. Un árbol de expansión es un subconjunto del gráfico que no tiene ciclos y tampoco se puede desconectar.

Un árbol de expansión consta de (n-1) aristas, donde 'n' es el número de vértices (o nodos). Los bordes del árbol de expansión pueden tener o no pesos asignados. Todos los posibles árboles de expansión creados a partir del gráfico dado G tendrían el mismo número de vértices, pero el número de aristas en el árbol de expansión sería igual al número de vértices en el gráfico dado menos 1.

Un gráfico no dirigido completo puede tener norte^n-2 número de árboles de expansión donde norte es el número de vértices del gráfico. Supongamos que si norte = 5 , el número de árboles de expansión máximos posibles sería 5^5-2= 125.

Aplicaciones del árbol de expansión

Básicamente, se utiliza un árbol de expansión para encontrar una ruta mínima para conectar todos los nodos del gráfico. Algunas de las aplicaciones comunes del árbol de expansión se enumeran a continuación:

Análisis de conglomerados
Planificación de redes civiles.
Protocolo de enrutamiento de red informática

Ahora, comprendamos el árbol de expansión con la ayuda de un ejemplo.

Ejemplo de árbol de expansión

Supongamos que la gráfica es -

Como se analizó anteriormente, un árbol de expansión contiene la misma cantidad de vértices que el gráfico; el número de vértices en el gráfico anterior es 5; por lo tanto, el árbol de expansión contendrá 5 vértices. Las aristas en el árbol de expansión serán iguales al número de vértices en el gráfico menos 1. Por lo tanto, habrá 4 aristas en el árbol de expansión.

Algunos de los posibles árboles de expansión que se crearán a partir del gráfico anterior se detallan a continuación:

Propiedades del árbol de expansión

Algunas de las propiedades del árbol de expansión se dan a continuación:

Puede haber más de un árbol de expansión de un gráfico conectado G.
Un árbol de expansión no tiene ciclos ni bucles.
Un árbol de expansión es mínimamente conectado, por lo que eliminar un borde del árbol desconectará el gráfico.
Un árbol de expansión es máximamente acíclico, entonces, agregar un borde al árbol creará un bucle.
Puede haber un máximo norte^n-2 Número de árboles de expansión que se pueden crear a partir de un gráfico completo.
Un árbol generador tiene n-1 bordes, donde 'n' es el número de nodos.
Si el gráfico es un gráfico completo, entonces el árbol de expansión se puede construir eliminando los bordes máximos (e-n+1), donde 'e' es el número de bordes y 'n' es el número de vértices.

Entonces, un árbol de expansión es un subconjunto del gráfico conexo G y no hay un árbol de expansión de un gráfico desconectado.

Árbol de expansión mínimo

Un árbol de expansión mínimo se puede definir como el árbol de expansión en el que la suma de los pesos de los bordes es mínima. El peso del árbol de expansión es la suma de los pesos dados a los bordes del árbol de expansión. En el mundo real, este peso puede considerarse como la distancia, la carga de tráfico, la congestión o cualquier valor aleatorio.

Ejemplo de árbol de expansión mínima

Entendamos el árbol de expansión mínimo con la ayuda de un ejemplo.

La suma de los bordes del gráfico anterior es 16. Ahora, algunos de los posibles árboles de expansión creados a partir del gráfico anterior son:

Entonces, el árbol de expansión mínimo que se selecciona de los árboles de expansión anteriores para el gráfico ponderado dado es:

Aplicaciones del árbol de expansión mínima

Las aplicaciones del árbol de expansión mínimo se dan de la siguiente manera:

El árbol de expansión mínima se puede utilizar para diseñar redes de suministro de agua, redes de telecomunicaciones y redes eléctricas.
Se puede utilizar para encontrar rutas en el mapa.

Algoritmos para árbol de expansión mínimo

Se puede encontrar un árbol de expansión mínimo a partir de un gráfico ponderado utilizando los algoritmos que se detallan a continuación:

Algoritmo de Prim
Algoritmo de Kruskal

Veamos una breve descripción de los dos algoritmos enumerados anteriormente.

Algoritmo de Prim - Es un algoritmo codicioso que comienza con un árbol de expansión vacío. Se utiliza para encontrar el árbol de expansión mínimo del gráfico. Este algoritmo encuentra el subconjunto de aristas que incluye cada vértice del gráfico de modo que se pueda minimizar la suma de los pesos de las aristas.

tupla de Python ordenada

Para obtener más información sobre el algoritmo de prim, puede hacer clic en el siguiente enlace: https://www.javatpoint.com/prim-algorithm

Algoritmo de Kruskal - Este algoritmo también se utiliza para encontrar el árbol de expansión mínimo para un gráfico ponderado conectado. El algoritmo de Kruskal también sigue un enfoque codicioso, que encuentra una solución óptima en cada etapa en lugar de centrarse en un óptimo global.

Para obtener más información sobre el algoritmo de prim, puede hacer clic en el siguiente enlace: https://www.javatpoint.com/kruskal-algorithm

Entonces, eso es todo sobre el artículo. Espero que el artículo le resulte útil e informativo. Aquí hemos analizado el árbol de expansión y el árbol de expansión mínimo junto con sus propiedades, ejemplos y aplicaciones.