해밀턴 경로 문제

그래프 이론의 수학 분야에서 해밀턴 경로 문제와 해밀턴 순환 문제는 주어진 그래프에 해밀턴 경로(각 정점을 정확히 한 번 방문하는 무방향 또는 유향 그래프의 경로) 또는 해밀턴 순환이 존재하는지를 결정하는 문제이다.두 문제 모두 NP-완전.^[1]

해밀턴 사이클 문제는 여행 세일즈맨 문제의 특별한 경우로, 두 도시 사이의 거리를 인접한 경우 1개로 설정하고, 총 주행 거리가 n개인지 확인합니다(그렇다면 경로는 해밀턴 회로이며, 해밀턴 회로가 없는 경우 최단 경로 wi).더 길어집니다).

경로 문제와 사이클 문제 간의 감소

해밀턴 경로와 해밀턴 사이클을 찾는 문제는 다음과 같이 연관될 수 있습니다.

한편, 그래프 G의 해밀턴 패스 문제는 새로운 범용 정점 x를 더해 G의 모든 정점에 x를 접속함으로써 G로부터 얻은 그래프 H의 해밀턴 사이클 문제와 관련지을 수 있다.따라서, 해밀턴 경로를 찾는 것은 해밀턴 주기를 찾는 것보다 훨씬 느릴 수 없습니다(최악의 경우, 정점 수의 함수).
다른 방향에서는 그래프 G의 해밀턴 사이클 문제는 G의 정점 v와 v'의 근방을 v'와 같은 근방을 주는 v의 절단 복사인 단자(1도)의 정점 s 및 t를 각각 더한 그래프 H의 해밀턴 패스 문제와 동등하다. $s-v-x-\cdots -y-v'-t$ s - $s-v-x-\cdots -y-v'-t$ - $s-v-x-\cdots -y-v'-t$ - $s-v-x-\cdots -y-v'-t$ - $s-v-x-\cdots -y-v'-t$ - $s-v-x-\cdots -y-v'-t$ $s-v-x-\cdots -y-v'-t$ - $s-v-x-\cdots -y-v'-t$ { $display$ style s - v - x - \ $cdots$ - y - $t }$ 를 $s-v-x-\cdots -y-v'-t$ 통과하는 $v-x-\cdots -y(-v)$ ^[2]H의 해밀턴 경로는 v $v-x-\cdots -y(-v)$ - $v-x-\cdots -y(-v)$ - $v-x-\cdots -y(-v)$ - $v-x-\cdots -y(-v)$ ( - $)$ 를 $v-x-\cdots -y(-v)$ 하는 G의 해밀턴 사이클에 해당합니다.

알고리즘

주어진 n-vertex 그래프(및 완전한 그래프)에는 해밀턴 경로일 수 있는 n!개의 정점 시퀀스가 있기 때문에 가능한 모든 시퀀스를 테스트하는 브루트 포스 검색 알고리즘은 매우 느립니다.방향 그래프에서 해밀턴 순환을 찾기 위한 초기 정확한 알고리즘은 마르텔로의 ^[3]열거 알고리즘이었다.Frank^[4] Rubin의 검색 절차에서는 그래프의 가장자리를 경로에 있어야 하는 클래스, 경로에 있을 수 없는 클래스 및 미정의 세 가지 클래스로 나눕니다.검색이 진행됨에 따라 일련의 결정 규칙이 미정의 에지를 분류하고 검색을 중지할지 또는 계속할지를 결정합니다.이 알고리즘은 그래프를 개별적으로 해결할 수 있는 구성요소로 나눕니다.또, Bellman, Held, Karp의 동적 프로그래밍 알고리즘을 사용해, 시간 O(n2ⁿ)에² 있어서의 문제를 해결할 수 있다.이 방법에서는 S의 각 정점 집합 S와 S의 각 정점 v에 대해 S의 정점을 정확히 커버하고 v에서 끝나는 경로가 있는지 여부를 결정한다. S와 v의 각 선택에 대해 v가 (S - vw)에 대해 (S - vw)에 대한 경로가 존재하는 경우 및 그 정보에서 이미 조회할 수 있는 (S - vw)에 대한 경로가 존재하는 경우에만 (S, v)에 대한 경로가 존재한다.동적 ^[5]^[6]프로그램

Andreas Björklund는 특정 행렬 결정 인자를 계산하여 해결할 수 있는 해밀턴 사이클의 수를 단순한 계수 문제로 줄이기 위해 포함-제외 원리를 사용하는 대체 접근법을 제공했다.이 방법을 사용하여, 그는 시간 O(1.657ⁿ)에서 몬테 카를로 알고리즘에 의해 임의의 n-vertex 그래프에서 해밀턴 사이클 문제를 해결하는 방법을 보여주었다. 초당 그래프의 경우 이 알고리즘은 시간 O(1.415ⁿ)^[7]로 더욱 개선될 수 있다.

