Paths  and  Cycles

 

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

 

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

 (정의 2.1)  

 (예제 2.2)  

                              (경로 1)

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

 (예제 2.3)  

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

(1, 2, 3, 4, 2)

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

 (정의 2.4)  

 (예제 2.5)  

 (예제 2.6)  

 

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

 (예제 2.7)  

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

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

 (정의 2.8)  

 (예제 2.9)  

 

그림 3  그래프

 

그림 4  의 부분

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

 (예제 2.10)  

 

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

 

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

 (정의 2.11)  

 (예제 2.12)  

 (예제 2.13)  

,    ,    

,    ,    

,    ,    

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

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

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

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

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

 (정의 2.14)  

 (예제 2.15)  

경          로

단순 경로?

사이클?

단순 사이클?

(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)   쾨닉스베르그 다리 문제

그림 7  쾨닉스베르그 다리

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

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

 (정리 2.17)

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

 (정리 2.18)

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

 (예제 2.19)

,    ,    

 

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

 (예제 2.20)

 (정리 2.21)

 (따름정리 2.22)

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

 (정리 2.23)

정리 2.23 을 일반화한 것이 연습 문제 42 와 44 에 주어져 있다.

특별한 결과보다는 7.2 절에서 사용될 다음을 증명함으로써 결론을 짓고자 한다.

 (정리 2.24)

 

그림 11  단순 사이클 또는 단순 사이클로 축소 가능한 사이클