bayram's blog

bipartite matching
By bayram, 11 years ago, In English

How can I solve this problem with bipartite matching? Someone solved it with hopcroft karp link.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

First, consider the graph where nodes correspond to squares on the grid, and there is an edge between nodes whose squares are a knight's move away. Note that it can easily be shown that this graph is bipartite: simply color the grid like a chess board and realize that any two squares a knight's move away are different colors. Now, we are looking for the size of the largest set of nodes such that no two nodes have an edge between them.

It turns out that this is the size of the maximum independent set, which is equal to the number of nodes minus the size of the minimum vertex cover. And, size of minimum vertex cover is equal to the size of maximum matching in bipartite graphs, by König's theorem. So, finding the size of the maximum bipartite matching gives the answer.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Close enough.

http://community.topcoder.com/stat?c=problem_statement&pm=6070

:)

→ Reply