Dirac's Theorem and its Generalization
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
