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