G. Minimum Spanning Tree
Definisi
Pohon rentangan atau spanning tree dari suatu connected graph didefinisikan
sebagai free-tree yang terbentuk dari subset sisi-sisi serta menghubungkan
setiap verteks dalam graph tersebut. Minimum Spanning
Tree (MST) adalah pohon rentangan dengan total
bobot dari sisi-sisinya adalah minimal. Dalam
penelusuran vertex tidak diperkenankan terbentuk siklus (cycle).
Diketahui sebuah graph
tak berarah dan tak berbobot sebagai berikut :
Kemungkinan
Spanning Tree :
Bila jalur (edge) mempunyai biaya (cost)
maka yang dicari adalah minimum
cost spanning tree.
No comments:
Post a Comment