그래프 이론 : 경로 와 사이클

Paths and Cycles

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

어떤 그래프에서 정점을 도시라 하고 간선을 도로로 간주한다면, 경로는 어떤 도시를 출발하여 몇몇 도시를 거쳐 어떤 도시에서 끝내는 여행에 해당한다. 경로에 대한 공식적인 정의로 시작해 보자.

(정의 2.1)

와 을 그래프에서 정점이라 하자. 에서 의 길이 을 가지는 경로 (path) 는 에서 시작하여 에서 끝나는 개의 정점들과 개의 간선들이 다음과 같이 교대로 나타나는 순서열이다.

이때 에 대해 간선 는 정점 과 에 부속되어 있다.

정의 1 에서의 형식은 다음을 의미한다 : 정점 에서 출발한다 ; 간선 을 거쳐 로 간다 ; 간선 을 거쳐 정점 로 간다 ; 등등.

(예제 2.2)

그림 1 의 그래프에서

(경로 1)

은 정점 1 에서 2 로 가는 길이가 4 인 경로이다.

그림 1 길이가 6 인 경로 와 길이가 0 인 경로 (6) 를 가지는 연결된 그래프

(예제 2.3)

그림 1 의 그래프에서 정점 6 하나로 구성된 경로 (6) 은 정점 6 에서 정점 6 으로 가는 길이 0 인 경로이다.

병렬 간선이 없는 경우에는 경로를 표기하는 데 있어 간선을 표기하지 않을 수도 있다. 예를 들어, 경로 (1) 은 다음과 같이 표기할 수 있다.

(1, 2, 3, 4, 2)

연결된 그래프 (connected graph) 는 경로상에서 어떤 정점에서 어떠한 정점으로도 갈 수 있는 그래프이다. 공식적인 정의는 다음과 같다.

(정의 2.4)

그래프 G 안의 어떤 정점들 와 가 연결되었다면 (connected) 에서 로의 경로가 존재하기 때문에 연결되었다.

(예제 2.5)

그림 1 의 그래프 G 는 G 안의 어떤 정점들 와 로의 경로가 존재하기 때문에 연결되었다.

(예제 2.6)

그림 2 의 그래프 G 는 연결되어 있지 않다. 예를 들어, 정점 에서 로 가는 경로가 없기 때문이다.

그림 2 연결되지 않은 그래프

(예제 2.7)

G 는 미국의 50 개 주로 구성된 정점의 집합인 그래프라 하자. 주 와 주 가 경계를 같이하면 주 와 사이에 간선을 긋는다. 예를 들어, 켈리포니아와 오리건 그리고 일리노이와 미주리 사이에 간선이 존재한다. 조지아와 뉴욕 사이에는 간선이 존재하지 않고 유타와 뉴멕시코 사이에도 간선이 없다 (경계점은 세지 않는다 ; 주는 경계선을 공유하여야 한다). 그래프 G 는 하와이와 켈리포니아 (또는 하와이에서 다른 어떤 주) 사이에 경로가 존재하지 않으므로 연결되어 있지 않다.

그림 1 과 2 에서 보는 바와 같이 연결된 그래프는 하나의 "조각" 으로 구성되어 있지만 연결되지 않은 그래프는 두 개 또는 그 이상의 "조각들" 로 구성되어 있다. 이 "조각들" 은 원래의 그래프의 부분 그래프 (subgraph) 이고 요소 (components) 라 한다. 부분 그래프에 관련하여 공식적인 정의를 내린다.

그래프 G 의 부분 그래프 G' 는 G 로부터 어떤 간선과 정점들을 선택하여 얻을 수 있는데 이 때 와 를 포함시켜야 한다. 이 제약 사항은 G' 가 실제로 그래프가 되도록 해 준다. 공식적인 정의는 다음과 같다.

(정의 2.8)

G = (V, E) 를 그래프라 하자. 다음과 같을 때 (V', E') 를 G 의 부분 그래프 (subgraph) 라 한다.

(a) V' ⊆ V 와 E' ⊆ E,

(b) 모든 간선 ∈ E' 에 대하여 가 와 에 부속된다면 , ∈ V' 이다.

(예제 2.9)

그림 3 의 그래프 G' = (V', E') 는 V' ⊆ V 이고 E' ⊆ E 이므로 그림 4 의 그래프 G = (V, E) 의 부분 그래프이다.

그림 3 그래프

그림 4 의 부분

