해밀턴 경로, 한붓그리기, 오일러 경로에 관하여

1. 개요

그래프 이론에서 해밀턴 경로, 한붓그리기, 그리고 오일러 경로는 서로 다른 유형의 경로를 나타내는 중요한 개념입니다. 이들은 특정 조건을 만족하는 경로를 그래프에서 찾는 문제와 관련되어 있으며, 다양한 알고리즘과 수학적 연구에서 핵심적인 역할을 합니다.

2. 해밀턴 경로란?

해밀턴 경로는 그래프에서 모든 정점을 정확히 한 번씩만 방문하는 경로를 말합니다. 이 경로가 시작점과 끝점을 연결하는 경우, 이를 해밀턴 회로 또는 해밀턴 사이클이라고 부릅니다.

• 특징:
  • 해밀턴 경로는 정점을 기준으로 경로를 설정합니다.
  • 모든 정점을 정확히 한 번씩 방문해야 합니다.
  • 해밀턴 경로를 찾는 문제는 NP-완전 문제로, 효율적인 해법을 찾기가 어렵습니다.
• 예시: TSP(Traveling Salesman Problem)와 같이 여러 도시를 각각 한 번씩 방문하는 문제는 해밀턴 경로를 찾는 문제로 모델링될 수 있습니다.

3. 한붓그리기란?

한붓그리기는 도형을 끊김 없이 한 번의 선으로 그릴 수 있는지에 대한 문제입니다. 이는 오일러 경로와 관련이 깊습니다.

• 특징:
  • 그래프의 모든 변을 한 번만 지나도록 경로를 설정합니다.
  • 모든 변을 지나가야 하므로, 이는 사실상 오일러 경로 문제와 동일합니다.
  • 시작점과 끝점이 같은 경우, 이를 한붓그리기 회로로 볼 수 있습니다.
• 예시: 한붓그리기를 통해 복잡한 도형을 끊김 없이 한 번에 그리는 것이 가능한지를 판단할 수 있습니다.

4. 오일러 경로란?

오일러 경로는 그래프에서 모든 변을 한 번씩만 방문하는 경로를 말합니다. 이 경로가 시작점과 끝점이 동일할 경우 오일러 회로라고 부릅니다.

• 특징:
  • 오일러 경로는 변을 기준으로 경로를 설정합니다.
  • 모든 변을 한 번씩 지나야 하며, 정점은 여러 번 방문할 수 있습니다.
  • 무향 그래프에서 오일러 회로가 존재하려면 모든 정점의 차수가 짝수여야 하고, 오일러 경로가 존재하려면 정확히 두 개의 홀수 차수 정점이 있어야 합니다.
• 예시: 쾨니히스베르크의 다리 문제는 오일러 경로의 고전적인 예시로, 이 문제를 통해 오일러는 자신의 이론을 정립했습니다.

5. 해밀턴 경로와 오일러 경로의 비교

• 해밀턴 경로는 정점을 중심으로 하며, 모든 정점을 한 번씩만 방문합니다. 반면 오일러 경로는 변을 중심으로 하며, 모든 변을 한 번씩만 지나야 합니다.
• 해밀턴 경로는 NP-완전 문제로 어려운 반면, 오일러 경로는 차수 조건에 따라 쉽게 결정될 수 있습니다.

6. 구체적인 사례와 Python 코드 예제

오일러 경로 예제 코드:

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.vertices = vertices

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def _dfs_count(self, v, visited):
        count = 1
        visited[v] = True
        for i in self.graph[v]:
            if not visited[i]:
                count += self._dfs_count(i, visited)
        return count

    def is_connected(self):
        visited = [False] * self.vertices
        for i in range(self.vertices):
            if len(self.graph[i]) > 0:
                break
        if i == self.vertices - 1:
            return True

        self._dfs_count(i, visited)
        for i in range(self.vertices):
            if visited[i] == False and len(self.graph[i]) > 0:
                return False
        return True

    def is_eulerian(self):
        if not self.is_connected():
            return 0

        odd = 0
        for i in range(self.vertices):
            if len(self.graph[i]) % 2 != 0:
                odd += 1

        if odd == 0:
            return 2  # 오일러 회로
        elif odd == 2:
            return 1  # 오일러 경로
        else:
            return 0  # 오일러 경로 없음

# 그래프 생성 및 엣지 추가
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.add_edge(4, 0)

res = g.is_eulerian()

if res == 0:
    print("오일러 경로 없음")
elif res == 1:
    print("오일러 경로 존재")
else:
    print("오일러 회로 존재")