Research on Stable Marriage Pairing Based on Graph Theory

Abstract

This paper uses the bipartite graph correlation theory in graph to study the algorithm of stable marriage matching problem, and systematically analyzes the application scenario of stable marriage matching problem and the algorithm's advantages and disadvantages. Based on the implementation of the Gale Shapley algorithm, this paper designs a deep traversal-first algorithm based on the backtracking method to find all stable pairing solutions. The backtracking method can find all the solutions of the matching problem, but the time complexity is O (nn); the Gale Shapley algorithm can find a stable solution to the matching problem, and the time complexity is O (n2). In this paper, two algorithms for solving this problem are systematically analyzed and the effectiveness of the algorithm is verified by experiments. The experimental analysis of the Gale Shapley algorithm is a better solution to this problem. Experiments show that the active party can get the most satisfactory object that can be obtained by itself. We find that the stable marriage matching algorithm can also be used to solve the matching problems in the fields of personnel management and educational management.