ON THE MATCHING NUMBER OF AN UNCERTAIN GRAPH

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. Dierent 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 rst 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 simplied form. What is more, a polynomial time algorithm to numerically calculate the uncertain measure is derived from the simplied form. Finally, some numerical examples are illustrated to show the application and eciency of the algorithm.