3. Графы. Экстремальная теория графов. Теорема Турана. Теорема Рамсея (Слайды к лекциям)

Лекция: Наследственные свойства графов.Экстремальные графы. Числа Рамсея.Лектор - доцент Селезнева Светлана Николаевнафакультет ВМК МГУ имени М.В. ЛомоносоваЛекции на сайте http://mk.cs.msu.suНаследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оНаследственное свойство графаСвойство P графов называется наследственным, если из еговыполнения для графа G следует его выполнение и для любогоподграфа графа G .Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оОценка числа реберОбозначение: P(n) — наибольшее число ребер в графах снаследственным свойством P, содержащих n вершин.Теорема 1.

Если P — наследственное свойство графов, тоnP(n) ≤ n−2· P(n − 1), n ≥ 3.Доказательство.Пусть G = (V , E ) — граф с наследственным свойством P,|V | ≥ 3, и V = {v1 , . . . , vn }.Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оОценка числа реберДоказательство.Рассмотрим графы Gi = G − vi = (Vi , Ei ): Vi = V \ {vi },|Ei | = |E | − dG (vi ), i = 1, .

. . , n.Графы Gi — также с наследственным свойством P, откуда|E | − dG (vi ) = |Ei | ≤ P(n − 1)для всех i = 1, . . . , n. Сложим все неравенства:n · |E | −nXi=1dG (vi ) ≤ n · P(n − 1).Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оОценка числа реберДоказательство.По формуле Эйлера для степеней вершинnPdG (vi ) = 2 · |E |,i=1откудаn· P(n − 1).n−2Неравенство выполняется для любого графа с наследственнымсвойством P, а значит, и для графа G = (V , E ) с |E | = P(n). |E | ≤Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оГрафы без полных подграфов KnОтсутствие в графах подграфа Kn — наследственное свойство.Обозначение: ex(p, Kn ) — наибольшее число ребер в графах с pвершинами, не содержащих подграф Kn .Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оЧисло ребер в графах без треугольниковТеорема 2.

Справедливо равенство ex(p, K3 ) = bp 2 /4c, p ≥ 1.Доказательство верхней оценки: индукция по числу вершин p.1. Сначала рассмотрим случай четного p.Базис индукции p = 2 верен.Индуктивный переход: пусть утверждение верно для всехграфов с p = 2s вершинами.Рассмотрим граф G = (V , E ) с p + 2 вершинами.Выберем в графе G две смежные вершины w1 , w2 ∈ V ирассмотрим граф G 0 = G − {w1 , w2 }.Граф G 0 = (V 0 , E 0 ) не содержит треугольников и для неговерно предположение индукции, т.е. |E 0 | ≤ s 2 .Тогда|E | ≤ s 2 + (dG (w1 ) − 1) + (dG (w2 ) − 1) + 1,где единица в сумме соответствует ребру (w1 , w2 ) ∈ E .Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оЧисло ребер в графах без треугольниковДоказательство верхней оценки.Граф G 0 — без треугольников, поэтому вершины w1 и w2 немогут быть смежны c какой-то вершиной u ∈ V 0 , откуда(dG (w1 ) − 1) + (dG (w2 ) − 1) ≤ p.Следовательно,|E | ≤ s 2 + 2s + 1 = (s + 1)2 .2.

Случай нечетного p доказывается аналогично.Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оЧисло ребер в графах без треугольниковДоказательство нижней оценки.Граф — двудольный, если его вершины можно разбить на двенепересекающиеся части (доли) так, что смежны тольковершины из разных частей.Двудольный граф с долями из n и m вершин, в которомсмежны любые две вершины из разных долей, называетсяполным двудольным графом Kn,m .Графы без треугольников Ks,s и Ks,(s+1) при четном p = 2s инечетном p = 2s + 1 соответственно показывает достижимостьверхней оценки.Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оЧисло ребер в графах без подграфов KnТеорема 3 (Турана).

При p ≥ 1, n ≥ 3 справедливо равенствоex(p, Kn ) =(n − 2)(p 2 − r 2 ) r (r − 1)+,2(n − 1)2где r — остаток от деления p на n − 1.Доказательство. Пусть p = (n − 1) · s + r , где 0 ≤ r ≤ n − 2.Доказательство верхней оценки проведем индукцией по s прификсированном r .Базис индукции: s = 0.В этом случае ex(r , Kn ) = r (r 2−1) , т.к. наибольшее число реберсодержит полный граф Kr .Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оЧисло ребер в графах без подграфов KnДоказательство верхней оценки.Индуктивный переход: пусть утверждение верно для всехграфов с p = (n − 1)s + r вершинами.Рассмотрим граф G = (V , E ) с p + (n − 1) = (n − 1)(s + 1) + rвершинами, в котором нет подграфов Kn и содержитсянаибольшее число ребер.Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оЧисло ребер в графах без подграфов KnДоказательство верхней оценки.В графе G обязательно найдется полный подграф с (n − 1)вершиной.В самом деле, пусть это не так, т.е.

