Undirected Hamiltonian Cycle은 NP-Complete이다.

안녕하세요! Zedd입니다 :)

오늘은 UHC(Undirected Hamiltonian Cycle)는 NP-Complete인 것을 증명해볼려고 해요 XD

 Hamiltonian Cycle(이하 헤밀토니안 사이클)문제는 <TSP는 NP-Complete>글에서 소개했었죠? 

헤밀토니안 사이클이 뭔지 모르시는 분들은 읽고와주세요 :)

이 글 역시 P, NP, NP-Hard, NP-Complete에 대한 개념이 없으면 전혀 이해를 하지 못하실거에요 :(

P, NP : <P와 NP의 개념>

NP-Hard, NP-Complete : <NP-Hard, NP-Complete>

그럼 시작할게요!

Undirected Hamiltonian Cycle은 NP-Complete이다.

---

주어진 그래프에서 출발점과 종료점만 두 번 나타나는 것을 제외하고는 정점이 한 번씩만 나타나는 사이클을 해밀턴 사이클 (Hamiltonian cycle) 이라고 했었죠? 

그럼 Undirected Hamiltonian Cycle은, 주어진 그래프가 방향이 없는, 즉 "무향 그래프"겠네요.

이 Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)이 NP-Complete임을 증명해봅시다.

어떤 문제가 NP-Complete임을 증명하고싶으면 딱 두가지만 하면됐었죠?

1. NP임을 증명

2. NP-Hard임을 증명

이 두가지 조건을 만족하는 것이 NP-Complete니까요 :)

그럼 1번부터 시작해봅시다.

1. Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)이 NP임을 증명.

NP : "어떤 certificate가 다항시간(Polynomial Time)에 verify할 수 있으면, 

그 문제는 클래스 NP에 속한다"

Certificate는 무향그래프 노드들의 시퀀스겠죠? 그대로 이 노드들을 따라가서 확인하면 됩니다. 

1 - 1 )모든 노드들을 "한번씩"지나가야하니, 모든 노드가 한번씩 나와있는지 체크. 

1 - 2 ) 그 노드들을 따라가는 간선이 있는지 체크.

1 - 3 ) Cycle의 조건을 만족해야 하므로, 출발점과 도착점이 같은지 체크.

1 - 4 ) 노드의 개수가 N+1(출발점, 도착점 포함)인지 체크.

1 - 5 ) Certificate의 간선이 모두 "존재하는"간선인지 체크.

위 조건들은 Polynomial time에 판별이 가능합니다. 

즉, Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)은 클래스 NP에 속합니다.

2. Transformation Function고안 == NP-Hard임을 증명

2 - 1 ) 알려진 NP-Complete문제 중에서 비슷한 것을 고른다.
==> DHC(Directed Hamiltonian Cycle) 

Directed Hamiltonian Cycle이니 "유향" 헤밀토니안 사이클이네요. 딱봐도 Undirected Hamiltonian Cycle과 굉장히 비슷해 보이는 문제죠? 

2 - 2 ) Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)의 인풋을 Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)의 인풋으로 바꾼다. 

우리는  Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)이 NP-Hard임을 보이고 싶이때문에,  Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)로 Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)을 해결하면 Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)이 NP-Hard임이 증명됩니다.

(계속 Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클), Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)이렇게 풀어쓰는 이유는 ㅠㅠㅠ UHC, DHC로 이야기 하다보면 나중에 헷갈려서......제가 그랬죠..........조금 보기 힘들더라도 이해바랍니다1!!)

즉! Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)의 인풋 -> Transformation Function ->  Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)의 인풋

으로 만들면 되는 것입니다.

Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)의 인풋은 뭐였죠? 네, "유향 그래프"겠죠? <TSP는 NP-Complete >글에서도 말씀드렸듯이, 헤밀토니안 사이클은 완전그래프가 아닌 정말 그냥 "그래프"여도 됩니다. 

예를 하나 들어볼까요?

제가 수업시간 때 배운 예제를 그대로 가져와봤어요 :)

간선에 방향이 있으니, 유향 그래프 맞죠?

이게 바로 Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)의 인풋입니다.

그럼 위 인풋을 Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)의 인풋으로 바꿔야겠죠?

이 Transformation Function이 어떻게 이루어졌는지는 저도 모르지만..

일단 위 인풋이 Transformation Function을 거쳐 어떻게 Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)의 인풋으로 만드는지 알려드릴게요.

1. 노드와 간선이 2N개가 추가된다. 

