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

被引:37
作者
Dey, Arindam [1 ]
Broumi, Said [2 ]
Le Hoang Son [3 ]
Bakali, Assia [4 ]
Talea, Mohamed [2 ]
Smarandache, Florentin [5 ]
机构
[1] Saroj Mohan Inst Technol, Hooghly, W Bengal, India
[2] Univ Hassan 2, Fac Sci Ben MSik, Lab Informat Proc, BP 7955, Casablanca, Morocco
[3] Vietnam Natl Univ, VNU Univ Sci, 334 Nguyen Trai, Hanoi, Vietnam
[4] Ecole Royale Navale, Casablanca, Morocco
[5] Univ New Mexico, Dept Math, 705 Gurley Ave, Gallup, NM 87301 USA
关键词
Neutrosophic sets; Neutrosophic graph; Score function; Spanning tree problem; FUZZY; SYSTEMS; SETS; NETWORKS; COLONY;
D O I
10.1007/s41066-018-0084-7
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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.
引用
收藏
页码:63 / 69
页数:7
相关论文
共 53 条
[1]   A neutrosophic recommender system for medical diagnosis based on algebraic neutrosophic measures [J].
Ali, Mumtaz ;
Le Hoang Son ;
Nguyen Dang Thanh ;
Nguyen Van Minh .
APPLIED SOFT COMPUTING, 2018, 71 :1054-1071
[2]   Interval Complex Neutrosophic Set: Formulation and Applications in Decision-Making [J].
Ali, Mumtaz ;
Luu Quoc Dat ;
Le Hoang Son ;
Smarandache, Florentin .
INTERNATIONAL JOURNAL OF FUZZY SYSTEMS, 2018, 20 (03) :986-999
[3]   Bipolar neutrosophic soft sets and applications in decision making [J].
Ali, Mumtaz ;
Le Hoang Son ;
Deli, Irfan ;
Nguyen Dang Tien .
JOURNAL OF INTELLIGENT & FUZZY SYSTEMS, 2017, 33 (06) :4077-4087
[4]   Segmentation of dental X-ray images in medical imaging using neutrosophic orthogonal matrices [J].
Ali, Mumtaz ;
Le Hoang Son ;
Khan, Mohsin ;
Nguyen Thanh Tung .
EXPERT SYSTEMS WITH APPLICATIONS, 2018, 91 :434-441
[5]  
[Anonymous], 2005, INT C COMPUTATIONAL
[6]  
[Anonymous], 1976, GRAPH THEORY APPL, DOI [10.1007/978-1-349-03521-2, DOI 10.1007/978-1-349-03521-2]
[7]  
[Anonymous], 2012, CONTROL CYBERN
[8]   INTERVAL VALUED INTUITIONISTIC FUZZY-SETS [J].
ATANASSOV, K ;
GARGOV, G .
FUZZY SETS AND SYSTEMS, 1989, 31 (03) :343-349
[9]   INTUITIONISTIC FUZZY-SETS [J].
ATANASSOV, KT .
FUZZY SETS AND SYSTEMS, 1986, 20 (01) :87-96
[10]  
Broumi S, 2016, INT C ADV MECH SYST, P417, DOI 10.1109/ICAMechS.2016.7813484