평면 그래프와 다익스트라: 오일러 해밀턴 경로 이해하기

핵심 정의와 기호

문제	목표
오일러 경로	모든 간선을 정확히 한 번 사용
오일러 회로	위 조건을 만족하며 시작점으로 복귀
해밀턴 경로	모든 정점을 정확히 한 번 방문
해밀턴 사이클	모든 정점을 한 번씩 방문한 뒤 시작점 복귀
최단 경로	지정한 두 정점 사이 비용 합 최소화

‘오일러 경로’는 관용적 이름이며 정점 반복을 허용하는 trail입니다. 10회차의 정점 반복 없는 path와 구분합니다. 간선이 있는 연결 무방향 그래프에서는 홀수 차수 정점이 0개면 오일러 회로, 2개면 서로 다른 끝점을 가진 오일러 경로가 있습니다. 일반적으로는 고립 정점을 제외한 부분의 연결성을 확인해야 합니다.

평면 그래프는 간선 내부의 교차 없이 평면에 그릴 수 있는 그래프입니다. 이미 그린 그림에 교차가 있다는 이유만으로 비평면이라고 판정하지 않습니다. 연결 평면 그림에서 V−E+F=2이며 F에는 바깥 면도 포함합니다.

가장 작은 예제

삼각형은 V=3,E=3,F=2여서 3−3+2=2입니다. A−B−C−A는 모든 간선을 한 번 쓰는 오일러 회로이면서 해밀턴 사이클입니다. 두 성질이 같은 그래프에서 성립해도 정의가 같다는 뜻은 아닙니다.

헷갈리는 반례

4개 정점의 완전그래프 K₄는 각 차수가 3이라 홀수 차수 정점이 4개입니다. 해밀턴 사이클은 있지만 오일러 경로는 없습니다. 최단 경로 역시 모든 간선이나 모든 정점을 방문할 필요가 없습니다.

다익스트라는 음수 가중치가 없는 그래프에서 한 시작점의 최단 거리를 구하는 대표 알고리즘입니다. 우선순위 큐 구현과 시간복잡도 최적화는 후속 과정의 범위입니다.

손으로 풀어보기

정점 A,B,C,D와 무방향 간선 AB,BC,CD,DA,AC를 둡니다. 차수는 A:3,B:2,C:3,D:2입니다. 홀수 정점 A,C가 끝점인 오일러 경로 A−B−C−D−A−C가 있으며 오일러 회로는 없습니다. 해밀턴 경로 A−B−C−D도 있습니다.

모든 간선 비용을 1로 보면 A에서 C로의 최단 경로는 직접 간선 AC(비용 1)입니다. 사각형 안에 대각선 AC를 그린 평면 그림은 내부 2면·외부 1면이므로 4−5+3=2입니다.

별도 가중 예제 AB=2,BC=3,AC=10에서는 직접 AC보다 A−B−C의 비용 2+3=5가 작습니다. 간선 개수 최소와 비용 합 최소가 다를 수 있습니다.

선택: JavaScript로 검산하기

코드 직접 실행

본문 예제를 선택하고 실제 계산 결과를 확인합니다.

예제 크게 보기 (새 탭)

손풀이 뒤 선택해서 실행하는 짧은 전체 코드입니다. 브라우저 Console 또는 Node.js가 준비된 환경의 check.mjs에서 실행할 수 있으며 수학 학습에 설치는 필수가 아닙니다.

const edges = [
  ['A', 'B', 2],
  ['B', 'C', 3],
  ['A', 'C', 10],
];
console.log('A→B→C cost', 2 + 3);
console.log('A→C direct cost', 10);

기대 결과: A→B→C cost 5, A→C direct cost 10이 출력됩니다.

별도 세 정점 가중 예제의 두 비용만 계산합니다. 다익스트라를 구현하거나 모든 그래프의 최단 경로를 검증한 코드가 아닙니다.

자주 발생하는 오해와 교정

모든 정점을 방문하는 문제에 오일러의 차수 조건을 적용하지 않습니다. 평면 공식의 바깥 면을 빼지 않고, 그림의 우연한 교차를 비평면의 증거로 삼지 않습니다. 음수 가중치에 다익스트라의 보장을 적용하지 않습니다.

직접 풀어볼 문제와 해설

쉬운 개념

오일러 경로는 간선을 한 번씩, 해밀턴 경로는 정점을 한 번씩 방문합니다. 최단 경로는 지정한 두 점 사이 비용 합을 최소화합니다.

단계별 예제

1. 삼각형 AB,BC,CA에 잎 정점 D와 간선 AD를 붙입니다.
2. 차수는 A:3, B:2, C:2, D:1이어서 홀수 차수 정점 A,D가 두 개입니다.
3. D−A−B−C−A는 네 간선을 한 번씩 쓰는 오일러 경로입니다.

직접 풀 문제

같은 그래프에 해밀턴 경로가 있나요? 평면 그림의 V,E,F를 세어 V−E+F도 확인하세요.

정답·해설 보기

1. D−A−B−C는 네 정점을 한 번씩 방문하는 해밀턴 경로입니다.
2. 정점 4개, 간선 4개, 내부 삼각형 면 1개와 바깥 면 1개로 F=2입니다.
3. 4−4+2=2입니다. 오일러와 해밀턴의 성립 이유는 서로 다릅니다.

다음 학습

12회차에서 정수 나눗셈·최대공약수·합동식을 손으로 계산합니다. 다음 글 읽기

학습 완료 체크리스트

• 정의의 적용 범위와 기호를 말로 설명할 수 있습니다.
• 위 손풀이를 답을 가린 상태에서 다시 계산합니다.
• 반례가 어떤 조건을 어기는지 설명합니다.

알고리즘 수학 노트

누적 이전 체크포인트: discrete-step-10-graph. 아래는 이번 회차의 완성 예시입니다. 자신의 다른 예제 하나를 덧붙여도 좋습니다.

노트에서 ‘간선1회·정점1회·비용최소’를 세 열로 나눕니다. 4정점5간선 예제의 차수, 오일러 경로, 최단 직접간선, 바깥 면을 포함한 F=3을 기록합니다. 구현을 고르기 전에 문제의 목표를 수학적 조건으로 적는 연습입니다.

완료 체크포인트

discrete-step-11-graph-problems

다음 학습

정수론 RSA 쉽게 이해하기: 유클리드 호제법과 합동식 기준에서 다음 개념을 이어갑니다.