Introduction

이산수학 : Richard Johnsonbaugh 저서, 강홍식.김정인.이도훈.이명재 번역, 교보문고, 1999 (원서 : Discrete Mathematics 6th ed, Prentice-Hall, 1997), Page 363~373

1736 년 그래프 이론에 대한 첫 논문이 발표되었고, 19 세기에 중요한 업적들이 몇몇 있었지만, 그래프 이론이 학문으로 인정되고 널리 연구되기 시작한 것은 1920 년대에 와서다. 실제로 그래프 이론에 대한 첫 교재 ([König]) 는 1936 년에야 발간되었다. 최근 들어 그래프 이론에 대한 관심도가 높아지는 이유 중의 하나는 전산학, 화학, 오퍼레이션 리서치 (operation research), 전자공학, 언어학, 경제학 등 다양한 분야에서 응용되고 있기 때문이다.

이 장에서는 기본적인 그래프 용어와 예들을 살펴보고 경로와 사이클 같은 그래프 이론에서 매우 중요한 개념에 대해 알아본다. 최단 경로 문제는 주어진 두 점 간의 최단 경로를 찾는 문제이다. 해밀턴 사이클의 존재 여부와 판매원 방문 문제와 같은 두 개의 고전적인 문제를 살펴본다. 그래프 표현 방법을 살펴본 후, 두 개의 그래프가 근본적으로 같은지, 그리고 주어진 그래프를 간선들의 겹침 없이 그릴 수 있는지에 대한 문제를 공부한다. 마지막으로 순간 착란 (Instant Insanity) 퍼즐을 그래프 모델을 이용해 해법을 찾는다.

1. 서  론

그림 1 은 와이오밍 주의 고속도로 시스템이다. 어떤 한사람이 이 도로를 순찰할 의무를 가지고 있다. 특히 이 도로 순찰자는 모든 도로들을 조사해야 하고, 도로 분리선의 선명도, 교통 신호의 상태 등에 관한 보고서에 작성해야 한다. 도로 순찰자는 그레이불 (Greybull) 에 살고 있다. 그가 모든 도로를 순찰할 가장 경제적인 방법은 그레이불에서 출발하는 것이고, 모든 도로를 한 번씩 지나 다시 그레이불로 되돌아 와야 한다. 이것이 가능할까? 진도를 나가기 전에 가능한지 결정해 보자.

그림 1  와이오밍 고속도로 시스템의 부분

이 문제는 그래프 (graph) 로 모델화할 수 있다. 사실 그래프는 점과 선으로 그려지기 때문에 도로 지도같이 보인다. 그림 2 는 그림 1 의 지도를 그래프 G 로 모델화하였다. 그림 2 에서 점들을 정점 (vertices) 들이라 하고 정점 간을 이어주는 선들을 간선 (edge) 이라고 한다 (이 절의 끝에 이들의 용어를 상세히 정의할 것이다). 각 정점에 해당되는 도시 이름의 앞 세 글자로 정점 이름을 준다. 간선들은 라고 이름을 붙인다. 그래프를 그릴 때, 중요한 정보는 어느 정점들이 어떤 간선들과 연결되느냐 하는 것이다. 이런 이유로 그림 2 의 그래프를 그림 3 과 같이 그릴 수 있다.

그림 2  그림 1 고속도로 시스템의 그래프 모델

그림 3  그림 1 고속도로 시스템의 그래프 모델의 대안

정점 에서 출발하여 정점 으로 가는 간선을 따라가고, 또 정점 로 가는 또 다른 간선을 따라 가는 등 결국 정점 에 도착한다. 이때 에서 으로의 완전한 방문 (순회) 를 경로 (path) 라 한다. She 을 출발해서 Buf 를 거쳐 Gil 에서 끝나는 경로는 그림 1 의 지도에서 Sheridan 에서 시작하여 Buffalo 를 지나서 Gillette 에서 끝나는 여정에 해당된다. 도로 순찰자 문제는 그래프 모델 G 에 대해 다음과 같이 다시 고쳐 쓰면 : 정점 Gre 으로부터 모든 간선을 한 번만 지나서 정점 Gre 로 오는 경로가 존재하는가?

