한붓그리기 할 수 있는 조건은 무엇일까? (Eulerian circuit/path) / Graph Theory #3

어린 시절 한붓그리기를 해본 경험이 있을 것이다. (없어도 상관 없다.) 하나의 “점”에서 “길”을 통해서 다른 “점”으로 이동한다. 전체적인 이동 경로를 살피었을 때 다음 두 가지 조건을 만족한다면 “한붓그리기가 성공했다.” 고 한다.

  1. 한 번 이동한 “길”을 다시 이용하지 않는다.
  2. 모든 길을 이용해야 한다.

위의 규칙이 이해된다면 한붓그리기가 이해가 된 것이다. 이처럼 한붓그리기가 가능한 점 (vertex)과 길 (edge)로 구성된 그림 (graph)를 Eulerian circuit (path)이라고 한다.

Eulerian Circuit의 정의

전체적인 경로가 잘 완성이 되어야 한붓그리기 여부를 판별할 수 있다. 따라서, 경로를 어떻게 정의하는지 알아야 한다. 한붓그리기의 경로는 같은 vertex를 여러 번 이용할 수 있지만 같은 edge를 여러 번 이용해서는 안 된다. 이런 특성을 가진 경로를 trail이라고 한다.

A graph is Eulerian if it has a closed trail containing all edges.

위와 같이 Eulerian circuit은 trail로 정의된다. 모든 edges를 포함해야 하며, 닫혀있어야 한다. (시작하는 vertex과 끝나는 vertex가 같아야 한다는 이야기이다.) 어떤 그래프가 한붓그리기가 가능한지 확인하려면, 모든 edges를 포함하는 닫힌 trail을 찾아야 한다는 것인데… 매우 어려울 것이다. 아래의 정리에 따라서 위와 같은 trail의 여부를 빠르게 확인할 수 있다. (직접 trail을 찾는 것은 다른 이야기이지만 있다는 것을 확인할 수는 있다.)

Eulerian Circuit의 존재 조건

A graph G is Eulerian iff it has at most one nontrivial component and its vertices all have even degree.

위의 정리에 따르면 두 가지 조건을 만족하면 한붓그리기가 가능하다는 것이다.

첫 번째, “at most one nontrivial component” edge가 달린 vertices uv가 있다면 이 둘 사이를 연결하는 경로가 있어야만 한다는 얘기이다. 만약 u에서 출발해서 v까지 갈 수 있는 방법이 없다면, u에서 출발해서 v와 연결된 길을 지날 수 있는 방법은 없다. 따라서, u에서 v까지 어떻게든 갈 수 있는 방법은 있어야 된다.
+ 물론, edge가 연결되지 않은 vertices (trivial components)는 많이 있어도 상관없다.

두 번째, 모든 vertices에 연결된 edges의 개수가 짝수 개이어야 한다. 얼핏 보기에는 굉장히 간단한 조건이다. 직관적으로 이해가 되지 않으니 자세한 증명을 통해서 살펴보자.

Eulerian circuit → All vertices have even degree.

임의의 vertex v에 대해서 생각해보자. v에 연결된 edge가 k개라고 하자. 그래프 상에서 한붓그리기를 시작하면 edge를 통해서 v에 도착하고 edge를 통해서 v를 나갈 것이다. 한붓그리기가 완성되기 위해서는 결국 k개의 edges를 모두 지나야 한다. k개의 edges를 지나는 순서에 따라서 e_1,~e_2,~\cdots,~e_k라고 인덱싱하자. e_{2l-1}을 통해서 v에 도착했다면 e_{2l}을 통해서 v를 나간다. 만약 k가 홀수 개라면 e_k를 통해서 v에 도착하지만 v에서 나갈 edge가 더 이상 남아있지 않다. (다른 edges는 이미 한 번 씩 지나서 더 이상 이용할 수 없다.) 따라서, k는 짝수가 되어야 하고, 이것은 모든 vertices가 짝수 개의 edges를 가져야 한다는 것을 의미한다.

All vertices have even degree. → Eulerian circuit

수학적 귀납법을 활용하기 위해서, 그래프 G의 edges의 개수가 최대 m개 이고, 모든 vertices가 짝수 개의 edges를 가지면 Eulerian circuit이라고 정리를 살짝 수정하자. 위의 정리가 임의의 m에 대해서 만족한다면 기존의 정리와 같아진다.

m=0일 때, edge가 없기 때문에 해당 그래프는 이미 Eulerian circuit의 조건을 만족한다.

m>0일 때, edges의 개수가 m보다 작으면 정리는 성립해서 Eulerian circuit이 된다. edges의 개수가 m개인 경우는 어떨까?
Vertices와 연결된 edges의 개수가 짝수 개이므로 vertices들은 최소 2개의 edges들과 연결되어 있다. (0개인 경우는 신경 쓸 필요가 없다.) Vertices와 연결된 edges의 개수가 2개 이상이면 이 그래프는 cycle C을 포함한다. (아래에 해당 정리에 대한 증명이 있다.)

G-E(C)를 생각해보자. Edges가 사라지면서 더 이상 모든 vertices들이 연결되어 있지 않고, 여러 components가 생길 것이다. 하지만 이 components의 vertices도 모두 짝수 개의 edges와 연결되어 있을 것이다. 또한, components의 edges 개수는 m보다 작다. 수학적 귀납법 가정에 따라 각 components는 Eulerian circuit이다.

Cycle C의 모든 vertices를 돌면서 다른 G-E(C)의 components와 만나는 vertex를 지날 때마다 components를 한붓그리기 해준다. (Eulerian이기 때문에 한붓그리기가 가능하다.) 한붓그리기가 끝나면 다시 C의 vertex에 위치하고 있을 것이다. 그러면 다시 C를 돈다.

위와 같은 규칙을 통해서 이동한다면 그래프 G 전체를 한붓그리기로 이동이 가능하고 따라서 G가 Eulerian circuit이 된다.

결과적으로, 모든 vertices에 연결된 edges의 개수가 짝수 개이면, Eulerian circuit이 된다.

모든 vertices의 degree가 2 이상이면, cycle을 포함한다.

그래프 Gn개의 vertices~(v_1,\cdots,v_n)를 가진다. 최대한 cycle을 포함하지 않도록 G에 edges를 추가하여 보자. Cycle을 만들지 않기 위해서는 edges 개수가 적은 것이 좋기 때문에 모든 vertices가 2개의 edges를 가진다고 가정하자.

v_1에서 v_2v_3로 edges를 연결했을 때, cycle을 만들지 않기 위해서 v_2는 하나의 edge를 v_4로 연결해야 한다. (v_3로 연결하면 cycle이 생긴다.) v_3v_5로 새로운 edge를 연결해야 한다. 즉, 새로운 edge를 다른 edge와 연결된 vertex와 연결시키면 안 된다. v_iv_{i+2}와 edge를 연결해야만 하고, v_{n-1}은 연결할 vertex가 없다. 따라서, 기존의 i<n-1인 vertex와 연결하면 cycle이 생길 수 밖에 없다. 따라서 모든 vertices에 연결된 edges 개수가 2 이상이면, cycle이 있을 수 밖에 없다.

Leave a Comment

Index