[자료구조] 그래프

1. 정의

• 그래프 G는 정점 V(Vertex)와 간선 E(Edge)로 구성되며 G = (V, E)로 표시된다
• V는 정점(Vertices)들의 집합이다.
• E는 간선(Edge)들의 집합이다.
• 정점과 간선은 모두 관련되는 데이터를 가질 수 있다.
• 트리는 사이클이 없는 그래프의 한 종류이다.

 

1) 그래프 종류

 

그래프 종류

 

• G1과 G2는 무방향 그래프다.
• G2는 Tree다.
• G3은 방향성 그래프다.

 

2. 무방향 그래프(Undirected Graph)

• 두 정점을 연결하는 간선의 방향이 없는 그래프
• 정점 Vi와 정점 Vj를 연결하는 간선을 (Vi, Vj)로 표현
• (Vi, Vj)와 (Vj, Vi)는 같은 간선을 나타낸다.
• V(G1) = {A, B, C, D}
• E(G1) = {(A, B), (A, D), (B, C), (B, D), (C, D)}
• V(G2) = {A, B, C}
• E(G2) = {(A, B), (A, C), (B, C)}

 

3. 방향 그래프(Directed Graph)

• 방향 그래프는 방향 그래프(Directed Graph) 또는 다이그래프(Digraph)로 부른다.
• 간선이 방향을 가지고 있는 그래프
• 정점 Vi에서 정점 Vj를 연결하는 간선 즉, Vi → Vj를 <Vi, Vj>로 표현
• Vi를 꼬리(tail), Vj를 머리(head)라고 한다.
• <Vi, Vj>와 <Vj, Vi>는 서로 다른 간선
• V(G3) = {A, B, C, D}
• E(G3) = {<A, B>, <A, D>, <B, C>, <B, D>, <C, D>}
• V(G4) = {A, B, C}
• E(G4) = {<A, B>, <A, C>, <B, A>, <B, C>}

 

4. 완전 그래프(Complete Graph)

• 각 정점에서 다른 모든 정점을 연결하여 가능한 초대의 간선 수를 가진 그래프
• 정점이 n개인 무방향 그래프에서 최대의 간선 수 : n(n - 1) / 2개
• 정점이 n개인 방향 그래프의 최대 간선 수 : n(n - 1)개

 

1) 완전 그래프의 예

• G5는 정점의 개수가 4개인 무방향 그래프이므로 완전 그래프가 되려면 4(4 - 1) / 2 = 6개의 간선 연결
• G6은 정점의 개수가 4개인 방향 그래프이므로 완전 그래프가 되려면 4(4 - 1) = 12개의 간선 연결

 

완전 그래프

 

방향, 무방향 완전 그래프가 되기 위한 조건식을 가지고 1-1 그래프 종류에서 나올 수 있는 그래프는 위 그래프밖에 없다.

 

5. 부분 그래프(Subgraph)

• 원래 그래프에서 일부의 정점이나 간선을 제외하여 만든 그래프
• 그래프 G와 부분 그래프 G'의 관계
• V(G') ⊆ V(G), E(G') ⊆E(G)

 

1) G1에 대한 부분 그래프 예

 

부분 그래프

 

6. 그래프 용어

1) 인접 정점(adjacent vertex)

• 간선에 의해 연결된 정점
• 정점 0과 정점 1

2) 차수(Degree)

• 그 정점에 연결된 다른 정점의 개수
• 정점 0의 차수는 3
• Indegree : Indegree(A) = 1
• Outdegree : Outdegree(A) = 2

예

3) 경로(Path)

• 정점의 나열로 표현
• 단순 경로 : 0, 1, 2, 3

4) 사이클(Cycle)

• 첫 시작으로 다시 돌아오는 경우
• 0, 1, 2, 0

5) 경로의 길이

• 경로를 구성하는 데 사용된 간선의 수

6) 완전 그래프

• 모든 정점이 연결된 그래프

 

7. 그래프의 종류

1) 간선의 종류에 따른 분류

• 간선의 종류에 따라 그래프는 무방향 그래프(Undirected Graph)와 방향 그래프(Directed Graph)로 구분

(1) 무방향 간선

• 간선을 통해서 양방향으로 갈 수 있음을 나타내며 (A, B)와 같이 정점의 쌍으로 표현
• (A, B) = (B, A)

(2) 방향 간선

• 방향성이 존재하는 간선으로 도로의 일방 통로와 마찬가지로 한쪽으로만 갈 수 있음을 나타냄
• <A, B>로 표시
• <A, B> ≠ <B, A>

 

2) 가중치 그래프(Weighted Graph), 네트워크(Network)

• 간선에 비용이나 가중치가 할당된 그래프
• A에서 B로 가는 간선에 값, 가중치를 할당한다.