그림 4 그래프 그림 3 에서 이 부분 그래프를
나타내고 있다

(예제 2.10)

그림 5 의 그래프 G 에서 적어도 하나의 정점을 갖는 모든 부분 그래프를 찾아라.

만약 간선이 없으면 정점이 하나 또는 둘 다 선택하여 그림 6 에서 보는 바와 같이 부분 그래프 , , 그리고 을 얻을 수 있다. 가능한 하나의 간선 을 선택하면 에 부속된 두 개의 정점을 다 선택해야 한다. 이와 같은 경우 그림 6 에서 보는 바와 같이 부분 그래프 를 얻는다. 따라서 G 는 그림 6 에서 보는 바대로 네 개의 부분 그래프를 가진다.

그림 5 예제 10을 위한 그래프

그림 6 그림 5 그래프의 4 개의 부분 그래프

(정의 2.11)

G 는 그래프이고 을 G 안의 하나의 정점이라 하자. 에서 시작되는 어떤 경로에 포함된 G 안의 모든 간선들과 정점들로 구성된 G 의 부분 그래프 G' 는 를 포함하는 G 의 요소 (component) 라 한다.

(예제 2.12)

그림 1 의 그래프 G 는 그 자체가 하나의 요소를 가진다. 사실 한 그래프가 연결되어 있을 필요 충분 조건은 그 그래프가 정확히 하나의 요소일 때이다.

(예제 2.13)

G 를 그림 2 의 그래프라 하자. 를 포함하고 있는 G 의 요소는 다음 부분 그래프이다.

, ,

를 포함하고 있는 G 의 요소는 다음 부분 그래프이다.

, ,

를 포함하는 G 의 요소는 다음 부분 그래프이다.

, ,

그래프 G = (V, E) 요소의 또 다른 특징은 다음의 규칙에 의한 정점의 집합 V 상의 관계 R 을 정의함으로써 얻을 수 있다.

, 에서 로의 경로가 존재할 때.

R 이 V 상에 동치 관계이고 만약 ∈ V 인 을 포함하는 요소의 정점들의 집합이 다음과 같이 동치류 (equivalence class) 임을 보일 수 있다.

경로의 정의는 정점 또는 간선, 혹은 모두의 반복을 허용한다는 데 주의하자. 경로 (1) 에서 정점 2 는 두 번 나타난다.

경로의 부분 클래스는 정점 또는 간선의 반복을 허용하지 않음으로써 혹은 정의 1 의 정점 과 을 동일하게 함으로써 얻을 수 있다.

(정의 2.14)

와 를 그래프 G 안의 정점이라 하자. 에서 로의 단순 경로 (simple path) 는 에서 까지 반복되는 정점이 없는 경로 (path) 이다. 사이클 (cycle) (또는 회로 (circuit)) 은 에서 까지 반복되는 간선 없이 길이가 0 이 아닌 경로이다.

단순 사이클 (simple cycle) 는 시작과 끝나는 것이 인 것을 제외하고는 반복되는 정점이 없는 에서 로의 사이클이다.

(예제 2.15)

그림 1 의 그래프에 대하여 다음을 알 수 있다.

경 로

단순 경로?

사이클?

단순 사이클?

(6, 5, 2, 4, 3, 2, 1)

(6, 5, 2, 4)

(2, 6, 5, 2, 4, 3, 2)

(5, 6, 2, 5)

(7)

아니오

예

아니오

예

아니오

예

아니오

예

아니오

다음은 서론에서 소개하였던 문제를 그래프에서 모든 간선을 한 번만 방문하는 사이클을 찾는 문제로 다시 살펴보도록 하자.

(예제 2.16) 쾨닉스베르그 다리 문제

그래프 이론의 첫 논문은 1736 년 레오나드 오일러 (Leonhand Euler) 의 것이었다. 그 논문은 현재 쾨닉스베르그 (Königsberg) 다리 문제에 대한 해법을 포함한 일반적인 그래프 이론을 제시하였다.

쾨닉스베르그 (Königsberg, 지금 러시아의 칼리닌그라드) 에 있는 프레겔 강에 있는 두 개의 섬이 그림 7 과 같이 다리에 의해 각각 연결되어 있고 강둑도 다리로 연결되어 있다. 문제는 어떤 위치 - A, B, C, 또는 D - 에서 출발하여 ; 각각의 다리를 한 번만 건너서 ; 출발점으로 돌아오는 것이다.

