이산수학 오일러 순환과 해밀턴 순환

Ja_an·2021년 7월 19일
0

이산수학

목록 보기
6/13

이산수학 그래프1: 오일러 순환과 해밀턴 순환

그래프

  • 그래프는 정점(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)
profile
주말은 쉬어요

0개의 댓글