해밀턴 경로: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 +분류:해밀턴 경로 |
|||
18번째 줄:
* <math>G</math>의 폐포는 해밀턴 그래프이다.
특히, 크기가 3 이상인 [[완전 그래프]]는 해밀턴 그래프이므로, 폐포가 완전 그래프인 그래프는 해밀턴 그래프이다. 즉, 다음과 같은 [[따름정리]]를 얻을 수 있다. 모든 유한 그래프 <math>G</math>에 대하여, 만약 <math>|V(G)|\ge3</math>라면 다음이 성립한다.
* ('''디랙의 정리''' {{llang|en|Dirac’s theorem}}) 만약 임의의 v에 대해 <math>\deg v\ge|V(G)|/2</math>라면 <math>G</math>는 해밀턴 그래프이다.
* ('''오레의 정리''' {{llang|en|Ore’s theorem}}) 만약 모든 인접하지 않은 꼭짓점 <math>u,v\in V(G)</math>에 대하여 <math>\deg u+\deg v\ge|V(G)|</math>라면, <math>G</math>는 해밀턴 그래프이다.
디랙의 정리는 디랙({{llang|en|G. A. Dirac}})이 1952년에 증명하였다. 오레의 정리는 [[외위스테인 오레]]가 1960년에 증명하였다.
| |||