ZeddiOS

안녕하세요! Zedd입니다 :)오늘은 UHC(Undirected Hamiltonian Cycle)는 NP-Complete인 것을 증명해볼려고 해요 XD Hamiltonian Cycle(이하 헤밀토니안 사이클)문제는 글에서 소개했었죠? 헤밀토니안 사이클이 뭔지 모르시는 분들은 읽고와주세요 :)이 글 역시 P, NP, NP-Hard, NP-Complete에 대한 개념이 없으면 전혀 이해를 하지 못하실거에요 :(P, NP : NP-Hard, NP-Complete : 그럼 시작할게요! Undirected Hamiltonian Cycle은 NP-Complete이다. 주어진 그래프에서 출발점과 종료점만 두 번 나타나는 것을 제외하고는 정점이 한 번씩만 나타나는 사이클을 해밀턴 사이클 (Hamiltonian cycl..