그래프이론

그래프의 정의

가장 일반적인 의미에서 그래프(graph)는 순서쌍 G = (V, E)으로 볼 수 있으며, 여기에서 집합 V는 꼭짓점, E는 변 을 의미한다. 혼동을 피하기 위해, 방향이 없는 단순한 그래프 만을 다루겠다. 

 

복잡하게 생각하지 말고, 가장 대표적인 예시로는 10명의 사람들이 인사를 주고받을 때, 10명을 점으로 하고 인사를 주고받았다면 선으로 연결, 주고 받지 않았더라면 연결하지 않았을 때, 나오는 모양을 의미한다. 점들의 배치는 중요하지 않다.

 

그래프 용어

 

1. n-정규그래프

n-정규그래프는 모든 점들의 차수가 n 으로 동일한 것을 의미한다. 위 예시로는 각 10명이 모두 인사를 7명에게 하였을 때, 나오는 그래프 이다.

 

2. 이분할그래프

이분할 그래프는, 두 그룹으로 나누어진 점에 의해 이루어진 그래프 이다. 각 그룹 내 에서는 서로 연결되면 안되며, 다른 그룹끼리만 연결된 그래프이다. 위 예시에서는 남자 5명, 여자 5명이 있을 때 동성 끼리는 인사를 하지 않는 경우 나올 수 있는 그래프이다. 

 

3. 회로

회로는 어떤 점으로 부터 시작해서, 변을 타고 움직였을때 다시 돌아 올 수 있는 경로가 회로이다. 위 예시에서는 인사를 할때 초콜릿을 넘겨준다면, 임의 사람 A 로 부터 시작 되서, 초콜릿이 돌다가 다시 A 한테 돌아오면 이 초콜릿의 경로는 회로라고 할 수 있다.  n 개의 점이 있다면 보통 Cn 이라고 쓴다.

 

4. 차수

차수는 각 점에서 연결된 변의 개수이다.

응용 정리로는 악수정리가 있다. 이는 모든 차수의 합은 짝수라는 정리인데, 서로 연결되었을때 차수의 합은 각 변을 모두 두 번씩 세기 때문에 항상 짝수일 수밖에 없다. 

 

5. 완전그래프

모든 점이 연결된 그래프를 의미한다. 모든 사람과 인사를 하였을 때 나오는 그래프이다. n 개의 점이 있다면 보통 Kn 으로 쓴다.

 

6. 연결요소

어떤 "덩어리"를 의미한다. 점들이 회로 또는 경로로 모두 연결되어 있는 그룹들을 연결요소라 하고, 연결요소 끼리는 연결되지 않는다.