A Necessary and Sufficient Condition for the Uniqueness of Minimum Spanning Tree

Maman A. Djauhari (Fakultas Matematika ITB)

Journal of Mathematical and Fundamental Sciences
Vol. 29 No. 1/2 (1996)

We develop a fundamental property of min-max transitive closure of a dissimilarity, considered as a fuzzry relation, in connection with its subdominant ultrametric. This will enable us firstly to derive a necessary and sufficient condition for the uniqueness of its minimum spanning tree, and secondly to find all possible local minima.Dengan menggunakan relasi samar sebagai sudut pandang, dalam tulisan ini dikembangkan suatu sifat fundamental dari penutup transitif min-maks suatu disimilaritas, dalam hubungannya dengan ultrametrik sub-dominan. Sifat tersebut memungkinkan kita merumuskan dan membuktikan suatu syarat cukup dan perlu agar suatu disimilaritas memiliki pohon kerangka minimum yang tunggal. Apabila tidak tunggal, sifat itu dapat menjadi landasan untuk menentukan semua pohon kerangka minimum lokal.