Li, H., Zhang, B., Peng, J. (2018). ON THE MATCHING NUMBER OF AN UNCERTAIN GRAPH. Iranian Journal of Fuzzy Systems, 15(2), 89-108. doi: 10.22111/ijfs.2018.3761
Hui Li; Bo Zhang; Jin Peng. "ON THE MATCHING NUMBER OF AN UNCERTAIN GRAPH". Iranian Journal of Fuzzy Systems, 15, 2, 2018, 89-108. doi: 10.22111/ijfs.2018.3761
Li, H., Zhang, B., Peng, J. (2018). 'ON THE MATCHING NUMBER OF AN UNCERTAIN GRAPH', Iranian Journal of Fuzzy Systems, 15(2), pp. 89-108. doi: 10.22111/ijfs.2018.3761
Li, H., Zhang, B., Peng, J. ON THE MATCHING NUMBER OF AN UNCERTAIN GRAPH. Iranian Journal of Fuzzy Systems, 2018; 15(2): 89-108. doi: 10.22111/ijfs.2018.3761
1School of Information and Engineering, Wuchang University of Technology, Wuhan, 430223, China
2School of Statistics and Mathematics, Zhongnan University of Economics and Law, Wuhan, 430073, China
3Institute of Uncertain Systems, Huanggang Normal University, Huang- gang, 438000, China
Abstract
Uncertain graphs are employed to describe graph models with indeterministic information that produced by human beings. This paper aims to study the maximum matching problem in uncertain graphs. The number of edges of a maximum matching in a graph is called matching number of the graph. Due to the existence of uncertain edges, the matching number of an uncertain graph is essentially an uncertain variable. Different from that in a deterministic graph, it is more meaningful to investigate the uncertain measure that an uncertain graph is $k$-edge matching (i.e., the matching number is greater than or equal to $k$). We first study the properties of the matching number of an uncertain graph, and then give a fundamental formula for calculating the uncertain measure. We further prove that the fundamental formula can be transformed into a simplified form. What is more, a polynomial time algorithm to numerically calculate the uncertain measure is derived from the simplified form. Finally, some numerical examples are illustrated to show the application and efficiency of the algorithm.
[1] B. Bollobas, Degree sequences of random graphs, Discrete Mathematics, 33 (1981), 1-19. [2] J. Bondy and U. Murty, Graph Theory with Applications, Elsevier, New York, 1976. [3] L. Clark, The strong matching number of a random graph, Canadian Journal of Mathematics, 24 (2001), 47-57. [4] J. Edmonds, Paths, trees, and owers, Canadian Journal of Mathematics, 17(3) (1965), 449-467. [5] A. EI Maftouhi and L. M. Gordones, The maximum size of a strong matching in a random graph, Australasian Journal of Combinatorics, 10 (1994), 97-104. [6] A. EI Maftouhi, The minimum size of a maximal strong matching in a random graph, Australasian Journal of Combinatorics, 12 (1995), 77-80. [7] P. Erdos and A. Renyi, On random graph I, Publicationes Mathematicae Debrecen, 6 (1959), 290-297. [8] P. Erdos and A. Renyi, On the strength of connectedness of a random graph, Acta Mathematica Hungarica, 12(1-2) (1964), 261-267.
[9] H. N. Gabow, An efficient implementation of Edmonds' algorithm for maximum matching on graphs, The Journal of the ACM, 23(2) (1976), 221-234. [10] X. Gao, Cycle index of uncertain graph, Information: An International Interdisciplinary Journal, 16(2(A)) (2013), 1131-1138. [11] X. Gao, Regularity index of uncertain graph, Journal of Intelligent and Fuzzy Systems, 27(4) (2014), 1671-1678. [12] X. Gao and Y. Gao, Connectedness index of uncertain graphs, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 21(1) (2013), 127-137. [13] Y. Gao, Shortest path problem with uncertain arc lengths, Computers and Mathematics with Applications, 62(6) (2011), 2591-2600. [14] Y. Gao, L. Yang, S. Li and S. Kar, On distribution function of the diameter in uncertain graph, Information Sciences, 296 (2015), 61-74. [15] Y. Gao and Z. Qin, On computing the edge-connectivity of an uncertain graph, IEEE Transactions on Fuzzy Systems, 24(4) (2015), 981-991. [16] A. Gibbons, Algorithmic Graph Theory, Cambridge University Press, Cambridge, 1985. [17] E. Gilbert, Random graphs, Annals of Mathematical Statistics, 30(4) (1959), 1141-1144. [18] S. Han, Z. Peng and S. Wang, The maximum ow problem of uncertain network, Information Sciences, 265 (2014), 167-175. [19] A. N. Kolmogorov, Grundbegriffe der Wahrscheinlichkeitsrechnung, Julius Springer, Berlin, 1933. [20] B. Liu, Uncertainty Theory, second ed., Springer-Verlag, Berlin, 2007. [21] B. Liu, Some research problems in uncertainty theory, Journal of Uncertain Systems, 3(1) (2009), 3-10. [22] B. Liu, Uncertainty theory: A Branch of Mathematics for Modeling Human Uncertainty, Springer-Verlag, Berlin, 2010. [23] B. Liu, Why is there a need for uncertainty theory? Journal of Uncertain Systems, 6(1) (2012), 3-10. [24] B. Liu, Uncertainty Theory, fourth ed., Springer-Verlag, Berlin, 2015. [25] B. Liu and K. Yao, Uncertain multilevel programming: Algorithm and applications, Computers & Industrial Engineering, 89 (2015), 235-240. [26] H. M. Mahmoud, R. T. Smythe and J. Szymanski, On the structure of random plane-oriented recursive trees and their branches, Random Structures & Algorithm, 4(2) (1993), 151-176. [27] S. Mathew and M. S. Sunitha, Node connectivity and arc connectivity of a fuzzy graph, Information Sciences. 180(4) (2010), 519-531. [28] J. N. Mordeson and P. S. Nair, Fuzzy Graphs and Fuzzy Fypergraphs, Physica-Verlag, Heidelberg, 2000. [29] A. Rosenfeld, Fuzzy Graphs, In: L. A. Zadeh, K. S. Fu and M. Shimura (Eds.), Fuzzy sets and their applications to cognitive and decision processes. Academic Press, New York, 1975. [30] S. Samanta and M. Pal, Fuzzy k-competition graphs and p-competition fuzzy graphs, Fuzzy Information and Engineering, 5(2) (2013), 191-204. [31] Y. Sheng and K. Yao, Fixed charge transportation problem in uncertain environment, Industrial Engineering and Management Systems, 11(2) (2012), 183-187. [32] Y. Sheng and K. Yao, A transportation model with uncertain costs and demands, Information: An International Interdisciplinary Journal, 15(8) (2012), 3179-3186. [33] M. S. Sunitha and S. Mathew, Fuzzy graph theory: A survey, Annals of Pure and Applied Mathematics, 4(1) (2013), 92-110. [34] X. Wu, R. Zhao and W. Tang, Optimal contracts for the agency problem with multiple uncertain information, Knowledge-Based Systems, 59 (2014), 161-172. [35] K. Yao, No-arbitrage determinant theorems on mean-reverting stock model in uncertain mar- ket, Knowledge-Based Systems, 35 (2012), 259-263. [36] R. T. Yeh and S. Y. Bang, Fuzzy Relations, Fuzzy Graphs and Their Applications to Clus- tering Analysis, In: L. A. Zadeh, K. S. Fu and M. Shimura (Eds.), Fuzzy sets and their applications to cognitive and decision processes. Academic Press, New York, 1975. [37] L. A. Zadeh, Fuzzy sets, Information and Control, 8 (1965), 338-353.
[38] B. Zhang and J. Peng, Uncertain programming model for Chinese postman problem with uncertain weights, Industrial Engineering and Management Systems, 11(1) (2012), 18-25. [39] B. Zhang and J. Peng, Euler index in uncertain graph, Applied Mathematics and Computation, 218(20) (2012), 10279-10288. [40] B. Zhang and J. Peng, Matching index of an uncertain graph: Concept and algorithm, Applied and Computational Mathematics, 12(3) (2013), 381-391. [41] J. Zhou, L. Chen and K. Wang, Path optimality conditions for minimum spanning tree problem with uncertain edge weights, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 23(1) (2015), 49-71.
Top