Теорема Дирака — различия между версиями
Kirelagin (обсуждение | вклад) (пояснение) |
|||
| Строка 3: | Строка 3: | ||
Если <tex>n > 3</tex> и <tex>deg\ v \ge n/2</tex> для любой вершины <tex>v</tex> неориентированного графа <tex>G</tex>, то <tex>G</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>, поскольку левая её часть всегда ложна. |
}} | }} | ||
== Источники == | == Источники == | ||
Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4''' | Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4''' | ||
Версия 19:44, 23 января 2011
| Теорема: |
Если и для любой вершины неориентированного графа , то - гамильтонов граф. |
| Доказательство: |
| По теореме Хватала: для верна импликация , поскольку левая её часть всегда ложна. |
Источники
Харари Ф. - Теория графов. ISBN 978-5-397-00622-4
