그래프
- 그래프는 정점(Vertex)의 집합과 선(Edge)들의 집합으로 구성되며 G = {V, E}로 표시한다
- 차수(degree)
- 정점u에 접합된 연결선(Edge)의 수
- deg(u)와 같이 표기하기도 한다
- 자기 자신을 연결하는 연결선(loop)의 경우 차수를 2로 본다
오일러 순환
- 오일러 경로
- 그래프 G의 모든 연결선(Edge)를 한번만 방문하는 경로
- 2개 이상의 정점을 갖는 루프가 없는 연결 그래프에서
홀수 차수를 갖는 정점이 하나도 없거나 오직 2개(시작점, 끝점)만 존재해야 한다
- 오일러 순환
- 시작점과 끝점이 동일한 오일러 경로
- 오일러 경로에서 모든 정점이 짝수 차수를 가지면 오일러 순환이 존재한다
- 오일러 그래프
- 오일러 순환이 존재하는 그래프
- 각 정점의 차수를 이용해 오일러 순환을 구할경우 시간복잡도
- n 차수 ≤ n(n-1) ≤ n^2
- O(n^2) O(n*m) (m<n), (m은 평균차수)
해밀턴 순환
- 해밀턴 경로
- 그래프 G에서 모든 정점(Vertex)을 정확히 한번만 지나는 경로
- 해밀턴 순환
- 시작점과 끝점이 같은 해밀턴 경로
- 해밀턴 순환을 찾는 알고리즘은 존재하지 않는다
- 브루트포스 해야함
- O(x^n) (x는 간선의 갯수, n은 정점의 수)
- np Problem
- TSP(traveling salesman problem, 방문 판매원 문제)
- 연결선에는 비용이 주어진다
- 일반적으로 완전 그래프
- 이 그래프에서 비용이 최소가 되는 해밀톤 순환을 찾는문제
- n≤11일경우: 브루트포스(O(n!))
- n≤12일경우: 백트래킹
- n≤16일경우: DP+BitMasking(2^n*n^2)
주말은 쉬어요