해밀턴 경로

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
정십이면체의 모든 꼭지점을 지나는 해밀턴 회로

해밀턴 경로(영어: Hamiltonian path)는 어떤 그래프에서 모든 꼭지점을 단 한번만 지나는 경로를 의미한다. 또한, 해밀턴 회로, 해밀턴 사이클(Hamiltonian cycle)은 모든 꼭지점을 단 한번만 지나는 회로를 의미한다. 이 이름은 아일랜드수학자 윌리엄 로언 해밀턴의 이름을 따서 지어졌다.

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

관련 정리[편집]

디랙의 정리 (1952)[편집]

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

오레의 정리 (1960)[편집]

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

같이 보기[편집]