도로 순찰자는 Greybull 에서 출발하여, 모든 도로를 한 번만 거쳐 Greybull 로 돌아올 수 없다. 그래프 용어를 사용하여 정리하면, 그림 2 에서 정점 Gre 로부터 모든 간선을 한 번만 지나서 정점 Gre 로 되돌아오는 경로는 없다. 이를 알기 위해 앞에서 정의한 경로가 존재한다고 가정하고 정점 Wor 를 고려해 보자. 어떤 간선이 Wor 에 도착하면 다른 간선을 따라 반드시 떠나야 한다. 나아가 Wor 에 연결된 모든 간선은 사용되어야 한다. 그래서 Wor 에서의 간선은 쌍으로 존재한다. 짝수 개의 간선이 Wor 에 연결되어야 함을 뜻한다. 세 개의 간선이 Wor 에 연결되어 있으므로 모순됨을 알 수 있다. 따라서 그림 2 에서 정점 Gre 에서 출발하여 모든 간선을 한 번씩 돌아서 정점 Gre 로 되돌아오는 경로는 존재하지 않는다. 이와 같은 주장은 임의의 그래프 G 에도 적용된다. 정점 에서부터 모든 간선을 한 번씩 방문하고 정점 로 되돌아 오는 경로가 존재하면 짝수 개의 간선이 각 정점에 연결되어 있어야 한다. 이 문제는 2 절에서 더 자세하게 논의한다.

여기서 몇 가지 공식적인 정의들을 살펴보자.

 (정의 1.1)

그래프 (또는 무방향 그래프) G 는 정점 (또는 node) 의 집합 V 와 간선 (또는 arcs) 집합 E 로 구성되어 있고, 각각의 간선 는 정점의 순서 없는 쌍으로 나타낸다. 만약 정점 와 를 연결하는 유일한 간선 가 존재하면 또는 라고 쓴다. 여기서는 는 무방향 그래프에서 와 간의 간선을 나타내며, 방향이 있는 쌍은 아니다.

방향 그래프 (또는 digraph (다이그래프)) G 는 정점 (또는 nodes) 의 집합 V 와 간선 (또는 arcs) 집합 E 로 이루어져 있고, 각각의 간선 는 정점의 순서를 가지는 쌍이다. 만약 순서를 가지는 정점의 쌍 에 해당되는 유일한 간선 가 존재하면 라고 쓰고 에서 로의 간선을 나타낸다.

그래프 (무방향 또는 방향) 에서 정점의 쌍 와 를 의미하는 간선 는 와 에 부속된다, 라고 말한다. 그리고 정점 와 는 간선 에 부속되어졌다, 하고 인접 정점이라 한다.

G 는 정점 V 와 간선 E 를 가지는 그래프이면 G = (V, E) 라고 표기한다.

특별한 언급이 없으면 집합 E 와 V 는 유한하다 가정하고 V 는 비어 있지 않다고 가정한다.

 (예제 1.2)

그림 2 에서 (무방향) 그래프 G 는 정점의 집합 V 로 다음과 같고

V = {Gre, She, Wor, Buf, Gil, Sho, Cas, Dou, Lan, Mud}

간선의 집합 E 는 다음과 같다.

E = {}.

간선 는 정점의 무순서쌍 {Gre, She} 에 해당하고 간선 는 정점의 무순서쌍 {Cas, Dou} 에 해당된다. 간선 는 (Gre, She) 또는 (She, Gre) 라 표시하고 간선 는 (Cas, Dou) 또는 (Dou, Cas) 라 표기한다. 간선  는 정점 Wor 와 Buf 에 부속되어 있고 정점 Buf 와 Wor 는 인접한다.

 (예제 1.3)

그림 4 는 방향 그래프이다. 방향 간선은 화살표로 나타낸다. 간선 는 정점들의 순서쌍 에 해당되고 간선 은 정점의 순서쌍 를 나타낸다. 간선 는 로 는 로 표기한다.

그림 4  방향 그래프

정의 1 은 정점들의 같은 쌍에 대해서도 서로 다른 간선을 허용한다. 예를 들어, 아래의 그림 5 에서 간선 과 는 둘다 정점의 쌍 를 나타낸다. 이런 간선을 병렬 간선 (parallel edges) 이라 한다. 하나의 정점으로 표기되는 간선을 루프 (loop) 라 한다. 예를 들어, 그림 5 에서 간선 는 루프이다. 그림 5 에서 정점 와 같은 정점은 어떠한 간선을 갖지 않는데 이를 분리된 정점 (isolated vertex) 이라 한다. 루프도 가지지 않고 병렬 간선도 가지지 않은 그래프를 단순 그래프 (simple graph) 라 한다.

