Problem Solving/Algorithm notes
Konig's Theorem
helloneo
2010. 8. 1. 00:50
SRM 397 - HouseProtection 문제를 풀다가..
Konig's Theorem 이란게 있어서 찾아보니..
bipartite graph 에서..
minimum vertex cover problem <=> maximum matching problem
이라고 하는군..~
여기서 파란 선이 maximum matching 이고 빨간 점이 minimum vertex cover 이다..
둘다 결과가 6이다..
출처: http://wapedia.mobi/en/König's_theorem_(graph_theory)
그러고보니.. GCJ 2009 이 문제도 이 원리를 이용해서 푸는건감..?
Konig's Theorem 이란게 있어서 찾아보니..
bipartite graph 에서..
minimum vertex cover problem <=> maximum matching problem
이라고 하는군..~
여기서 파란 선이 maximum matching 이고 빨간 점이 minimum vertex cover 이다..
둘다 결과가 6이다..
출처: http://wapedia.mobi/en/König's_theorem_(graph_theory)
그러고보니.. GCJ 2009 이 문제도 이 원리를 이용해서 푸는건감..?