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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 1: Строка 1:
 
==Теорема Турана==
 
==Теорема Турана==
 
[[Файл:Turan example.png|200px|thumb|right|Пример графа Турана при <tex>n = 8, r = 4</tex>]]
 
[[Файл:Turan example.png|200px|thumb|right|Пример графа Турана при <tex>n = 8, r = 4</tex>]]
'''Теорема Ту́рана''' (англ. ''Turán's theorem'') {{---}} классическая теорема экстремальной теории графов. Она послужила образцом для большого количества подобных теорем, которые изучают некоторые глобальные параметры, такие как [[Раскраска графа| хроматическое число]], относительно присутствия тех или иных подструктур.
+
'''Теорема Ту́рана''' (англ. ''Turán's theorem'') {{---}} классическая теорема экстремальной теории графов.  
 +
Она послужила образцом для большого количества подобных теорем, которые изучают некоторые глобальные параметры, такие как [[Раскраска графа| хроматическое число]], относительно присутствия тех или иных подструктур.
  
 
Впервые задачу сформулировал Пал Туран в 1941 году.
 
Впервые задачу сформулировал Пал Туран в 1941 году.
Строка 16: Строка 17:
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Среди <tex>(r - 1)</tex>-дольных графов <tex>T^{r-1}(n)</tex> имеет максимальное количество ребер.
+
Если <tex>G</tex> {{---}} <tex>(r - 1)</tex>-дольный граф с максимальным количеством ребер, то <tex>G = T^{r-1}(n)</tex>.
 
|proof=
 
|proof=
Пусть есть существует максимальный <tex>(r - 1)</tex>-дольный граф, в котором есть две доли <tex>V_1</tex> и <tex>V_2</tex>, такие что <tex>|V_1| - |V_2| > 1</tex>. Но тогда перекинув одну вершину из <tex>V_1</tex> в <tex>V_2</tex>, количество ребер увеличится. Противоречие.
+
Докажем от противного. Пусть существует <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>V_1</tex> в <tex>V_2</tex> и количество ребер увеличится.
 +
Это противоречит предположению, что граф <tex>G_m</tex> максимален по числу ребер.  
 
}}
 
}}
 
{{Теорема
 
{{Теорема
Строка 33: Строка 39:
 
'''Шаг индукции:'''
 
'''Шаг индукции:'''
  
Пусть теперь <tex>n \ge r</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>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>|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>
Строка 40: Строка 49:
 
Равенство справа следует непосредственно из графа Турана <tex>T^{r-1}(n)</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>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>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 - 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>T^{r-1}(n)</tex> {{---}} единственный <tex>(r-1)</tex>-дольный граф с <tex>n</tex> вершинами и максимальными числом ребер, наше утверждение, что <tex>G = T^{r-1}(n)</tex>, следует из предположения об экстремальности <tex>G</tex>.
 
Так как по Лемме <tex>T^{r-1}(n)</tex> {{---}} единственный <tex>(r-1)</tex>-дольный граф с <tex>n</tex> вершинами и максимальными числом ребер, наше утверждение, что <tex>G = T^{r-1}(n)</tex>, следует из предположения об экстремальности <tex>G</tex>.
  
 
}}
 
}}
 
==См. также==
 
==См. также==
[[Раскраска графа]]
+
*[[Раскраска графа]]
 
==Источники информации==
 
==Источники информации==
 
''Дистель, Рейнград.'' Теория графов: Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. — 166-170 стр. — ISBN 5-86134-101-X.
 
''Дистель, Рейнград.'' Теория графов: Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. — 166-170 стр. — ISBN 5-86134-101-X.

Версия 13:13, 28 декабря 2017

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

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

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

Впервые задачу сформулировал Пал Туран в 1941 году.


Определение:
[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] вершинах, доли которого по мощности не отличаются более чем на 1. Если [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]V_1[/math] в [math]V_2[/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]T^{r-1}(n)[/math] — единственный [math](r-1)[/math]-дольный граф с [math]n[/math] вершинами и максимальными числом ребер, наше утверждение, что [math]G = T^{r-1}(n)[/math], следует из предположения об экстремальности [math]G[/math].
[math]\triangleleft[/math]

См. также

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

Дистель, Рейнград. Теория графов: Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. — 166-170 стр. — ISBN 5-86134-101-X.