오일러경로 == 한붓그리기

쾨니히스베르크 다리 문제 그러나 이 문제는 모든 정점이 짝수개의 차수를 갖지 않아 오일러 경로가 아니다

오일러는 쾨니히스베르크 다리에 a~g의 이름을 붙이고 도식화해 논문을 발표

그림의 스케치는 현대의 그래프 구조의 원형이 되었다.

A, B, C, D : 정점(vertex)

a~g : 간선(edge)

오일러의 “모든 정점이 짝수개의 차수(Degree)를 갖는다면 모든 다리를 한 번씩만 건너서 도달하는 것이 성립한다.” 는 주장을 100년도 더 뒤에 칼 히어홀저가 수학적으로 이를 증명한 것이 오일러 정리 이다.

⇒ 모든 간선을 한 번씩 방문하는 유한그래프(Finite Graph)를 오일러경로(Eulerian Trail, Eulerian Path)라고 한다

해밀턴경로

“각 정점을 한 번씩 방문하는 무향 혹은 유향 그래프 경로”

해밀턴 경로를 찾는 문제는 최적 알고리즘이 없는 대표적인 NP-Complete problem이다(NP문제 중 난해인 문제)

NP 복잡도

원래의 출발점으로 돌아오는 경로 : 특별히 해밀턴 순환 이라고 불린다

이 중 최단 거리를 찾는 문제는 알고리즘 분야에서 외판원 문제(Salesman Problem)로 유명하다

외판원 문제(Traveling Salesman Problem, TSP) : 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 문제 (최단 거리인 해밀턴 순환을 찾는 문제) , NP-Hard 문제로 Theoretical Computer Science 분야의 매우 중요한 문제 중 하나

이 문제에서 도시가 20개라면, 문제의 정답을 찾기 위해 다녀야하는 총 경로 수 $= 20! = 2,432,902,008,176,640,000$

😱

❓왜 해밀턴 경로 문제와 외판원 문제의 NP문제가 다를까?