Теорема Дирака — различия между версиями
м |
|||
| Строка 1: | Строка 1: | ||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
| − | Если <math>\ n > 3</math> и <math>deg\ v \ge n/2</math> для любой вершины <math>\ v</math> графа '''G''', то '''G''' - гамильтонов граф. | + | Если <math>\ n > 3</math> и <math>deg\ v \ge n/2</math> для любой вершины <math>\ v</math> неориентированного графа '''G''', то '''G''' - гамильтонов граф. |
|proof= | |proof= | ||
По теореме Хватала: '''для''' <math>\forall k</math> '''верна импликация''' <math>d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k</math> | По теореме Хватала: '''для''' <math>\forall k</math> '''верна импликация''' <math>d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k</math> | ||
}} | }} | ||
Версия 00:09, 12 октября 2010
| Теорема: |
Если и для любой вершины неориентированного графа G, то G - гамильтонов граф. |
| Доказательство: |
| По теореме Хватала: для верна импликация |
