[이산수학] 그래프의 종류와 오일러/해밀턴 경로

<<이산수학 5주차>>

1. 그래프소개 
2. 부분그래프 
3. 연결그래프 
4. 이동경로 
5. 최단경로찾기

---------------------------------------------------------------------------------

① 그래프 모델링
: 주어진 문제를 그래프로 표현하여 해결
 (정점과 정점을 잇는 간선으로 표현)

주요 구성 요소
- 정점(꼭짓점)
- 간선(모서리)

G = (V,E)
V = {1,2,3,4,5,6}
E = {{1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6}} 
  // 집합으로 나타내면 '연결'이 되어 있음.
  // 순서쌍으로 연결되어 있으면 '방향' 그래프로 표현 가능


다중 간선 : 두 정점을 연결하는 간선의 수가 두 개 이상인 경우
 (루프 : 자기에서 자기에게로 오는 간선)

다중간선과 루프가 있으면 집합을 표현할 때, 그래프의 수학적 정의가 불편해짐
따라서 우리는 단순 그래프(다중 간선 X, 루프 X)를 사용하여 표현한다. 

인접 vs 근접 // 두 용어의 차이점 이해하기
- 인접 : 이웃 관계
          정점이 기준
- 근접 : 붙어있는 관계
          간선이 기준

인접행렬
- nxn 대칭 행렬(n은 정점 수)
- 각 칸에 정점 사이에 연결된 간선의 수
- 0-1 행렬 >> 단순 그래프
- 정수 행렬 >> 그 외 그래프

인접행렬 예시

근접 행렬
- 정점이 n, 간선이 m
- nxm 행렬
- 각 칸에 간선의 근접 연결

근접행렬 예시

정점의 이웃과 차수
- 이웃 : 정점과 인접한 정점 >> v의 이웃을 N(v)
- 차수 : 각 정점에 연결된 간선의 수 >> v의 차수를 deg(v)
          // 루프는 2로 카운트한다. 
(ex)
N(a) = {c,d} / N(c) = {a,b,d}
N({a,c}) = {a,b,c,d}


★차수의 성질★
  // 그래프의 성질을 나타냄
- 모든 정점의 차수 합은 짝수
- 홀수 차수를 갖는 정점은 짝수개
- 모든 정점의 차수 합은 = 간선 *2  //핸드쉐이킹 정리
- 루프는 2개로 카운트

단순그래프 유형
  // 루프 또는 다중 간선이 없음
1. 완전 그래프(Complete Graph)
: 모든 정점(n)이 연결되어 있음
  K_n으로 표시
  완전 그래프의 간선수는 n*(n-1)/2 이다.)
  (불완전 그래프는 모든 정점들 연결 X.)
★(ex. K5)

2. 정규 그래프
: 모든 정점의 차수(k)가 같은 그래프이다.
  if  G=(V,E)  is  k-regular일 때, K*|V| = 2*|E| 이다.