2. 간선을 추가할 때,  Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)에서의 방향을 보면서 출발점의 3번노드와 도착점의 1번노드를 연결해준다. 

엥..? 무슨소리인지 잘 모르시겠죠? 

그림으로 알려드리겠습니다. 

1. 노드와 간선이 2N개가 추가된다.

무슨 노드와 간선이 추가된다는 거지..? 먼저 노드가 Transformation function을 거쳐 2N개가 추가된 모습을 보여드릴게요. 

자! 이렇게 노드가 추가된다는 말이었습니다 ㅎㅎ

원래 노드가 추가된 노드는 12개로, 처음 있었던 노드의 개수 = 6개의 두배 맞죠?

2. 간선을 추가할 때, Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)에서의 방향을 보면서 출발점의 3번노드와 도착점의 1번노드를 연결해준다. 

그리고 이제 간선을 2N개 추가해볼게요. 

먼저, 같은 노드들끼리 이어줍니다. 

그리고, 가장 중요한!!Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)에서의 방향을 보면서 출발점의 3번노드와 도착점의 1번노드를 연결해준다!!입니다. 

흠.. 자, 예를 하나 들어볼까요? 지금 Y에서 U로 간선이 하나 있네요.

출발점은 Y고, U가 도착점이라고 할 수 있어요.

그럼 "출발점의 3번노드와 도착점의 1번노드를 연결하라"고 했으니

연결해줘볼까요?

짠!! 이렇게요 ㅎㅎ

다른 노드들도 다 이어줘볼게요.

짠ㅎㅎ

자..이제 우리는

Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)의 인풋 -> Transformation Function ->  Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)의 인풋으로 만든 작업을 한거에요. 이 작업은 Polynomial Time에 할 수 있답니다.

그럼 이제, 우리가 만든 Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)을 푼 결과로, 

Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)의 모든 인스턴스에 정확한 대답을 할 수 있다면 Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)로 Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)을 푼 것이니, Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)은 NP-Hard가 되겠네요.

Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)이 Yes면 Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)도 Yes.

Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)이 No면 Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)도 No인 것을 원하는 거죠. 

1. Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)이 Yes면 Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)도 Yes증명 == Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)이 있으면 Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)도 있다.

그럼 우리가 아까 만든 Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클) 그래프에서 만약 헤밀토니안 사이클이 있다고 가정해봅시다. 

Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)그래프는 정말 "무향" 이므로 방향이 2가지라고 할 수 있죠? 한 버텍스에서 3->2->1 순이었다면, 다른버텍스도 반드시 3->2->1 순일 것이며,

1->2->3 순이었다면 다른버텍스도 반드시 1->2->3순일것입니다. 그러니 만약 Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)그래프에서 Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)이 존재한다면, 자연스럽게 Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)그래프에서 Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)이 존재할 수 밖에 없는 것이죠.

2. Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)이 No면 Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)도 No증명 == Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)이 없으면 Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)도 없다. 

여러분 "대우" 아시나요? A이면 B이다의 대우는 B가 아니면 A가 아니다죠?

Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)이 없으면 Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)도 없다. 의 대우는 Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)이 있으면, Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)도 있다.죠?

이 대우를 증명하면, 대우를 하기 전 명제도 자연스럽게 참이 됩니다. 

 Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)이 있었다면, 그 간선을 따라서 우리가 만들었던  Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)그래프에서 3->1로 가게 됩니다. 반드시.

그 노드들끼리는 반드시 갈 수 있습니다. 너무나도 자명하죠?

즉,  Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)이 있으면 Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)이 반드시 존재합니다. 

우리는 대우가 참임을 증명했으니, Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)이 없으면 Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)도 없다. 도 자연스럽게 참이 됩니다. 

위 증명과정을 보면,  Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)과 Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)은 서로 필요충분조건임을 알 수 있네요.

즉 우리는, Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)을 푼 결과로, 

Directed Hamiltonian Cycle(유향 헤밀토니안 사이클)의 모든 인스턴스에 정확한 대답을 했으니!!

Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)이 NP-Hard임을 증명했습니다.

1과 2에 따라, Undirected Hamiltonian Cycle은 NP-Complete입니다.

어떠셨나요? ㅎㅎ 조금 어려우셨죠 ㅠㅠㅠㅠ (이건..TSP보단 재미없음)

아무튼!! Undirected Hamiltonian Cycle(무향 헤밀토니안 사이클)이 NP-Complete라는 증명이 다 영어라 ㅠㅠㅠ 한글로 증명을 찾는분들에게 도움이 되었으면 좋겠네요💕