그림 7 쾨닉스베르그 다리

그림 8 쾨닉스베르그 다리의 그래프 모델

이 다리의 구성은 그림 8 과 같이 그래프로 모델화할 수 있다. 정점은 위치를 나타내고 간선은 다리를 나타낸다. 쾨닉스베르그 다리 문제는 그림 8 의 그래프에서 모든 에지와 모든 정점이 다 포함되어 있는 사이클을 찾는 문제로 변형된다. 오일러의 업적을 기리어 그래프 G 안의 모든 정점과 모든 에지가 포함되는 사이클을 오일러 사이클 (Euler cycle) 이라 부른다. 서론의 논의로부터, 그림 8 의 그래프 안에는 정점 A 에 부속된 모서리선이 홀수이므로 오일러 사이클은 없다 (사실, 그림 8 의 그래프에서, 모든 정점은 홀수 개의 간선이 부속되어 있다).

오일러 사이클의 존재성에 대한 해는 정점의 차수 개념을 도입하면서 그럴 듯하게 출발한다. 정점 의 차수 (degree of a vertex ) 는, , 에 부속된 정점의 수이다 (정의에 의해 상의 각 루프는 의 차수가 2 를 보태게 된다). 서론에서 어떤 그래프 G 는 오일러 사이클을 가지면 G 안의 모든 정점은 짝수 차수를 가짐을 알았다. 그리고 G 가 연결되었음을 증명할 수 있다.

(정리 2.17)

그래프 G 가 오일러 사이클을 가지면, G 는 연결되어 있고 각 정점은 짝수 차수이다.

증명 G 가 오일러 사이클을 가진다고 가정하자. 서론에서 G 안의 모든 정점은 짝수 차수를 가진다고 주장했다. 와 가 G 안의 정점이면, 에서 까지 취한 오일러 사이클의 부분은 에서 까지의 경로 역할을 한다. 따라서 G 는 연결되었다.

정리 2.17 의 역 역시 참이다. [Fowler] 에 의한 수학적 귀납법 증명 방법을 제시한다.

(정리 2.18)

G 가 연결된 그래프이고 모든 정점이 짝수 차수를 가지면 G 는 오일러 사이클을 가진다.

증명 이 증명은 G 안의 간선의 수 에 대한 귀납법으로 증명한다.

기본 단계 G 가 연결되어 있으므로, G 가 간선을 가지지 않으면, G 는 하나의 정점으로 구성된다. 오일러 사이클은 간선이 없는 하나의 정점으로 구성된다.

귀납 단계 G 가 0 보다 큰 개의 간선을 가진다고 하면, 인 개의 간선을 가지고, 모든 정점이 짝수 차수를 가지는 연결된 그래프는 오일러 사이클을 가진다고 가정한다.

정점이 하나 또는 둘인 연결된 그래프는 각각 짝수 차수를 가지며 오일러 사이클을 가진다는 것은 바로 증명된다. 따라서 그래프의 정점이 적어도 3 개라고 가정한다.

G 가 연결되어 있으므로, 정점 과 에 부속된 간선 과 정점 와 에 부속된 간선 를 가지는 G 안의 정점 가 존재한다. 정점은 그대로 두고 간선 과 를 제거한 다음, 정점 과 에 부속된 간선 를 추가하여 그래프 G' 을 얻는다 [그림 9(a) 을 보라]. 그래프 G' 의 각 요소는 보다 작은 간선을 가지고 그래프 G' 각 요소 안의 모든 정점은 짝수 차수를 가진다는 것을 유념하라. G' 이 하나 또는 두 개의 요소를 가짐을 보인다.

를 정점이라 하자. G 가 연결되었으므로 G 안의 에서 으로의 경로 P 가 존재한다. 경로 P 에서 정점 에서 출발하여 G' 안에 있는 간선의 일부분으로 구성된 것을 경로 P' 라 하자. P' 는 , 또는 에서 끝이나야 하는데, 그 이유는 P 가 G' 안의 경로에서 끝내는 한 방법이 P 가 삭제된 간선 또는 중 하나를 포함하고 있기 때문이다. P' 이 에서 끝이 나면, 는 G' 의 과 같은 요소 안에 존재한다. P' 가 에서 끝이나면 [그림 9(b) 를 보라], 는 G' 의 와 같은 요소 안에 존재한다. 또한 는 G' 의 과 같은 요소 안에 존재한다 (G' 의 간선 는 과 에 부속되어 있기 때문이다). P' 는 에서 끝나면, 는 와 같은 요소 안에 존재한다. 그러므로 G' 안의 어떤 정점도 또는 와 같은 요소 안에 존재한다. 따라서 G' 은 하나 또는 두 개의 요소를 가진다.

