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 이 문제도 이 원리를 이용해서 푸는건감..?


'Problem Solving > Algorithm notes' 카테고리의 다른 글

Gaussian Prime  (0) 2011.04.03
Floating point number 연산시 Epsilon을 더하는(또는 빼는) 이유..  (2) 2011.03.02
Linear Diophantine Equation  (0) 2011.01.25
점과 선분과의 거리  (2) 2011.01.22
Articulation Points  (0) 2010.11.21
Konig's Theorem  (0) 2010.08.01
Modular Multiplicative Inverse  (0) 2010.06.13
Primality Testing (Miller-Rabin)  (0) 2010.03.23
Modular Exponentiation (Big Mod)  (2) 2010.02.19
KMP (Knuth-Morris-Pratt) Algorithm  (0) 2009.11.15
Sorting Algorithm O(n^2)  (0) 2009.08.31

Leave a Comment


to Top