Konig's Theorem
Problem Solving/Algorithm notes 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 이 문제도 이 원리를 이용해서 푸는건감..?
'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 |