자료구조 - 그래프(1)

[그래프]

그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 구성된 자료 구조로, 많은 컴퓨터 과학 및 수학 문제에서 중요한 역할을 합니다.

수학적으로는 G = (V, E)와 같이 표시합니다. 여기서 V(G)는 그래프 G의 정점들의 집합. E(G)는 그래프 G의 간선들의 집합을 의미합니다.

 

V(G) = { A, B, C, D}
E(G) = { (A, B), (A, C), (A, D), (C, D) }

 

 

 

 

[무방향 그래프와 방향 그래프]

 

무방향 그래프(Undirected Graph)

무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프입니다.

V(G) = { A, B, C, D }
E(G) = { (A, B), (A, D), (B, C), (B, D), (D, C) }

 

 

 

방향 그래프(Directed Graph)

방향 그래프는 두 정점을 연결하는 간선에 방향이 존재하는 그래프입니다.
간선의 방향으로만 이동할 수 있습니다

 

V(G) = { A, B, C, D }
E(G) = { <A, B>, <A, D>, <B, C>, <B, D>, <C, D> }

 

 

 

 

가중치 그래프(Weighted Graph)

간선에 가중치를 할당하게 되면, 간선의 역할이 두 정점간의 연결 유무뿐만 아니라 연결 강도까지 나타낼 수 있으므로 보다 복잡한 관계를 표현할 수 있게 됩니다.

그리고 가중치 그래프를 네트워크(Network)라고 부르기도 합니다.

 

 

부분 그래프(Sub Graph)

어떤 그래프의 정점의 일부와 간선의 일부로 이루어진 그래프를 부분 그래프라고 부릅니다.

 

 

정점의 차수

그래프에서 인접 정점(Adjacent Vertex)란 간선에 의해 직접 연결된 정점을 뜻합니다.

위의 경우 정점 A의 차수는 2, B의 정점 차수는 3, C의 정점 차수는 2, D의 정점 차수는 3 입니다.

 

무방향 그래프에서 모든 정점의 차수를 합하면 간선 수의 2배가 됩니다.

이것은 하나의 간선이 두개의 정점에 인접하기 때문입니다.

 

방향 그래프에서는 외부에서 오는 간선의 개수를 진입 차수(in-degree), 외부로 향하는 진출 차수(out-degree)라고 합니다.

 

 

 

경로(Path)

 

정점 A에서 B로 가는 경로는 다양합니다.

 

A -> B
A -> C -> B
A -> C -> E -> B
A -> C -> D -> E -> B

 

단순 경로(Simple Path) : 경로 중에서 반복되는 간선이 없는 경우를 말합니다.

사이클(Cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우를 말합니다.

 

 

 

 

연결 그래프(Connected Graph)

무방향 그래프 G에 있는 모든 정점쌍에 대하여 항상 경로가 존재한다면 G는 연결되었다고 하며, 이러한 무방향 그래프 G를 연결 그래프라고 부릅니다.

반대의 경우는 비연결 그래프(Unconnected Graph)라고 부릅니다.

트리는 그래프의 특수한 형태로서 사이클을 가지지 않는 연결 그래프입니다.

 

 

 

완전 그래프(Complete Graph)

그래프에 속해있는 모든 정점이 서로 연결되어 있는 그래프를 완전 그래프라고 합니다.

무방향 완전 그래프의 정점의 수를 n 이라고 하면, 하나의 정점은(n -1)개의 다른 정점으로 연결되므로 간선의 수는 n x (n-1) / 2 가 됩니다.