DinS Written on 2018/7/19
I’ll be lazy enough and introduce a great site on graphs.
https://www.hackerearth.com/zh/practice/algorithms/graphs/graph-representation/tutorial/
Not only do they have graphs, but other topics as well.
You can also check out the articles I wrote on graphs.
Here I’ll mention only briefly something noteworthy.
Eulierian cycles: it visits every edge exactly once.
Theorem: a connected undirected graph contains an Eulerian cycle if and only if the degree of every edge is even. A strongly connected directed graph contains an Eulerian cycle if and only if for every node, its in-degree equals its out-degree.
Hamiltonian cycles: it visits every node exactly once.
Right now no simple criteria is known to check it. This is the core of P-NP problem. The well-known Travelling Salesman Problem (TSP) is such an example.
For stable matching problem, there’s a Nobel Winning Prize algorithm: Gale-Shapley algorithm.
A typical setting for stable matching problem is like this. We have n candidates and n jobs. Each candidate and job has its full list of preference. Our goal is to find n pairs that are stable, which means no one has a tendency to change its current pair according to its preference.
The tradition narration for this problem is n men and n women prepared to get married. The algorithm runs roughly like this.
Start with no matching.
Each step: partial matching.
A random man without partner makes a proposal. If he is rejected, nothing changes. If he is accepted, it will destroy an existing pair.
Repeat until every get married.
Rule for man:
Make proposals according to his preference, ignoring existing pairs.
Never leave the current partner on his own.
Never repeat a rejected proposal, either rejected right away or the woman later abandoned him.
As we can see things get worse with time for man.
Rule for woman:
Accept a proposal if she currently has no partner or an improvement.
As we can see things get better with time for woman.
Proof:
I. Termination
Proposals are never repeated, at most n2 proposals. Thus it must end.
II. Perfect matching
If a man remains without partner -> all women rejected him, right away or later -> all women get married at some point -> contradiction: number of women != number of men
III. Stability
Assume a dangerous pair (m,w) at the end -> for m, w is better than his current partner -> since w is in m’s list, w must have rejected m at some stage -> at some time w’s partner must be better than m -> but things could only improve for w -> w have no motivation to change to m -> contradiction.
Last caution. Although Gale-Shapley algorithm can solve stable matching problem, it is very unfair. It works best for man and gives the best one possible. It works worst for woman and gives the worst one possible.