[이산수학] (4) Fundamentals of Graph Thoery

Graph Theory에 대해 알아보자. graph G는 (V(G), E(G))다. V(G)는 유한개의 꼭짓점(vertices) 집합이고, E(G)는 V(G)의 원소 중 두개로 구성된 변(edges)이다. 

 

1번예시를 살펴보자. V(G)가 v1, v2, v3, v4, v5로 구성된 유한개의 집합이고, E(G)는 V(G)의 원소 2개로 구성된 부분집합이다. 이 때 G=(V(G), E(G))는 그래프라 한다. 

 

사실 이렇게 기호로 나열하는 것보다 그림을 그리는 것이 좋다. vertices의 위치가 정의된 것이 아니기에 다양한 종류의 그래프가 그려질 수 있지만 모두 같은 그래프로 간주한다.

 

좌우측 그림 모두 같은 그래프다. 

 

그래프에 대한 몇가지 특성을 살펴보자.

첫째, edge에는 방향성이 없다. {r1, r2}와 {r2, r1}은 ordered pair가 아닌 set이기 때문에 순서에 영향을 받지 않는다. 

digraph(유향그래프)라고 edge가 방향을 가지는 그래프가 존재하긴 한다. 

둘째, 우리는 V(G)를 유한집합으로 간주하기에 G는 유한그래프다. 만약 V(G)가 무한집합이면 G 또한 무한그래프다.

셋째, 일단 기초적인 그래프이론을 살피고 있기 때문에 simple graph만을 고려한다. loop이나 multiple edges를 동반한 그래프를 다루고 있지 않음을 미리 알린다.

 

Neighborhood에 대한 개념을 살펴보자. v1의 neighborhood는 v2와 v6이다. edge가 연결되어있으면 N(v1)={v2,v6}로 표현한다. v2의 경우 {v1,v3,v6}로 표현한다. 

degree는 neighborhood의 수다. d(v1)=2, d(v2)=3이다. 

관련된 내용은 이후 더 다뤄보겠다. 

 

G를 그래프라 가정할 때, {u,v}가 E(G)의 원소라면, 우리는 u가 v에 대해 adjacent하다고 말한다. u~v라고 표현한다.

가령 위와 같은 그래프가 존재할 때, v1은 v2, v3와 adjacent하다. 그러나 v4, v5와는 adjacent하지 않다. 왜냐하면 그 두가 vertices간의 edge가 존재하지 않기 때문이다. 

 

세번째 예시를 살피면 v4, v6가 adjcent한지 헷갈릴수도 있다. 그러나 이둘이 직접적으로 연결된 것이 아니기 때문에 E(G)에 속하지 않고 따라서 둘은 adjacent하지 않다.

 

이쯤해서 정리해보자.

첫째, 만약 u~v라면, v~u다. {u,v}가 ordered pair가 아니기 때문에 그렇다. symmetric하다. 

둘째, simple graph G만을 고려하기 때문에, u~u는 아니다. 따라서 adjacent to라는 사실은 reflexible을 뜻하진 않는다. 

셋째, u~v이고, v~w라도, u~w를 뜻하진 않는다. 위 그림이 이를 뒷받침한다.

 

그래프 G가 있다고 가정하자. Neighborhood of v는 N(v)={u of V(G) | u~v}로 정의된다. 즉, v에 adjacent to한 u의 집합을 N(v)로 표현한다. 위 예시를 통해 이해해보도록 하자. 

 

그래프 G가 있다고 가정하자. degree of v는 d(v) = |N(v)|로 정의된다. 즉 N(v)에 속하는 원소의 개수가 d(v)다. 

 

만약 u가 N(v)의 원소라면, v는 N(u)의 원소다. u가 N(v)의 원소라는 사실이 u~v라는 것이고, u~v라면 v~u다. 

우리가 현재 simple graph G만을 고려하고 있기 때문에, u가 N(u)의 원소가 아니다. 

 

E(G)에 속하는 edge e에 대해서, {v1,v2} = e1이라면 e가 v1, v2에 대해 incident(근접)하다고 표현한다.

 

N(v)는 v에 대해 u~v의 관계에 있는 u의 집합이다. d(v)는 vertices와 연결된 vertices의 갯수이니 |N(G)|=d(v)다. 

 

 

우리는 계속 G가 simple graph임을 가정하고 있기 때문에 |N(V)|=d(v)가 가능한 것이다. 

 

G가 그래프일 때, for all vertices, sigma sum of d(v) = 2|E(G)|다. 

잘 생각해보면 d(v)의 합은 edge가 두번 계산된 것이니 |E(G)|의 두배가 맞다. 

 

동어반복

 

handshaking lemma를 증명하기 위해선,

G가 그래프일때, G에 대한 adjacency matrix(= A(G))는 nXn 행렬이다. 이 행렬의 (i,j) element는 vi와 vj가 서로 incident한지 여부를 담고 있다. 

 

6번예시. simple graph이기에 diag는 전부 0이다. 대신 이 행렬은 무조건 symmetric할 수 밖에 없다. 

v1은 v2, v4와 incident하기 때문에 (2,1), (4,1) element가 1이다. symmetric이라 (1,2), (1,4) 또한 그렇다. 

 

 

A(G)의 특성은 다음과 같다.

1) diag의 element는 모두 0이다. 이는 G가 simple graph이기 때문에 보장된다.

2) A(G)는 symmetric matrix다. vi가 vj와 adjacent하면, vj와 vi 또한 그렇기 때문이다.

3) A(G)의 모든 원소는 0 아니면 1이다. simple graph를 가정했기 때문에 그 이상은 안된다.

4) i번째 행의 모든 원소의 합 = d(vi) 

 

A(G)의 모든 element sum = 

1st row + 2nd row + ... + nth row = 

d(v1) + d(v2) + d(v3) + ... + d(vn) = 

2|E(G)|

 

n개의 vertices, m개의 edge를 가진 Graph가 있을 때, incidence mtx I(G)는 nXm 행렬이다. 

이 행렬은 v_i가 e_j에 incident(인접)하지 않으면 0, 인접하면 1인 행렬이다. 

위 예시처럼, vertices 4개, edge 4개인 graph는 I(G)가 4X4 행렬이 된다. 

 

한번 살펴보면 안다.

 

I(G)의 특성은 다음과 같다.

1) sum of ith row = num of edges incident to vi = d(vi) (

2) sum of jth column = 2 (열은 edge니까 무조건 1이 2개)

 

the sum of all entries in I(G) = 

the sum of 1st row + ... + nth row =

d(v1)+d(v2) + ... + d(vn) = 

sum of 1st column + ... + nth columns = 

2 * m = 2|E(G)|

: proof of handshaking lemma