그림 5  병렬 간선을 가지는 그래프

그림 6  볼트를 위한 구멍을 가진 금속관

 (예제 1.4)

그림 2 의 그래프는 병렬 간선도 루프도 가지지 않기 때문에 단순 그래프이다.

어떤 저자들은 그래프를 정의할 때 루프와 병렬 간선을 취하지 않는다. 그래프에 대한 정의에 있어 이처럼 동의하지 않는 용어 대부분 다른 용어들도 표준적인 정의를 따르지 않을 것이다. 따라서, 그래프를 다룬 논문이나 저서를 읽을 때, 저자가 취하고 있는 정의를 점검해 볼 필요가 있다.

다음 예제는 제조 문제를 분석할 때 그래프 모델이 어떻게 사용될 수 있는지를 보여 준다.

 (예제 1.5)

많은 구멍을 뚫어야 할 금속판이 있다 (그림 6 을 보라). 그리고 이런 금속판들을 볼트로 조여 제품을 만들 수도 있다. 그런 구멍들은 컴퓨터의 제어 하에 드릴 프레스를 이용하여 뚫릴 것이다. 시간과 경비를 절감하기 위해 드릴 프레스는 가능한 한 빠르게 움직여야 한다. 이 상황을 그래프로 모델화한다.

그래프의 정점들은 구멍에 해당된다 (그림 7 을 보라). 모든 정점의 쌍은 간선에 의해 연결된다. 각각의 간선에는 드릴 프레스가 해당되는 구멍간에 움직이는 시간을 기입한다. 간선상에 숫자를 가지는 그래프 (그림 7 과 같은 그래프) 는 가중치 그래프 (weighted graph) 이다. 간선 에 값이 부여되어 있다면 간선 의 가중치는 이다, 라고 말한다. 예를 들어, 그림 7 에서 간선 의 가중치는 7 이다. 가중치 그래프에서 경로의 길이 (length of a path) 는 경로상의 간선 가중치의 합이다. 예를 들어, 그림 7 에서 에서 출발하여 정점 를 방문하고 정점 에서 끝나는 경로의 길이는 8 이다. 이 문제에서 정점 에서 이와 같은 순서로 정점 에서 끝나는 경로의 길이는 드릴 프레스가 구멍 에서 시작하여 에서 끝내는 데 걸리는 시간으로 다시 표현할 수 있다. 이때 구멍 는 정점 에 해당된다. 모든 정점을 한 번씩 방문하는 최소 길이 경로는 드릴 프레스가 움직이는 최적의 길이를 나타낸다.

그림 7  그림 6 의 금속판을 위한 그래프 모델. 간선 가중치는 드릴 프레스가 움직이는 데 걸리는 시간이다.

이 문제에서는 정점 에서 시작하여 정점 에서 끝내는 경로라고 가정하자. 최소 길이 경로는 정점 에서 모든 정점을 단 한 번씩 거쳐 정점 로 가는 모든 경로를 열거하여 가장 짧은 것을 선택해 찾을 수 있다 (표 1 을 보라). 정점 를 순서대로 방문하는 경로가 최소 길이를 가짐을 알 수 있다. 물론 출발점과 끝나는 점이 서로 다른 쌍에서는 이보다 더 짧은 경로를 얻을 수 있을지 모른다.

표 1  그림 7 그래프에 에서 로의 모든 정점을 한 번만 지나가는 경로와 그 길이

예제 5 에서 했던 것처럼, 정점 에서 정점 로 가는 모든 경로를 열거하는 방식은 정점 에서 모든 정점을 한 번씩 방문하여 로 가는 최소 길이 경로를 찾는, 다소 시간이 많이 결리는 방법이다. 불행하게도 임의의 그래프에 대해서 보다 실용적인 방법은 알지 못한다. 이 문제는 판매원 방문 문제 (traveling salesperson problem) 이다. 헤밀턴 사이클과 판매원 방문 문제에서 이 문제가 논의될 것이다.

 (예제 1.6)   유사도 그래프

이 예제는 객체들의 특징에 따라 "비슷한 (like)" 객체들을 클래스로 묶는 문제이다. 예를 들어, 특별한 알고리즘이 여러 사람에 의해 C 로 구현되었고, 프로그램의 어떤 특징에 따라 "비슷한" 프로그램을 클래스로 나누었다고 하자 (표 2 를 보라). 다음과 같은 특징들을 선택했다고 하면,

