University of Sistan and BaluchestanIranian Journal of Fuzzy Systems1735-065415220180429ON THE MATCHING NUMBER OF AN UNCERTAIN GRAPH89108376110.22111/ijfs.2018.3761ENHuiLiSchool of Information and Engineering, Wuchang University of Technology,
Wuhan, 430223, ChinaBoZhangSchool of Statistics and Mathematics, Zhongnan University of Economics
and Law, Wuhan, 430073, ChinaJinPengInstitute of Uncertain Systems, Huanggang Normal University, Huang-
gang, 438000, ChinaJournal Article20161108Uncertain graphs are employed to describe graph models with indeterministic<br />information that produced by human beings. This paper aims to study the<br />maximum matching problem in uncertain graphs.<br />The number of edges of a maximum matching in a graph is called matching number<br />of the graph. Due to the existence of uncertain edges, the matching number of an uncertain graph is essentially an uncertain variable.<br />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$).<br />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<br />into a simplified form. What is more, a polynomial time algorithm to numerically calculate the uncertain measure is derived from the simplified form.<br />Finally, some numerical examples are illustrated to show the application and efficiency of the algorithm.https://ijfs.usb.ac.ir/article_3761_843af24ca521b1d9f207a6a79751dcc4.pdf