Теорема Дирака — различия между версиями
| Строка 5: | Строка 5: | ||
По [[Теорема Хватала|теореме Хватала]]: для <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> | ||
}} | }} | ||
| + | |||
| + | == Источники == | ||
| + | Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4''' | ||
Версия 06:02, 28 октября 2010
| Теорема: |
Если и для любой вершины неориентированного графа , то - гамильтонов граф. |
| Доказательство: |
| По теореме Хватала: для верна импликация |
Источники
Харари Ф. - Теория графов. ISBN 978-5-397-00622-4
