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' 카테고리의 다른 글
| Euler's phi (Totient function) (0) | 2016.08.15 |
|---|---|
| Inversion Count (0) | 2016.01.31 |
| The Tower of Hanoi (0) | 2011.08.28 |
| Gaussian Prime (0) | 2011.04.03 |
| 점과 선분과의 거리 (2) | 2011.01.22 |
| 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 |
| Bell Number (0) | 2009.07.12 |