그림 9 정리 2.18 의 증명. (a) 에서 간선 과 를 제거하고 를 추가한다. (b) 에서 P (간선 를 제외한 것) 는 G 에서 에서 으로 경로이고, P' (굵은 실선으로 표시된 것) 는 역시 G' 에 있는 간선들로 에서 출발하는 P 의 일부분이다. 보는 바와 같이, P' 는 에서 끝난다. 가 G' 에 속하기 때문에, G' 에 에서 으로의 경로가 존재한다. 그래서 와 은 같은 요소이다. (c) 에서 C' (굵은 선으로 표시된 것) 는 하나의 요소로서 오일러 사이클이다. 그리고 C'' (가는 실선으로 표시한 것) 는 또 다른 요소를 이루는 오일러 사이클이다. C' 에서 를 , C'', 으로 대체하면 G 를 위한 오일러 사이클 (연한 굵은 선과 가는 실선, 점선으로 표시된 것) 을 만들 수 있다.

그림 9 정리 2.18의 증명. (a) 에서 간선 과 를 제거하고 e 를 추가한다. (b) 에서 P (간선 e 를 제외한 것 )는 G에서 v 에서 으로 경로이고, P' (굵은 실선으로 표시된 것) 는 역시 G' 에 있는 간선들로 v 에서 출발하는 P 의 일부분이다. 보는 바와 같이, P' 는 에서 끝난다. e 가 G' 에 속하기 때문에, G' 에 v 에서 으로의 경로가 존재한다. 그래서 v와 같은 요소이다. (c) 에서 C' (굵은 선으로 표시된 것) 는 하나의 요소로서 오일러 사이클이다. 그리고 C'' (가는 실선으로 표시한 것) 는 또 다른 요소를 이루는 오일러 사이클이다. C' 에서 를 , C'', 대체하면 G 를 위한 오일러 사이클 (연한 굵은 선과 가는 실선, 점선으로 표시된 것) 을 만들 수 있다.

G' 가 하나의 요소를 가진다면, 즉, 연결되어 있다면, 귀납적 가정을 G' 는 오일러 사이클 C' 를 가진다는 결론에 적용할 수 있다. 이 오일러 사이클은 G 안에 오일러 사이클을 생성할 수 있도록 수정되어질 것이다 : C' 에서 간선 을 가져와서 간단히 간선 과 와 대체한다.

G' 이 두 개의 요소를 갖는다고 가정하자 [그림 9(c) 를 보라]. 귀납 가정에 의해, 를 포함하는 요소는 오일러 사이클 C' 를 가지고, 를 포함하는 요소는 에서 시작하고 끝나는 오일러 사이클 C'' 를 가진다. G 에서 오일러 사이클은 C' 을 다음과 같이 수정하여 얻어진다. 즉, C' 의 을 다음에 C'', 다음에 와 대체하거나, C' 의 을 다음에, C'', 다음에 과 대체한다. 귀납적 단계는 끝이다 ; G 는 오일러 사이클을 갖는다.

G 가 연결된 그래프이며 모든 정점은 짝수 차수를 가지고, 또 G 가 간선이 몇 개 되지 않는다면, 관찰에 의해 오일러 사이클을 항상 찾을 수 있다.

(예제 2.19)

그림 10 의 그래프를 G 라 하자. 정리 18 을 이용하여 G 가 오일러 사이클을 가짐을 증명하려 한다. G 에 대한 오일러 사이클을 찾아라.

G 는 연결되어 있고 다음을 관찰할 수 있다.

, ,

모든 정점의 차수가 짝수이므로 정리 18 에 의해, G 는 오일러 사이클을 가진다. 관찰에 의해 다음과 같이 오일러 사이클을 찾을 수 있다.

그림 10 예제 19 를 위한 그래프

(예제 2.20)

도미노는 하나의 직사각형을 2 개의 정사각형으로 나눈 것으로 0, ..., 6 중에 하나의 숫자가 있다. 하나의 도미노위에 2 개의 사각형이 같은 숫자를 가질 수 있다. 서로 다른 도미노들이 맞닿는 도미노들이 인접한 사각형이 같은 숫자를 가지도록 하나의 원이 되도록 정열할 수 있다.

