[Algorithm] 그래프 알고리즘 - 오일러의 정리와 오일러 경로, 해밀턴 경로와 해민턴 순환, 회판원 문제, NP 복잡도

지금으로부터 300여 년 전 프로이센 공국의 쾨니히스베르크에는 프레겔 강이 흐르고 있었다. 프레겔 강에는 2개의 큰 섬이 있었고, 섬과 도시를 연결하는 7개의 다리가 놓여 있었다. 어느날 도시의 시민 한 명이 "이 7개 다리를 한 번씩만 건너서 모두 지나갈 수 있을까?"라는 흥미로운 문제를 냈다. 그러나 쉽게 풀릴 것처럼 보였던 이 문제를 풀 수 있는 이는 아무도 없었다.

'수학의 모차르트'라 불리는 레온하르트 오일러가 '쾨니히스베르크의 다리 문제'를 조사하기 시작했다. 오일러는 이 문제가 도형 문제처럼 보이지만, 당시까지 알려진 기하학으로는 풀 수 없음을 알았다. 그리고 미지의 영역에 그 해법이 있다는 사실을 처재적인 직관으로 간파했다.

이것이 바로 '그래프 이론'의 시작이다.

오일러 경로

오일러는 모든 정점이 짝수 개의 차수(Degree)를 갖는다면 모든 다리를 한 번씩만 건너서 도달하는 것이 성립한다고 말했다. 그로부터 100년이 훨씬 더 지난 1873년, 독일의 수학자 칼 히어홀저가 이를 수학적으로 증명해낸다. 이를 '오일러의 정리'라 부른다. 아울러 모든 간선을 한 번씩 방문하는 유한 그래프를 일컬어 오일러 경로라 부르며, 어려서부터 즐겨 하던 놀이 중 하나인 '한붓 그리기'라고도 말한다.

해밀턴 경로

해밀턴 경로는 각 정점을 한 번씩 방문하는 무향 또는 유향 그래프 경로를 말한다. 해밀턴 경로와 오일러 경로의 차이점을 들자면, 오일러 경로는 간선을 기준으로 하고 해밀턴 경로는 정점을 기준으로 한다는 점이다. 그러나 이러한 단순한 차이에도 불구하고 놀랍게도 해민턴 경로를 찾는 문제는 최적 알고리즘이 없는 대표적인 NP-완전 문제다.

원래의 출발점으로 돌아오는 경로는 특별히 해밀턴 순환이라 하는데, 이종에서도 특히 최단 거리를 찾는 문제는 알고리즘 분야에서는 회판원 문제으로 더욱 유명하다. 외판원 문제란 각 도시를 바문하고 돌아오는 가장 짧은 경로를 찾는 문제, 즉 최단 거리인 해밀턴 순환을 찾는 문제이며, NP-난해 문제로 이론 컴퓨터과학 분야의 매우 중요한 문제 중 하나이기도 하다.

NP 복잡도

NP는 비결정론적 튜링 기계(NTM)로 다항 시간 안에 볼 수 있는 판정 문제의 집합으로, NP는 비결정론적 다항시간(Non-deterministic Polynomial time)의 약어이다.

NP 속하는 문제는 결정론적 튜링 기계로 다항 시간에 검증이 가능하고, 그 역도 성립한다. 또한 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 문제는 비결정론적 튜링 기계로도 다항 시간 안에 풀 수 있으므로, P 집합은 NP의 부분집합이다. 이때 P가 NP의 진부분집합인지, 혹은 P와 NP가 같은지에 대해서는 아직 알려지지 않았다. 이 문제는 P-NP문제로 불리우며 컴퓨터과학 부야의 대표적인 미해결 문제 중 하나다.

• 해밀턴 경로 : 한 번만 방문하는 경로
• 해밀턴 순환 : 한 번만 방문하여 출발지로 돌아오는 경로
• 외판원 문제 : 한 번만 방문하여 출발지로 돌아오는 경로 중 가장 짧은 경로

따라서 이 세문제는 '해밀턴 경로 > 해밀턴 순환 > 외판원 문제'의 포함 관계를 이룬다. 이제 해밀턴 경로와 외판원 문제, 2가지 문제를 다시 한번 정의해보자.

1. 해민턴 경로가 존재하는가?
2. 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾아라(최단 거리 해밀턴 순환을 찾아라)

1번 문제는 결정 문제로 다항 시간에 정답을 검증할 수 있다. 즉 NP 문제이며, NP-난해 문제다. NP-완전 문제의 조건에 부합하며 따라서 1번 문제는 NP-완전 문제다. 그러나 2번 문제는 결정 문제가 아니므로 NP 문제가 아닐 수 있다. 증명할 수 있는 NP-난해 문제이지만 NP 문제가 아닐 수 있으므로 NP-완전 문제가 아니다. 따라서 2번은 NP-난해 문제다.

출처

파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]