★(ex. 피터슨(peterson)의 3-regular  // 선들이 겹치지 않고는 만들어질 수 없는 그래프)

3. 이분할 그래프(Bipartite Graph)
: "이분 그래프"
  정점들을 두 그룹으로 나눌 수 있음. 같은 집합에 속한 애들끼리 간선이 연결 X
  두 색으로 모든 정점을 색칠할 수 있다.

4. 완전 이분할 그래프
: 각 정점은 다른 집합의 모든 정점들과 연결된다.
  K_m,n으로 표시
  간선의 수 = m*n
★(ex. K_3,3 // 선들이 꼬이거나 겹치지 않고는 만들어질 수 없는 그래프)



② 부분 그래프 
: 원본 그래프의 일부분 //그래프가 모두 필요한 것이 아니기 때문에 일부분만 추출
  G' = (V', E')
유도된 그래프? >> 숙제
정점 또한 부분그래프가 될 수 있다. && 자기 자신 또한 부분 그래프가 될 수 있다.

1. 신장 부분 그래프
 // Spanning Subgraph
: 원본 그래프가 존재한다면, 간선은 부분집합이되 모든 정점을 반영함. // 정점 유지

(신장 트리)
 >> 신장 부분 그래프 보다 더 제약적. 모든 정점을 갖고 있으면서, 간선의 수가 정점보다 -1이다.
 >> 순환이 존재하지 X



③ 연결 그래프
: 정점에서 다른 '모든' 정점으로의 경로가 존재하는 그래프
  (그렇지 않으면, 비연결 그래프)
 >> 정점의 수가 n인 연결그래프, 최소 n-1개의 간선이 존재

(연결 요소)
 // 연결된 덩어리
- C(G)로 표기 , C(G)는 끊어진 부분 그래프 수
 (ex. C(G)=1이면 모든 정점들이 연결되어 있음)

C(G) 계산 알고리즘
G=(V, E)
while  V ≠ 공집합
연결된 모든 간선들을 제거
c += 1
return c



④ 그래프에서의 움직임 
이동경로  : 방문한 정점과 간선의 '시퀀스'로 표현함.
 시작과 끝은 정점이며, 길이는 방문한 간선의 수
 (단순 그래프이면, 정점만으로 표시해도 된다.)

때로는 제한을 둘 경우도 있음
- 정점의 반복 허용 X
- 간선의 반복 허용 X
- 시작과 끝 정점이 동일해야함.

(용어 설명 // 이동형태)
워크? 제한 없음
트레일? 중복간선 X
서킷? 중복간선 X, 시작과 끝 정점 동일
패스? 중복정점 X
사이클? 중복정점 X, 시작과 끝 정점 동일

1) 오일러 circuit
: 모든 간선을 오직 한 번만 방문하고, 시작점으로 되돌아옴.
 "중복 정점 허용"
 >> 모든 정점의 차수는 짝수

2) 오일러 trail
: 모든 간선을 오직 한번만 방문하고, 시작점으로 되돌아오지 않아도 됨
 >> 홀수 차수의 정점이 2개 존재
     (홀수 차수 정점에서 시작해서 차수가 홀수인 다른 정점에서 종료됨)

쾨니스베르그 다리 문제
모든 정점의 차수가 홀수이므로 오일러 circuit 존재 X
다리 2개를 더 연결해주니 모든 정점의 차수가 짝수가 되고 오일러 circuit이 존재하게 된다.

- 오일러 circuit의 활용
: 제설차 운행 시, 모든 도로를 한번만 방문하고 출발점으로 되돌아오기
- 오일러 trail의 활용
: 전시장의 모든 문을 한번만 통과하고 나올 수 있는가?

3) 해밀턴 사이클
: 모든 정점을 한번만 통과해서 출발점으로 돌아온다.
 (모든 간선을 통과하지 않아도 된다.)

4) 해밀턴 패스
시작점과 끝점이 다르지만 모든 정점을 한 번만 방문한다.

- 해밀턴 cycle의 활용
: 우체통 방문 경로, 모든 우체통을 한번만 돌고 출발점으로 되돌아오기

해밀턴 사이클 vs 오일러 서킷 



⑤ 최단 경로 찾기
"가중치 그래프(weighted Graph)"
G = (V, E, f)  // f : E->N

(예제)
V={a,b,c,d,e,z}
E={(a,b),(a,d), ... (e,z)}
f((a,b))=4 )   // 가중치는 거리, 시간, 비용 등


다익스트라 "최단 경로 알고리즘" >> 네비
-------
(알고리즘)
for i=1 to n 모든 가중치가 양수 값
      L(vi) = 무한
L(a)=0  // 처음 시작 지점이므로 0을 둔다.
S := 공집합  // 처음 S의 집합은 공집합
while  z !∈ S
   ...

L(z)를 반환함. // z길이까지의 가중치
-------

"폴로이드 알고리즘"
최단 경로(최단 비용)
모든 정점 간의 최단 비용을 구해준다.