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

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

Версия 10:39, 16 ноября 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]k[/math]: пусть это будут вершины [math]x[/math] и [math]y[/math] (если вершина степени менее [math]k[/math] в графе всего одна, то [math]x = y[/math]).

1) Если [math]dist_G(x, y) \geqslant g - 1[/math], то соединим их ребром и получим граф [math]G' = G \cup xy, G'\in G_{set}(g, n, k)[/math], при этом [math]|E(G')| \gt |E(G)|[/math] (так как в графе [math]G'[/math] есть все те рёбра, которые есть в [math]G[/math], и ребро [math]xy[/math]). Значит, граф [math]G[/math] не может быть выбран из множества [math]G_{set}(g, n, k)[/math], так как у него не максимальное количество рёбер.

2) Так [math]d_G(x), d_G(y) \leqslant k - 1 [/math], а степени остальных вершин графа не более [math]k[/math], то на расстоянии не более [math]g - 1[/math] от [math]y[/math] находится не более чем [math]1 + (k - 1) + \ldots + (k - 1)^{g - 1} = \sum\limits_{n=0}^{g - 1} (k - 1)^n = \dfrac{(k-1)^{g} - 1}{k - 2}[/math] вершин графа, а на расстоянии не более [math]g - 2[/math] от [math]x[/math] находится не более чем [math]1 + (k - 1) + \ldots + (k - 1)^{g - 2} = \sum\limits_{n=0}^{g - 2} (k - 1)^n =\dfrac{(k-1)^{g - 1} - 1}{k - 2}[/math] вершин. Так как [math]\dfrac{(k-1)^{g - 1} - 1}{k - 2} + \dfrac{(k-1)^{g} - 1}{k - 2} = \dfrac{k(k-1)^{g-1} - 2}{k - 2}[/math], а [math] n \gt \dfrac{k(k-1)^{g-1} - 2}{k - 2}[/math], то по условию теоремы существует такая вершина [math]z[/math], что [math]dist(x, z) \geqslant g - 1[/math] и [math]dist(y, z) \geqslant g[/math].

Рассмотрим случай 2а) [math]d_G(z) \lt k[/math]. В таком случае, [math]d_G(z) \lt k, d_G(y) \lt k, dist_G(y, z) \geqslant g[/math], что невозможно, согласно пункту 1. В таком случае:

2б) [math]d_G(z) = k \geqslant 3[/math], следовательно, существует ребро [math]zu \in E(G)[/math], через которое проходят не все простые циклы длины [math]g[/math] графа [math]G[/math], тогда [math]g(G \setminus zu) = g(G) = g[/math]

Пусть [math]G' = G \setminus zu \cup zx[/math]. Из

[math] dist_G(y, u) \geqslant dist_G(y, z) - 1 \geqslant g - 1 \gt dist_G(x, y) = dist_{\lt k}(G) ~~~ \textbf{(1)} [/math].

Следует, что [math]d_G(u) = k[/math]

[math]g(G') = g(G) = g, |E(G')| = |e(G)| - 1 + 1 = |E(G)| [/math]

[math] d_{G'}(x) = d_G(x) + 1 \leqslant k, d_{G'}(u) = d_G(u) - 1 = k - 1 ~~~ \textbf{(2)} [/math].


Степени всех остальных вершин в [math]G[/math] и [math]G'[/math] совпадают. Тогда [math]G' \in G_{set}(g, n, k)[/math]. Из [math]\textbf{(2)}[/math] следует, что [math]v_{\lt k}(G') \geqslant v_{\lt k}(G)[/math]. Тогда ввиду выбора графа [math]G[/math] должно быть [math]v_{\lt k}(G') = v_{\lt k}(G)[/math], что возможно лишь при [math]d_{G'}(x) = k[/math] и [math]d_G(x) = k - 1[/math]. Так как [math]kn[/math] чётно, вершина [math]x[/math] не может быть единственной вершиной степени менее [math]k[/math] в графе [math]G[/math], поэтому [math]x \neq y[/math].

Докажем, что [math]dist_{G'}(y, u) \gt dist_{G}(y, x)[/math]. Действительно, рассмотрим путь [math]P: y \leadsto u[/math], который реализует расстояние между [math]y[/math] и [math]u[/math] в [math]G'[/math]. Если [math]P[/math] проходит только по рёбрам [math]G[/math], то, учитывая [math]\textbf{(1)}[/math], получаем

[math] dist_{G'}(y, u) = dist_G(y, u) \geqslant g - 1 \gt dist_G(y, x) [/math]

Значит, [math]P[/math] проходит по ребру [math]zx[/math]. Следовательно, [math]P[/math] содержит путь по рёбрам графа [math]G[/math] от [math]y[/math] до одной из вершин [math]x[/math] или [math]z[/math] и ребро [math]xz[/math]. Тогда

[math] dist_{G'}(y, u) = \min(dist_G(y, x), dist_G(y, z)) + 1 \gt dist_G(y, x) [/math],

так как [math]dist_G(y, z) \geqslant g \gt dist_G(y, x)[/math]. Таким образом

[math] dist_{\lt k}(G') \geqslant dist_{G'}(y, u) \gt dist_G(y, x) dist_{\lt k}(G) [/math]
Получили противоречие с принципом выбора графа [math]G[/math], что доказывает, что [math]G[/math][math]k[/math]—регулярный.
[math]\triangleleft[/math]

Источники информации

  • Карпов В. Д. - Теория графов, стр 108