Home > Published Issues > 2013 > Volume 8, No. 9, September 2013 >

The Inverse Spanning Tree of a Fuzzy Graph Based on Credibility Measure

Jian Zhou, Qina Wang, and Xiang Zhang
School of Management, Shanghai University, Shanghai 200444, China

Abstract—An inverse spanning tree problem is to make theleast modification on the edge weights such that apredetermined spanning tree is a minimum spanning tree. In thispaper, based on the notion of fuzzy α-minimum spanning tree,the inverse spanning tree problem with fuzzy edge weights isdiscussed and formulated as a fuzzy programming model withsome chance constraints. It shows that when all the edgeweights are assumed to be independent fuzzy variables withregular credibility distributions, the proposed model can bereformulated into a traditional nonlinear programmingaccording to the equivalent condition of fuzzy α-minimumspanning tree characterized by a set of constraints on non-treeedges and their tree paths. Moreover, if all the fuzzy weights aretriangular fuzzy numbers, a linear programming problem can beobtained and solved efficiently with the help of some welldeveloped software packages. 

 
Index Terms—inverse spanning tree, credibility measure,inverse optimization, fuzzy programming

Cite: Jian Zhou, Qina Wang, and Xiang Zhang, "The Inverse Spanning Tree of a Fuzzy Graph Based on Credibility Measure," Journal of Communications, vol. 8, no. 9, pp. 566-571, 2013. doi: 10.12720/jcm.8.9.566-571