1. 프로그램에서의 라인의 수

2. 프로그램에서의 return 문장의 빈도수

3. 프로그램에서의 함수 호출 횟수

표 2  같은 알고리즘을 구현한 C 프로그램들

유사도 그래프 (similarity graph) G 는 다음과 같이 구축된다. 정점은 프로그램에 해당된다. 정점은 로 표기하고 는 특징 의 값이다. 비유사도 함수 (dissimilarity function) 는 다음과 같이 정의한다.

각 정점 쌍 와 에 대해 다음과 같이 둔다.

프로그램 에 해당하는 정점을 라 하면 다음을 얻을 수 있다.

와 가 두 개의 프로그램이라면 는 두 프로그램이 얼마나 다른지를 나타낸다. 가 큰 값이면 서로 다름을 나타내고 반면에 작은 값은 서로 유사하다는 것을 뜻한다.

고정된 값 S 에 대해, 이면 정점 와 사이에 간선을 추가한다 (일반적으로 S 가 다르면 다른 유사 그래프가 존재할 것이다). 만약 이거나 에서 로의 경로가 존재하면 와 는 같은 클래스안에 있다 (in the same class) 라고 한다. 그림 8 에서 표 2 에서 S = 25 인 프로그램에 대응되는 그래프를 보이고 있다. 이 그래프에서 프로그램들은 3 가지 클래스, {1, 3, 5}, {2}, {4} 로 분류된다. 실제 문제에서 S 에 대한 근사값은 시행 착오에 의해 선택되거나, S 의 값은 미리 계산된 어떤 기준에 따라 자동적으로 선택될 것이다.

그림 8  표 2 에서 S=25 에 대응되는 유사도 그래프

예제 6 은 패턴 인식 (pattern recognition) 이라는 주제에 속하는 문제이다. 패턴 인식은 주어진 자료의 성질에 따라 자료를 클래스로 분류하는 것과 관련이 있다. 컴퓨터에 의한 패턴 인식은 실상의 문제에 있어 아주 중요하다. 예를 들어, X-레이로부터 암을 발견한다든지, 감사 받아야 할 납세 신고서를 잡아내거나, 위성 사진을 분석하고, 글자 인식, 일기 예보를 하는 데 사용되어 왔다.

 (예제 1.7)    (하이퍼큐브)

전통적인 컴퓨터는, 종종 직렬 컴퓨터 (serial computer) 라고 하는, 한 번에 하나의 명령을 수행한다. 우리의 알고리즘의 정의 역시 이와 같이 한번에 하나의 명령이 수행된다고 가정한다. 이와 같은 알고리즘을 직렬 알고리즘 (serial algorithm) 이라 한다. 근래에 하드웨어 가격이 떨어지면서 한 번에 여러 개의 명령을 수행할 수 있는 다수의 프로세서를 가지는 병렬 컴퓨터 (parallel computer) 를 쉽게 제작할 수 있게 되었다. 그래프는 이런 기계들을 묘사하는 데 아주 편리한 모델이다. 이에 관련된 알고리즘이 병렬 알고리즘 (parallel algorithm) 이다. 많은 문제들을 직렬 컴퓨터가 아닌 병렬 컴퓨터를 이용하여 보다 빠르게 해결할 수 있게 되었다. 여기서 -큐브 (n-cube) 또는 하이퍼큐브 (hypercube) 라는 병렬 계산을 위한 하나의 모델에 대해 논의해 보자.

그림 9  3-큐브

-큐브는 프로세서를 가진다. 이때 이고 각 정점은 0, 1, ...,  라는 번호를 부여한다. 각 프로세서는 각각의 지역 메모리를 가진다. 간선은 부여된 값을 이진수로 표현할 때 한 비트만 다른 두 정점을 연결한다. 단위 시간 동안에 -큐브 안에 있는 모든 프로세서들은 동시에 명령을 수행할 것이고 인접한 프로세서에게 통신을 할 것이다. 하나의 프로세서가 인접하지 않은 프로세서로 통신을 하고자 한다면, 첫 번째 프로세서는 경로가 포함되어 있는 메시지를 보낼 것이고 궁극적으로 받아야 할 목적지로 가게 된다. 하나의 프로세서가 인접하지 않은 프로세서로 통신하려면 약간의 단위 시간이 걸릴 것이다.

