오일러와 해밀턴 경로

도로를 모두 점검하는 순회와 방문 지점을 한 번씩 들르는 여행은 다른 문제입니다. 그래프 기본의 보행·차수·연결을 사용해 무엇을 한 번씩 세는지부터 구분합니다.

오일러는 간선을 세는 문제

오일러 경로는 모든 간선을 정확히 한 번 사용하는 보행이며 정점은 반복할 수 있습니다. 출발점으로 돌아오면 오일러 회로입니다. 간선이 있는 유한 무방향 그래프에서는 차수가 0이 아닌 정점들이 한 연결 성분에 있어야 합니다. 이 조건 아래 홀수 차수 정점이 0개면 회로가 있고, 정확히 2개면 그 두 정점을 끝점으로 하는 열린 경로가 있습니다.

중간 정점에 들어왔으면 다른 간선으로 나가야 하므로 사용 간선이 짝을 이룹니다. 시작과 끝만 짝이 하나 모자랄 수 있습니다. 이 설명은 필요조건의 직관입니다. 충분조건은 사용하지 않은 간선으로 닫힌 순회를 만들고 남은 순회를 접합하는 방법으로 보일 수 있습니다.

E={AB,AC,BC,CD}에서 홀수 정점은 C(3),D(1)라 D→C→A→B→C는 오일러 경로입니다. C를 두 번 방문해도 각 간선을 한 번씩 썼으므로 조건을 만족합니다. C→A→B→C만 적으면 CD가 빠져 오일러 회로가 아닙니다.

방향 그래프는 진입·진출 차수와 방향에 맞는 연결 조건을 따로 적용합니다. 무방향의 홀수 차수 규칙을 그대로 사용하지 않습니다.

해밀턴은 정점을 세는 문제

해밀턴 경로는 모든 정점을 정확히 한 번 방문하는 단순경로입니다. 모든 정점을 방문한 후 출발점으로 되돌아오는 간선까지 있으면 해밀턴 사이클입니다. 위 예제는 D→C→A→B가 해밀턴 경로입니다. D의 차수가 1이므로 해밀턴 사이클은 없습니다. 사이클에서 각 정점은 들어오는 간선과 나가는 간선 두 개가 필요하기 때문입니다.

정점 차수 ≥2라는 조건만으로 해밀턴 사이클이 보장되지는 않습니다. 오일러의 홀짝 규칙처럼 모든 그래프에 간단히 적용할 완전한 차수 판정으로 혼동하면 안 됩니다. 소규모에서는 후보 방문 순서를 나열하고 간선 존재를 검사할 수 있지만 정점 수가 늘면 경우의 수가 빠르게 늘어납니다.

스스로 풀어보기

문제 1. 중심 O와 잎 A,B,C를 잇는 세 간선의 별 그래프에서 오일러 경로와 해밀턴 경로가 존재하나요?

풀이: 차수는 O=3,A=B=C=1로 홀수 정점 네 개라 오일러 경로가 없습니다. 해밀턴 경로는 O를 한 번만 사용할 수 있어 서로 다른 세 잎을 모두 연결해 방문할 수 없습니다. A→O→B 뒤에는 C로 가려면 O를 반복해야 합니다.

문제 2. 삼각형 ABC에서 A→B→C→A는 어떤 두 종류의 순회인가요?

풀이: 세 간선을 한 번씩 사용하고 출발점으로 돌아오므로 오일러 회로입니다. 세 정점을 한 번씩 방문한 후 출발점으로 돌아오므로 해밀턴 사이클이기도 합니다. 한 순회가 두 성질을 동시에 가질 수 있지만 두 정의가 같은 것은 아닙니다.

결과를 적은 뒤 원래 간선 목록이나 정점 목록에서 사용한 것을 지워 검산하세요. 가장 짧은 이동을 찾는 문제는 최단경로로 이어집니다.