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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 1: Строка 1:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Если <math>\ n > 3</math> и <math>deg\ v \ge n/2</math>  для любой вершины <math>\ v</math> графа  '''G''', то  '''G''' - гамильтонов граф.
+
Если <math>\ n > 3</math> и <math>deg\ v \ge n/2</math>  для любой вершины <math>\ v</math> неориентированного графа  '''G''', то  '''G''' - гамильтонов граф.
  
 
|proof=
 
|proof=
 
По теореме Хватала: '''для''' <math>\forall k</math> '''верна импликация''' <math>d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k</math>  
 
По теореме Хватала: '''для''' <math>\forall k</math> '''верна импликация''' <math>d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k</math>  
 
}}
 
}}

Версия 00:09, 12 октября 2010

Теорема:
Если [math]\ n \gt 3[/math] и [math]deg\ v \ge n/2[/math] для любой вершины [math]\ v[/math] неориентированного графа G, то G - гамильтонов граф.
Доказательство:
[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]