• 평면 그래프와 4색 정리
• 오일러 트레일과 오일러 투어
• 해밀턴 경로와 해밀턴 사이클
• 가중 그래프와 데이크스트라 알고리즘
• 정리
• FAQ

평면 그래프와 4색 정리

평면 그래프는 그래프의 모든 변을 서로 교차하지 않게 평면 위에 그릴 수 있는 그래프를 말합니다. 여기서 중요한 점은 현재 그려진 모양이 아니라, 다시 배치해서라도 변의 교차를 없앨 수 있는지를 보는 것입니다. 즉 그림이 복잡해 보인다고 바로 비평면 그래프라고 판단하면 안 됩니다. 시험에서는 지금 보이는 그림만 보는 것이 아니라, 정점을 옮겨 그렸을 때 교차를 제거할 수 있는지까지 생각해야 합니다.

4색 정리는 평면 그래프와 함께 자주 등장하는 개념입니다. 서로 맞닿은 영역이 같은 색이 되지 않도록 지도를 칠할 때, 평면 그래프 구조에서는 많아도 네 가지 색이면 충분하다는 내용입니다. 그래서 평면 그래프는 단순히 교차 여부만 보는 개념이 아니라, 지도 색칠 문제와도 연결되는 중요한 구조로 이해하면 좋습니다.

평면 그래프를 볼 때 먼저 확인할 기준

현재 그림에서 선이 교차한다
→ 바로 비평면 그래프라고 단정하지 않음
→ 정점 위치를 바꿔 다시 그려 본다
→ 모든 변을 교차 없이 그릴 수 있으면 평면 그래프
→ 끝까지 교차를 없앨 수 없으면 비평면 그래프

평면 그래프 판별은 눈에 보이는 첫 모양보다 다시 그릴 수 있는 가능성이 더 중요합니다. 따라서 문제를 풀 때는 선이 겹친다는 사실 자체보다, 그 겹침이 본질적인지 아닌지를 구분해야 합니다. 이 단원에서 가장 먼저 익혀야 할 태도는 그래프를 고정된 그림이 아니라 구조로 보는 것입니다.

읽기 어려운 기호 빠르게 보기

v : 꼭지점 하나를 나타내는 기호
E : 변들의 집합
V : 꼭지점들의 집합
A-B : A와 B가 변으로 연결됨
cycle : 시작점으로 다시 돌아오는 순환
path : 꼭지점을 겹치지 않고 지나가는 경로
trail : 변을 겹치지 않고 지나가는 이동

그래프 단원은 용어만 헷갈리지 않아도 이해가 훨씬 쉬워집니다. 특히 path와 trail은 비슷하게 보이지만 기준이 다릅니다. path는 꼭지점의 중복이 없어야 하고, trail은 변의 중복이 없어야 합니다. 뒤에서 오일러와 해밀턴을 구분할 때 이 차이가 그대로 연결됩니다.

오일러 트레일과 오일러 투어

오일러 개념의 핵심은 모든 꼭지점이 아니라 모든 변입니다. 그래프의 모든 변을 각각 한 번씩만 지나는 트레일을 오일러 트레일이라 하고, 그중 시작점과 끝점이 같으면 오일러 투어라고 합니다. 따라서 오일러 문제를 볼 때는 내가 모든 정점을 지났는지가 아니라, 모든 변을 빠짐없이 정확히 한 번씩 지났는지를 먼저 봐야 합니다.

학생들이 가장 많이 헷갈리는 부분은 오일러가 모든 점을 한 번씩 지나는 것이라고 착각하는 지점입니다. 하지만 오일러는 꼭지점이 아니라 변이 기준입니다. 같은 꼭지점을 다시 지날 수는 있어도, 같은 변을 두 번 지나면 오일러 트레일이 아닙니다. 이 기준을 분명히 잡아야 해밀턴 경로와 헷갈리지 않습니다.

오일러 트레일과 오일러 투어의 차이

오일러 트레일
: 모든 변을 한 번씩 지난다
: 시작점과 끝점은 달라도 된다

오일러 투어
: 모든 변을 한 번씩 지난다
: 시작점과 끝점이 반드시 같다

두 개념의 차이는 마지막에 제자리로 돌아오느냐입니다. 둘 다 모든 변을 한 번씩 지난다는 공통점이 있지만, 오일러 투어는 출발한 꼭지점으로 다시 돌아와야 합니다. 문제를 풀 때는 경로를 직접 그려 보는 것도 좋지만, 먼저 기준이 변이라는 점을 떠올리면 훨씬 덜 헷갈립니다.

해밀턴 경로와 해밀턴 사이클

해밀턴 경로는 그래프의 모든 꼭지점을 한 번씩 지나는 경로입니다. 여기서는 변이 아니라 꼭지점이 기준이 됩니다. 경로의 정의상 같은 꼭지점을 다시 방문하면 안 되므로, 해밀턴 경로는 모든 꼭지점을 정확히 한 번씩 지나야 합니다. 그리고 시작점과 끝점이 다시 이어지면 해밀턴 사이클이 됩니다.

오일러와 해밀턴은 이름이 비슷해서 시험에서도 자주 섞입니다. 하지만 기준을 하나만 기억하면 바로 구분됩니다. 오일러는 변을 모두 사용하는 문제이고, 해밀턴은 꼭지점을 모두 방문하는 문제입니다. 따라서 어떤 그래프는 오일러는 가능하지만 해밀턴은 불가능할 수 있고, 반대로 해밀턴은 가능하지만 오일러는 불가능할 수도 있습니다.

해밀턴 경로를 보는 방식

A → B → C → D → E
모든 꼭지점을 정확히 한 번씩 지나면 해밀턴 경로
마지막 E에서 다시 A로 연결되면 해밀턴 사이클

