TY - JOUR
ID - 3761
TI - ON THE MATCHING NUMBER OF AN UNCERTAIN GRAPH
JO - Iranian Journal of Fuzzy Systems
JA - IJFS
LA - en
SN - 1735-0654
AU - Li, Hui
AU - Zhang, Bo
AU - Peng, Jin
AD - School of Information and Engineering, Wuchang University of Technology,
Wuhan, 430223, China
AD - School of Statistics and Mathematics, Zhongnan University of Economics
and Law, Wuhan, 430073, China
AD - Institute of Uncertain Systems, Huanggang Normal University, Huang-
gang, 438000, China
Y1 - 2018
PY - 2018
VL - 15
IS - 2
SP - 89
EP - 108
KW - Uncertainty theory
KW - Uncertain measure
KW - Maximum matching
KW - Matching number
KW - Uncertain graph
DO - 10.22111/ijfs.2018.3761
N2 - Uncertain graphs are employed to describe graph models with indeterministicinformation that produced by human beings. This paper aims to study themaximum matching problem in uncertain graphs.The number of edges of a maximum matching in a graph is called matching numberof 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 transformedinto 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.
UR - https://ijfs.usb.ac.ir/article_3761.html
L1 - https://ijfs.usb.ac.ir/article_3761_843af24ca521b1d9f207a6a79751dcc4.pdf
ER -