개발일지

개념 그래프 G에서 정점들의 집합을 S라고 할 때 S의 부분집합 'S로 모든 간선을 포함하면 이를 Vertex Cover라고 한다. Minimum Vertex Cover는 NP지만 이분 그래프에서 Minimun Vertex Cover는 최대 매칭과 동치이다. 작동 원리 콰닉의 정리 Kőnig's theorem (graph theory) - Wikipedia An example of a bipartite graph, with a maximum matching (blue) and minimum vertex cover (red) both of size six. In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (19..