이산 수학 - 13 그래프

 

 

쾨니흐스베르크의 다리 문제

- 7개의 다리들을 한번씩만 건너면서 처음 위치로 돌아오는 길이 있는가?

오일러의 증명

- 그래프를 이용하여 다리 문제가 불가능함을 증명함

 

 

평면 그래프

- 어떤 연결선도 노드가 아닌곳에서 교차하지 않는 그래프

 

 

그래프의 정의

그래프 G = (V, E)

- 이산 수학에서의 그래프 : 점과 선들의 집합

- V = {$v_1$, $v_2$} :: 노드 집합

- E = {$e_{ij$} = ($v_i$, $v_j$) | $v_i$, $v_j$ $\in$ V} : 연결 선(에지)들의 집합

 

 

 

그래프 G = (V, E)에 대하여

- u, v $\in$ V 이고, e = (u, v) $\in$ E

 -> u와 v는 인접(adjacent)

 -> e는 u와 v에 근접(incident)

- u $\in$ V 이고, e = (u, u) $\in$ E -> e: 루프(loop)

 

 연결선의 종류

- (v, w)와 (w, v)를 다르게 취급 -> 유향 그래프

- (v, w)와 (w, v)를 동일하게 취급 -> 무향 그래프

 

 

다중 그래프

- 두 노드 사이에 두 개 이상의 연결선이 있는 그래프

 

가중 그래프

- 각 연결선에 가중치가 부여된 그래프

- 네트워크 라고도 함.

- a, b, c, d가 도시를 나타내고 연결선의 가중치는 각 도시를 자동차로 갈 때 걸리는 시간을 나타내면, a에서 d까지 가는 최소 시간 경로는?

- 도로망, 철도망 또는 네트워크를 설계할 때 유용하게 사용됨.

 

 

그래프 용어

v $\in$ G의 차수

- v에 근접하는 연결선의 개수

 -> deg(v)로 표기 (deg(v)가 홀수면 v는 홀수 노드, deg(v)가 짝수면 v는 짝수 노드)

- G가 유향 그래프인 경우

 -> v의 진입 차수 : v로 들어오는 연결선 개수, in_deg(v)로 표기

 -> v의 진출 차수 : v에서 나가는 연결선의 개수, out_deg(v)로 표기

- 그래프 G의 차수 : 각 노드의 차수 중 최대 차수 -> deg(G)로 표기

 

 

그래프 차수 예시

- deg(1) = 2 -> 1 : 짝수 노드

- deg(2) = 2 -> 2: 짝수 노드

- deg(3) = 3 -> 3: 홀수 노드

- deg(4) = 2 -> 4 : 짝수 노드

- deg(5) = 1 -> 5: 홀수 노드

- deg(G) = 3

 

차수 특성

- $\sum_{v \in V}$ deg(v) = 2 |E|

 -> 모든 노드들의 차수의 합은 연결선의 개수의 2배와 같다.

- 홀수 노드의 개수는 짝수이다.

 

 

 

보행 Walk

- 노드와 연결선이 화살표와 함께 교대로 나열된 형태로, 각 연결선의 앞과 뒤에 위치한 노드는 그 연결선의 양 끝에 위치한 노드를 의미

- 표기시 연결선을 생략하기도 함.

- 보행의 길이 : 보행을 구성하는 연결선의 구성

 

1 -> $e_1$ -> 3 -> $e_3$ -> 4 -> $e_4$->2

or 1 -> 3 -> 4 -> 2

=> 길이 = 3

 

경로 Path

- 연결선이 중복되지 않는 보행. 보행의 특수한 경우

- 경로의 길이 : 경로를 구성하는 연결선의 개수

 

단순 경로 simple path

- 시작노드와 끝노드를 제외하고 노드가 중복되지 않는 경로

 

사이클 cycle

- 시작 노드와 끝 노드가 같은 경로

 

그래프에서의 연결

- v $\in$ V, w $\in$ V가 연결 -> v에서 w까지의 경로가 존재

 

연결 그래프

- 서로 다른 모든 노드를이 연결된 그래프

- 단절 그래프 : 모두 연결되지 않은 그래프

 

 

그래프의 종류

- 정규 그래프 : 모든 노드의 차수가 동일한 그래프

 -> 차수가 k인 무향 정규 그래프의 연결선 개수는 |V| x $\frac{k} {2}$

- 완전 그래프 : 모든 노드의 차수가 |V|(노드의 개수) - 1인 정규 그래프

 -> 노드의 개수가 n인 무향 완전 그래프는 $K_n$으로 표기

 -> 무향 완전 그래프의 연결선 개수는 |V| x $\frac{|V| - 1} {2}$

 

 

