Matrix Algorithm for Minimum Spanning Tree Problem on Fuzzy Weighted Network

doi:10.3969/j.issn.1006-2475.2016.09.005

Abstract

Abstract:

The minimum spanning tree problem on fuzzy weighted network was studied. Based on the weighted ranking of fuzzy number’s structured element and the improved weight matrix method for the classical minimum spanning tree problem, a matrix algorithm was proposed for the minimum spanning tree problem on this fuzzy weighted network whose weight is triangular fuzzy number. And its complexity and correctness was analyzed. Experimental result shows that the algorithm is effective.

Key words: fuzzy weighted network, triangular fuzzy number, fuzzy structured element, weight matrix method, minimum spanning tree

CLC Number:

TP301.6

SUN Xiao-jun. Matrix Algorithm for Minimum Spanning Tree Problem on Fuzzy Weighted Network[J]. Computer and Modernization, 2016, 0(9): 21-24.

References

［1］Nesetril J, Milkova E, Nesetrilova H. Otakar Boruvka on minimum spanning tree problem: Translation of both the 1926 papers, comments, history［J］. Discrete Mathematics, 2001(1-3),233:3-36.
［2］ Kruskal J. On the shortest spanning subtree of a graph and the traveling sales man problem［J］. Proceedings of the American Mathematical Society, 1956,7(1):48-50.
［3］ Prim R C. Shortest connection networks and some generations［J］. Bell System Technical Journal, 1957,36(6):1389-1401
［4］ Dijkstra E W. A note on two problems in connexion with graphs［J］. Numerische Mathematik, 1959,1(1):269-271.
［5］ Bortolan G, Degani R. A review of some methods for ranking fuzzy subsets［J］. Fuzzy Sets and Systems, 1985,15(1):1-19.
［6］ Nakamura K. Preference relations on a set of fuzzy utilities as a basis for decision making［J］. Fuzzy Sets and Systems, 1986,20(2):147-162.
［7］ Li R J, Lee E S. Ranking fuzzy number-A comparison［C］// Proc NAFIPS Workshop. West Lafayette, IL, 1987:169-204.
［8］ Lee E S, Li R J. Comparison of fuzzy numbers based on the probability measure of fuzzy events［J］. Computer and Mathematics with Applications, 1988,15(10):887-896.
［9］ Baldwin J F, Guild N C F. Comparison of fuzzy sets on the same decision space［J］. Fuzzy Sets and Systems, 1979,2(3):213233.
［10］Chen Shanhuo. Ranking fuzzy numbers with maximizing set and minimizing sets［J］. Fuzzy Sets and Systems, 1985,17(2):113129.
［11］Chang W. Ranking of fuzzy utilities with triangular membership functions［C］// Proceedings of International Conference on Policy Analysis and Systems. 1981:263272.
［12］Yuan Yufei. Criteria for evaluating fuzzy ranking methods［J］ . Fuzzy Sets and Systems, 1991,43(2):139157.
［13］郭嗣琮. 模糊数比较与排序的结构元方法［J］. 系统工程理论与实践, 2009,29(3):106111.
［14］刘海涛,郭嗣琮. 基于模糊结构元表述的模糊数排序［J］. 模糊系统与数学, 2010,24(5):61-67.
［15］郭嗣琮. 基于模糊结构元理论的模糊数学分析原理［M］. 沈阳:东北大学出版社, 2004.
［16］赵海坤,郭嗣琮,傅秀峰. 证劵组合的模糊规划模型［J］. 模糊系统与数学, 2010,24(6):104-109.

[1]	LU Sai, ZHUANG Yi. Information System Risk Assessment Model Based on Self-Adaptive Expert Weight [J]. Computer and Modernization, 2021, 0(08): 85-93.
[2]	ZHAO Da-cheng, XU Dao-yun. MST Stereo Matching Algorithm Based on Weighted Median Filtering [J]. Computer and Modernization, 2018, 0(05): 16-.
[3]	KONG Qianqian, ZHAO Liaoying, ZHANG Li. Indoor Window Detection Based on Image Contour Analysis [J]. Computer and Modernization, 2018, 0(04): 56-.
[4]	YE Qing1,2, HU Chang-biao1,2. An Improved Image Segmentation Method Based on Graph Theory [J]. Computer and Modernization, 2016, 0(9): 64-67.
[5]	CHENG Yuan;. An Update Strategy for Minimum Spanning Tree of Net [J]. Computer and Modernization, 2012, 1(6): 125-130.
[6]	YE Qing;TANG Peng-ju. An Improved Clustering Method Based on MST [J]. Computer and Modernization, 2011, 1(8): 17-19,2.
[7]	RAN Yu-mei;WANG Hong-guo;YANG Yu-hui;XU Zhen. Color Image Segmentation Based on Adaptive Local Thresholds [J]. Computer and Modernization, 2010, 1(01): 109-112.