최대 3도 그래프의 경우 신중하게 역추적 검색을 통해 시간 O(1.251)^[8]에서ⁿ 해밀턴 사이클을 찾을 수 있습니다.

해밀턴 경로 및 사이클은 SAT 솔버를 사용하여 찾을 수 있습니다.

기존의 컴퓨터에서는 해밀턴의 경로와 사이클 문제를 해결하기 어렵기 때문에, 그것들은 또한 컴퓨팅의 비전통적인 모델에서도 연구되어 왔습니다.예를 들어, 레너드 애들먼은 해밀턴 경로 문제가 DNA 컴퓨터를 사용하여 해결될 수 있다는 것을 보여주었다.화학 반응에 내재된 병렬성을 이용하여, 문제는 그래프의 꼭지점 수에서 선형인 여러 화학 반응 단계를 사용하여 해결될 수 있다. 그러나,^[9] 반응에 참여하기 위해서는 요인 수의 DNA 분자가 필요하다.

해밀턴 문제에 대한 광학 해법도 ^[10]제안되었다.광케이블과 빔 스플리터로 만든 그래프 형태의 구조를 만들어 이 문제를 해결하는 것이 아이디어다.이 접근법의 약점은 노드 수가 기하급수적으로 증가하는 필요한 에너지량입니다.

복잡성

해밀턴 사이클 또는 경로를 찾는 문제는 FNP에 있습니다. 유사한 결정 문제는 해밀턴 사이클 또는 경로가 존재하는지 테스트하는 것입니다.유도 및 비지향 해밀턴 사이클 문제는 Karp의 21개의 NP-완전 문제 중 2개였다.다음과 같은 특수한 종류의 그래프에서도 NP-완전 상태로 유지됩니다.

초당 그래프,^[11]
최대 ^[12]3도의 무방향 평면 그래프,
인디와 ^[13]아웃도(outdegree)가 최대 2개인 평면 그래프를 지향한다.
브릿지리스 무방향 평면 3정규 초당 그래프,
3-연결된 3-규칙 초당 그래프,^[14]
정사각형 ^[15]그리드 그래프의 하위 그래프,
정사각형 ^[16]그리드 그래프의 입방체 하위 그래프.

그러나 일부 특수 클래스의 그래프에서는 다항식 시간으로 문제를 해결할 수 있습니다.

4연결 평면 그래프는 항상 Tutte의 결과로 인해 Hamiltonian이며, 이러한 그래프에서 Hamiltonian cycle을 찾는 계산 태스크는 소위 Tutte 경로를 계산함으로써 선형^[17] 시간으로 수행될 수 있다.
Tutte는 모든 2연결 평면 그래프가 Tutte 경로를 포함함을 보여줌으로써 이 결과를 증명했다.Tutte 경로는 평면 그래프의 일반화에서 해밀턴 주기 및 긴 주기를 찾는 데 사용될 수 있는 2-연결 평면 ^[18]그래프에 대해서도 2차 시간으로 계산될 수 있다.

이 모든 조건을 종합하면, 3-연결된 3정규 초당 평면 그래프가 항상 해밀턴 사이클을 포함해야 하는지 여부는 열려 있으며, 이 경우 이러한 그래프로 제한된 문제가 NP-완전일 수 없다. Barnette의 추측을 참조한다.

모든 정점이 홀수 차수를 갖는 그래프에서, 핸드쉐이킹 보조법칙과 관련된 인수는 고정된 가장자리를 통과하는 해밀턴 주기의 수가 항상 짝수라는 것을 보여주므로, 만약 하나의 해밀턴 주기가 주어진다면, 두 번째 주기도 ^[19]존재해야 한다.그러나 이 두 번째 주기를 찾는 것은 쉬운 계산 작업이 아닌 것 같습니다.Papadimitriou는 이와 같은 ^[20]문제를 캡슐화하기 위해 복잡도 클래스 PPA를 정의했습니다.

레퍼런스

Wikimedia Commons의 해밀턴