для любых (n − 1) вершинграфа G хотя бы одно ребро с концами в этих вершинах в немне содержится.Тогда выберем (n − 1) вершину v1 , . . . , vn−1 ∈ V в графе G иесли e = (vi , vj ) ∈/ E , то добавим к графу G ребро e. Получимграф G1 = G + e.В графе G1 отсутствуют полные подграфы Kn , но ребербольше, чем в графе G , чего не может быть.Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оЧисло ребер в графах без подграфов KnДоказательство верхней оценки.Итак, в графе G найдется подграф H = Kn−1 и пустьw1 , . . . , wn−1 ∈ V — его вершины.Рассмотрим граф G 0 = G − {w1 , . .

. , wn−1 }.Граф G 0 = (V 0 , E 0 ) не содержит подграфов Kn и для него вернопредположение индукции, т.е.|E 0 | ≤(n − 2)(p 2 − r 2 ) r (r − 1)+.2(n − 1)2Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оЧисло ребер в графах без подграфов KnДоказательство верхней оценки.Получаем|E | ≤(n−2)(p 2 −r 2 )2(n−1)++ (n−1)(n−2)+2r (r −1)2 +n−1P(dG (wi ) − (n − 2)),i=1где число (n−1)(n−2)в сумме соответствует всем ребрам2подграфа H = Kn−1 .Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оЧисло ребер в графах без подграфов KnДоказательство верхней оценки.Граф G 0 не содержит подграфов Kn , поэтому вершиныw1 , . .

. , wn−1 не могут быть одновременно смежны c какой-товершиной u ∈ V 0 , откудаn−1X(dG (wi ) − (n − 2)) ≤ p(n − 2).i=1Следовательно,|E | ≤==(n−2)(p 2 −r 2 )+ r (r 2−1) + (n−1)(n−2)+ p(n − 2)22(n−1)(n−2)(p 2 −r 2 )+(n−1)2 (n−2)+2p(n−1)(n−2)+ r (r 2−1)2(n−1)22(n−2)((p+(n−1)) −r )+ r (r 2−1) .2(n−1)==Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оЧисло ребер в графах без подграфов KnДоказательство нижней оценки.Граф — k-дольный, k ≥ 2, если его вершины можно разбитьна k непересекающихся частей (долей) так, что смежны тольковершины из разных частей.Граф с долями из n1 , . .

. , nk вершин, в котором смежны любыедве вершины из разных долей, называется полнымk-дольным графом Kn1 ,...,nk .Графы Kp1 ,...,pn−1 при p = (n − 1)s + r , где 0 ≤ r ≤ n − 2,p1 = . . . = pr = (s + 1), pr +1 = . . . = pn−1 = s,показывают достижимость верхней оценки.Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оЧисла РамсеяГраф Ḡ = (V , Ē ) — дополнительный к графу G = (V , E ),если Ē состоит из всех тех ребер, которых нет в E , т.е.Ē = {(v , w ) | v , w ∈ V , v 6= w , (v , w ) ∈/ E }.Число R(m, n) — такое наименьшее число x, что для любогографа G с x вершинами:либо в G есть подграф Km ,либо в Ḡ есть подграф Kn .Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оЧисла РамсеяРаскраска ребер графа G = (V , E ) в два цвета —отображение ρ : E → {1, 2}.Число R(m, n) — такое наименьшее число x, что при любойраскраске ребер полного графа Kx в два цветалибо в нем найдется подграф Km с ребрами цвета 1,либо в нем найдется подграф Kn с ребрами цвета 2.Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оВерхняя оценка числа РамсеяВерны равенства: R(1, n) = R(m, 1) = 1 и R(m, n) = R(n, m).Теорема 4.

При m, n ≥ 2 справедливо неравенствоR(m, n) ≤ R(m − 1, n) + R(m, n − 1).Доказательство.Положим x = R(m − 1, n) + R(m, n − 1).Рассмотрим произвольную раскраску ребер полного графа Kx вцвета 1 и 2.Из произвольной вершины v графа Kx исходитлибо R(m − 1, n) ребер цвета 1,либо R(m, n − 1) ребер цвета 2.Случаи аналогичны, рассмотрим один из них.Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оВерхняя оценка числа РамсеяДоказательство.1. Пусть из вершины v графа Kx исходит R(m − 1, n) реберцвета 1.Положим V — множество из y = R(m − 1, n) концов этих ребер.Множество V вместе с соединяющими их ребрами образуютполный подграф Ky графа Kx .По определению числа R(m − 1, n) в графе Ky найдется либополный подграф Kn с ребрами цвета 2, либо полный подграфKm−1 с ребрами цвета 1.В первом случае этот полный подграф Kn с ребрами цвета 2есть и в графе Kx .Во втором случае добавим к этому полному подграфу Km−1вершину v и получим полный подграф Km с ребрами цвета 1 вграфе Kx .Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оВерхняя оценка числа РамсеяСледствие 4.1.

При m, n ≥ 1 справедливо неравенствоm−1R(m, n) ≤ Cm+n−1.Доказательство: индукция по m.Базис индукции m = 1 верен.Индуктивный переход: по теореме получаемR(m − 1, n) ≤ R(m − 1, n) + R(m, n − 1) ≤m−2m−1m−1≤ Cm+n−2+ Cm+n−2= Cm+n−1.Наследственные свойства Графы без треугольников Теорема Турана Числа Рамсея Верхняя оценка Нижняя оНижняя оценка числа РамсеяТеорема 5 (Эрдеша). При k ≥ 2 справедливо неравенствоR(k, k) ≥ 2k/2 .Доказательство. Рассмотрим k ≥ 3, т.к.