Cubriendo árboles

Cubriendo árboles

Se dice que un subgrafo de G cubre si contiene todos los vértices de G.
Un subgrafo de expansión no es necesariamente conexo. A árbol el cubrimiento de G es un subgrafo cubriente de G, y este subgrafo es un árbol.

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.

cubierta de árboles

Es fácil construir una cubierta para árboles:

  • siempre que no hayamos sumado 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 utiliza ampliamente en el contexto de los bordes ponderados.

Esto se conoce como árbol de expansión de peso mínimo. Este problema es un problema de creación de red: no lugares para conectar, conocemos los costos de conectar un lugar a otro, buscamos conectar todos los lugares al menor costo.

Para hacer un árbol de expansión de peso mínimo, estableceremos dos algoritmos codiciosos.

Algoritmo de Kruskal

Al principio, el gráfico G 'contiene solo 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 que la cola no esté vacía
    • Desplazarse F -> borde Para
    • si la adición de Para no crea un ciclo en G 'luego agrega 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.

 cubierta de árbol kruskal

Algoritmo de Prim

El principio es agrandar un árbol agregando un borde de peso mínimo incidente al árbol.

Al principio, el gráfico G 'contiene solo un vértice de G:

  • siempre que G 'no contenga todos los vértices de G
    • poner en fila 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 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 complejo el algoritmo de entender por escrito, mostraremos un ejemplo:

cubierta de árbol primitiva

Kruskal paso a paso

cubierta de árbol kruskal

A continuación se muestra la lista de bordes ordenados por peso:

Espina de pescadoEDABCDAEantes de CristoEFCFAFBFFD
Peso2344556788

______________

cubierta de árbol kruskal

Ningún ciclo detectado

Espina de pescadoEDABCDAEantes de CristoEFCFAFBFFD
Peso2344556788

______________

cubierta de árbol kruskal

Ningún ciclo detectado

Espina de pescadoEDABCDAEantes de CristoEFCFAFBFFD
Peso2344556788

______________

cubierta de árbol kruskal

Ningún ciclo detectado

Espina de pescadoEDABCDAEantes de CristoEFCFAFBFFD
Peso2344556788

______________

cubierta de árbol kruskal

Ningún ciclo detectado

Espina de pescadoEDABCDAEantes de CristoEFCFAFBFFD
Peso2344556788

______________

cubierta de árbol kruskal

Espina de pescadoEDABCDAEantes de CristoEFCFAFBFFD
Peso2344556788
  • Ciclo detectado: no usar BC

Ningún ciclo detectado, n-1 flanco-> FIN

Espina de pescadoEDABCDAEantes de CristoEFCFAFBFFD
Peso2344556788

Prim paso a paso

cubierta de árbol primitivacubierta de árbol primitivacubierta de árbol primitivacubierta de árbol primitivacubierta de árbol primitivacubierta de árbol primitiva

Compartir, repartir