오일러 순환과 해밀턴 순환

그래프

• 그래프 G는 다음의 두 가지 집합으로 구성되며, G={V,E}로 표시된다. 여기서 V는 정점들의 집합이며, E는 정점들을 연결하는 선들의 집합이다.

차수

• 정점 u에 접합된 연결선의 수
• 차수는 deg(u)와 같이 표기하기도 함

오일러 경로를 갖기 위한 필요 충분 조건

• 2개 이상의 정점을 갖는 루프가 없는 연결 그래프에서 홀수 차수를 갖는 정점이 하나도 없거나 오직 두 개만 존재해야 한다.
• 특히 모든 정점이 짝수 차수를 가지면 오일러 순환이 존재하며, 이 그래프는 오일러 그래프이다.

해밀톤 경로(Hamitonian Path)

그래프 G에서 모든 정점을 정확히 한 번만 지나는 경로

해밀톤 순환(Hamiltonian cycle 혹은 circuit)

시작점과 끝점이 같은 해밀톤 경로

 TSP 알고리즘

1. 하나의 정점을 선택하여 출발점으로 한다.
2. 이 정점에 연결된 연결선의 비용이 가장 작은 정점을 선택한다.
3. 이 정점에서부터 아직 선택되지 않은 정점들 중에서 연결선의 비용이 가장 작은 정점을 선택한다.
4. 모든 정점을 선택할 때까지 2와 3의 절차를 반복한다.