Теорема Дирака — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(пояснение)
Строка 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

Теорема:
Если [math]n \gt 3[/math] и [math]deg\ v \ge n/2[/math] для любой вершины [math]v[/math] неориентированного графа [math]G[/math], то [math]G[/math] - гамильтонов граф.
Доказательство:
[math]\triangleright[/math]
По теореме Хватала: для [math]\forall k[/math] верна импликация [math]d_k \le k \lt n/2 \Rightarrow d_{n-k} \ge n-k[/math], поскольку левая её часть всегда ложна.
[math]\triangleleft[/math]

Источники

Харари Ф. - Теория графов. ISBN 978-5-397-00622-4