^ Michael R. Garey and David S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 978-0-7167-1045-5 A1.3: GT37–39, 페이지 199–200.
^ 해밀턴 순환에서 해밀턴 경로로의 환원
^ Martello, Silvano (1983), "An Enumerative Algorithm for Finding Hamiltonian Circuits in a Directed Graph", ACM Transactions on Mathematical Software, 9 (1): 131–138, doi:10.1145/356022.356030
^ Rubin, Frank (1974), "A Search Procedure for Hamilton Paths and Circuits", Journal of the ACM, 21 (4): 576–80, doi:10.1145/321850.321854
^ 를 클릭합니다Bellman, R. (1962), "Dynamic programming treatment of the travelling salesman problem", Journal of the ACM, 9: 61–63, doi:10.1145/321105.321111.
^ 를 클릭합니다Held, M.; Karp, R. M. (1962), "A dynamic programming approach to sequencing problems" (PDF), J. SIAM, 10 (1): 196–210, doi:10.1137/0110015, hdl:10338.dmlcz/103900.
^ 를 클릭합니다Björklund, Andreas (2010), "Determinant sums for undirected Hamiltonicity", Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS '10), pp. 173–182, arXiv:1008.0541, doi:10.1109/FOCS.2010.24, ISBN 978-1-4244-8525-3.
^ 를 클릭합니다Iwama, Kazuo; Nakashima, Takuya (2007), "An improved exact algorithm for cubic graph TSP", Proc. 13th Annual International Conference on Computing and Combinatorics (COCOON 2007), Lecture Notes in Computer Science, vol. 4598, pp. 108–117, CiteSeerX 10.1.1.219.1672, doi:10.1007/978-3-540-73545-8_13, ISBN 978-3-540-73544-1.
^ 를 클릭합니다Adleman, Leonard (November 1994), "Molecular computation of solutions to combinatorial problems", Science, 266 (5187): 1021–1024, Bibcode:1994Sci...266.1021A, CiteSeerX 10.1.1.54.2565, doi:10.1126/science.7973651, JSTOR 2885489, PMID 7973651.
^ Mihai Oltean (2006). A light-based device for solving the Hamiltonian path problem. Unconventional Computing. Springer LNCS 4135. pp. 217–227. arXiv:0708.1496. doi:10.1007/11839132_18.
^ "Proof that the existence of a Hamilton Path in a bipartite graph is NP-complete". Computer Science Stack Exchange. Retrieved 2019-03-18.
^ 를 클릭합니다Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), "Some simplified NP-complete problems", Proc. 6th ACM Symposium on Theory of Computing (STOC '74), pp. 47–63, doi:10.1145/800119.803884.
^ 를 클릭합니다Plesńik, J. (1979), "The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two" (PDF), Information Processing Letters, 8 (4): 199–201, doi:10.1016/0020-0190(79)90023-1.
^ 를 클릭합니다Akiyama, Takanori; Nishizeki, Takao; Saito, Nobuji (1980–1981), "NP-completeness of the Hamiltonian cycle problem for bipartite graphs", Journal of Information Processing, 3 (2): 73–76, MR 0596313.
^ 를 클릭합니다Itai, Alon; Papadimitriou, Christos; Szwarcfiter, Jayme (1982), "Hamilton Paths in Grid Graphs", SIAM Journal on Computing, 4 (11): 676–686, CiteSeerX 10.1.1.383.1078, doi:10.1137/0211056.
^ 를 클릭합니다Buro, Michael (2000), "Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs" (PDF), Conference on Computers and Games, Lecture Notes in Computer Science, vol. 2063, pp. 250–261, CiteSeerX 10.1.1.40.9731, doi:10.1007/3-540-45579-5_17, ISBN 978-3-540-43080-3.
^ Chiba, Norishige; Nishizeki, Takao (1989), "The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs", Journal of Algorithms, 10 (2): 187–211, doi:10.1016/0196-6774(89)90012-6
^ Schmid, Andreas; Schmidt, Jens M. (2018), "Computing Tutte Paths", Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP'18), to appear.
^ 를 클릭합니다Thomason, A. G. (1978), "Hamiltonian cycles and uniquely edge colourable graphs", Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics, vol. 3, pp. 259–268, doi:10.1016/S0167-5060(08)70511-9, ISBN 9780720408430, MR 0499124.
^ 를 클릭합니다Papadimitriou, Christos H. (1994), "On the complexity of the parity argument and other inefficient proofs of existence", Journal of Computer and System Sciences, 48 (3): 498–532, CiteSeerX 10.1.1.321.7008, doi:10.1016/S0022-0000(05)80063-7, MR 1279412.

[1] Michael R. Garey and David S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 978-0-7167-1045-5 A1.3: GT37–39, 페이지 199–200.

[2] 해밀턴 순환에서 해밀턴 경로로의 환원

[3] Martello, Silvano (1983), "An Enumerative Algorithm for Finding Hamiltonian Circuits in a Directed Graph", ACM Transactions on Mathematical Software, 9 (1): 131–138, doi:10.1145/356022.356030

[4] Rubin, Frank (1974), "A Search Procedure for Hamilton Paths and Circuits", Journal of the ACM, 21 (4): 576–80, doi:10.1145/321850.321854

[5] 를 클릭합니다Bellman, R. (1962), "Dynamic programming treatment of the travelling salesman problem", Journal of the ACM, 9: 61–63, doi:10.1145/321105.321111.

[6] 를 클릭합니다Held, M.; Karp, R. M. (1962), "A dynamic programming approach to sequencing problems" (PDF), J. SIAM, 10 (1): 196–210, doi:10.1137/0110015, hdl:10338.dmlcz/103900.

[7] 를 클릭합니다Björklund, Andreas (2010), "Determinant sums for undirected Hamiltonicity", Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS '10), pp. 173–182, arXiv:1008.0541, doi:10.1109/FOCS.2010.24, ISBN 978-1-4244-8525-3.

[8] 를 클릭합니다Iwama, Kazuo; Nakashima, Takuya (2007), "An improved exact algorithm for cubic graph TSP", Proc. 13th Annual International Conference on Computing and Combinatorics (COCOON 2007), Lecture Notes in Computer Science, vol. 4598, pp. 108–117, CiteSeerX 10.1.1.219.1672, doi:10.1007/978-3-540-73545-8_13, ISBN 978-3-540-73544-1.

[9] 를 클릭합니다Adleman, Leonard (November 1994), "Molecular computation of solutions to combinatorial problems", Science, 266 (5187): 1021–1024, Bibcode:1994Sci...266.1021A, CiteSeerX 10.1.1.54.2565, doi:10.1126/science.7973651, JSTOR 2885489, PMID 7973651.

[oltean_hamiltonian-10] Mihai Oltean (2006). A light-based device for solving the Hamiltonian path problem. Unconventional Computing. Springer LNCS 4135. pp. 217–227. arXiv:0708.1496. doi:10.1007/11839132_18.

[11] "Proof that the existence of a Hamilton Path in a bipartite graph is NP-complete". Computer Science Stack Exchange. Retrieved 2019-03-18.

[12] 를 클릭합니다Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), "Some simplified NP-complete problems", Proc. 6th ACM Symposium on Theory of Computing (STOC '74), pp. 47–63, doi:10.1145/800119.803884.

[13] 를 클릭합니다Plesńik, J. (1979), "The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two" (PDF), Information Processing Letters, 8 (4): 199–201, doi:10.1016/0020-0190(79)90023-1.

[14] 를 클릭합니다Akiyama, Takanori; Nishizeki, Takao; Saito, Nobuji (1980–1981), "NP-completeness of the Hamiltonian cycle problem for bipartite graphs", Journal of Information Processing, 3 (2): 73–76, MR 0596313.

[15] 를 클릭합니다Itai, Alon; Papadimitriou, Christos; Szwarcfiter, Jayme (1982), "Hamilton Paths in Grid Graphs", SIAM Journal on Computing, 4 (11): 676–686, CiteSeerX 10.1.1.383.1078, doi:10.1137/0211056.

[16] 를 클릭합니다Buro, Michael (2000), "Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs" (PDF), Conference on Computers and Games, Lecture Notes in Computer Science, vol. 2063, pp. 250–261, CiteSeerX 10.1.1.40.9731, doi:10.1007/3-540-45579-5_17, ISBN 978-3-540-43080-3.

[17] Chiba, Norishige; Nishizeki, Takao (1989), "The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs", Journal of Algorithms, 10 (2): 187–211, doi:10.1016/0196-6774(89)90012-6

[18] Schmid, Andreas; Schmidt, Jens M. (2018), "Computing Tutte Paths", Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP'18), to appear.

[19] 를 클릭합니다Thomason, A. G. (1978), "Hamiltonian cycles and uniquely edge colourable graphs", Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics, vol. 3, pp. 259–268, doi:10.1016/S0167-5060(08)70511-9, ISBN 9780720408430, MR 0499124.

[20] 를 클릭합니다Papadimitriou, Christos H. (1994), "On the complexity of the parity argument and other inefficient proofs of existence", Journal of Computer and System Sciences, 48 (3): 498–532, CiteSeerX 10.1.1.321.7008, doi:10.1016/S0022-0000(05)80063-7, MR 1279412.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

Search

해밀턴 경로 문제

네임스페이스

더

목차

경로 문제와 사이클 문제 간의 감소

알고리즘

복잡성

레퍼런스