기초수학해밀턴그래프#359

해밀턴그래프

Hamiltonian Graphs

해밀턴그래프는 모든 꼭짓점을 한 번씩 방문한 뒤 출발점으로 돌아오는 단순회로가 있는 그래프다. 변을 모두 사용하는 오일러 문제와 다르며, 모든 차수가 2 이상이라는 필요조건만으로는 충분하지 않다.

읽는 시간
약 7분
선수 개념
오일러그래프

직관 — 복도 대신 방문할 장소를 센다

직관

전시실을 빠짐없이 한 번씩 방문하고 입구로 돌아오는 관람 동선을 정한다고 하자. 쓰지 않는 복도가 있어도 괜찮지만 같은 방을 중간에 두 번 방문해서는 안 된다. 모든 복도를 청소하는 문제와는 확인할 대상이 달라진다.

오일러그래프에서는 모든 변을 한 번씩 썼다. 이제는 유한한 단순 무방향그래프의 모든 꼭짓점을 방문하는 순서를 찾는다. 먼저 동선이 있는지를 따지고, 마지막 절에서 거리가 붙은 경우의 가장 짧은 동선을 다룬다.

해밀턴그래프는 모든 꼭짓점을 포함한 단순회로를 갖는다

해밀턴 회로는 모든 꼭짓점을 정확히 한 번씩 방문하고 출발점으로 돌아오는 단순회로다. 마지막에 출발점 이름을 한 번 더 쓰는 것은 닫혔음을 표시하는 것이며, 그 외 꼭짓점은 반복하지 않는다. 해밀턴 회로가 있는 그래프를 해밀턴그래프(Hamiltonian graph)라고 한다.

꼭짓점이 nn개(n≥3n\ge3)일 때 해밀턴 회로는 다음 꼴이며, 이웃한 두 항과 마지막·첫 항 사이에 실제 변이 있어야 한다.

v1,v2,…,vn,v1.(1)v_1,v_2,\ldots,v_n,v_1. \tag{1}
정의
기호이름원어뜻
nn꼭짓점 수number of vertices방문할 서로 다른 장소 수
v1,…,vnv_1,\ldots,v_n방문 순서vertex ordering모든 꼭짓점을 중복 없이 나열한 것
deg⁡(v)\deg(v)차수degree꼭짓점 vv에 닿은 변의 수
KnK_n완전그래프complete graphnn개의 점을 모두 서로 이은 그래프

우리교과서의 ‘해밀턴 회로’를 여기서도 사용한다. 보통 회로는 꼭짓점을 다시 만날 수 있지만 해밀턴 회로는 시작·끝 외에는 그러지 못한다. 모든 꼭짓점을 한 번씩 지나는 단순경로를 해밀턴 경로라 하며, 해밀턴 경로가 있어도 끝점에서 출발점으로 돌아오는 변이 없으면 해밀턴 회로는 아니다.

예를 들어 그림 1 위의 K4K_4에서 A,B,C,D,AA,B,C,D,A는 네 점을 한 번씩 방문하고 돌아오는 해밀턴 회로다.

해밀턴그래프와 오일러그래프는 무엇이 다를까?

해밀턴 회로는 모든 꼭짓점을, 오일러 회로는 모든 변을 한 번씩 지난다. 확인하는 대상이 달라서 한쪽이 있다고 다른 쪽이 있는 것은 아니며, 네 조합이 모두 나온다.

오일러 회로 있음오일러 회로 없음
해밀턴 회로 있음사각형 A,B,C,D,AA,B,C,D,AK4K_4 (차수가 모두 3)
해밀턴 회로 없음두 삼각형 모형 (차수 2,2,4,2,22,2,4,2,2)중심 하나에 잎 셋을 이은 별 모양

그림 1 위의 K4K_4는 차수가 모두 3이어서 홀수 차수 점이 4개이므로 오일러 경로조차 없다. 그림 1 아래는 삼각형 ABCABC와 CDECDE가 꼭짓점 CC 하나만 공유하는 모형이다. 차수가 모두 짝수라 C,A,B,C,D,E,CC,A,B,C,D,E,C라는 오일러 회로가 있지만, 해밀턴 회로는 없다는 것을 다음 절에서 보인다.