이 상황을 0 과 6 이 표시된 정점이 7 개를 가지는 그래프 G 로 모델화할 수 있다. 차수는 도미노들을 표현한다 : 각각이 다른 정점의 짝 사이에는 하나의 간선이 존재하고, 각각의 정점에는 하나의 루프가 존재한다. G 는 연결된 그래프임을 알아야 한다. 자, 이제 도미노들을 같은 숫자를 가진, 인접한 사각형을 갖는 도미노끼리 서로 맞닿도록 하나의 원에 정렬할 수 있다. 이에 대한 필요 충분 조건은 G 가 오일러 사이클을 갖는다. 각 정점들의 차수는 8 이고 (루프는 차수가 2 가 됨을 유의하자), 각 정점은 짝수 개를 가진다. 정리 18 에 의해 G 는 오일러 사이클이다. 그러므로 도미노들을 서로 같은 숫자끼리 이웃한 곳에 맞닿도록 하나의 원에 정리할 수 있다.

모든 정점이 짝수 차수를 가지지 않은 연결된 그래프는 무어라 하는가? 첫 관찰 (따름 정리 2.22) 은 홀수 차수의 정점의 수가 홀수일 때이다. 이는 다음 사실 (정리 2.21), 그래프 안의 모든 차수의 합이 짝수라는 사실을 얻는다.

(정리 2.21)

G 가 개의 간선과 정점들이 을 가진 그래프라면 다음과 같은 차수를 갖는다.

특히, 그래프 안의 모든 정점들의 차수의 합은 짝수이다.

증명 모든 정점들의 차수들을 합산할 때, 각 모서리 를 두 번씩 센다. 한번은 의 차수에서 로 다시 한 번 더 센다. 따라서 주어진 결론이 성립한다.

(따름정리 2.22)

어떤 그래프에서 홀수 차수의 짝수 개의 정점이 존재한다.

증명 정점을 두 개의 그룹으로 나누자 : 짝수 차수를 가지는 것을 라 하고 홀수 차수를 가지는 것을 라 하자. 이것을 다음과 같이 두자.

정리 21 에 의해, S + T 는 짝수이다. S 가 짝수의 합이므로 S 는 짝수이다. 그러므로 T 는 짝수이다. 그러나 T 가 개의 홀수의 합이고, 따라서 은 짝수이다.

연결된 그래프 G 는 홀수 차수는 와 , 두 개의 정점만 가진다고 가정하자. 에서 로의 간선 를 임시적으로 추가하자. 그 결과 그래프 G' 는 연결되고 모든 정점은 짝수 차수이다. 정리 2.18 에 의해, G' 는 오일러 사이클을 가진다. 오일러 사이클에서 를 제거하면, 에서 로 가는 모든 정점과 간선을 포함하는 반복되는 간선 없는 경로를 얻을 수 있다. 어떤 그래프가 홀수 차수를 가지는 두 정점 와 로 가는 모든 정점과 간선을 포함하는 반복되는 간선 없는 경로를 얻을 수 있다. 어떤 그래프가 홀수 차수를 가지는 두 정점 와 만을 가질 때, 에서 로 가는 모든 간선과 정점을 포함하는 간선이 반복됨이 없는 경로가 존재한다는 것을 보였다. 그 역도 유사하게 증명할 수 있다.

(정리 2.23)

어떤 그래프가 에서 로 가는, 모든 정점과 모든 간선을 포함하는 반복된 모선이 없는 경로가 존재할 필요 충분 조건은 그 그래프가 연결되고 와 만이 홀수 차수를 가질 때이다.

증명 어떤 그래프가 모든 간선과 모든 정점을 포함하는 에서 로의 간선의 반복이 없는 경로 P 를 가진다고 가정하자. 그 그래프는 확실히 연결되었다. 에서 로의 간선 를 추가한다면, 그 결과 그래프는 추가된 간선을 가지는 경로 P 인 오일러 사이클이다. 정리 2.17 에 의해, 모든 정점은 짝수 차수를 가진다. 와 에만 영향을 주었던 추가된 간선을 제거함으로써 각각의 차수는 1 씩 감소된다. 따라서 원래의 그래프에서, 와 는 홀수 차수를 가지고 모든 다른 정점은 짝수 차수를 가진다.