9-1 그래프의 종류

1. 특수한 그래프

① 평면 그래프

  - 평면에 그릴 대 정점이 아닌 곳에서는 어떤 간선도 교차하지 않는 그래프

  - 교차하는 간선이 존재하는 그래프 -> 비평면 그래프

 

② 오일러의 공식 : 각 다리를 겹치지 않고 한번 씩만 거쳐서 갈 수 있는 경로가 있는 지?

  - 그래프 G가 평면 그래프일 때 정점의 수 v, 간선의 수 e, 그래프G에 의해 평면상 형성되는 영역의 수가 r이라 하자.

  - r = e-v+2 => 오일러의 공식 

③ 정규 그래프 

  - 그래프 G=(V,E)에 대하여, 모든 정점의 차수가 같으면 정규 그래프

  - n개의 정점을 갖는 정규 그래프 G는 

    N= 1/2(r+r+...+r) = 1/2*n*r 이며, 이 때 정규 그래프 차수를 r이라고 함.

④ 입체 그래프

  -  차수가 3인 정규그래프를 입체 그래프라 함.

⑤ 동형 그래프

  - 모양과 생김새는 다르지만 두 그래프가 똑같은 정점과 똑같은 간선으로 구성되어 있는 그래프

  - 그래프를 구성하는 정점과 간선이 같다면 다양한 형태의 동형 그래프가 존재 가능.

  - 두 그래프가 동형 그래프가 되려면 정점의 개수, 간선의 개수, 정점의 차수, 사이클의 길이 등이 같아야 함.

  - 예시) 두 그래프 G/H가 동형 그래프인지 식별하시오.

     >함수 f는 전단사 함수이므로 E에 속하는 임의의 간선을 선택했을 때,그 간선에 대응하게 되는

       간선의 쌍이 F에 존재함.

     >ex) (a,b) ∈ E이면 (f(a),f(b)) = (p,q) ∈ F이고 그 역도 성립! 따라서 두 그래프 G,H는 서로 동형 그래프이다.

 

2. 오일러 사이클

① 오일러 경로

  - 그래프 G=(V,E)에서 각 간선을 정확하게 한 번씩만 경유해서 그래프의 모든 간선을 지날 수 있는 경로가 존재한다면 그래프 G는 오일러 경로를 갖는다고 함.

  - 그래프 정점 v에서 시작해서 모든 간선을 꼭 한 번씩 지나 v로 돌아오는 경로를 오일러 사이클이라고 함!

  - 그래프 G가 오일러 경로를 갖기위한 필요충분 조건은 그래프 G가 연결 그래프이고 홀수 차수의 정점이 0(모든 정점의 차수가 짝수)또는 2개인 것임!

 

 

② 그래프 이론에서 중요한 문제

  - 모든 도시를 방문해야 하는 판매원의 경우, 각 도시를 한 번씩만 거칠 때 가장 경제적임

     => 방문할 도시들을 정점으로 표현할 수 있으며 각 도시를 정확히 한 번만 경유하는 최적의 방문 경로를 찾는 데 목적이 있음!

 

3. 해밀턴 경로와 해밀턴 사이클

① 해밀턴 경로

  - 어떤 두 정점에 인접하는 간선이 존재하지 않더라고 다른 정점들과 간선들을 통해 두 정점이 연결되면 두 정점 간의 경로가 존재하는 것임

  - 그래프 G=(V,E)가 주어진 모든 정점들을 정확하게 한 번만 경유하는 하나의 경로가 있는 그래프를 해밀턴 경로가 존재한다고 함.

 

② 해밀턴 사이클 (다시 자기자신으로 돌아오는 것)

  - 연결된 그래프가 각 정점을 정확히 한 번만 경유하는 경로인 사이클