[이산수학] 그래프 이론

그래프 이론은 객체 간의 관계를 모델링하기 위해 사용하는 이론이다. 

소셜 네트워크 관계망, 네비게이션 서비스 등등 다양한 분야에서 사용되고 있다고 한다.

 

먼저 간단한 용어 정리부터.

Vertex : 정점

Edge : 연결선

 

정점과 연결선을 잇는 형태로 그래프가 만들어진다고 보면 된다.

---

[다양한 그래프의 종류]

1. 단순 그래프 (Simple Graph)

2. 멀티 그래프 (Multi Graph)

3. 의사 그래프 (Pseudograph)

4. 방향 그래프 (Directed Graph) / 무방향 그래프 (Undirected Graph)

 

 

 

앞서 그래프들의 특징을 정리하면 다음과 같다.

Simple Directed Graph, Directed multigraph 가 생소해보일 수 있는데 영어 뜻을 생각해보면 간단하다.

 

Simple Directed는 말그대로 심플하게 방향성을 가진 그래프, 출력 방향만 가진 그래프다.

Directed multigraph 는 방향성을 가진 멀티그래프, 입력/출력 방향을 가진 그래프다.

---

약수정리

정점 v와 연결된 연결선의 개수를 차수(degree)라고 한다. 그리고 deg(v)로 나타낸다.

이때 연결선은 그래프의 차수를 계산할 때 두번 반복해 계산된다. 그러므로

모든 정점들의 차수 합은 연결선 개수의 두 배가 된다.

(좀만 생각해보면 당연한 얘기)

출력차수/입력차수

출력이 '+', 입력이 '-' 다. 부호에 신경쓰도록 하자.

인접목록

 

정점 A에 대해 연결선으로 이어진 인접한 정점을 이웃(Neighbor) 이라고 하고, N(a)로 표현할 수 있다.

위 그림에서 첫번째 그림의 N(a) 는 {b, c, e} 가 된다.

 

 

인접행렬

조금 중요한 포인트다. 1행 A의 형태를 해석하자면 다음과 같다.

{0, 1, 1, 1} 이 만들어진 과정을 보자.

a에서 a로 돌아오는 연결선이 있는가? NO. => 0

a에서 b로 돌아오는 연결선이 있는가? YES. => 1

a에서 c로 돌아오는 연결선이 있는가? YES. => 1

a에서 d로 돌아오는 연결선이 있는가? YES. => 1

 

마찬가지로 2행 역시 정점 b를 기준으로 다른 정점과의 관계를 적어내면 된다.

 

멀티 그래프에서도 마찬가지로 적용된다.

 

얼핏 보면 인접행렬은 다 대칭인가? 싶을수도 있지만 그건 아니다.

방향성 그래프는 인접행렬에서 대칭이 아니다.

 

결합행렬

 

인접행렬과 비슷해보이지만 완전 다르다. 정점 v와 개별적인 연결선 e와의 관계를 행렬로 나타내야 한다.

1행에서 { 1, 1, 0, 0, 0, 0 } 이 만들어진 과정을 보자.

 

v1이 e1과 인접하는가? YES => 1

v1이 e2와 인접하는가? YES => 1

v1이 e3와 인접하는가? NO=> 0

v1이 e4와 인접하는가? NO=> 0

v1이 e5와 인접하는가? NO=> 0

v1이 e6와 인접하는가? NO=> 0