프로그래머 수학

프로그래머 수학

10주차 강의

그래프(1)

1. 그래프의 정의

 그래프(graph)

 순서쌍 (V, E)로 정의,

 정점의 집합 V={v₁, v₂, …, v_n}와 간선의 집합 E

 예 :

 G＝(V, E)

 V＝{v₁, v₂, v₃, v₄, v₅}

 E＝{e₁, e₂, e₃, e₄, e₅, e₆, e₇, e₈ }

＝{(v₁, v₂), (v₁, v₃), (v₁, v₄), (v₂, v₃), (v₂, v₅), (v₃, v₄),

(v₃, v₅),(v₄, v₅)}

그래프의 정의

 차수(degree)

 간선 e=(u, v)에서

 e는 정점 u와 정점 v에 접했다(incident).

 정점 u와 정점 v는 서로 인접했다(adjacent).

 정점 v의 차수는 v에 접한 간선의 수.

 예제

 서로 인접함: v₁과 v₂, v₁과 v₄, v₂와 v₃, v₂와 v₄

 v₁과 v₄의 차수는 2, v₂의 차수는 3, v₃의 차수는 1.

그래프의 정의

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

 경로(path) : 정점의 열(sequence) v₀, v_1, v₂, …, v_k에서 (v_k－1, v_k) ∈ E인 경우. 경로의 길이(length)는 k이다.

 단순 경로(simple path): 경로가 같은 연결선을 두 번 포함하지 않는 경로

 기본 경로(elementary path): 어떤 정점들도 두 번 만나지 않는 경로

 사이클(cycle): 경로 (v₁, v₂, …, v_n)에서 종점 v_n과 시점 v₁이 일치하는 경우

 단순 사이클(simple cycle): 같은 연결선을 반복하여 방문하지 않는 사이클

 기본 사이클(elementary cycle): 시작점을 제외한 어떠한 정점도 반복하여 방문하지 않는 사이클

 부분 그래프(subgraph)

그래프 G＝(V, E)가 있을 때,V'⊆V이고 E'⊆E인 그래프 G'＝(V', E')를 부분 그래프라고 함

 생성 부분 그래프(spanning subgraph)

그래프 G＝(V, E)가 있을 때,V‘=V이고 E'⊂ E인 그래프 G'＝(V', E')를 생성부분 그래프라고 함

 다중 그래프(multi-graph)

두 정점 사이에 두 개 이상의 에지가 있는 그래프

 단순 그래프(simple-graph) 다중그래프가 아닌 그래프

그래프의 정의

 방향 그래프(directed graph)

그래프 G＝(V, E)에서 정점의 집합 V와 간선의

끝점이라고 하는 정점들의 순서쌍인 아크(arc)들의 집합으로 구성된다.

 정점 v에서 정점 w로 가는 아크는 v → w로 표시

그래프의 정의

아 크

1 2 3 4

그래프의 정의

 연결 그래프 (connected graph)

그래프의 모든 정점들이 연결되어 있는 그래프

 강한 연결 그래프(strongly connected graph)

방향 그래프에서, 모든 두 정점 a와 b에 대해, a에서 b로의 경로와 b에서 a로의 경로들이 존재하는 그래프

 연결 요소(connected component)

모든 정점들이 연결되어 있는 부분을 말하며 연결수 (connectivity number)란 그래프 G에서의 연결 요소의 개수를 말한다.

 인접 행렬(adjacency matrix)을 사용

 인접 리스트(adjacency list)를 사용

2. 그래프의 표현

2-1. 그래프의 인접 행렬 표현

 인접 행렬(adjacency matrix)을 사용

 그래프 G = (V, E)에서 |V|=n일 때, G의 인접 행렬은 n× n 행렬 A로 나타내지며, 이 때 A의 각 원소

a

a

 예제: 주어진 그래프에 대한 인접 행렬은 다음과 같이 표시된다.

a b c d

î í

ì Î

e otherwis

E v

v

) , ( 1

2-2. 그래프의 인접 리스트 표현

 인접 리스트(adjacency list)을 사용

 각 정점에 대해 포인터(pointer)가 주어지고, 그 점으로부터 연결된 정점들을 차례로 연결 리스트(linked list)로 표시함.

 순서에는 관계가 없음

 예제: 주어진 그래프에 대한

인접 행렬은 다음과 같이 표시된다.

3. 특수 그래프

 완전 그래프(complete graph)

 그래프 G＝(V, E)의 모든 정점의 쌍 사이에 간선이 존재

 n(n-1)/2개의 간선을 가지며, K_n으로 표시

특수 그래프

 이분 그래프(bipartite graph)

 그래프 G＝(V, E)에서 V가 두 부분 집합 X와

Y＝V－X로 분할되어, 각 간선이 X 내의 정점과 Y 내의 정점의 쌍으로 나타내어질 때.

 완전 이분 그래프(complete bipartite graph)

 X 내의 모든 정점과 Y 내의 모든 정점 사이에 간선이 존재할 때

 예제 : K_2,3, K_3,3 완전이분그래프

특수 그래프

 정규 그래프(regular graph)

그래프 G의 모든 정점의 차수가 r인 경우, r-정규그래프라 함

2-정규그래프 3-정규그래프 4-정규그래프

특수 그래프

 동형 그래프(isomorphic graph)

 그래프 G＝(V, E)와 G'＝(V', E')에서 전단사(1-1대응) 함수 f:V→V'가 존재하여 (u, v) ∈ E ⇔ (f(u),f(v)) ∈ E‘ 이면 f를 동형, G와 G'를 동형 그래프라고 함.

 동형 그래프의 예:

G1과 G2,

G3와 G4는 동형그래프임.

G1: G2:

G3: G4:

특수 그래프

 오일러 사이클(Euler cycle)

그래프 G에서 각 간선을 한 번씩만 지나는 사이클

 오일러 그래프 (Euler graph)

오일러 사이클을 갖는 그래프

G의 모든 정점의 차수가 짝수이어야 함

특수 그래프

 해밀톤 사이클(Hamilton cycle)

그래프G에서 각 정점을 한 번씩만 지나는 사이클

 해밀톤 그래프 (Hamilton graph) 해밀톤 사이클을 갖는 그래프.

특수 그래프

 평면 그래프(planar graph)

그래프G를 평면에 그릴 때 어떤 간선도 정점이 아닌 곳에서 교차하지 않도록 그릴 수 있다면 G를 평면 그래프라고 함.

 예제^:

다음 그래프들은 평면 그래프인가?

(1) (2) (3) (4)

평면그래프에서의 오일러 정리

 오일러 정리

 예제^:

다음 그래프에서 오일러 정리가 성립함을 보여라.

<풀이> 꼭지점의 개수 v=6, 연결선의 개수 e=9, 면의 개수 f=

참고문헌

 본 강의 자료에서 예제 등의 출처는 다음과 같은 참고 문헌이다.

1) PLD: Programming Logic and Design using Flowchart, 주형석 저(IT미디어)

2) 이산수학: 논리,명제에서 알고리즘까지, 홍영진 저(한빛미디어) 3) 이산수학 및 응용, 임은기 번역(한티미디어)

4) 전산수학, 김대수 (생능)