해밀턴 경로: 두 판 사이의 차이

'''해밀턴 경로'''({{llang|en|Hamiltonian path}})는 어떤 그래프에서 모든 [[꼭지점꼭짓점]]을 단 한번만 지나는 [[경로 (그래프 이론)|경로]]를 의미한다이다. 또한, '''해밀턴 회로''', '''해밀턴 사이클순환'''({{llang|en|Hamiltonian cycle}})은 모든 꼭지점을 단 한번만 지나는 [[회로순환 (그래프 이론)|순환]]를 의미한다이다. 이 이름은 [[아일랜드]]의 [[수학자]] [[윌리엄 로언 해밀턴]]의 이름을 따서 지어졌다.

어떤 그래프에서 해밀턴 경로가 존재하는지 여부를 묻는 문제는 [[NP-완전]] 문제에 속한다문제이다.

[[노드꼭짓점]]의 수가 n개인(n>2) 그래프의 각 노드의꼭짓점의 [[차수]]가 n/2이상이면 해밀턴 회로가 있다.

노드의꼭짓점의 수가 n개인(n>2) 그래프의 모든 인접하지 않은 두 노드꼭짓점 x,y에 대해 (x의 차수)+(y의 차수)≥n이면, 이 그래프는 해밀턴 회로를 갖는다.