Теорема Татта о существовании регулярного графа заданного размера с заданным обхватом — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|id = defMain.  
 
|id = defMain.  
|definition = Обхват графа <tex>G</tex>(обозначается <tex>g(G)</tex>) {{---}} это длина наименьшего цикла в графе <tex>G</tex>
+
|definition = Обхват''(англ. girth)'' графа <tex>G</tex> (обозначается <tex>g(G)</tex>) {{---}} это длина наименьшего простого цикла в графе <tex>G</tex>
 
}}
 
}}
  

Версия 19:39, 14 ноября 2017

Определение:
Обхват(англ. girth) графа [math]G[/math] (обозначается [math]g(G)[/math]) — это длина наименьшего простого цикла в графе [math]G[/math]


Теорема (В. Татт, о существовании регулярного графа заданного размера с заданным обхватом):
Пусть [math] k, g, n \in [/math] [math] \mathbb{N} [/math], причём [math] k, n \geqslant 3, n \gt \dfrac{k(k-1)^{g-1} - 2}{k - 2}, kn [/math] чётно. Тогда существует [math]k[/math]-регулярный граф [math]G[/math] c обхватом [math]g(G) = g[/math] и количеством вершин [math] |V| = n[/math]
Доказательство:
[math]\triangleright[/math]
(coming soon)
[math]\triangleleft[/math]