해밀턴 회로
마스터의견: 0
정점이 \(N\)개, 간선이 \(M\)개인 단순 무방향 그래프가 주어진다. 해밀턴 회로(Hamiltonian cycle) 란 모든 정점을 정확히 한 번씩 지나 출발점으로 돌아오는 순환을 말한다. 즉 \(N\)개의 서로 다른 정점을 늘어놓은 순서 \(v_1, v_2, \dots, v_N\)에서, 연속한 두 정점 사이마다 간선이 있고 \(v_N\)과 \(v_1\) 사이에도 간선이 있어야 한다.
이 그래프의 해밀턴 회로를 하나 찾아 그 정점 순서를 출력하여라.
이 문제는 해밀턴 회로 판정 문제로, 대표적인 NP-완전 문제이다. 다항 시간 알고리즘은 알려져 있지 않으며, 존재한다면 \(P = NP\)가 증명된다. (참고로 모든 간선을 한 번씩 지나는 오일러 회로는 다항 시간에 풀리지만, 모든 정점을 한 번씩 지나는 이 해밀턴 회로 문제는 본질적으로 어렵다.) 인스턴스들은 평균 차수가 낮게(약 \(3\)~\(5\)) 유지되어, 심어 둔 회로가 단순한 그리디로는 드러나지 않는 어려운 영역에 놓여 있다. 모든 인스턴스에는 해밀턴 회로가 적어도 하나 존재함이 보장된다.
모든 정점을 한 번씩 지나는 어떤 유효한 회로든 정답으로 인정된다.
\(4 \le N \le 400\)
\(N \le M \le \dfrac{N(N-1)}{2}\)
그래프는 단순 무방향 그래프이며, 해밀턴 회로가 적어도 하나 존재한다.
첫 줄에 정점의 수 \(N\)과 간선의 수 \(M\)이 주어진다.
다음 \(M\)개의 줄에 각 간선의 두 끝점 \(u\ v\)가 주어진다(\(1 \le u, v \le N\), \(u \ne v\)). 그래프는 단순하다(자기 간선·중복 간선 없음).
해밀턴 회로를 이루는 \(N\)개의 정점을 방문 순서대로 한 줄에 공백으로 구분하여 출력한다. 출력한 순서대로 이동하며, 마지막 정점에서 첫 정점으로 돌아온다(이 간선도 존재해야 한다).
4 4
2 3
2 1
3 4
4 1
1 2 3 4정사각형 모양의 4-사이클. \(1 \to 2 \to 3 \to 4 \to 1\)이 해밀턴 회로이다.
5 6
3 4
1 5
2 1
2 3
3 1
4 5
1 2 3 4 55-사이클에 현 \(1\)-\(3\)이 하나 추가된 그래프. 바깥 사이클 \(1 \to 2 \to 3 \to 4 \to 5 \to 1\)이 해밀턴 회로이다.
riseoj 작성
출처 Original
평가 및 의견
해밀턴 회로
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
해밀턴 회로