[이산수학] 외판원문제(TSP문제)와 그래프 동형

<< 이산수학 6주차 >>

6. TSP 문제
7. 매칭 
8. 그래프동형 
9. 평면그래프 
10. 그래프색칠

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

⑥ TSP(Traveling Salesman Problem)
: 외판원 방문 문제
: 모든 도시를 한 번만 방문하고, 출발점으로 다시 돌아오는 최단 경로
>> 최소비용의 헤밀턴 사이클 찾기

★TSP의 어려움★
 : 도시 수가 많을수록 최적의 해를 계산하는 데에 엄청난 시간이 소요된다.
  해밀턴 순환의 총 수 = (n-1)! / 2
  "팩토리얼 증가"

해결 방안
타협 >> 품질 vs 비용
Naive algorithm vs Greedy algorithm
   (숲전체)     (나무)

Best solution -> good solution


//Greedy 알고리즘
(Nearest neighbor Algorithm)
단 이러한 greedy 알고리즘은 최적의 해를 보장하지 않는다.
출발점에 따라서 소요 비용이 다르기 때문이다.

input : G=(V,E)
v' = v1 // 복제
do while문 // v'에 가장 접해있는 것 중에서 weight가 가장 낮은 u를 선택&반복

문제풀이 할 때, 각각 구해야함.
전수조사를 통한 최소비용의 헤밀턴 사이클은? Nearest Neighbor알고리즘은?



⑦ 매칭 문제

1. 최대 매칭(Maximal Matching)
 완전 매칭이 불가능할 경우
2. 완전 매칭(Complete Matching)
 Maximal이면서 Complete함.

완전 매칭의 조건은?
Hall's Marriage Theorem(홀의 결혼 정리)
이분법이 가능함 >> 두 개의 집합의 정점들로 나눌 수 있다.
|N(A)| >= |A| // N은 이은 정점들의 집합
  (ex) N({a,b}) = 2
지원자, 직업
|N({A,B,D}| = |{J2, J5}| = 2
따라서 완전 매칭이 안된다.

N({W,Y})=1



⑧ 그래프 동형
: 두 그래프의 형태는 달라도, 본질 구조는 같은 것.

1. 인접 행렬 이용
두 행렬이 같다면 동형(isomorphic)이다.

2. 동형 함수
전단사 함수 f : V1->V2 가 존재.  //역함수도 존재
해당 전단사 함수는 그래프의 구조(인접 정보)를 보존되어 있다.

예제) 동형 함수 존재
1. G1의 정점들을 G2의 정점들로 매핑하는 전단사 함수를 제시 >> v / f(v)
2. 인접 정보가 그대로 보존을 보인다. >> {u,v} / {f(u), f(v)}

불변 정보(Invariant)
: 동형이기 위해서 두 그래프가 항상 만족해야할 조건
1. 정점의 수 동일
2. 간선의 수 동일
3. 정점의 차수 동일

또 다른 불변조건의 필요성
>> 위 세 조건을 만족한다고 "동형이라 단정할 수 없다."
>> ★같은 길이의 사이클이 존재해야 함.★ 

동형의 불변 조건 위반 예시

⑨ 평면 그래프
"간선들이 겹치지 않고 배열 할 수 있는가?"
>> tree는 대표적인 평면 그래프이다.
    (순환이 없기 때문에)

k3,3 / k5  >> 대표적인 비평면 그래프

- 평면 그래프는 전체 영역을 여러 영역으로 분할한다.
- 간선들로 둘러 싸인 영역도 존재하지만, 그렇지 않은 영역도 존재함

영역의 차수(R) = "경계의 길이"
모든 영역의 차수(R) = 2 x 간선

정점, 간선, 영역과의 관계
>> |E|-|V|+|R|=2

평면 그래프의 성질
(정점이 3개 이상인 단순그래프에서 다루자.) 
 "따름 정리"
① |V|>=3, |E|<= 3|V|-6
② 차수가 5를 초과하지않는 정점들이 존재해야 함.

(k5는 비평면 그래프)
정점 5개, 간선 10개
|E| ≤ 3|V|-6
10 ≤ 9 따라서 비평면

(k3,3도 비평면 그래프)
정점 6개, 간선 9개
|E| ≤ 3|V|-6
9 ≤ 18-6 이어서 평면 그래프 같지만! "평면 그래프가 아님"

또 다른 비평면 그래프의 정리가 필요함. >> 사이클의 최소 길이
③ |V|≥3 이며, 길이 3의 순환을 갖지 않으면, |E| ≤ 2|V|-4
 >> 쿠라토우스키 정리
 그래프가 K5 또는 K3,3에 준동형인 부분 그래프를 포함한다면 비평면 그래프이다.
 similar하다. 

세분할 >> 간선을 분할 가능하여 동형 그래프를 만들 수 있음.
1. 두 그래프는 isomorphic하지 않지만, homeometic 하다.
2. 두 그래프는 isomorphic하다.



⑩ 그래프 색칠
>> 인접된 정점을 서로 다르게 구분하는데 필요한 최소 색상 수?

지도에 대한 dual graph이다.

그래프 컬러링 알고리즘
숲 전체를 보면 시간이 오래 걸리기 때문에, GREEDY 알고리즘을 사용하자.
최적의 답은 보장하지 않는다.

① 웰치-포웰 알고리즘
1) 차수의 내림차순으로 정렬하라.
2) 첫번째 정점에 C1 배정, 해당 정점과 인접되지 않는 곳에 C1을 배정

② 또 다른 GREEDY 알고리즘
1) 모든 정점에 번호를 주었다.
2) 순서대로 정점마다 가장 낮은 번호의 색상부터 확인하면서 채워간다.


클리크(Clique)
완전 그래프를 갖는 부분 그래프이다.