직관 — 복도 대신 방문할 장소를 센다
전시실을 빠짐없이 한 번씩 방문하고 입구로 돌아오는 관람 동선을 정한다고 하자. 쓰지 않는 복도가 있어도 괜찮지만 같은 방을 중간에 두 번 방문해서는 안 된다. 모든 복도를 청소하는 문제와는 확인할 대상이 달라진다.
오일러그래프에서는 모든 변을 한 번씩 썼다. 이제는 유한한 단순 무방향그래프의 모든 꼭짓점을 방문하는 순서를 찾는다. 먼저 동선이 있는지를 따지고, 마지막 절에서 거리가 붙은 경우의 가장 짧은 동선을 다룬다.
해밀턴그래프는 모든 꼭짓점을 포함한 단순회로를 갖는다
해밀턴 회로는 모든 꼭짓점을 정확히 한 번씩 방문하고 출발점으로 돌아오는 단순회로다. 마지막에 출발점 이름을 한 번 더 쓰는 것은 닫혔음을 표시하는 것이며, 그 외 꼭짓점은 반복하지 않는다. 해밀턴 회로가 있는 그래프를 해밀턴그래프(Hamiltonian graph)라고 한다.
꼭짓점이 개()일 때 해밀턴 회로는 다음 꼴이며, 이웃한 두 항과 마지막·첫 항 사이에 실제 변이 있어야 한다.
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| 꼭짓점 수 | number of vertices | 방문할 서로 다른 장소 수 | |
| 방문 순서 | vertex ordering | 모든 꼭짓점을 중복 없이 나열한 것 | |
| 차수 | degree | 꼭짓점 에 닿은 변의 수 | |
| 완전그래프 | complete graph | 개의 점을 모두 서로 이은 그래프 |
우리교과서의 ‘해밀턴 회로’를 여기서도 사용한다. 보통 회로는 꼭짓점을 다시 만날 수 있지만 해밀턴 회로는 시작·끝 외에는 그러지 못한다. 모든 꼭짓점을 한 번씩 지나는 단순경로를 해밀턴 경로라 하며, 해밀턴 경로가 있어도 끝점에서 출발점으로 돌아오는 변이 없으면 해밀턴 회로는 아니다.
예를 들어 그림 1 위의 에서 는 네 점을 한 번씩 방문하고 돌아오는 해밀턴 회로다.
해밀턴그래프와 오일러그래프는 무엇이 다를까?
해밀턴 회로는 모든 꼭짓점을, 오일러 회로는 모든 변을 한 번씩 지난다. 확인하는 대상이 달라서 한쪽이 있다고 다른 쪽이 있는 것은 아니며, 네 조합이 모두 나온다.
| 오일러 회로 있음 | 오일러 회로 없음 | |
|---|---|---|
| 해밀턴 회로 있음 | 사각형 | (차수가 모두 3) |
| 해밀턴 회로 없음 | 두 삼각형 모형 (차수 ) | 중심 하나에 잎 셋을 이은 별 모양 |
그림 1 위의 는 차수가 모두 3이어서 홀수 차수 점이 4개이므로 오일러 경로조차 없다. 그림 1 아래는 삼각형 와 가 꼭짓점 하나만 공유하는 모형이다. 차수가 모두 짝수라 라는 오일러 회로가 있지만, 해밀턴 회로는 없다는 것을 다음 절에서 보인다.
figures/hamilton_compare.py사각형 에 대각선 를 더해도 해밀턴 회로는 그대로 남는다. 변을 더하는 것은 이미 있는 해밀턴 회로를 없애지 않는다. 반면 와 의 차수가 3이 되어 오일러 회로는 사라진다. 같은 변 추가를 두 문제에서 다르게 읽어야 한다.
차수가 모두 2 이상이면 충분할까?
충분하지 않다. 해밀턴 회로에서 각 꼭짓점에는 들어오는 변과 나가는 변이 서로 다르게 필요하므로 다음은 필요조건일 뿐이다.
그림 1 아래의 차수는 로 모두 2 이상이다. 그러나 왼쪽의 와 오른쪽의 를 모두 방문한 뒤 돌아오려면 두 부분을 잇는 유일한 관문 를 중간에 다시 지나야 한다. 해밀턴 회로에서 를 지우면 나머지 점을 모두 잇는 단순경로가 남아야 하는데, 이 그래프에서 를 지우면 와 가 떨어진다.
이 논증은 일반화된다. 해밀턴 회로는 모든 점을 꿴 고리여서, 점 개()를 지우면 고리가 많아야 곳에서 끊긴다. 남은 그래프는 그 고리 조각들을 품으므로 서로 오갈 수 있는 덩어리도 개를 넘지 않는다.
그림 2 위는 다섯 점의 고리에서 두 점을 지운 모습으로, 남은 덩어리가 2개다. 아래의 은 두 점 를 세 점 와 모두 이은 그래프로, 차수 가 식 (2)를 만족한다. 하지만 두 점을 지우면 가 따로 떨어진 세 덩어리가 되어 식 (3)을 어기므로 해밀턴 회로가 없다.
figures/ring_cut.py해밀턴 회로는 어떻게 빠짐없이 찾을까?
출발점을 하나 정하고 갈 수 있는 다음 점을 모두 가지로 펼치면 빠짐없이 찾을 수 있다. 가능하다는 것은 성공한 순서 하나로, 불가능하다는 것은 모든 가지가 막혔다는 것으로 보인다.
그림 3 위의 그래프는 변 로 이루어진다. 아래는 에서 출발해 아직 가지 않은 이웃으로만 나아가는 순서를 수형도로 펼친 것이다. 처음 시도한 는 다섯 점을 다 돌았지만 와 사이에 변이 없어 회로가 되지 못한다.
figures/search_tree.py네 가지 중 와 가 회로이고, 둘은 같은 회로를 거꾸로 읽은 것이다. 첫 시도가 막혔다고 멈췄다면 이 회로를 놓쳤을 것이다.
완전그래프 에서 서로 다른 해밀턴 회로를 세려면 출발점을 고정하고 나머지 개를 순열로 배열한 뒤, 거꾸로 읽은 것을 같은 회로로 본다. 그래서 회로의 수는 다음과 같다.
는 3개, 는 12개지만 은 181,440개다. 점이 늘면 후보가 빠르게 불어나 손으로 모두 확인하기 어렵다.
해밀턴 회로가 있다고 보장하는 조건은 있을까?
오일러 회로처럼 차수만으로 정확히 판정하는 간단한 조건은 알려져 있지 않다. 대신 충분조건이 몇 가지 있으며, 대표적인 것이 디랙 정리다.
는 모든 차수가 여서 조건을 만족한다. 세 점 를 세 점 과 모두 이은 도 차수가 이고, 실제로 가 해밀턴 회로다.
거꾸로 조건을 만족하지 않아도 회로가 있을 수 있다. 다섯 점을 둘레로만 이은 오각형은 차수 2가 에 못 미치지만 그 자체가 해밀턴 회로다. 디랙 정리는 충분조건이지 필요조건이 아니며, 증명은 이 단원의 범위를 넘는다.
해밀턴 회로는 외판원 문제에 어떻게 쓰일까?
모든 장소를 한 번씩 들러 돌아오는 가장 짧은 동선을 찾는 외판원 문제는, 거리가 붙은 그래프에서 총거리가 가장 작은 해밀턴 회로를 찾는 문제다. 네 장소라면 식 (4)에 따라 서로 다른 회로가 3개뿐이어서 모두 계산하면 된다.
그림 4 위의 숫자가 네 장소 사이의 거리(km)다. 세 회로의 총거리는 다음과 같다.
- :
- :
- :
figures/tsp_tours.py가장 짧은 것은 의 11 km다. 매번 가장 가까운 곳으로 가면 (1), (4), (3), (6)로 14 km가 되어 최단을 놓친다. 마지막에 출발점으로 돌아오는 거리까지 따져야 하기 때문이다.
해밀턴그래프는 모든 꼭짓점을 한 번씩 방문하고 출발점으로 돌아오는 단순회로를 갖는다. 모든 차수가 2 이상이라는 조건은 필요하지만 충분하지 않다.
해밀턴 회로에서는 모든 변도 지나야 하나요?
해밀턴 회로는 모든 변을 지날 필요가 없다. 의 해밀턴 회로 는 여섯 변 중 네 변만 쓰고 는 남긴다. 모든 변을 한 번씩 쓰라는 조건은 오일러 회로의 조건이다.
꼭짓점이 두 개뿐이면 왕복해서 회로를 만들 수 있나요?
꼭짓점이 두 개인 단순 그래프에는 해밀턴 회로가 없다. 두 점 사이의 유일한 변을 왕복하면 같은 변을 두 번 쓰기 때문이다. 단순 그래프의 회로는 길이가 적어도 3이므로 해밀턴 회로에는 꼭짓점이 3개 이상 필요하다.
해밀턴 회로가 없으면 모든 점을 방문할 수도 없나요?
해밀턴 회로가 없어도 모든 점을 한 번씩 방문하는 해밀턴 경로는 있을 수 있다. 그림 1 아래의 는 각 점을 한 번씩 방문한다. 다만 에서 로 돌아오는 변이 없어 회로가 아니며, 돌아오려면 이미 지난 를 다시 만나야 한다.
해밀턴그래프의 흔한 오해
- 모든 차수가 짝수이면 해밀턴그래프다. — 그림 1 아래는 모두 짝수지만 해밀턴 회로가 없다. 짝수 조건은 연결성과 함께 오일러 회로에 쓰인다.
- 후보 한 개가 막혔으니 해밀턴 회로가 없다. — 그림 3에서 처음 시도한 는 막혔지만 다른 가지가 성공한다. 불가능성에는 전체 후보 검사나 식 (3) 같은 방해 조건이 필요하다.
직접 해보기
- 꼭짓점 와 변 이 있다. 해밀턴 회로를 하나 쓰시오.
- 중심 와 네 잎을 잇는 네 변만 있다. 해밀턴 회로가 불가능한 이유를 차수로 설명하시오.
- 사각형 둘레 와 삼각형 가 만 공유한다. 차수 목록을 구하고 해밀턴 회로와 오일러 회로의 존재를 구별하시오.
- 네 점의 완전그래프에서 를 지워도 해밀턴 회로가 남는가? 실제 순서를 쓰시오.
- 네 장소 사이의 거리가 , , , , , 이다. 에서 출발해 모든 장소를 한 번씩 들러 돌아오는 가장 짧은 회로와 그 거리를 구하시오.
답과 풀이
- 다. 다섯 꼭짓점을 한 번씩 방문하고 실제 변 다섯 개로 돌아온다. 변 은 쓰지 않아도 된다.
- 잎의 차수가 1이므로 서로 다른 들어오는 변과 나가는 변을 고를 수 없다. 식 (2)를 만족하지 않는다.
- 의 차수는 다. 한 점을 지우면 과 의 두 덩어리가 되어 식 (3)을 어기므로 해밀턴 회로는 없다. 모든 차수가 짝수이고 연결되어 오일러 회로는 있으며 가 한 예다.
- 남는다. 의 네 변은 모두 남아 있고 네 점을 한 번씩 방문한다. 삭제한 변을 꼭 써야 하는 것은 아니다.
- 서로 다른 회로는 식 (4)에 따라 3개다. 는 , 는 , 는 이므로 의 15가 가장 짧다.
더 읽기
- 교육부 2022 개정 교육과정 고시 — 별책20 [12이수04-05]의 해밀턴그래프와 활용.
- Levin, Euler Paths and Circuits의 Hamilton Paths — 변 순회와 꼭짓점 순회를 구별한다. 본문의 두 삼각형 반례는 별도로 구성했다.
- Buckingham, Graph Theory — 2.8 「Hamilton cycles」의 명제 2.24(점을 지운 뒤의 덩어리 수)와 오어 정리, 그 따름정리인 디랙 정리를 대조했다. 식 (3)과 식 (5)가 여기에 기댄다.
영상 노트
- 00:00 방문할 장소와 사용할 복도를 구별하기
- 00:40 식 (1)의 방문 순서에서 끝점 복귀 확인하기
- 01:20 네 조합 표로 오일러 회로와 해밀턴 회로 비교하기
- 02:00 식 (2)의 필요성과 두 삼각형 반례, 식 (3)으로 K₂,₃ 판정하기
- 03:00 그림 3의 수형도로 후보 순서를 빠짐없이 펼치기
- 03:50 디랙 정리와 오각형으로 충분조건과 필요조건 구별하기
- 04:30 외판원 문제에서 세 회로의 총거리 비교하기
지도에서의 위치
- 2026-11-16 · 에이전트 초안
- 2026-11-17 · 전수 검수 반영 — 오일러 회로와의 네 조합 비교, 점을 지운 뒤 덩어리 수로 불가능을 보이는 일반 조건과 K2,3, 빠짐없이 찾는 수형도, 완전그래프의 회로 수, 디랙 정리, 외판원 문제 절과 해보기 5번 추가, 질문 답 첫 문장 보강, 덩어리 수 조건을 점을 하나 이상 지울 때로 좁힘 (에이전트 수정, 그림 1→4)
- 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림