[이산수학] (8) Eulrian Graph

Eulrian graph(한붓그리기)

시점과 종점이 같고, G의 모든 edge를 정확히 한번씩만 지나가는 walk를 Eulrian Tour라 부른다.

만약 G가 Eulrian Tour를 가진다면, G를 Eulrian이라 부른다.

 

Euler Thm)

G가 connected일 때, G는 Eulrian다 iff 모든 vertices가 짝수의 degree를 가진다면,

Euler's Thm을 사용한다면 각 vertices의 degree가 모두 같은지만 check하면된다.

 

예시1) K5는 Eulrian,

예시2) K2,4는 complete bipartite graph인데, 잘 살피면 vertice 당 degree가 2 or 4이기 때문에 Eulrian이다.

예시3) G는 우선 connected graph가 아니다.

 

하나의 connected comp만 존재하고 나머진 null graph인 경우 이를 connected graph로 간주한다. 

 

예시1) G는 Eulrian이 아니다. G가 connected인데 odd #의 degree가 존재하기 때문이다.

예시2) skip

 

예시3)  complete graph 중 d(v) = n-1 이기 때문에 d(v)가 even #가 되기 위해선 n이 odd여야 한다. 따라서 k1,k3,k5 ... 등은 Eulrian이고, k2,k4,k6... 등은 아니다. 

 

예시4) complete bipartite graph Km,n의 경우 m <= n이라면 d(v)=m이 n개, d(v)=n이 m개 있다. 이 Km,n이 Eulrian이려면 m,n이 모두 even #가 되어야만 한다. 하나라도 odd #라면 Eulrian이 아니다.

 

예시5) Complete multipartite graph의 경우,

sigma sum of (m_i  - m_j)가 모든 j =1,2,3,4,5,6,...,k에 대해 짝수라면 Eulrian이다.

즉, 1<=i<=k에 대하여, 모든 m_i가 짝수면 ok

내지는 m_i가 홀수인데 k가 홀수라면 Eulrian이다. 홀수-(홀수*짝수) = 짝수이기 때문이다. 

 

예시1) 모두 홀수인데 k=3도 홀수니까 Eulrian이다.

예시2) 모두 홀수인데 k=4로 짝수니까 Eulrian이 아니다. 

 

Hamiltonian cycle은 모든 vertices를 한번씩만 포함하는 cycle이다.

Hamiltonian Cycle을 보유한 G를 Hamiltonian이라 부른다. 

 

 

complete graph는 eulerian임과 동시에 hamiltonian이다(n=odd#)

만약 Graph가 Hamiltonian이라면, G는 connected다.

만약 G가 connected가 아니라면 사이클도 없으니까 Hamiltonian이 아니다.

 

G가 Hamiltonian이라면 모든 V(G)의 부분집합 S에 대해서, G-S의 connected comp 갯수가 |S|보다 작다.

 

만약 G-S >= |S|인 S가 존재한다면, G는 Hamiltonian이 아니다.

 

우린 이 Lemma를 활용하여 G가 Hamiltonian인지 아닌지 확인할 수 있다.

위 예시의 경우 가운데 vertice를 S로 잡아보자. 이 경우 G-S의 connected comp는 2개인데 |S|=1이니 Lemma가 위배된다. 따라서 G는 Hamiltonian이 아니다. 

 

예시) Km,n의 경우 m != n이면 Hamiltonian이 아니다. 

m < n의 경우, S={v1, ... vm}으로 설정하면, G-S는 {u1, ... , un}이 된다. G-S의 connected comp = n > m = |S|이기 때문에 

Km,n은 Lemma에 위배되어 Hamiltonian이 아니다.

따라서 m=n이어야만 Hamiltonian Cycle임을 알 수 있다.

 

 

C가 G의 Hamiltonian Cycle이라 가정해보자. 그럼 어떠한 V(G)의 부분집합 S에 대해서도 connected comp of C-S가 |S|보다 작아야한다. 위 예시에서 형광색 2개의 vertcies를 제외하면 connected comp of C-S는 2개다. 

동시에 C는 G의 spanning subgraph(모든 vertcies를 포함하고 있는 부분그래프)다. 따라서 edge가 일부 없는 C-S가 G-S보다 connected comp의 개수가 많을 수 밖에 없다. 이 예시에서 S의 개수를 늘릴수록 connected comp의 갯수는 늘어나기 때문에 Hamiltonian이면 무조건 |S| >= # of connected comp of G-S 이다. 

 

예시) 

G-S = 1 = |S| 이기 때문에 # of conected comp of G-S <= |S| 조건을 만족시켰으나, G는 Hamiltonian이 아니다. 

Lemma의 역은 서읿하지 않기 때문이다. 

 

따라서 우리는 그저 G-S > |S| 인 S가 존재함을 보여 G가 Hamiltonian이 아님을 보일 수 있을 뿐이다.