Cubriendo árboles
Para minimizar el costo de las redes eléctricas, conexiones de cableado, tuberías, reconocimiento automático de voz, etc., utilizamos algoritmos que construyen gradualmente un árbol de expansión (o más de estos árboles) como pasos intermedios en el proceso de búsqueda de árboles de cobertura mínima. .
Internet y muchas otras redes de telecomunicaciones tienen enlaces de transmisión que conectan los nodos en una topología de malla que incluye algunos bucles. Para evitar bucles de puente y bucles de enrutamiento, muchos protocolos de enrutamiento diseñados para tales redes requieren que cada enrutador recuerde un árbol de expansión.
Es fácil construir una cubierta para árboles:
- siempre y cuando no hayamos añadido n-1 aristas a G', siendo n el número de vértices de la grafico, elegimos una arista de G de tal manera que su suma no cree un ciclo en G'.
- siempre que el número de aristas restantes sea mayor que n-1, eliminamos una arista de G de modo que G siempre esté conectado.
El problema de los árboles de expansión se usa ampliamente en el contexto de los bordes ponderados.
Para hacer un árbol de expansión de peso mínimo, estableceremos dos algoritmos codiciosos.
Algoritmo de Kruskal
Al principio, el grafo G' solo contiene los vértices de G y tenemos una cola vacía (fifo) F :
- para cada vértice v por G
- agregar v Para F
- ordenar F en orden ascendente
- siempre y cuando la cola no esté vacía
- Desplazarse F -> borde Para
- si la adición de Para no crea un ciclo en G' así que agregue Para En g'
- volver G'
Para saber si creamos un ciclo, basta con saber si podemos llegar a un vértice de la arista partiendo del otro vértice en G'. Como recordatorio, en un árbol solo hay un camino de un vértice a otro.
Algoritmo de Prim
El principio consiste en agrandar un árbol añadiendo un borde de peso mínimo incidente al árbol.
Al principio, el grafo G' contiene solo un vértice de G:
- siempre que G' no contenga todos los vértices de G
- poner en cola todas las aristas de G que conectan un vértice de G' a un vértice que no está en G'
- ordenar en orden ascendente la cola
- siempre que la cola no esté vacía o no se haya agregado un borde
- desplazarse por la cola -> borde Para
- si la adición de Para no crea un ciclo en G' luego agrega Para En g'
Siendo el algoritmo complejo de entender por escrito, mostraremos un ejemplo:
Kruskal paso a paso
A continuación se muestra la lista de bordes ordenados por peso:
| Espina de pescado | ED | AB | CD | AE | antes de Cristo | EF | CF | AF | BF | FD |
| Peso | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |
______________
Ningún ciclo detectado
| Espina de pescado | ED | AB | CD | AE | antes de Cristo | EF | CF | AF | BF | FD |
| Peso | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |
______________
Ningún ciclo detectado
| Espina de pescado | ED | AB | CD | AE | antes de Cristo | EF | CF | AF | BF | FD |
| Peso | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |
______________
Ningún ciclo detectado
| Espina de pescado | ED | AB | CD | AE | antes de Cristo | EF | CF | AF | BF | FD |
| Peso | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |
______________
Ningún ciclo detectado
| Espina de pescado | ED | AB | CD | AE | antes de Cristo | EF | CF | AF | BF | FD |
| Peso | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |
______________
| Espina de pescado | ED | AB | CD | AE | antes de Cristo | EF | CF | AF | BF | FD |
| Peso | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |
- Ciclo detectado: no usar BC
Ningún ciclo detectado, n-1 flanco-> FIN
| Espina de pescado | ED | AB | CD | AE | antes de Cristo | EF | CF | AF | BF | FD |
| Peso | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 7 | 8 | 8 |
Prim paso a paso
