POJ 2446 - Chessboard
Problem : There are n*m grids, some grids has a hole on it. Find if there is a way to put wood of size 1x2 on the grids, make all the non-hole grid is occupied by wood, and no wood is on the hold, and the wood is not overlapped.
Solution : Split each non-hole grid to 2 vertices in a equaly binary chart. If non-hole grid i and j is adjacent, connect an edge from i to j'. If the maximum match is full, there is a solution. Otherwise not.
Proof:
->: If there is a solution, for every grid i and the grid j which shares the same wood with i, makes a pair i-j'. The match is obviously full.
<-: Define G is the equaly graph of n*m grids, each non-hole grid is a vertice in the G, and there is an edge to all its adjacent non-hole grid. If there is a full match in binary chart, we can make G' the sub-graph of G by selecting the edge of G if it's the match in binary chart. Obviously each vertice in G' has degree of 2, it's means G' is formed by cycles of at least 2 vertices. Since there is no odd length circle in G, so does G'. Thus we can destruct all the cycle with length larger than 2, and reconstruct it to cycles that each of them has length 2. Then we get the solution of original problem: Each pair of vertices shares the same wood.
POJ 2536 - Gopher II
Problem : Raw maximum match.