6. Наследственные свойства графов. (1176847)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Лекция 6. Наследственные свойства графов.Наибольшее число ребер в графах снаследственным свойством. Наибольшее числоребер в планарных графах. Наибольшее числоребер в графах без полного подграфа сn вершинами.Лектор — Селезнева Светлана Николаевнаselezn@cs.msu.suфакультет ВМК МГУ имени М.В. ЛомоносоваЛекции на сайте http://mk.cs.msu.ruНаследственные свойстваПланарные графыГрафы без треугольниковТеорема ТуранаЗадачиНаследственное свойство графаСвойство 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 | ≤Наследственные свойстваПланарные графыГрафы без треугольниковТеорема ТуранаЗадачиПланарный графГраф G = (V , E ) называется планарным, если его можно такнарисовать на плоскости, что каждой вершине v ∈ Vсоответствует точка плоскости, причем разным вершинам —разные точки, а каждому ребру (v , w ) ∈ E — линия,соединяющая точки, соответствующие вершинам v , w , и непроходящая через точки, соответствующие другим вершинам,кроме того, линии, соответствующие различным ребрам, непересекаются за исключением своих концов.Такое изображение планарного графа называется егоукладкой на плоскости.Области плоскости, определяемые укладкой планарного графа,называются гранями, неограниченная область — внешнейгранью.Наследственные свойстваПланарные графыГрафы без треугольниковТеорема ТуранаФормула ЭйлераТеорема 2 (формула Эйлера для планарных графов).Если G = (V , E ) — связный планарный граф с p вершинамии q ребрами, то для для каждой его укладки на плоскостиверно равенство p − q + r = 2, где r — число граней в этойукладке.Доказательство: индукция по q при заданном p.Базис индукции: если q = p − 1, то G — дерево.Каждое дерево — планарный граф с одной гранью, поэтомуформула верна.ЗадачиНаследственные свойстваПланарные графыГрафы без треугольниковТеорема ТуранаЗадачиФормула ЭйлераДоказательство.Индуктивный переход: пусть в графе G всего q ≥ p ребер.Тогда в графе G найдется хотя бы один цикл, пусть e — реброиз какого-то его цикла.Граф G 0 = G − e — связный и планарный с p вершинами и(q − 1) ребрами, и его укладка на плоскости содержит(r − 1) граней.Для графа G 0 верно предположение индукции, т.е.p − (q − 1) + (r − 1) = 2, откуда p − q + r = 2.Наследственные свойстваПланарные графыГрафы без треугольниковТеорема ТуранаЗадачиЧисло ребер в планарных графахТеорема 3.

Наибольшее число ребер в планарном графе (безпетель и кратных ребер) с p, p ≥ 3, вершинами равно 3p − 6.Доказательство. Можно рассматривать двусвязные графы.1. Пусть G = (V , E ) — двусвязный планарный граф сp вершинами и q ребрами.Рассмотрим укладку графа G на плоскости, и пусть qi — числоребер в цикле, ограничивающем i-ю грань в этой укладке,i = 1, . . .

, r .rPТогдаqi = 2q, т.к. каждое ребро разделяет две грани.i=1Наименьшее число ребер в цикле равно трем, поэтому 3r ≤ 2q,или r ≤ 32 q.По формуле Эйлера r = q − p + 2, откуда q ≤ 3p − 6.Наследственные свойстваПланарные графыГрафы без треугольниковТеорема ТуранаЗадачиЧисло ребер в планарных графахДоказательство.2. Построим графы, на которых достигается эта оценка.Если p = 3, то Gp = K3 .Пусть уже построен связный планарный граф Gp с pвершинами и 3p − 6 ребрами, каждая грань которогоограничена треугольником.Тогда граф Gp+1 получается из Gp добавлением новойвершины внутри какой-то грани и ребер, соединяющих этувершину с тремя вершинами этой грани.Наследственные свойстваПланарные графыГрафы без треугольниковТеорема ТуранаЧисло граней в планарных графахСледствие 3.1. Наибольшее число граней в укладкепланарного графа (без петель и кратных ребер) с p, p ≥ 3,вершинами равно 2p − 4.ЗадачиНаследственные свойстваПланарные графыГрафы без треугольниковТеорема ТуранаГрафы без полных подграфов KnОтсутствие в графах подграфа Kn — наследственное свойство.Обозначение: ex(p, Kn ) — наибольшее число ребер в графахс p вершинами, не содержащих подграф Kn .ЗадачиНаследственные свойстваПланарные графыГрафы без треугольниковТеорема ТуранаЗадачиЧисло ребер в графах без треугольниковТеорема 4.

Справедливо равенство 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 — без треугольников, поэтому вершины w1 и w2 немогут быть одновременно смежны c какой-то вершиной u ∈ V 0 ,откуда (dG (w1 ) − 1) + (dG (w2 ) − 1) ≤ p.Следовательно,|E | ≤ s 2 + 2s + 1 = (s + 1)2 .2.

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

При 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 не содержит подграфов Kn , поэтому вершиныw1 , . . .

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций