해밀턴 경로: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
→알고리즘: 봇: 인용 틀 변수 이름 수정 |
Osteologia (토론 | 기여) |
||
20번째 줄:
* ('''디랙의 정리''' {{llang|en|Dirac’s theorem}}) 만약 <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 x+\deg y\ge|V(G)|</math>라면, <math>G</math>는 해밀턴 그래프이다.
디랙의 정리는 디랙({{llang|en|G. A. Dirac}})이 1952년에 증명하였다. 오레의 정리는 [[외위스테인 오레
=== 알고리즘 ===
| |||