Determination of All Minimum Spanning Tree on Weighted Connected Graph

  • Tri Hartati Jurusan Matematika FMIPA Universitas Jember
  • Firdaus Ubaidillah Jurusan Matematika FMIPA Universitas Jember
  • Ahmad Kamsyakawuni Jurusan Matematika FMIPA Universitas Jember

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.

Published
2015-09-08
How to Cite
HARTATI, Tri; UBAIDILLAH, Firdaus; KAMSYAKAWUNI, Ahmad. Determination of All Minimum Spanning Tree on Weighted Connected Graph. Majalah Ilmiah Matematika dan Statistika, [S.l.], v. 15, n. 2, p. 49-60, sep. 2015. ISSN 2722-9866. Available at: <https://jurnal.unej.ac.id/index.php/MIMS/article/view/23722>. Date accessed: 23 may 2024. doi: https://doi.org/10.19184/mims.v15i2.23722.