A new algorithm for finding minimum spanning trees with undirected neutrosophic graphs

摘要

In this paper, we discuss the minimum spanning tree (MST) problem of an undirected neutrosophic weighted connected graph in which a single-valued neutrosophic number, instead of a real number/fuzzy number, is assigned to each arc as its arc length.We define this type of MST as neutrosophic minimum spanning tree (NMST). We describe the utility of neutrosophic numbers as arc lengths and its application in different real world MST problems. Here, a new algorithm for designing the MST of a neutrosophic graph is introduced. In the proposed algorithm, we incorporate the uncertainty in Kruskal algorithm for designing MST using neutrosophic number as arc length. A score function is used to compare different NMSTs whose weights are computed using the addition operation of neutrosophic numbers. We compare this weight of the NMST with that of an equivalent classical MST with real numbers as arc lengths. Compared with the existing algorithms for NMST, the proposed algorithm is more efficient due to the fact that the addition operation and the ranking of neutrosophic number can be done in straightforward manners. The proposed algorithm is illustrated by numerical examples.