위는 해밀턴 회로 A,B,C,D,A가 강조된 K₄이고, 점선은 사용하지 않는 두 변이다. 아래는 오일러 회로는 있지만 해밀턴 회로는 없는 두 삼각형 모형이다. 아래의 C를 지우면 두 부분이 떨어진다.
그림 1 위는 해밀턴 회로 A,B,C,D,A가 강조된 K₄이고, 점선은 사용하지 않는 두 변이다. 아래는 오일러 회로는 있지만 해밀턴 회로는 없는 두 삼각형 모형이다. 아래의 C를 지우면 두 부분이 떨어진다. figures/hamilton_compare.py

사각형 A,B,C,D,AA,B,C,D,A에 대각선 ACAC를 더해도 해밀턴 회로는 그대로 남는다. 변을 더하는 것은 이미 있는 해밀턴 회로를 없애지 않는다. 반면 AA와 CC의 차수가 3이 되어 오일러 회로는 사라진다. 같은 변 추가를 두 문제에서 다르게 읽어야 한다.

차수가 모두 2 이상이면 충분할까?

충분하지 않다. 해밀턴 회로에서 각 꼭짓점에는 들어오는 변과 나가는 변이 서로 다르게 필요하므로 다음은 필요조건일 뿐이다.

deg⁡(v)≥2모든 꼭짓점 v에 대하여.(2)\deg(v)\ge2\qquad\text{모든 꼭짓점 }v\text{에 대하여}. \tag{2}

그림 1 아래의 차수는 2,2,4,2,22,2,4,2,2로 모두 2 이상이다. 그러나 왼쪽의 A,BA,B와 오른쪽의 D,ED,E를 모두 방문한 뒤 돌아오려면 두 부분을 잇는 유일한 관문 CC를 중간에 다시 지나야 한다. 해밀턴 회로에서 CC를 지우면 나머지 점을 모두 잇는 단순경로가 남아야 하는데, 이 그래프에서 CC를 지우면 ABAB와 DEDE가 떨어진다.

이 논증은 일반화된다. 해밀턴 회로는 모든 점을 꿴 고리여서, 점 kk개(k≥1k\ge1)를 지우면 고리가 많아야 kk곳에서 끊긴다. 남은 그래프는 그 고리 조각들을 품으므로 서로 오갈 수 있는 덩어리도 kk개를 넘지 않는다.

점 k개를 지운 뒤 남는 덩어리 수≤k(k≥1).(3)\text{점 }k\text{개를 지운 뒤 남는 덩어리 수}\le k\qquad(k\ge1). \tag{3}

그림 2 위는 다섯 점의 고리에서 두 점을 지운 모습으로, 남은 덩어리가 2개다. 아래의 K2,3K_{2,3}은 두 점 A,BA,B를 세 점 C,D,EC,D,E와 모두 이은 그래프로, 차수 3,3,2,2,23,3,2,2,2가 식 (2)를 만족한다. 하지만 A,BA,B 두 점을 지우면 C,D,EC,D,E가 따로 떨어진 세 덩어리가 되어 식 (3)을 어기므로 해밀턴 회로가 없다.

위는 다섯 점을 도는 회로에서 × 표시한 두 점을 지운 모습으로, 남은 덩어리는 2개다. 아래는 K₂,₃에서 두 점 A, B를 지우면 C, D, E가 세 덩어리로 흩어진다. 지운 점보다 덩어리가 많으면 해밀턴 회로가 없다.
그림 2 위는 다섯 점을 도는 회로에서 × 표시한 두 점을 지운 모습으로, 남은 덩어리는 2개다. 아래는 K₂,₃에서 두 점 A, B를 지우면 C, D, E가 세 덩어리로 흩어진다. 지운 점보다 덩어리가 많으면 해밀턴 회로가 없다. figures/ring_cut.py

해밀턴 회로는 어떻게 빠짐없이 찾을까?

