Теорема Турана об экстремальном графе — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема Турана)
м (rollbackEdits.php mass rollback)
 
(не показано 19 промежуточных версий 4 участников)
Строка 1: Строка 1:
'''Теорема Ту́рана''' {{---}} классическая теорема экстремальной теории графов. Она послужила образцом для большого количества подобных теорем, которые изучают некоторые глобальные параметры, такие как [[Раскраска графа| хроматическое число]], относительно присутствия тех или иных подструктур.  
+
==Теорема Турана==
 +
[[Файл:Turan example.png|200px|thumb|right|Пример графа Турана при <tex>n = 8, r = 4</tex>]]
 +
'''Теорема Ту́рана''' (англ. ''Turán's theorem'') {{---}} классическая теорема экстремальной теории графов<ref>[https://ru.wikipedia.org/wiki/%D0%AD%D0%BA%D1%81%D1%82%D1%80%D0%B5%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2 Экстремальная теория графов]</ref>.
 +
Она послужила образцом для большого количества подобных теорем, которые изучают, как наличие тех или иных подструктур влияет на некоторые глобальные параметры ([[Раскраска графа|хроматическое число]]).
  
Впервые задачу сформулировал Пал Туран в 1941 году.
+
Впервые теорему сформулировал венгерский математик Пал Туран в <tex>1941</tex> году.
 +
 
 +
{{Определение
 +
|definition=
 +
<tex>K_n</tex> {{---}} полный граф на <tex>n</tex> вершинах.
 +
}}
 +
 
 +
{{Определение
 +
|definition=
 +
<tex>ex(n, K_r)</tex> {{---}} максимальное количество ребер, которое может иметь граф на <tex>n</tex> вершинах, не включая в себя <tex>K_r</tex> как подграф.
 +
}}
 +
 
 +
{{Определение
 +
|definition=
 +
'''Граф Турана'''  <tex>T^{r-1}(n)</tex> {{---}} полный <tex>(r - 1)</tex>-[[Двудольные графы|дольный]] граф на <tex>n > r-1</tex> вершинах, доли которого по мощности отличаются не более чем на <tex>1</tex>. Если количество вершин не превосходит количество долей (<tex>n \leqslant r - 1</tex>), то <tex>T^{r-1}(n) = K_n</tex>.
 +
}}
 +
 
 +
{{Определение
 +
|definition=
 +
<tex>t_{r-1}(n)</tex> {{---}} количество ребер в <tex>T^{r-1}(n)</tex>.
 +
}}
 +
 
 +
 
 +
{{Лемма
 +
|statement=
 +
Если <tex>G</tex> {{---}} <tex>(r - 1)</tex>-дольный граф с максимальным количеством ребер, то <tex>G = T^{r-1}(n)</tex>.
 +
|proof=
 +
Докажем от противного. Пусть существует <tex>(r - 1)</tex>-дольный граф с максимальным числом ребер, который не является графом Турана.
 +
Обозначим его <tex>G_m</tex>.
 +
Очевидно, что <tex>G_m</tex> является полным <tex>(r - 1)</tex>-дольным.
 +
Так как <tex>G_m \ne T^{r-1}(n) </tex>, то в <tex>G_m</tex> существуют доли <tex>V_1</tex> и <tex>V_2</tex>, что <tex>|V_1| - |V_2| > 1</tex>.
 +
Но тогда возьмем вершину <tex>a \in V_1</tex> и перекинем ее в <tex>V_2</tex>. Тогда количество вершин, которые не могут быть соседями <tex>a</tex> уменьшилось с размером ее доли. Остальной граф не изменился, поэтому общее количество ребер увеличилось.
 +
Это противоречит предположению, что граф <tex>G_m</tex> максимален по числу ребер.
 +
 
 +
Значит лемма доказана.
 +
}}
 +
{{Теорема
 +
|statement=
 +
Для всех натуральных чисел <tex>r</tex>, <tex>n</tex>, где <tex>r > 1</tex>, любой граф <tex>G \nsubseteq K_r</tex> с <tex>n</tex> вершинами и <tex>ex(n, K_r)</tex> ребрами есть <tex>T^{r-1}(n)</tex>.
 +
|proof=
 +
[[Файл:Turan theorem induction step.png|300px|thumb|left|Шаг индукции]]
 +
Применим индукцию по <tex>n</tex>.
 +
 
 +
'''База:'''
 +
 
 +
При <tex>n \leqslant r - 1</tex> имеем <tex>G = K_n = T^{r-1}(n)</tex>, что и утверждалось. База доказана.
 +
 
 +
'''Шаг индукции:'''
 +
 
 +
Пусть теперь <tex>n \geqslant r</tex>.
 +
Поскольку <tex>G</tex> реберно-максимален и не содержит подграфа <tex>K_r</tex>, то <tex>G</tex> содержит подграф <tex>K^{r-1}</tex>.
 +
Обозначим любой из них как <tex>K</tex>.
 +
Тогда по индукционному предположению <tex>G - K</tex> имеет не более <tex>t_{r-1}(n - r + 1)</tex> ребер, а любая вершина <tex>G - K</tex> имеет не более <tex>r - 2</tex> соседей в <tex>K.</tex>
 +
Следовательно мы можем оценить количество ребер в <tex>G</tex>:
 +
 
 +
<tex>|E(G)| \leqslant \underbrace{t_{r-1}(n - r + 1)}_{G-K} + \underbrace{(n - r + 1)(r - 2)}_{(G-K) \rightleftarrows (K)} + \underbrace{{r-1 \choose 2}}_{K} = t_{r-1}(n); (1)</tex>
 +
 
 +
Равенство справа следует непосредственно из графа Турана <tex>T^{r-1}(n)</tex>.
 +
 
 +
Поскольку <tex>G</tex> экстремален для <tex>K_r</tex>, то в <tex>(1)</tex> имеет место равенство.
 +
Таким образом, любая вершина из <tex>G - K</tex> имеет ровно <tex>r - 2</tex> соседа в <tex>K</tex> {{---}} точно так же, как и вершины <tex>x_1,\cdots, x_{r-1}</tex> из самого <tex>K</tex>.
 +
 
 +
При <tex>i = 1,\cdots, r-1</tex> пусть <tex>V_i = \{v \in V(G) \mid vx_i \not\in E(G)\}</tex> есть множество всех вершин <tex>G</tex>, чьи <tex>r - 2</tex> соседей в <tex>K</tex> отличны от <tex>x_i</tex>.
 +
Так как каждая вершина <tex>G - K</tex> имеет ровно <tex>r - 2</tex> соседа в <tex>K</tex>, то все <tex>V_i</tex> не зависимы.
 +
При этом они в объединении дают <tex>V(G)</tex> поскольку <tex>K_r \nsubseteq G</tex>.
 +
Следовательно, граф <tex>G</tex> является <tex>(r-1)</tex>-дольным.
 +
Тогда по лемме из предположения об экстремальности <tex>G</tex> следует, что <tex>G = T^{r-1}(n)</tex>.
 +
 
 +
}}
  
 
==См. также==
 
==См. также==
 +
*[[Раскраска графа]]
 +
*[[Двудольные графы]]
 +
==Примечания==
 +
<references />
 
==Источники информации==
 
==Источники информации==
* Книга по дискре
+
*''Дистель, Рейнград.'' Теория графов: Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. — 166-170 стр. — ISBN 5-86134-101-X.
 +
*[https://ru.wikipedia.org/wiki/%D0%AD%D0%BA%D1%81%D1%82%D1%80%D0%B5%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2 Экстремальная теория графов]
 +
 
 +
[[Категория:  Раскраски графов]]
 +
[[Категория: Алгоритмы и структуры данных]]

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

Теорема Турана

Пример графа Турана при [math]n = 8, r = 4[/math]

Теорема Ту́рана (англ. Turán's theorem) — классическая теорема экстремальной теории графов[1]. Она послужила образцом для большого количества подобных теорем, которые изучают, как наличие тех или иных подструктур влияет на некоторые глобальные параметры (хроматическое число).

Впервые теорему сформулировал венгерский математик Пал Туран в [math]1941[/math] году.


Определение:
[math]K_n[/math] — полный граф на [math]n[/math] вершинах.


Определение:
[math]ex(n, K_r)[/math] — максимальное количество ребер, которое может иметь граф на [math]n[/math] вершинах, не включая в себя [math]K_r[/math] как подграф.


Определение:
Граф Турана [math]T^{r-1}(n)[/math] — полный [math](r - 1)[/math]-дольный граф на [math]n \gt r-1[/math] вершинах, доли которого по мощности отличаются не более чем на [math]1[/math]. Если количество вершин не превосходит количество долей ([math]n \leqslant r - 1[/math]), то [math]T^{r-1}(n) = K_n[/math].


Определение:
[math]t_{r-1}(n)[/math] — количество ребер в [math]T^{r-1}(n)[/math].


Лемма:
Если [math]G[/math][math](r - 1)[/math]-дольный граф с максимальным количеством ребер, то [math]G = T^{r-1}(n)[/math].
Доказательство:
[math]\triangleright[/math]

Докажем от противного. Пусть существует [math](r - 1)[/math]-дольный граф с максимальным числом ребер, который не является графом Турана. Обозначим его [math]G_m[/math]. Очевидно, что [math]G_m[/math] является полным [math](r - 1)[/math]-дольным. Так как [math]G_m \ne T^{r-1}(n) [/math], то в [math]G_m[/math] существуют доли [math]V_1[/math] и [math]V_2[/math], что [math]|V_1| - |V_2| \gt 1[/math]. Но тогда возьмем вершину [math]a \in V_1[/math] и перекинем ее в [math]V_2[/math]. Тогда количество вершин, которые не могут быть соседями [math]a[/math] уменьшилось с размером ее доли. Остальной граф не изменился, поэтому общее количество ребер увеличилось. Это противоречит предположению, что граф [math]G_m[/math] максимален по числу ребер.

Значит лемма доказана.
[math]\triangleleft[/math]
Теорема:
Для всех натуральных чисел [math]r[/math], [math]n[/math], где [math]r \gt 1[/math], любой граф [math]G \nsubseteq K_r[/math] с [math]n[/math] вершинами и [math]ex(n, K_r)[/math] ребрами есть [math]T^{r-1}(n)[/math].
Доказательство:
[math]\triangleright[/math]
Шаг индукции

Применим индукцию по [math]n[/math].

База:

При [math]n \leqslant r - 1[/math] имеем [math]G = K_n = T^{r-1}(n)[/math], что и утверждалось. База доказана.

Шаг индукции:

Пусть теперь [math]n \geqslant r[/math]. Поскольку [math]G[/math] реберно-максимален и не содержит подграфа [math]K_r[/math], то [math]G[/math] содержит подграф [math]K^{r-1}[/math]. Обозначим любой из них как [math]K[/math]. Тогда по индукционному предположению [math]G - K[/math] имеет не более [math]t_{r-1}(n - r + 1)[/math] ребер, а любая вершина [math]G - K[/math] имеет не более [math]r - 2[/math] соседей в [math]K.[/math] Следовательно мы можем оценить количество ребер в [math]G[/math]:

[math]|E(G)| \leqslant \underbrace{t_{r-1}(n - r + 1)}_{G-K} + \underbrace{(n - r + 1)(r - 2)}_{(G-K) \rightleftarrows (K)} + \underbrace{{r-1 \choose 2}}_{K} = t_{r-1}(n); (1)[/math]

Равенство справа следует непосредственно из графа Турана [math]T^{r-1}(n)[/math].

Поскольку [math]G[/math] экстремален для [math]K_r[/math], то в [math](1)[/math] имеет место равенство. Таким образом, любая вершина из [math]G - K[/math] имеет ровно [math]r - 2[/math] соседа в [math]K[/math] — точно так же, как и вершины [math]x_1,\cdots, x_{r-1}[/math] из самого [math]K[/math].

При [math]i = 1,\cdots, r-1[/math] пусть [math]V_i = \{v \in V(G) \mid vx_i \not\in E(G)\}[/math] есть множество всех вершин [math]G[/math], чьи [math]r - 2[/math] соседей в [math]K[/math] отличны от [math]x_i[/math]. Так как каждая вершина [math]G - K[/math] имеет ровно [math]r - 2[/math] соседа в [math]K[/math], то все [math]V_i[/math] не зависимы. При этом они в объединении дают [math]V(G)[/math] поскольку [math]K_r \nsubseteq G[/math]. Следовательно, граф [math]G[/math] является [math](r-1)[/math]-дольным.

Тогда по лемме из предположения об экстремальности [math]G[/math] следует, что [math]G = T^{r-1}(n)[/math].
[math]\triangleleft[/math]

См. также

Примечания

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