Determination of All Minimum Spanning Tree on Weighted Connected Graph

Abstract

Minimum Spanning Tree is spanning tree with minimum weigth. There are algorithms was used to get MST, include Kruskal’s Algorithm and Prim’s Algorithm. But all of that just give one solution, although MST problems have many solution. The ways to get all of MST from a simple weighted connected graph G can do by: the first, decide reference MST, is one of MST from G. Then choose all edges of graph G which use in MST. Futhermore decide equivalen class from every edges in graph G is not contained in reference MST with less weight or equal maximum weight in reference MST and decide choosen subset. Combinating choosen subset so getting all of MST from random simple weighted connected graph. There are two special criteria in decision all MST of simple weighted connected graph, are decision all MST with combine choosen edge is not make cycle and decision all MST with combine choosen edge make cycle. The purposes are counting and getting all MST which formed by a random simple weighted connected graph.