출발점을 하나 정하고 갈 수 있는 다음 점을 모두 가지로 펼치면 빠짐없이 찾을 수 있다. 가능하다는 것은 성공한 순서 하나로, 불가능하다는 것은 모든 가지가 막혔다는 것으로 보인다.

그림 3 위의 그래프는 변 AB,AC,BC,BD,CE,DEAB,AC,BC,BD,CE,DE로 이루어진다. 아래는 AA에서 출발해 아직 가지 않은 이웃으로만 나아가는 순서를 수형도로 펼친 것이다. 처음 시도한 A,B,C,E,DA,B,C,E,D는 다섯 점을 다 돌았지만 DD와 AA 사이에 변이 없어 회로가 되지 못한다.

위 그래프에서 A부터 갈 수 있는 방문 순서를 모두 펼친 수형도다. 네 가지 모두 다섯 점을 방문하지만 × 표시한 둘은 마지막 점이 A와 이웃하지 않는다. 파란 A로 닫힌 두 가지가 같은 해밀턴 회로를 서로 거꾸로 읽은 것이며, 위 그래프에 굵게 표시했다.
그림 3 위 그래프에서 A부터 갈 수 있는 방문 순서를 모두 펼친 수형도다. 네 가지 모두 다섯 점을 방문하지만 × 표시한 둘은 마지막 점이 A와 이웃하지 않는다. 파란 A로 닫힌 두 가지가 같은 해밀턴 회로를 서로 거꾸로 읽은 것이며, 위 그래프에 굵게 표시했다. figures/search_tree.py

네 가지 중 A,B,D,E,C,AA,B,D,E,C,A와 A,C,E,D,B,AA,C,E,D,B,A가 회로이고, 둘은 같은 회로를 거꾸로 읽은 것이다. 첫 시도가 막혔다고 멈췄다면 이 회로를 놓쳤을 것이다.

완전그래프 KnK_n에서 서로 다른 해밀턴 회로를 세려면 출발점을 고정하고 나머지 n−1n-1개를 순열로 배열한 뒤, 거꾸로 읽은 것을 같은 회로로 본다. 그래서 회로의 수는 다음과 같다.

(n−1)!2(n≥3).(4)\frac{(n-1)!}{2}\qquad(n\ge3). \tag{4}

K4K_4는 3개, K5K_5는 12개지만 K10K_{10}은 181,440개다. 점이 늘면 후보가 빠르게 불어나 손으로 모두 확인하기 어렵다.

해밀턴 회로가 있다고 보장하는 조건은 있을까?

오일러 회로처럼 차수만으로 정확히 판정하는 간단한 조건은 알려져 있지 않다. 대신 충분조건이 몇 가지 있으며, 대표적인 것이 디랙 정리다.

n≥3이고 모든 꼭짓점에서 deg⁡(v)≥n2 ⟹ 해밀턴 회로가 있다.(5)n\ge3\text{이고 모든 꼭짓점에서 }\deg(v)\ge\frac{n}{2}\ \Longrightarrow\ \text{해밀턴 회로가 있다}. \tag{5}

K4K_4는 모든 차수가 3≥23\ge2여서 조건을 만족한다. 세 점 A,B,CA,B,C를 세 점 P,Q,RP,Q,R과 모두 이은 K3,3K_{3,3}도 차수가 3≥33\ge3이고, 실제로 A,P,B,Q,C,R,AA,P,B,Q,C,R,A가 해밀턴 회로다.

거꾸로 조건을 만족하지 않아도 회로가 있을 수 있다. 다섯 점을 둘레로만 이은 오각형은 차수 2가 5÷2=2.55\div2=2.5에 못 미치지만 그 자체가 해밀턴 회로다. 디랙 정리는 충분조건이지 필요조건이 아니며, 증명은 이 단원의 범위를 넘는다.

해밀턴 회로는 외판원 문제에 어떻게 쓰일까?

