3. Графы. Экстремальная теория графов. Теорема Турана. Теорема Рамсея (1268164)
Текст из файла
Лекция: Наследственные свойства графов.Экстремальные графы. Числа Рамсея.Лектор - доцент Селезнева Светлана Николаевнафакультет ВМК МГУ имени М.В. ЛомоносоваЛекции на сайте 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, т.к.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
