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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 18 промежуточных версий 2 участников)
Строка 4: Строка 4:
 
}}
 
}}
  
 +
==Лемма о существовании вершины на заданном расстоянии==
 +
{{Лемма
 +
|statement= Пусть <tex> k, g \in \mathbb{N} </tex>, причём <tex> k \geqslant 3</tex>, <tex>G</tex>{{---}}граф, <tex>|V(G)| > \dfrac{k(k-1)^{g-1} - 2}{k - 2} </tex>, <tex>\forall v \in V(G) : d_G(v) \leqslant k;</tex> <tex> x, y \in V(G), d_G(x), d_G(y) \leqslant k - 1</tex>, тогда существует такая вершина <tex>z</tex>, что <tex>dist(x, z) \geqslant g - 1</tex> и <tex>dist(y, z) \geqslant g</tex>.
 +
|proof =
 +
[[Файл:Лемма к Татту.png|300px|thumb|left|Иллюстрация к теореме для <tex>k = 4</tex>. У вершины <tex>x</tex>(чёрной) не более <tex>k - 1 = 3</tex> соседей (синих вершин), у каждой из <tex>k - 1</tex> синих вершин не более <tex>k - 1</tex> нерассмотренных соседей (красных вершин), то есть красных вершин не более <tex>(k - 1)^2</tex>, и так далее]]
 +
Так как <tex>d_G(x), d_G(y) \leqslant k - 1 </tex>, а степени остальных вершин графа не более <tex>k</tex>, то на расстоянии не более <tex>g - 1</tex> от <tex>y</tex> находится не более чем <tex>1 + (k - 1) + \ldots + (k - 1)^{g - 1} = \sum\limits_{n=0}^{g - 1} (k - 1)^n = \dfrac{(k-1)^{g} - 1}{k - 2}</tex> вершин графа, а на расстоянии не более <tex>g - 2</tex> от <tex>x</tex> находится не более чем <tex>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}</tex> вершин. Так как <tex>\dfrac{(k-1)^{g - 1} - 1}{k - 2} + \dfrac{(k-1)^{g} - 1}{k - 2} = \dfrac{k(k-1)^{g-1} - 2}{k - 2}</tex>, а <tex> |V(G)| > \dfrac{k(k-1)^{g-1} - 2}{k - 2}</tex>, то  существует такая вершина <tex>z</tex>, что <tex>dist(x, z) \geqslant g - 1</tex> и <tex>dist(y, z) \geqslant g</tex>.
 +
}}
 +
 +
==Теорема==
  
 
{{Теорема
 
{{Теорема
 
|id = thMain.  
 
|id = thMain.  
 
|author = В. Татт
 
|author = В. Татт
|about = о существовании регулярного графа заданного размера с заданным обхватом
+
|statement = Пусть <tex> k, g, n \in \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>-регулярный граф <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</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>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>.
Строка 20: Строка 28:
 
  y</tex>).  
 
  y</tex>).  
  
1) Если <tex>dist_G(x, y) \geqslant g - 1</tex>, то соединим их ребром и получим граф <tex>G' = G \cup xy, G'\in G_{set}(g, n, k)</tex>, при этом <tex>|E(G')| > |E(G)|</tex> (так как в графе <tex>G'</tex> есть все те рёбра, которые есть в <tex>G</tex>, и ребро <tex>xy</tex>). Значит, граф <tex>G</tex> не может быть выбран из множества <tex>G_{set}(g, n, k)</tex>, так как у него не максимальное количество рёбер.
+
# [[Файл:Татт 1.png|300px|thumb|right|Расположение вершины <tex>z</tex> относительно вершин <tex>x</tex> и <tex>y</tex>]] Если <tex>dist_G(x, y) \geqslant g - 1</tex>, то соединим их ребром и получим граф <tex>G' = G \cup xy, G'\in G_{set}(g, n, k)</tex>, при этом <tex>|E(G')| > |E(G)|</tex> (так как в графе <tex>G'</tex> есть все те рёбра, которые есть в <tex>G</tex>, и ребро <tex>xy</tex>). Значит, граф <tex>G</tex> не может быть выбран из множества <tex>G_{set}(g, n, k)</tex>, так как у него не максимальное количество рёбер.
 
+
# Так <tex>d_G(x), d_G(y) \leqslant k - 1 </tex>, а степени остальных вершин графа не более <tex>k</tex>, то по лемме существует такая вершина <tex>z</tex>, что <tex>dist(x, z) \geqslant g - 1</tex> и <tex>dist(y, z) \geqslant g</tex>.  
2) Так <tex>d_G(x), d_G(y) \leqslant k - 1 </tex>, а степени остальных вершин графа не более <tex>k</tex>, то на расстоянии не более <tex>g - 1</tex> от <tex>y</tex> находится не более чем <tex>1 + (k - 1) + \ldots + (k - 1)^{g - 1} = \sum\limits_{n=0}^{g - 1} (k - 1)^n = \dfrac{(k-1)^{g} - 1}{k - 2}</tex> вершин графа, а на расстоянии не более <tex>g - 2</tex> от <tex>x</tex> находится не более чем <tex>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}</tex> вершин. Так как <tex>\dfrac{(k-1)^{g - 1} - 1}{k - 2} + \dfrac{(k-1)^{g} - 1}{k - 2} = \dfrac{k(k-1)^{g-1} - 2}{k - 2}</tex>, а <tex> n > \dfrac{k(k-1)^{g-1} - 2}{k - 2}</tex>, то по условию теоремы существует такая вершина <tex>z</tex>, что <tex>dist(x, z) \geqslant g - 1</tex> и <tex>dist(y, z) \geqslant g</tex>.  
+
## <tex>d_G(z) < k</tex>. В таком случае, <tex>d_G(z) < k, d_G(y) < k, dist_G(y, z) \geqslant g</tex>, что невозможно, согласно пункту 1. В таком случае:
 
