9-2 오일러 사이클과 해밀턴 사이클

1. 오일러 사이클 (간선 탐색 방법)

① 그래프 이론 : 유한개의 정점과 간선의 결합 방법에 대한 이론

 

② 해밀턴 문제

  -  12면체 20개의 각 정점에 도시 이름을 적고 어느 한 도시에서 출발하여 모서리를 따라서

      다른 모든 19개 도시 방문하고 처음 출발한 도시로 돌아오는 게임

  -  각 도시는 단 한 번만 방문 가능

③오일러 사이클

  - 2개의 섬과 7개의 다리로 구성된 공원에서 7개의 다리를 모두 지나가는데 이미 지나갔던 다리는

    다시 거치지 않고 갈 수 있는 전체 경로를 해결하는데 오일러는 그래프 이론 사용.

  - 오일러는 이 문제를 해결하는데 각 정점에 연결된 간선의 개수가 모두 짝수일때만 가능함을 증명

  - 각 간선을 정확하게 한번씩만 경유해서 그래프의 모든 간선을 지날 수 있는 경로가 존재하고,

    출발 정점과 최종 도착 정점이 같으면 오일러 사이클이라고 함.

 

④ 오일러 사이클

  - 각 간선을 한번씩만 경유해서 그래프의 모든 간선을 지날 수 있는 경로가 존재한다면

    그래프는 오일러 경로를 갖는다고함.

  - 그래프 G가 오일러 경로를 갖기 위한 필요충분조건은 그래프 G가 연결 그래프이고

     홀수 차수 정점이 2개인 것이다.

 

 

2. 해밀턴 사이클 (정점 탐색 방법)

① 해밀턴 경로

  - 그래프 G=(V,E)가 주어진 모든 정점들을 정확하게 한 번만 경유하는 경로가 있는 그래프

    를 해밀턴 경로가 존재한다고 함.

② 해밀턴 사이클 - 시작점과 끝점이 같은 해밀턴 경로

  - 한 정점에서 출발하여 인접한 간선과 이웃하는 정점을 따라 교대로 통과하되 시작점을 제외한

    모든 정점을 단 한 번씩만 지나서 시작점으로 되돌아오는 것

  - 해밀턴 사이클 존재 O -> 해밀턴 경로 존재 O

    해밀턴 경로 존재 O -> 해밀턴 사이클 존재 O 

③ 해밀턴 그래프

  - 방문 판매원 문제

    :  방문 판매원이 수많은 도시를 순회하여 출발한 도시로 돌아와야 하는데 이때 각 도시를 단 한 번만 방문하되

       총 이동거리를 가능한 짧게하고자 한다. 각 도시들 사이의 거리가 다양하게 주어짐(가중치) . 어떤 경로 선택해야 하는가?

       - 정점이 늘어나면 어려워져서 NP-난해 문제로서 문제를 푸는 효율적 알고리즘이 아직 안알려짐.

3. 트리

① 트리

  - 사이클이 없는 연결 그래프

  - 상위 원소에서 하위 원소로 내려가면서 확장되는 트리 모양의 구조

  -1) 루트 트리

      - 루트라 부르는 노드가 1개 존재

      -  나머지 노드들은 m개의 서로 분리된 집합 T1,T2,...,Tm으로 나뉘며 Ti는 다시 루트 트리가 됨

      - 중첩된 집합, 중첩된 괄호, 들여쓰기 등을 표현할 때 사용

②

③