그래프 이론에서 그래프란: 객체의 일부 쌍들이 ‘연관되어’ 있는 객체 집합 구조

오일러의 경로

오일러의 정리: 모든 정점이 짝수 개의 차수를 갖는다면 모든 다리를 한 번씩만 건너서 도달할 수 있다.

오일러의 경로: 모든 간선(edge)을 한 번씩 방문하는 유한 그래프

해밀턴 경로

각 정점(vertex)을 한 번씩 방문하는 무항 또는 유향 그래프 경로

해밀턴 경로를 찾는 문제는 최적 알고리즘이 없는 대표적인 NP-완전 문제이다.

해밀턴 순환: 원래의 출발점으로 돌아오는 경로. 이 중에서도 특히 최단 거리를 찾는 문제는 외판원 문제로 유명하다.

NP 복잡도

NP: 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합

P(결정론적 튜링 기계 문제) < NP

• 해밀턴 경로: 한 번만 방문하는 경로 (NP-완전 문제)
• 해밀턴 순환: 한 번만 방문하여 출발지로 돌아오는 경로 (NP-난해 문제)