Stable Marriage Problem and Its Completion

Mathematics and computer science are two knowledge that are close to each other, not excluding the share of the same problem, such as the stable marriage problem. This classical problem is known as the problem of matchmaking. Computer is a technology that has been familiar will all of people around the world. It includes the people who consider themselves not a “computer literate”, yet they are aware of this kind of technology. In computer systems, mathematics is needed in order to make the computer works fine. There is a computer program that executing this matching problem, which make this device that can carry out any fine completion of instructions.

Here is a stable marriage problem example which is also the language of computer science. You might consider a set of W for women and M for men, the formula will be |M| = |W| = n. In this case, M x W has all the possible ordered pairs (m, w). Therefore, you will find the problem: given the set of W women and M men and a list of minion for each m Î M and each w Î W. Will there occur a stable matching for each set of minion lists, and if there is one, is it possible for us to construct a stable matching?

If we choose the algorithm to analyze this problem, we will get some answers. First, we are possible to remain engaged since her first offered engagement she received. Her partner she engaged with gets better in terms of her preferences. Secondly, m who proposes a woman can get worse in term of his preferences. To answer the second question, there are some proofs that exist: there is a stable matching for every set of the preference lists. We can do not that each W in women and M in men ranks their own preferences from one to n in a descending order very strictly. The formula will be |M| = |W| = 1. The only pair which is stable is S’, which consist of the pair (m1, w1).

The allegorical problems of this matchmaking is a lot. One of them is called bipartite matching, which is a part of Graph theory. This theory allow us to encounter algorithms in order to solve the general bipartite matching problem, especially the stable marriage problem, when we are studying network flow problems.