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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 9: Строка 9:
 
|author = В. Татт
 
|author = В. Татт
 
|about = о существовании регулярного графа заданного размера с заданным обхватом
 
|about = о существовании регулярного графа заданного размера с заданным обхватом
|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>{{---}}[[Основные определения теории графов#defRegularGraph | регулярный граф]] <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>-[[Основные определения теории графов#defRegularGraph | регулярный граф]] <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 > g</tex> очевидно, что <tex>G_{set}(g, n, k) \neq \emptyset</tex>: например, этому множеству принадлежит граф, состоящий из простого цикла на <tex>g</tex> вершинах и <tex>n - g</tex> изолированных вершин.  
 
Пусть <tex>G_{set}(g, n, k)</tex> {{---}} семейство всех графов с <tex>n</tex> вершинами, обхватом <tex>g</tex> и максимальной степенью вершин не более <tex>k</tex>. При <tex>n > g</tex> очевидно, что <tex>G_{set}(g, n, k) \neq \emptyset</tex>: например, этому множеству принадлежит граф, состоящий из простого цикла на <tex>g</tex> вершинах и <tex>n - g</tex> изолированных вершин.  
Строка 50: Строка 50:
 
<center> <tex> dist_{<k}(G') \geqslant dist_{G'}(y, u) > dist_G(y, x) dist_{<k}(G) </tex> </center>
 
<center> <tex> dist_{<k}(G') \geqslant dist_{G'}(y, u) > dist_G(y, x) dist_{<k}(G) </tex> </center>
  
Получили противоречие с принципом выбора графа <tex>G</tex>, что доказывает, что <tex>G</tex> {{---}} <tex>k</tex>{{---}}регулярный.
+
Получили противоречие с принципом выбора графа <tex>G</tex>, что доказывает, что <tex>G</tex> {{---}} <tex>k</tex>-регулярный.
  
 
}}
 
}}
Строка 60: Строка 60:
 
* Карпов В. Д. - Теория графов, стр 108
 
* Карпов В. Д. - Теория графов, стр 108
  
[[Категория: Дискретная математика]]
+
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория графов]]
+
[[Категория: Обходы графов]]

Версия 21:05, 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 \gt 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].
    1. [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