평면 그래프

- 그래프를 평면에 그릴때, 어떤 연결선도 노드가 아닌곳에서 교차하지 않도록 그릴수 있는 그래프

 

 

동형 그래프

- 그래프 G = (V, E)와 G' = (V', E')에 대하여 다음을 만족하는 함수

     f: V -> V'이 존재하면 G와 G'를 동형이라고 함

- f는 전단사 함수

- u, v $\in$ V에 대하여 (u, v) $\in$ E 이면 ( f(u), f(v) ) $\in$ E' 

 

이분 그래프 

- 그래프 G = (V,E)가 다음을 만족시키면 이분 그래프라고 함

- V = $V_1$ $\cup$ $V_2$, $V_1$ $\cap$ $V_2$ = $\Phi$를 만족하는 공집합이 아닌 노드 집합 $V_1$, $V_2$가 존재

- 모든 (u, v) $\in$ E에 대해 만약 u $\in$ $V_1$이면 v $\in$ $V_2$이고,반대로 u $\in$ $V_2$이면 v $\in$ $V_1$이다.

 

완전 이분 그래프

- 그래프 G = (V, E)가 다음을 만족 시 완전 이분 그래프라고 함

- G는 이분 그래프

- $V_1$의 모든 노드들과 $V_2$의 모든 노드들이 인접함 

 

부분 그래프 subgraph

- 그래프 G = (V, E)와 G' = (V', E')에 대해 V' $\subset$ V 이고, E' $\subset$ E이면 G'는 g의 부분그래프

 

 

 

생성 부분 그래프  spanning subgraph

- 그래프 G = (V, E)와 G' = (V', E')에 대해 V' = V이고, E' $\subset$ E이면, G'는 G의 생성 부분 그래프

 

 

오일러 그래프

- 오일러 경로 : 그래프의 모든 연결선을 한번씩만 지나가는 경로

- 오일러 순환 : 시작 노드와 끝 노드가 같은 오일러 경로

- 오일러 그래프 : 오일러 순환을 가지는 그래프

- 오일러 그래프는 한붓 그리기와 관련

 

 

 

 

해밀턴 경로

- 해밀턴 경로 : 시작 노드와 끝 노드를 제외하고 그래프 모든 노드를 한번씩만 지나가는 경로

- 해밀턴 순환 : 시작 노드와 끝 노드가 같은 해밀턴 경로

- 해밀턴 그래프 : 해밀턴 순환을 가지는 그래프

 

 

 

순환 그래프

- V = {$v_1$, $v_2$, .., $v_n$} 인 그래프 G = (V, E)가 다음을 만족하면 G를 순환그래프라 함

- G는 무향 그래프

- ($v_i$, $v_j$2) $\in$ E이면 j = i +- mod n

* 노드의 개수가 n인 순환 그래프를 $C_n$으로 표기

* 다각형의 그래프 모델

 

 

트리

- 그래프 G가 다음을 만족시키는 경우 G를 트리라고함

- G는 연결 그래프 -> 서로 다른 모든 노드들 사이에 경로가 존재

- 루트 노드가 존재 -> 루트 노드 : 나무의 뿌리에 해당하는 (트리의 가장 높은 곳에 존재하는) 노드

- G에는 사이클이 없어야 함

 

연결 그래프

- 좌측은 연결 그래프가 아니기 때문에 트리가 아니며, 우측 그래프는 사이클이 존재하므로 트리가 안됨

 

 

오일러 공식

- 연결된 평면 그래프 노드의 수를 v, 연결선의 수를 e, 영역(연결선으로 나눠진 공간)의 수를 s라 하면 다음이 성립

 

 

 

그래프의 표현

1. 인접 행렬

2. 인접 리스트

 

 

 

 

인접 행렬

- 그래프 G = (V, E)에서 |V| = n일때, G의 n x n 인접 행렬 $A_G$ = ($a_{ij}$는 다음과 같이 정의됨

- 무향 그래프의 인접 행렬은 대칭 행렬

- 그래프 인접행렬에 0이 아닌 대각 원소가 존재하면(위 경우 $a_{11}$ = 1) 그래프에 루프가 존재

 

 

인접 리스트

연결 리스트

- 자료구조의 일종

- 데이터 집합을 저장할때 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장

- 배열 방식에 비해 데이터의 추가/삽입 및 삭제가 용이하나 탐색 속도는 떨어지는 데이터 저장 방식

- 그래프 G = (V, E)를 구성하는 각 노드에 인접한 노드들을 연결 리스트로 표현한 것