Á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