Research On Bipartite Graph Matching Problem

Research and Development of matching theory has a hundred years ofhistory，and has evolved into an important part of operations research. Because manyof the problems relate to matching theory in our daily lives, with the deepening of thestudy, matching theory not only is one of the core content of graph theory, but alsohas a wide range of applications in other fields of mathematics such as chemical graphtheory, combinatorial optimization, mathematical modeling, and so on. Up to now,matching theory has become a vibrant and dynamic area of research. Therefore, itattracts many attentions of scholars. And many celebrated results have beenestablished, such as Hall’s theorem and Tutte’s theorem. At the same time due to theextension of their application, close connection with other subjects is established, anda series of special topics arise. This paper considers multi-partite graph and theirmatching in depth, provides an algorithm for the maximum matching of k-partite graphbased on vertex degree, applies the theory of k-partite graph and matching to thescheduling problem. The main contents are as follows：（1）Analyze and consider in depth matching of bipartite graph. Provide a newalgorithm to find matching of a bipartite graph based on vertex degree according to theprinciple of bipartite graph matching, introduce in detail the idea of the algorithm,verify the feasibleness and the effectiveness of the algorithm through experiments;（2）Generalize to multi-partite graph the method that finds the maximalmatching for a bipartite graph, provide a new algorithm to find matching of a multi-partite graph based on vertex degree, introduce the idea of the algorithm, verify thefeasibleness of the algorithm. It is worth mentioning that the paper defines the vertex-degree matrix the first time; （3）Apply the theory of multi-partite graph and matching to analyze thescheduling problem, conclude that a scheduling system is to find a4-matching (or a3-matching) in a5-partite graph (or a4-partite graph), provide a calculation method indetail. It provides a new idea and a new method to solve the scheduling problem.