Теорема Дирака — различия между версиями
Kirelagin (обсуждение | вклад) (пояснение) |
|||
| Строка 1: | Строка 1: | ||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
| − | Если <tex>n | + | Если <tex>n \ge 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:26, 24 января 2011
| Теорема: |
Если и для любой вершины неориентированного графа , то - гамильтонов граф. |
| Доказательство: |
| По теореме Хватала: для верна импликация , поскольку левая её часть всегда ложна. |
Источники
Харари Ф. - Теория графов. ISBN 978-5-397-00622-4
