Minimum Spanning Tree

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.