해밀턴 경로는 꼭지점을 방문 체크하듯이 생각하면 이해가 쉽습니다. 이미 방문한 꼭지점을 다시 가면 경로 조건이 깨지기 때문에, 문제를 풀 때는 어떤 점을 방문했는지 계속 추적하는 습관이 중요합니다. 특히 해밀턴 사이클은 모든 꼭지점을 한 번씩 지난 뒤 다시 출발점으로 복귀해야 하므로 조건이 더 강합니다.

오일러와 해밀턴을 헷갈리지 않는 한 줄 기준

오일러 = 모든 변을 한 번씩
해밀턴 = 모든 꼭지점을 한 번씩

이 한 줄은 이번 단원의 가장 중요한 정리입니다. 문제에서 선을 빠짐없이 따라가라는 느낌이면 오일러를 먼저 떠올리고, 모든 점을 한 번씩 방문하라는 느낌이면 해밀턴을 먼저 떠올리면 됩니다. 학습 초반에는 복잡한 판별법보다 이 기준을 몸에 익히는 것이 우선입니다.

가중 그래프와 데이크스트라 알고리즘

가중 그래프는 각 변에 거리, 시간, 비용처럼 수치가 붙어 있는 그래프입니다. 같은 두 정점을 연결하더라도 어떤 길은 더 짧고, 어떤 길은 더 오래 걸릴 수 있기 때문에 단순히 연결 여부만으로는 부족합니다. 그래서 가중 그래프에서는 어느 경로가 가장 효율적인지를 따지는 최단경로 문제가 매우 중요해집니다.

최단경로 문제는 출발점과 도착점이 주어졌을 때 전체 경로의 가중치 합이 가장 작은 길을 찾는 문제입니다. 이때 대표적으로 배우는 방법이 데이크스트라 알고리즘입니다. 데이크스트라는 출발점에서 가장 가까운 정점부터 차례대로 확정해 나가면서, 각 정점까지의 현재 최단 거리를 계속 갱신하는 방식으로 이해하면 됩니다.

가중 그래프 예시

A-B : 2
A-C : 5
B-C : 1
B-D : 4
C-D : 2

A에서 D까지
A → B → D = 6
A → C → D = 7
A → B → C → D = 5

이 예시에서는 A에서 D까지 직접 보이는 경로가 하나가 아니라 여러 개입니다. 단순히 변의 개수가 적다고 최단경로가 되는 것은 아니고, 각 변의 가중치를 모두 더한 결과가 가장 작아야 합니다. 그래서 가중 그래프에서는 경로 길이를 눈으로만 판단하면 틀리기 쉽고, 반드시 합을 계산해야 합니다.

데이크스트라 알고리즘 흐름

1. 출발점의 거리를 0으로 둔다
2. 아직 확정되지 않은 정점 중 가장 짧은 정점을 고른다
3. 그 정점을 거쳐 가는 더 짧은 경로가 있으면 갱신한다
4. 모든 정점이 확정될 때까지 반복한다

데이크스트라 알고리즘은 처음부터 완성된 답을 한 번에 찾는 방식이 아닙니다. 현재까지 알려진 가장 짧은 후보를 하나씩 확정하면서 주변 정점의 값을 수정해 가는 방식입니다. 따라서 계산 과정에서 표를 함께 그리면 실수를 줄일 수 있습니다. 이 단원에서는 복잡한 구현보다, 왜 더 짧은 후보를 갱신하는지가 이해의 핵심입니다.

정리

이번 단원은 서로 비슷해 보이는 그래프 개념을 정확히 구분하는 것이 가장 중요합니다. 평면 그래프는 변을 교차하지 않게 다시 그릴 수 있는지로 판단합니다. 오일러는 모든 변을 한 번씩 지나는지로 판단하고, 해밀턴은 모든 꼭지점을 한 번씩 지나는지로 판단합니다. 가중 그래프에서는 변마다 비용이 다르기 때문에 최단경로 문제가 등장하며, 이를 해결하는 대표 알고리즘으로 데이크스트라를 배웁니다.

시험 직전에는 아래 흐름으로 정리하면 좋습니다. 평면 그래프는 교차 없이 다시 그릴 수 있는가, 오일러는 모든 변을 한 번씩 지나는가, 해밀턴은 모든 꼭지점을 한 번씩 지나는가, 최단경로는 가중치 합이 가장 작은가를 차례대로 떠올리면 됩니다. 이 기준만 분명해도 문제를 읽는 순간 어떤 유형인지 빠르게 분류할 수 있습니다.

많이 받는 질문

Q. 선이 교차해서 그려져 있으면 무조건 비평면 그래프인가요?
아닙니다. 현재 그림에서 선이 교차해 보여도 정점 위치를 바꾸어 다시 그렸을 때 교차를 없앨 수 있으면 평면 그래프입니다. 지금 보이는 모양이 아니라 구조 자체를 기준으로 판단해야 합니다.

Q. 오일러와 해밀턴은 무엇만 확실히 구분하면 되나요?
오일러는 모든 변을 한 번씩 지나는 개념이고, 해밀턴은 모든 꼭지점을 한 번씩 지나는 개념입니다. 이 한 줄만 정확히 기억해도 대부분의 혼동을 줄일 수 있습니다.

Q. 데이크스트라 알고리즘은 언제 사용하나요?
변에 가중치가 있는 그래프에서 한 출발점으로부터 다른 정점까지의 최단경로를 찾을 때 사용합니다. 특히 거리, 비용, 시간처럼 음수가 아닌 값으로 경로 길이를 비교하는 상황에서 대표적으로 활용합니다.