Árbol de expansión - Categoría¶
El árbol de expansión de un grafo no dirigido es un árbol que incluye todos los vértices de G con el número mínimo posible de aristas.
Para un grafo desconectado, no hay un solo árbol, sino un bosque de expansión, que consiste en un árbol de expansión de cada componente conectado.
Características:
Su implementación es solo para grafo no dirigido.
El proceso se realiza sólo en aristas con costos positivos.
Cuando el grafo es conectado
Las aristas resultantes componen un árbol
Cuando el grafo no está conectado,
Encuentra un árbol de expansión mínimo para cada componente conectado.
Las aristas resultantes conforman un bosque.
Ver también¶
Índices y tablas