모든 장소를 한 번씩 들러 돌아오는 가장 짧은 동선을 찾는 외판원 문제는, 거리가 붙은 그래프에서 총거리가 가장 작은 해밀턴 회로를 찾는 문제다. 네 장소라면 식 (4)에 따라 서로 다른 회로가 3개뿐이어서 모두 계산하면 된다.

그림 4 위의 숫자가 네 장소 A,B,C,DA,B,C,D 사이의 거리(km)다. 세 회로의 총거리는 다음과 같다.

  • A,B,C,D,AA,B,C,D,A: 1+4+3+6=141+4+3+6=14
  • A,B,D,C,AA,B,D,C,A: 1+5+3+2=111+5+3+2=11
  • A,C,B,D,AA,C,B,D,A: 2+4+5+6=172+4+5+6=17
위는 네 장소 사이의 거리(km)를 적은 K₄이고 굵은 선이 가장 짧은 회로다. 선의 길이는 거리에 비례하지 않는다. 아래는 서로 다른 세 해밀턴 회로의 총거리로, A,B,D,C,A의 11 km가 가장 짧다.
그림 4 위는 네 장소 사이의 거리(km)를 적은 K₄이고 굵은 선이 가장 짧은 회로다. 선의 길이는 거리에 비례하지 않는다. 아래는 서로 다른 세 해밀턴 회로의 총거리로, A,B,D,C,A의 11 km가 가장 짧다. figures/tsp_tours.py

가장 짧은 것은 A,B,D,C,AA,B,D,C,A의 11 km다. 매번 가장 가까운 곳으로 가면 A→BA\to B(1), B→CB\to C(4), C→DC\to D(3), D→AD\to A(6)로 14 km가 되어 최단을 놓친다. 마지막에 출발점으로 돌아오는 거리까지 따져야 하기 때문이다.

핵심

해밀턴그래프는 모든 꼭짓점을 한 번씩 방문하고 출발점으로 돌아오는 단순회로를 갖는다. 모든 차수가 2 이상이라는 조건은 필요하지만 충분하지 않다.

해밀턴 회로에서는 모든 변도 지나야 하나요?

해밀턴 회로는 모든 변을 지날 필요가 없다. K4K_4의 해밀턴 회로 A,B,C,D,AA,B,C,D,A는 여섯 변 중 AB,BC,CD,DAAB,BC,CD,DA 네 변만 쓰고 AC,BDAC,BD는 남긴다. 모든 변을 한 번씩 쓰라는 조건은 오일러 회로의 조건이다.

꼭짓점이 두 개뿐이면 왕복해서 회로를 만들 수 있나요?

꼭짓점이 두 개인 단순 그래프에는 해밀턴 회로가 없다. 두 점 사이의 유일한 변을 왕복하면 같은 변을 두 번 쓰기 때문이다. 단순 그래프의 회로는 길이가 적어도 3이므로 해밀턴 회로에는 꼭짓점이 3개 이상 필요하다.

해밀턴 회로가 없으면 모든 점을 방문할 수도 없나요?

해밀턴 회로가 없어도 모든 점을 한 번씩 방문하는 해밀턴 경로는 있을 수 있다. 그림 1 아래의 A,B,C,D,EA,B,C,D,E는 각 점을 한 번씩 방문한다. 다만 EE에서 AA로 돌아오는 변이 없어 회로가 아니며, 돌아오려면 이미 지난 CC를 다시 만나야 한다.

해밀턴그래프의 흔한 오해

  • 모든 차수가 짝수이면 해밀턴그래프다. — 그림 1 아래는 모두 짝수지만 해밀턴 회로가 없다. 짝수 조건은 연결성과 함께 오일러 회로에 쓰인다.
  • 후보 한 개가 막혔으니 해밀턴 회로가 없다. — 그림 3에서 처음 시도한 A,B,C,E,DA,B,C,E,D는 막혔지만 다른 가지가 성공한다. 불가능성에는 전체 후보 검사나 식 (3) 같은 방해 조건이 필요하다.

