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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 11: Строка 11:
 
|statement = Пусть <tex> k, g, n \in </tex> <tex> \mathbb{N} </tex>, причём <tex> k, n \geqslant 3, n > \dfrac{k(k-1)^{g-1} - 2}{k - 2}, kn </tex> чётно. Тогда существует <tex>k</tex>-регулярный граф <tex>G</tex> c обхватом <tex>g(G) = g</tex> и количеством вершин <tex> |V| = n</tex>
 
|statement = Пусть <tex> k, g, n \in </tex> <tex> \mathbb{N} </tex>, причём <tex> k, n \geqslant 3, n > \dfrac{k(k-1)^{g-1} - 2}{k - 2}, kn </tex> чётно. Тогда существует <tex>k</tex>-регулярный граф <tex>G</tex> c обхватом <tex>g(G) = g</tex> и количеством вершин <tex> |V| = n</tex>
 
|proof = Доказательство:
 
|proof = Доказательство:
Пусть <tex>G_{set}(g, n, k)</tex> {{---}} семейство всех графов с <tex>n</tex> вершинами, обхватом <tex>g</tex> и максимальной степенью вершин не более <tex>k</tex>. При <tex>n</tex> > <tex>g</tex> очевидно, что <tex>G_{set}(g, n, k) \neq \emptyset</tex>: например, этому множеству принадлежит граф, состоящий из простого цикла на <tex>g</tex> вершинах и <tex>n - g</tex> изолированных вершин. Пусть <tex>v_{<k}(G)</tex> {{---}} количество вершин степени меньше <tex>k</tex>в графе <tex>G</tex>, а <tex>dist_{<k}(G)</tex> {{---}} максимальное из расстояний между парами вершин степени менее <tex>k</tex> в графе <tex>G</tex>. (при <tex>v_{<k}(G) < 2</tex>, положим <tex>dist_{<k}(G) = 0</tex>). Выберем в <tex>G_{set}(g, n, k)</tex> граф следующим образом: сначала выберем все графы с максимальным количеством рёбер, затем из них выберем графы с максимальным <tex>v_{<k}</tex>, и, наконец, из оставшихся выберем граф <tex>G</tex> c максимальным <tex>dist_{<k}(G)</tex>.
+
Пусть <tex>G_{set}(g, n, k)</tex> {{---}} семейство всех графов с <tex>n</tex> вершинами, обхватом <tex>g</tex> и максимальной степенью вершин не более <tex>k</tex>. При <tex>n</tex> > <tex>g</tex> очевидно, что <tex>G_{set}(g, n, k) \neq \emptyset</tex>: например, этому множеству принадлежит граф, состоящий из простого цикла на <tex>g</tex> вершинах и <tex>n - g</tex> изолированных вершин.  
 +
Пусть <tex>v_{<k}(G)</tex> {{---}} количество вершин степени меньше <tex>k</tex>в графе <tex>G</tex>, а <tex>dist_{<k}(G)</tex> {{---}} максимальное из расстояний между парами вершин степени менее <tex>k</tex> в графе <tex>G</tex>. (при <tex>v_{<k}(G) < 2</tex>, положим <tex>dist_{<k}(G) = 0</tex>). Выберем в <tex>G_{set}(g, n, k)</tex> граф следующим образом: сначала выберем все графы с максимальным количеством рёбер, затем из них выберем графы с максимальным <tex>v_{<k}</tex>, и, наконец, из оставшихся выберем граф <tex>G</tex> c максимальным <tex>dist_{<k}(G)</tex>.
  
 
Докажем, что <tex>G</tex> {{---}} регулярный граф степени <tex>k</tex>.
 
Докажем, что <tex>G</tex> {{---}} регулярный граф степени <tex>k</tex>.

Версия 21:44, 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]

Доказательство: Пусть [math]G_{set}(g, n, k)[/math] — семейство всех графов с [math]n[/math] вершинами, обхватом [math]g[/math] и максимальной степенью вершин не более [math]k[/math]. При [math]n[/math] > [math]g[/math] очевидно, что [math]G_{set}(g, n, k) \neq \emptyset[/math]: например, этому множеству принадлежит граф, состоящий из простого цикла на [math]g[/math] вершинах и [math]n - g[/math] изолированных вершин. Пусть [math]v_{\lt k}(G)[/math] — количество вершин степени меньше [math]k[/math]в графе [math]G[/math], а [math]dist_{\lt k}(G)[/math] — максимальное из расстояний между парами вершин степени менее [math]k[/math] в графе [math]G[/math]. (при [math]v_{\lt k}(G) \lt 2[/math], положим [math]dist_{\lt k}(G) = 0[/math]). Выберем в [math]G_{set}(g, n, k)[/math] граф следующим образом: сначала выберем все графы с максимальным количеством рёбер, затем из них выберем графы с максимальным [math]v_{\lt k}[/math], и, наконец, из оставшихся выберем граф [math]G[/math] c максимальным [math]dist_{\lt k}(G)[/math].

Докажем, что [math]G[/math] — регулярный граф степени [math]k[/math].
[math]\triangleleft[/math]