+
## <tex>d_G(z) = k \geqslant 3</tex>, следовательно, существует ребро <tex>zu \in E(G)</tex>, через которое проходят не все простые циклы длины <tex>g</tex> графа <tex>G</tex>, тогда <tex>g(G \setminus zu) = g(G) = g</tex>
Рассмотрим случай 2а) <tex>d_G(z) < k</tex>. В таком случае, <tex>d_G(z) < k, d_G(y) < k, dist_G(y, z) \geqslant g</tex>, что невозможно, согласно пункту 1. В таком случае:
 
  
2б) <tex>d_G(z) = k \geqslant 3</tex>, следовательно, существует ребро <tex>zu \in E(G)</tex>, через которое проходят не все простые циклы длины <tex>g</tex> графа <tex>G</tex>, тогда <tex>g(G \setminus zu) = g(G) = g</tex>
+
[[Файл:Татт 2.png|300px|thumb|left|Получение графа <tex>G'</tex> из графа <tex>G</tex>]]
  
Пусть <tex>G' = G \setminus zu \cup zx</tex>. Из
+
Пусть <tex>G' = G \setminus zu \cup zx</tex>. Тогда из
  
<center> <tex> dist_G(y, u) \geqslant dist_G(y, z) - 1 \geqslant g - 1 > dist_G(x, y) = dist_{<k}(G) ~~~ \textbf{(1)} </tex>. </center>
+
<tex> dist_G(y, u) \geqslant dist_G(y, z) - 1 \geqslant g - 1 > dist_G(x, y) = dist_{<k}(G) ~~~ \textbf{(1)} </tex>.
  
Следует, что <tex>d_G(u) = k</tex>
+
следует, что <tex>d_G(u) = k</tex>.
  
<tex>g(G') = g(G) = g, |E(G')| = |e(G)| - 1 + 1 = |E(G)| </tex>
+
<tex>g(G') = g(G) = g, |E(G')| = |e(G)| - 1 + 1 = |E(G)| </tex>. Тогда
  
<center> <tex> d_{G'}(x) = d_G(x) + 1 \leqslant k, d_{G'}(u) = d_G(u) - 1 = k - 1 ~~~ \textbf{(2)} </tex>. </center>
+
<tex> d_{G'}(x) = d_G(x) + 1 \leqslant k, d_{G'}(u) = d_G(u) - 1 = k - 1 ~~~ \textbf{(2)} </tex>.
  
  
Строка 43: Строка 50:
 
Докажем, что <tex>dist_{G'}(y, u) > dist_{G}(y, x)</tex>. Действительно, рассмотрим путь <tex>P: y \leadsto u</tex>, который реализует расстояние между <tex>y</tex> и <tex>u</tex> в <tex>G'</tex>. Если <tex>P</tex> проходит только по рёбрам <tex>G</tex>, то, учитывая <tex>\textbf{(1)}</tex>, получаем
 
Докажем, что <tex>dist_{G'}(y, u) > dist_{G}(y, x)</tex>. Действительно, рассмотрим путь <tex>P: y \leadsto u</tex>, который реализует расстояние между <tex>y</tex> и <tex>u</tex> в <tex>G'</tex>. Если <tex>P</tex> проходит только по рёбрам <tex>G</tex>, то, учитывая <tex>\textbf{(1)}</tex>, получаем
  
<center> <tex> dist_{G'}(y, u) = dist_G(y, u) \geqslant g - 1 > dist_G(y, x)  </tex> </center>
+
<tex> dist_{G'}(y, u) = dist_G(y, u) \geqslant g - 1 > dist_G(y, x)  </tex>
  
 
Значит, <tex>P</tex> проходит по ребру <tex>zx</tex>. Следовательно, <tex>P</tex> содержит путь по рёбрам графа <tex>G</tex> от <tex>y</tex> до одной из вершин <tex>x</tex> или <tex>z</tex> и ребро <tex>xz</tex>. Тогда
 
Значит, <tex>P</tex> проходит по ребру <tex>zx</tex>. Следовательно, <tex>P</tex> содержит путь по рёбрам графа <tex>G</tex> от <tex>y</tex> до одной из вершин <tex>x</tex> или <tex>z</tex> и ребро <tex>xz</tex>. Тогда
  
<center> <tex> dist_{G'}(y, u) = \min(dist_G(y, x), dist_G(y, z)) + 1 > dist_G(y, x)  </tex>, </center>
+
<tex> dist_{G'}(y, u) = \min(dist_G(y, x), dist_G(y, z)) + 1 > dist_G(y, x)  </tex>,
  
 
так как <tex>dist_G(y, z) \geqslant g > dist_G(y, x)</tex>. Таким образом
 
так как <tex>dist_G(y, z) \geqslant g > dist_G(y, x)</tex>. Таким образом
  
<center> <tex> dist_{<k}(G') \geqslant dist_{G'}(y, u) > dist_G(y, x) dist_{<k}(G) </tex> </center>
+
<tex> dist_{<k}(G') \geqslant dist_{G'}(y, u) > dist_G(y, x) dist_{<k}(G) </tex>
  
Получили противоречие с принципом выбора графа <tex>G</tex>, что доказывает, что <tex>G</tex> {{---}} <tex>k</tex>{{---}}регулярный.
+
Получили противоречие с принципом выбора графа <tex>G</tex>, что доказывает, что <tex>G</tex> {{---}} <tex>k</tex>-регулярный.
  
 
}}
 
}}
 +
 +
==См. также==
 +
* [[Основные определения теории графов]]
  
 
==Источники информации==
 
==Источники информации==
 
* Карпов В. Д. - Теория графов, стр 108
 
* Карпов В. Д. - Теория графов, стр 108
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Обходы графов]]

Текущая версия на 19:27, 4 сентября 2022

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


Лемма о существовании вершины на заданном расстоянии

Лемма:
Пусть [math] k, g \in \mathbb{N} [/math], причём [math] k \geqslant 3[/math], [math]G[/math]—граф, [math]|V(G)| \gt \dfrac{k(k-1)^{g-1} - 2}{k - 2} [/math], [math]\forall v \in V(G) : d_G(v) \leqslant k;[/math] [math] x, y \in V(G), d_G(x), d_G(y) \leqslant k - 1[/math], тогда существует такая вершина [math]z[/math], что [math]dist(x, z) \geqslant g - 1[/math] и [math]dist(y, z) \geqslant g[/math].
Доказательство:
[math]\triangleright[/math]
Иллюстрация к теореме для [math]k = 4[/math]. У вершины [math]x[/math](чёрной) не более [math]k - 1 = 3[/math] соседей (синих вершин), у каждой из [math]k - 1[/math] синих вершин не более [math]k - 1[/math] нерассмотренных соседей (красных вершин), то есть красных вершин не более [math](k - 1)^2[/math], и так далее
Так как [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] |V(G)| \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].
[math]\triangleleft[/math]

Теорема

Теорема (В. Татт):
Пусть [math] k, g, n \in \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]z[/math] относительно вершин [math]x[/math] и [math]y[/math]
    Если [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]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'[/math] из графа [math]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