9. 그래프 이론과 P-NP 문제 (Graph Theory and P-NP Problem)
2020.10.18
어떤 그래프 $G$는 교점node(혹은 꼭짓점vertex)의 집합 $V$와 간선edge의 집합 $E$로 정의된다. 주로, 수학계에서는 꼭짓점, 컴퓨터 공학계에서는 노드(교점)이라는 표현을 사용한다. 위 그래프는 다음과 같은 $V$와 $E$의 집합으로 나타내어 진다. $$ V = \{1,2,3,4,5,6\}\\ E = \{(1,2), (1,5), (2,3), (2,5), (3,4), (4,5), (4, 6)\}$$ 정의 $(a,b)\in E$라면, 노드 $a$와 $b$는 인접adjacent해있다. 어떤 노드 $n$에 연결된 간선의 갯수를 노드의 차수degree라고 한다. 그래프에 루프loop나 다중 간선multiple edge이 없으면, 그 그래프는 단순simple하다고 한다. 반대의 경우는 복잡compl..