오일러 경로 (한붓그리기)

펜을 종이에서 떼지 않고, 같은 선을 두 번 긋지 않으면서 그림 전체를 그릴 수 있을까? 1736년 오일러는 쾨니히스베르크의 다리 7개를 두고 이 질문에 답하며 그래프 이론을 만들었다. 열쇠는 딱 하나 — 홀수 개의 선이 모이는 점이 몇 개인가.

1. 직접 그어 보기

정점을 눌러 출발점을 정하고, 이어진 정점을 차례로 누르며 선을 지나간다. 지나간 선은 초록색으로 바뀌고 순서 번호가 붙는다. 모든 선을 한 번씩 지나면 성공. 막히면 「되돌리기」로 무르거나 「처음부터」.

2. 왜 홀수 정점이 문제인가

한붓그리기 중 어떤 정점을 지나쳐 갈 때마다, 그 정점으로 들어오는 선 1개 + 나가는 선 1개를 함께 쓴다. 즉 통과할 때마다 선을 2개씩 소비한다. 그래서 시작점도 끝점도 아닌 정점은 이어진 선의 개수(차수)가 반드시 짝수여야 남김없이 쓸 수 있다.

시작점은 "나가는 선"이 1개 더, 끝점은 "들어오는 선"이 1개 더 필요하다. 그래서 홀수 차수 정점은 시작점이나 끝점으로만 쓸 수 있고, 그런 자리는 최대 2개뿐이다.

3. 쾨니히스베르크의 다리

프레겔 강이 도시를 네 구역(북안·남안·섬·동쪽 땅)으로 나누고 다리 7개가 잇는다. 오일러는 각 구역을 점으로, 다리를 선으로 바꿨다 — 땅의 모양·거리는 중요하지 않고 연결 관계만 남긴 것이 그래프의 출발점이다.

네 구역의 차수는 각각 5, 3, 3, 3 — 전부 홀수라 홀수 정점이 4개다. 규칙에 따라 모든 다리를 한 번씩만 건너는 산책은 불가능하다. (위 데모에서 "쾨니히스베르크 다리"를 골라 아무리 시도해도 항상 다리 1개가 남는다.)

4. 자동으로 찾기 — 히어홀저(Hierholzer) 알고리즘

조건(홀수 정점 0 또는 2개, 연결됨)이 맞으면 경로는 O(E)에 찾을 수 있다. 스택 하나로 "갈 수 있는 데까지 가서 막히면 되돌아 나오며 경로를 완성"하는 방식이다.

def hierholzer(adj, start):        # adj[v] = 아직 안 쓴 간선 목록
    stack = [start]
    circuit = []
    while stack:
        v = stack[-1]
        if adj[v]:                    # v에서 나갈 간선이 남았으면
            e = adj[v].pop()          # 아무 간선 하나 선택
            mark_used(e)              # 반대쪽 끝에서도 제거
            stack.append(other_end(e, v))
        else:                         # 막다른 길 → 경로에 확정
            circuit.append(stack.pop())
    return circuit[::-1]           # 뒤집으면 오일러 경로

「자동으로 풀기」 버튼이 이 결과를 한 선씩 애니메이션으로 보여준다. 홀수 정점이 2개면 그중 하나에서, 0개면 아무 데서나 시작한다.

5. 오일러 경로 vs 해밀턴 경로

6. 실제로 어디에 쓰이나