Document Type : Research Paper

**Authors**

^{1}
School of Information and Engineering, Wuchang University of Technology, Wuhan, 430223, China

^{2}
School of Statistics and Mathematics, Zhongnan University of Economics and Law, Wuhan, 430073, China

^{3}
Institute 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.

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.

**Keywords**

[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.

[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.

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.

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.

March and April 2018

Pages 89-108