그래프의 개요 - 8.1 그래프의 개요

8.1.1 그래프의 기본 개념

• 그래프(graph): 연결되어 있는 객체간의 관계를 표현하는 자료구조

• 그래프의 예: 전기회로, 프로젝트관리, 지도에서 도시들의 연결

• 그래프: 아주 일반적인 자료구조

• (예) 트리도 그래프의 일종으로 볼수 있다.

• 그래프 이론(graph theory): 그래프를 문제해결의 도구로

이용하는 연구분야

8.1.1 그래프의 기본 개념 (1)

• 1736년에 오일러에 의하 여 창안

• 오일러 문제: 모든 다리를 한번만 건너서 처음 출발 했던 장소로 돌아오는 문 제

• 문제의 핵심만을 표현

• 위치: 정점(node)

• 다리: 간선(edge)

• 오일러 경로: 정점에 연결

된 간선의 개수가 짝수이

면 존재

8.1.1 그래프의 기본 개념 (2)

• 그래프는 G(V, E)로 표시된다.

• V는 정점(vertices)들의 집합

• E는 간선(edge)들의 집합

• 정점과 간선은 모두 관련되는 데이터를 가질수 있다.

8.2: 그래프의 예

1 2 3

4

1 2 3

4 5 6

1 2 3

(a) G₁ (b) G₂ (c) G₃

V(G₁)={1, 2, 3, 4} E(G₁)={(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3.,4)}

V(G₂)={1, 2, 3, 4, 5, 6} E(G₂)={(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)}

V(G₃)={1, 2, 3, 4} E(G₃)={<1, 2>, <2, 3>, <3, 2>, <2, 4>}

4

8.1.2 그래프 관련 용어 (1)

• 완전 그래프(complete graph)

• 최대 수의 간선을 가진 그래프

• 정점이 n개일 때, 간선의 수는

• 무방향 그래프일 때 n(n-1)/2,

• 방향 그래프일 때 n(n-1)

• 다중 그래프(mutigraph)

• 두 정점사이 2개 이상의 간선이 존재하는 그래프

• 원칙적으로 그래프는 중복간선을 허용하지 않음

• 서브 그래프(subgraph)

• V(G’)⊆V(G)이고, E(G’)⊆E(G)인 그래프 G’를 그래프 G의 서브 그래프 또는 부분 그래프라 한다.

8.1.2 그래프 관련 용어 (2)

• 인접 (adjacent)과 부속 (incident):

무방향 그래프의 한 간선 (v

, v

)에 대해

• v^j와 v_k는 서로 인접한다.

• 간선 (vj, v_k)는 정점 v_j와 v_k에 부속한다.

• 예1) 그래프 G1

• 정점 1, 3 : 정점 0에 인접.

• 간선 (0, 1), (1, 2), (1, 3) : 정점 1에 부속.

• 예2) 그래프 G2

• 정점 1 : 정점 2로 인접(adjacent to 2)

• 정점 2 : 정점 1로부터 인접(adjacent to 1)

• 아크 <0, 1>, <1, 2>, <1, 0> : 정점 1에 부속.

0 1

3 2

0 1 2

8.1.2 그래프 관련 용어 (3)

• 경로(path)와 사이클(cycle)

• 경로: 정점 vj 로부터 v_i 까지의 경로(path)

• 경로의 길이(path length): 경로를 구성하는 간선의 수

• 단순 경로(simple path): 모두 상이한 간선들로 구 성된 경로

• 사이클(cycle): 첫 번째 정점과 마지막 정점이 동일 한 단순 경로

• 그래프 G1

• 경로 0,1,3,2 : 길이 3, 단순경로

• 경로 0, 1, 3, 0 : 사이클

• 그래프 G2

• 경로 0,1,2 : 단순 경로

• 경로 0, 1, 0 : 사이클

0 1

3 2

0 1 2

8.1.2 그래프 관련 용어 (4)

• 연결 그래프(connected graph)

서로 다른 모든 정점들 사이에 경로가 있는 무방향 그래프는 연 결 그래프 아니면 단절 그래프(disconnected graph)

• 어느 한 정점에서부터 다른 어떤 정점에로의 경로 존재

• 트리 : 사이클이 없는 연결 그래프 (acyclic connected graph)

• 연결 요소(connected component):

• 최대 연결 부분 그래프(maximal connected subgraph)

• 최대 : 최대의 정점과 최대의 간선

• 예) G : H₁, H₂ 두개의 요소를 가짐

0 1

3 2

4 5 6

H

₁

H

₂

8.1.2 그래프 관련 용어 (5)

• 강력 연결(strongly connected)

• 방향 그래프 G에서 V(G)에 있는 서로 다른 모든 정점의 쌍 u와 v에 대해 u에 서 v까지, 또한 v에서 u까지의 방향 경 로가 존재

• 예 : G₄

• 약한 연결(weakly connected)

• 무방향그래프로 생각할때(에지방향을 무시해서) 모든 정점사이에 경로가 존 재

• 예 : G₅

• 강력 연결 요소(strongly connected component)

• 강력 연결된 최대 부분 그래프

• 예) H_{1 ,}H₂: G₂의 강력연결요소

0 1 4

3 2

0 1 4

3 2

G4 G5

0 1 2

0 1

H₁

2

H₂ 방향그래프에 대해

8.1.2 그래프 관련 용어 (6)

• 차수(degree)

• 무방향 그래프의 차수(degree) : 무방향 그래프에서 그 정점에 부속된 간선의 수

예) G₁의 정점 3의 차수 : 3

정점이 n개인 무방향 그래프의 간선 수 e = ( ∑_i=0^n-1degree(i) ) / 2

• 방향 그래프의 차수(degree)

• 진입 차수(indegree) : 방향 그래프에서 정점 v를 머 리로 하는 간선의 수

• 진출 차수(outdegree) : 방향 그래프에서 정점 v를 꼬리로 하는 간선의 수

예) 그래프 G2

정점 0 : 진입 차수 = 진출 차수 = 1 정점 1 : 진입 차수 =1, 진출 차수 = 2