[알고리즘] 그래프1 - 그래프란?

그래프란?

그래프는 정점(노드, Vertex)과 그 사이를 잇는 간선(Edge)로 이루어져 있다.
G = (V, E)는 정점의 집합 V와 간선의 집합 E라고 할 때, 그래프 G는 V와 E의 집합 (V, E)라는 의미이다.

위의 그림에서,

V(G) = {1, 2, 3, 4, 5}이고,

E(G) = {(1, 2), (3, 1), (3, 2), (4, 1), (5, 2), (5, 4)} 이다.

 

 

 

그래프의 종류

무방향 그래프

이름 그대로 간선에 방향이 없는 그래프이다. 그렇기 때문에 정점 v와 정점 w를 잇는 간선 (v, w)가 있다고 하면 (w, v)도 같은 간선이 되는 것이다.

그러므로 정점이 n개일 때 무방향 그래프가 가질 수 있는 최대 간선 수는 n(n-1)/2개 이다.

무방향 그래프

 

 

방향 그래프

간선에 방향이 있는 그래프이다. 정점 v에서 w로 가는 간선 (v, w)와 w에서 v로 가는 (w, v)는 다른 간선이다. 

그러므로 정점이 n개일 때 그래프가 가질 수 있는 최대 간선 수는 n(n-1)개 이다.

방향 그래프

 

 

 

완전 그래프

모든 정점에 간선이 있고, 한 정점에서 다른 정점과 모두 연결되어 있는 그래프이다.

완전 그래프

 

 

 

가중치 그래프

간선에 가중치가 존재하는 그래프이다.

가중치 그래프