Теорема Татта о существовании регулярного графа заданного размера с заданным обхватом — различия между версиями
(→Теорема) |
|||
(не показано 14 промежуточных версий этого же участника) | |||
Строка 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 = В. Татт | ||
− | + | |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 | + | |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> изолированных вершин. | ||
Строка 20: | Строка 28: | ||
y</tex>). | y</tex>). | ||
− | 1 | + | # [[Файл:Татт 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>. | |
− | + | ## <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.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>. Тогда из |
− | + | <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>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>. Тогда |
− | + | <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>, получаем | ||
− | + | <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>. Тогда | ||
− | + | <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>. Таким образом | ||
− | + | <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 | ||
+ | |||
+ | [[Категория: Алгоритмы и структуры данных]] | ||
+ | [[Категория: Обходы графов]] |
Версия 22:20, 29 ноября 2017
Определение: |
Обхват (англ. girth) графа | (обозначается ) — это длина наименьшего простого цикла в графе
Содержание
Лемма о существовании вершины на заданном расстоянии
Лемма: |
Пусть , причём , —граф, , , тогда существует такая вершина , что и . |
Доказательство: |
Так как , а степени остальных вершин графа не более , то на расстоянии не более от находится не более чем вершин графа, а на расстоянии не более от находится не более чем вершин. Так как , а , то существует такая вершина , что и . |
Теорема
Теорема (В. Татт): |
Пусть регулярный граф c обхватом и количеством вершин , причём чётно. Тогда существует - |
Доказательство: |
Пусть — семейство всех графов с вершинами, обхватом и максимальной степенью вершин не более . При очевидно, что : например, этому множеству принадлежит граф, состоящий из простого цикла на вершинах и изолированных вершин.Пусть — количество вершин степени меньше в графе , а — максимальное из расстояний между парами вершин степени менее в графе . (при , положим ). Выберем в граф следующим образом: сначала выберем все графы с максимальным количеством рёбер, затем из них выберем графы с максимальным , и, наконец, из оставшихся выберем граф c максимальным . Если таких графов несколько, выберем любой.Докажем, что — регулярный граф степени .Предположим, что это не так и рассмотрим пару его максимально удаленных вершин степени менее : пусть это будут вершины и (если вершина степени менее в графе всего одна, то ).
Пусть . Тогда из. следует, что .. Тогда .
Докажем, что . Действительно, рассмотрим путь , который реализует расстояние между и в . Если проходит только по рёбрам , то, учитывая , получаем
Значит, проходит по ребру . Следовательно, содержит путь по рёбрам графа от до одной из вершин или и ребро . Тогда, так как . Таким образомПолучили противоречие с принципом выбора графа , что доказывает, что — -регулярный. |
См. также
Источники информации
- Карпов В. Д. - Теория графов, стр 108