직접 해보기

  1. 꼭짓점 P,Q,R,S,TP,Q,R,S,T와 변 PQ,QR,RS,ST,TP,PRPQ,QR,RS,ST,TP,PR이 있다. 해밀턴 회로를 하나 쓰시오.
  2. 중심 OO와 네 잎을 잇는 네 변만 있다. 해밀턴 회로가 불가능한 이유를 차수로 설명하시오.
  3. 사각형 둘레 P,Q,R,S,PP,Q,R,S,P와 삼각형 S,T,U,SS,T,U,S가 SS만 공유한다. 차수 목록을 구하고 해밀턴 회로와 오일러 회로의 존재를 구별하시오.
  4. 네 점의 완전그래프에서 PQPQ를 지워도 해밀턴 회로가 남는가? 실제 순서를 쓰시오.
  5. 네 장소 사이의 거리가 PQ=5PQ=5, PR=3PR=3, PS=6PS=6, QR=4QR=4, QS=2QS=2, RS=7RS=7이다. PP에서 출발해 모든 장소를 한 번씩 들러 돌아오는 가장 짧은 회로와 그 거리를 구하시오.
답과 풀이
  1. P,Q,R,S,T,PP,Q,R,S,T,P다. 다섯 꼭짓점을 한 번씩 방문하고 실제 변 다섯 개로 돌아온다. 변 PRPR은 쓰지 않아도 된다.
  2. 잎의 차수가 1이므로 서로 다른 들어오는 변과 나가는 변을 고를 수 없다. 식 (2)를 만족하지 않는다.
  3. P,Q,R,S,T,UP,Q,R,S,T,U의 차수는 2,2,2,4,2,22,2,2,4,2,2다. SS 한 점을 지우면 P,Q,RP,Q,R과 T,UT,U의 두 덩어리가 되어 식 (3)을 어기므로 해밀턴 회로는 없다. 모든 차수가 짝수이고 연결되어 오일러 회로는 있으며 S,P,Q,R,S,T,U,SS,P,Q,R,S,T,U,S가 한 예다.
  4. 남는다. P,R,Q,S,PP,R,Q,S,P의 네 변은 모두 남아 있고 네 점을 한 번씩 방문한다. 삭제한 변을 꼭 써야 하는 것은 아니다.
  5. 서로 다른 회로는 식 (4)에 따라 3개다. P,Q,R,S,PP,Q,R,S,P는 5+4+7+6=225+4+7+6=22, P,Q,S,R,PP,Q,S,R,P는 5+2+7+3=175+2+7+3=17, P,R,Q,S,PP,R,Q,S,P는 3+4+2+6=153+4+2+6=15이므로 P,R,Q,S,PP,R,Q,S,P의 15가 가장 짧다.

더 읽기

영상 노트

영상 노트
  • 00:00 방문할 장소와 사용할 복도를 구별하기
  • 00:40 식 (1)의 방문 순서에서 끝점 복귀 확인하기
  • 01:20 네 조합 표로 오일러 회로와 해밀턴 회로 비교하기
  • 02:00 식 (2)의 필요성과 두 삼각형 반례, 식 (3)으로 K₂,₃ 판정하기
  • 03:00 그림 3의 수형도로 후보 순서를 빠짐없이 펼치기
  • 03:50 디랙 정리와 오각형으로 충분조건과 필요조건 구별하기
  • 04:30 외판원 문제에서 세 회로의 총거리 비교하기

지도에서의 위치

꼭짓점의 차수기초수학오일러그래프기초수학해밀턴그래프지금 이 페이지
선수 개념
이 페이지
완성예정이 페이지까지 온 길전체 지도에서 보기 →
이 페이지의 기록
  1. 2026-11-16 · 에이전트 초안
  2. 2026-11-17 · 전수 검수 반영 — 오일러 회로와의 네 조합 비교, 점을 지운 뒤 덩어리 수로 불가능을 보이는 일반 조건과 K2,3, 빠짐없이 찾는 수형도, 완전그래프의 회로 수, 디랙 정리, 외판원 문제 절과 해보기 5번 추가, 질문 답 첫 문장 보강, 덩어리 수 조건을 점을 하나 이상 지울 때로 좁힘 (에이전트 수정, 그림 1→4)
  3. 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림