아이고리즘

이전 글에서 Kőnig's Theorem, 쾨니그 정리를 증명했다. 핵심 아이디어만 말하자면 bipartite graph에서 모든 maximum matching에 등장하는 vertex가 하나 이상 존재함이었다. https://cultivated-algorist.tistory.com/entry/Kőnigs-theorem-쾨니그의-정리-증명 Kőnig's theorem (쾨니그의 정리) 증명 Kőnig's theorem. $G$가 bipartite라면 $G$의 maximum matching과 minimum node cover는 크기가 같다. 많은 증명들이 있지만 그 중에서 개인적으로 좋아하면서 (추측건데) 많이 보지 못했을 증명을 소개하고자 한.. cultivated-algorist.tistory.com 해..

Graph/Matching 2022. 7. 6. 12:54

Kőnig's theorem. $G$가 bipartite라면 $G$의 maximum matching과 minimum node cover는 크기가 같다. 많은 증명들이 있지만 그 중에서 개인적으로 좋아하면서 (추측건데) 많이 보지 못했을 증명을 소개하고자 한다. Matching과 Node cover의 정의. $G(V,E)$가 주어졌을 때 matching은 $E$의 부분집합이고 node cover는 $V$의 부분집합이다. 어떤 조건을 만족해야 하냐면 matching $M$은 $V$에서 어떤 node를 고르더라도 $M$에 incident한 edge가 최대 하나여야 하고 node cover $C$는 $E$에서 어떤 edge를 고르더라도 $C$에 그것의 두 endpoint중 최소 하나가 포함되어야 한다. (쉽게 ..

Graph/Matching 2022. 3. 25. 19:54

Graph Theory (basic) Graph Theory (basic) 1. edge 수와 degree의 합의 관계. Graph에서 모든 정점의 degree의 합은 간선의 수의 두배와 같다. $V$와 $E$를 graph의 vertex set, edge set이라 했을 때, $$ \sum_{v\in V}d(v)=2|E| $$ 가 성립한다. 증명은.. cultivated-algorist.tistory.com 이전 글에서 minimum degree와 cycle의 관계를 활용해서 증명들을 몇 개 했었다. 이 글에서도 minimum degree $\delta$와 cycle, 특히 Hamilton cycle과의 관계를 살펴볼 예정이다. Hamilton Path, Hamilton Cycle, Hamiltonian..

Graph/Hamiltonian 2021. 11. 6. 15:33

1. edge 수와 degree의 합의 관계. Graph에서 모든 정점의 degree의 합은 간선의 수의 두배와 같다. $V$와 $E$를 graph의 vertex set, edge set이라 했을 때, $$ \sum_{v\in V}d(v)=2|E| $$ 가 성립한다. 증명은 모든 vertex에 대해서 degree의 합을 구할 때 각 edge가 2번씩 세졌다는 것으로 할 수 있다. (이를 통해 degree가 홀수인 vertex의 수가 짝수임을 알 수 있다.) Note. Directed graph인 경우 $\sum_{v\in V}d^-(v) = |E| = \sum_{v\in V}d^+(v) $가 성립한다. Triangle이 존재하기 위해선... Graph에 triangle의 존재성을 보장하기 위해 edge가..

Graph 2021. 10. 5. 20:50