오일러 그래프

[임꺽정]

Eulerian Graph and Hamiltonian Graph

  

그래프이론 중에서 가장 중요한 문제는 주어진그래프

에서 어떤 원하는 행로나 cycle 등을 찾는 방법이다.

우리는 이것을 학습하기 전에  기본적인 그래프 용어를 다시 알아보도록 합시다.

 

 

정의 1.  무방향 그래프 G에서 한 정점 v의 차수 (degree)는 정점 v에 연결되는 모서리의 개수이다.

정점 v의 차수를 deg(v)로 표시하며, deg(v)는 정점 v에 연결된 모서리의 수이다.

 

 

  다음 그래프에서 정점에 표시된 수는 각 정점의 degree(차수)를 나타낸다.

                  

 

 

정의 2.  단순 방향 그래프 G =< V , E >에서 한 정점에 대하여 정점 v를 출발점으로 갖는 모서리의 수를 v의 외부 차수(outdegree)라고 하며, v를 도착점으로 갖는 모서리의 수를 v의 내부 차수( indegree) 라고 말한다. 내부와 외부 차수의 합을 총 차수 (total degree) 라고 말한다.

 

 

   

이제  모든 vertex v에 대한 deg(v)의 합을 구하여 봅시다.

임의의 무방향 그래프 G에서  임의의 모서리(a,b)에 대하여,

각각의 deg(a)와 deg(b)의 수는 중복하여 더하게 된다.

결국 G =( V , E )가 무방향 그래프라면  

모든 vertex v에 대한 deg(v)의 합은

와 같이 전체 모서리의 수에  2 배와 같다.   

 

 

 

 

 

문제 2.   임의의 무방향 그래프에 대해, 홀수 차수를

갖는 정점의 수는 짝수임을 증명하시오.

 

 

 

 

각 정점이 같은 차수를 갖는 무방향 그래프를

정규(regular)그래프라고 하였다.

 

이 때, 정리 1의 응용으로 우리는 다음과 같은 문제를 생각하여 봅시다.

 

모든 정점이 차수 4를 갖고  전체 10개의 모서리를 갖는 정규그래프가 존재할 수 있는가 ?

 

우리는 이를 해결하는 도구로 정리 1을 사용할 수 있다.

즉,  2｜E｜= 20 = 4｜V｜이어야 하므로 차수 4인 5개의 정점을 갖는 그래프가 존재한다.  

다음 그림은 위 조건을 만족하는  2 개의 비동형 그래프이다.

 

 

 

문제 3.  모든 정점의 차수가  3인  20개의 모서리를

갖는 regular 그래프는 존재하는가 알아보시오.

 

 

 

 

이제  Euler의  Konigsberg의 다리문제를 해결하기

위하여 각 정점에서의 차수를 사용하여 봅시다.

 

앞 절에서 학습하였듯이, Konigsberg 도시는 Pregel강에 의하여 4개의 구역으로 나누어졌다.

 다음 그림처럼 ,이 지역은 7개의 다리로 연결되어있었고 주민들은 어느 점을 시작하여 산책하면 한 번 지나간 다리는 다시 거치지 않고 7개의 다리를 전부 산책할 수 있는가를  항상 궁금하게 생각하였다고 한다.

이 때 Euler라는 대수학자가 정점의 차수를 이용하여 해결할 수 있었으며, 이것이 곧 그래프이론 (graph theory) 의 시작이었던 것은 앞에서 말한바 있다.

이러한 문제를 해결하기 위하여, Euler는 그림 2처럼 그래프의 정점과 간선을 이용하여 간단하게 표현하였고. 여기서 각각의 정점의 차수는

   deg(1) = deg(2) = deg(3) = 3,  deg(5) = 5.

 

위 문제의 해결은 그래프에서 홀수 차수의 정점의 수에

달려있다는 것을 Euler는 발견했다.

 

 

 

정의 3.   G =( V , E )를 무방향 그래프라고 하자.

만일 각각의 모서리를 정확하게 한 번씩 경유해서

그래프의 모든 모서리를 지날 수 있는 경로가

존재한다며, 그래프 G 는 Euler경로 (Euler path)를

갖는다고 한다.  또,  Euler circuit 이란 Euler

경로로서 circuit인 것을 의미한다.

 

 

이제 Graph이론의 가장 중요한 정리를 학습하도록 합시다

 

 

정리 2.  G =( V , E )를 무방향 그래프라고 하자.

이 때  그래프 G가 Euler 경로를 갖기 위한 필요충분

조건은  그래프 G가 연결된 그래프이며, 모든 정점의

차수(degree)가 짝수인 것이다.

 

 

증명.  위 정리의 증명은 그래프이론에 대한 표준적인

교재들을 참고하여 학습하기 바랍니다.

  

 

 

정리 3.  G =( V , E )를 무방향 그래프라고 하자.

 (1) If a graph  G has more than two vertices of

odd degree, then there can be no Euler path in G.

 (2)  If  G  is connected and has exactly two vertices of odd degree, there is an Euler Path

in G.

  Any Euler path in G must begin at on vertex of odd degree and end at the other.

 

 

 

  Euler경로는 주어진 그래프에서 모서리에 관한 경로를 발견하였지만 , Euler는 모든 정점을 경유하는 경로에 대하여 다루지 않았다.

여기서 우리는 연결된 그래프가 각 정점을 정확히 한번만 경유하는 경로를 갖고 있는지를 생각하여봅시다.

이와 같은 문제는,  salesman의 여행 등과 같이 경제적으로 의미있는 응용문제이다.

즉, 정점들은 방문할 도시들을 나타냈으며, 이 게임의 목적으로는 각 도시를 정확히 한 번만 경유하는 최적의 sales 여행경로을 발견할 수 있는가하는 문제이다.