%0 Journal Article
%T ON THE MATCHING NUMBER OF AN UNCERTAIN GRAPH
%J Iranian Journal of Fuzzy Systems
%I University of Sistan and Baluchestan
%Z 1735-0654
%A Li, Hui
%A Zhang, Bo
%A Peng, Jin
%D 2018
%\ 04/29/2018
%V 15
%N 2
%P 89-108
%! ON THE MATCHING NUMBER OF AN UNCERTAIN GRAPH
%K Uncertainty theory
%K Uncertain measure
%K Maximum matching
%K Matching number
%K Uncertain graph
%R 10.22111/ijfs.2018.3761
%X 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.
%U https://ijfs.usb.ac.ir/article_3761_843af24ca521b1d9f207a6a79751dcc4.pdf