이 섹션에서는 오일러 및 해밀턴 그래프를 볼 것입니다. 그러나 그 내용에 대해 알아보기 전에 먼저 그래프에서 트레일이 무엇인지 확인해야 합니다. 아래와 같은 그래프가 있다고 가정해 보겠습니다. -
트레일은 모든 꼭짓점(v1, v2, … , vk)이 구별되지 않을 수 있는 가장자리(v1, v2), (v2, v3), … , 그러나 모든 가장자리는 구별됩니다. 이 예에서 하나의 흔적은 {(B, A), (A, C), (C, D), (D, A), (A, F)}입니다. 이것은 흔적입니다. 그러나 이것은 정점 A를 두 번 방문하므로 단순한 경로로 간주되지 않습니다. 첫 번째 정점과 마지막 정점이 같으면 닫힌 트레일이 됩니다.
오일리안 트레일
그래프 G(V, E)의 오일러 궤적은 모든 간선을 정확히 한 번 포함하는 궤적입니다. G가 Eulerian Trail을 닫았다면 그 그래프를 Eulerian Graph라고 합니다. 즉, 그래프 G는 오일러 그래프라고 할 수 있습니다. 한 정점에서 시작하면 모든 모서리를 정확히 한 번만 횡단하여 시작 정점으로 돌아갈 수 있습니다. 오일러는 모든 꼭짓점의 차수가 짝수인 경우에만 그래프를 오일러 그래프라고 함을 증명했습니다.
해밀턴 순환
한 주기는 그래프 G의 모든 꼭지점을 통과하는 경우 해밀턴 주기라고 합니다. 그래프가 해밀턴 주기에 충분한 조건을 제공하는 여러 가지 정리가 있습니다. 그러나 임의의 그래프가 해밀턴인지 판별하는 문제는 NPCComplete 문제입니다.