Graph Theory (basic)
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
