Dado un grafo
conexo, un árbol recubierto mínimo de ese grafo es un subgrafo que tiene que
ser un árbol y contener todos los vértices del grafo inicial. Cada arista tiene
asignado un peso proporcional entre ellos, que es un número representativo de
algún objeto, distancia, etc... , y se usa para asignar un peso total al árbol
recubierto mínimo computando la suma de todos los pesos de las aristas del
árbol en cuestión. Un árbol recubridor mínimo o un árbol expandido mínimo es un
árbol recubridor que pesa menos o igual que otros árboles recubridores.
Todo grafo tiene un
bosque recubridor mínimo. En el caso de un empate, porque podría haber más de
un árbol recubridor mínimo; en particular, si todos los pesos son iguales, todo
árbol recubridor será mínimo. De todas formas, si cada arista tiene un peso
distinto existirá sólo un árbol recubridor mínimo.
No hay comentarios:
Publicar un comentario