-큐브 역시 재귀적으로 표현할 수 있다. 1-큐브는 두 개의 프로세서를 가지고 0 과 1 의 번호가 부여되고 하나의 간선을 가진다. 과 를 이진수로 0, 1, ...,  의 번호가 부여된 두 개의 -큐브라 하자(그림 10 을 보라). 에서 로의 번호가 같은 각 정점의 쌍에 간선을 부여한다. 그런 다음 안의 각 정점에 번호 L 를 부여하여 0L 로 바꾸고, 의 번호에 L 을 추가하여 1L 로 변경한다. 그러면 -큐브를 만들 수 있다.

그림  10 두 개의 3-큐브를 결합하여 하나의 4-큐브를 얻는다.

-큐브는 이와 같은 기계들이 실제로 만들어지고 실행되기 때문에 중요한 계산 모델이다. 나아가 몇 개의 다른 병렬 계산 모델들이 하이퍼큐브로 시뮬레이션될 수 있다. 후자의 관점은 예제 6.3.5 와 6.6.3 에서 보다 자세히 언급할 것이다.

이 서론 절에서는 그래프 이론에 자주 나타나는 몇 가지 특별한 그래프를 정의하면서 끝맺음을 하고자 한다.

 (정의 1.8)   

개의 정점을 가지는 완전 그래프 (complete graph on n vertices) 는 이라 표기하고 모든 서로 다른 정점들 간에 간선이 존재하는 개의 정점을 가지는 단순 그래프이다.

 (예제 1.9)   

네 개의 정점을 가지는 완전 그래프 는 그림 11 에서 보이고 있다.

그림 11  완전 그래프

 (정의 1.10)   

그래프 G = (V, E) 가 이분 (bipartite) 이라 함은 정점의 집합 V 가 두 개의 부분 집합 과 으로 나누어지고, E 에 속한 각각의 간선이 하나는 에 속한 정점에 부속되고 하나는 에 속한 정점에 부속될 때를 말한다.

 (예제 1.11)  

그림 12 그래프는 다음과 같이 분리됨으로 이분이다.

과

각 간선은 하나는 에 속한 정점에 또 하나는 에 속한 정점에 부속된다.

 

그림 12  이분 그래프

 

그림 13  이분이 아닌 그래프

정의 10 은 가 이분 그래프에서의 간선이라면 는 에 있는 어느 한 정점에 부속되고 에 있는 어떤 한 정점에 부속된다는 것을 의미한다. 이는 에 속한 정점 과 에 속한 가 있으면 과 사이에 간선이 존재한다는 것은 아니다. 예를 들어, 그림 12 의 그래프는 각 간선이 에 있는 한 정점에 부속되고 안의 정점에 부속되므로 이분 그래프이다. 하지만 과 안의 모든 정점들 간에 간선이 있는 것은 아니다. 예를 들어, 간선 는 존재하지 않는다.

 (예제 1.12)  

그림 13 의 그래프는 이분 그래프가 아니다. 때때로 어떤 그래프가 이분 그래프가 아니라는 것을 모순을 사용하는 것이 가장 쉽다.

그림 13 에서 그래프가 이분 그래프라고 가정하자. 그러면 그 정점의 집합은 두 개의 부분 집합 과 로 분리할 수 있고, 각 간선은 하나는 에 있는 정점에 또 하나는 에 있는 정점에 부속된다. 정점들 그리고 에 대해 생각해 보자. 과 가 인접하므로 하나는 에 다른 하나는 에 속한다. 는 에 속하고 는 에 속하므로 는 에 포함된다. 와 가 인접하고 가 에 포함되므로 는 에 속한다. 그러나 여기서 가 과 에 동시에 포함되므로 과 가 서로 소여야 하는 것에 위배된다. 따라서 그림 13 의 그래프는 이분이 아니다.

 (정의 1.13)  

과 개의 정점을 가지는 완전 이분 그래프 (complete bipartite graph on m and n vertices) 는 이라 표기하고 정점의 집합이 개 정점을 가지는 집합 와 개 정점을 가지는 집합 으로 나뉘어지고 정점 과 각 정점 간에 간선이 존재한다. 이때   는 에 포함되고 는 에 포함된다.

 (예제 1.14)  

두 개와 네 개의 정점을 가지는 완전 이진 그래프 는 그림 14 에서 보이고 있다.

그림 14  완전 이분 그래프