해밀톤 경로
위키백과 ― 우리 모두의 백과사전.
수학의 한 분야인 그래프 이론에서 해밀톤 경로란 모든 꼭지점을 딱 한번씩 지나는 경로이다. 비슷하게 해밀톤 회로는 모든 꼭지점을 딱 한번씩 지나는 회로이다. 오일러 경로가 있는지 여부는 아주 쉽게 알수 있는 것과는 대조적으로, 어떤 그래프가 해밀톤 경로를 가지고 있느냐는 질문에 대답하는 문제는 NP-완전 문제이다.
해밀톤 경로와 회로에서 해밀톤이라는 이름은 아일랜드의 수학자였던 윌리엄 로완 해밀톤 경의 이름을 따서 지어졌다.
목차 |
[편집] 관련 정리
해밀톤 회로와 경로에 관해서는 아래 정리가 가장 널리 알려져있다. 물론 이 문제가 NP-완전인만큼, 아직 어떠한 수학자도 해밀톤 회로가 존재할 필요충분조건을 찾지는 못하였다.
[편집] 디렉의 정리 (1952)
꼭지점 n개인(n>2) 그래프의 각 꼭지점의 차수가 n/2이상이면 해밀톤 회로가 있다.
[편집] 오레의 정리 (1960)
꼭지점이 n개인(n>2) 그래프 G에서 모든 인접하지 않은 두 꼭지점 x,y에 대해 deg(x)+deg(y)≥ n이면 이 그래프 G는 해밀톤 회로를 갖는다.
