알고리즘 | 그래프(Graph)의 정의와 유형, 표현 방법

그래프 Graph

그래프 G는 다음과 같이 정의한다. 

$ G = (V, E) $ 여기서 V는 Vertices(Node)의 집합이고, E는 Edge의 집합을 의미한다. 

E의 각 edge는 $(u, v)$의 Pair로, $u, v \in V$이다. 

이렇게 edge를 통해 연결된 Vertex u, v를 Adjacent vertices라고 한다. 

한 노드(Vertex)의 Degree(차수)는 그 노드가 가진 adjacent vertices로 나타낸다. 

 

 

그래프의 유형

그래프는 방향성, 무게에 따라 두 유형으로 나뉜다. 

 

1. Directed VS. Undirected

Edge의 각 Pair (u, v)에 방향과 순서가 있으면, 이러한 그래프를 Directed Graph라고 한다. 그렇지 않은 경우를 Undirected Graph라고 한다. Undirected Graph에 Edge (u, v)가 있다고 하자. 이러한 경우, "v는 u에 adjacent하다", "u는 v에 adjacent하다"라고 표현할 수 있다. 

 

2. Weighted VS. Unweighted

Weighted Graph는 Edge에 Weight가 매겨지는 그래프의 유형이다. Unweighted Graph는 이와 발대로 Edge에 Weight가 없는 것을 말한다. 

 

기타 정의들

• Path
  • $(v_{i}, v_{i+1}) \in E $로 연결되는 Vertices $v_{1}, v_{2}, ..., v_{N}$의 순열
• Length of a path
  • Path에 존재하는 Edge의 개수
• Simple path
  • Path에 존재하는 모든 Vertices가 distinct한 Path를 Simple Path라고 한다.
  • 단, 이때 첫번째와 마지막 노드는 같아도 괜찮다. 
• Cycle
  
  •  첫번째 노드와 마지막 노드가 일치하는 Simple Path
  • Digraph에서의 cycle은 v1=vn이라는 정의를 만족하기 위해서 length가 최소 1 이상이어야 한다.