[데이터 사이언스 스쿨] 그래프 이론 기초 Graph theory basic

그래프(graph)는 다음 그림처럼 노드(node, vertex)와 그 사이를 잇는 간선(edge)으로 이루어진 구조를 말한다.

 

 

위 그래프는 4 개의 노드 집합(V={0,1,2,3})과 6개의 간선 집합(E={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)})을 가진다.

 

만약 간선 (a,b)(a,b)와 (b,a)(b,a)이 있을 때 이 두 간선을 다른 것으로 본다면 간선의 방향이 있는 방향성 그래프(directed graph)이고 두 간선을 같은 것으로 본다면 간선의 방향이 없는 비방향성 그래프(undirected graph)이다. 그래프를 시각화를 할 때 방향성은 화살표로 표시한다.

 

• 워크(walk) : 어떤 노드를 출발해서 다른 노드로 도달하기 위한 인접한 노드의 순서열
• 패스(path) : 워크 중에서 시작과 끝을 제외한 다른 노드에 대해서 동일한 노드를 두 번 이상 지나지 않는 워크
• 사이클(cycle) : 패스 중에서 시작점과 끝점이 동일한 패스
• 어사이클릭 그래프(acyclic graph) : 사이클이 없는 그래프
• 트레일(trail) : 어떠한 노드든 동일한 노드를 두 번 이상 지나지 않는 워크

○ 클리크(clique) : 무방향성 그래프의 노드 집합 중에서 모든 노드끼리 간선이 존재하면 그 노드 집합을 클리크(clique)라고 한다. 만약 클리크에 포함된 노드에 인접한 다른 노드를 추가하면 클리크가 아니게 되는 것을 최대클리크(maximal clique)라고 한다.

 

 

 

dss_ml39_1_graph theory basic 그래프 이론 기초.ipynb

0.50MB

 

- 출처 : [데이터 사이언스 스쿨] 그래프 이론 기초 Graph theory basic