Лекции по Дискретным моделям, страница 2

Покажем, что при такой раскраске в графе G не окажется ребер, обаконца которых окрашены в один и тот же цвет. В самом деле, предположим противное:пусть (u, w) ∈ E и ρ(u) = ρ(w). Тогда рассмотрим в графе G замкнутый маршрут M :сначала цепь из u в v в дереве D, затем цепь из v в w в дереве D и, наконец, по ребру(w, u) в u. Длина этого маршрута нечетна, т.к. у длин цепей из u в v и из v в w в деревеD одинаковая четность. Значит, из указанного замкнутого маршрута M можно выделитьцикл нечетной длины. Противоречие.Теорема 3.2.

Для произвольного графа G = (V, E) верно χ(G) ≤ ∆(G) + 1.Доказательство. Доказательство проведем индукцией по числу вершин n = |V |.Базис индукции n = 1 верен. Индуктивный переход: пусть утверждение верно длявсех графов с n вершинами. Рассмотрим граф G = (V, E) с n + 1 вершинами. Пустьv ∈ V , и рассмотрим граф G0 = G − v. Для графа G0 верно предположение индукции, т.е.χ(G0 ) ≤ ∆(G0 ) + 1 ≤ ∆(G) + 1. Перенесем раскраску вершин графа G0 в χ(G0 ) цветов навершины графа G. При этом вершина v останется неокрашенной. Окрасим вершину v вцвет, который не встречается среди цветов вершин, смежных с ней.

Тогда χ(G) ≤ ∆(G)+1,т.к. вершина v смежна не более, чем с ∆(G) вершинами.Теорема 3.3. Если в графе G = (V, E) с ∆(G) ≥ 3 найдется вершина v ∈ V , для которойdG (v) < ∆(G), то χ(G) ≤ ∆(G).Доказательство. Доказательство проведем индукцией по числу вершин n = |V |. Базисиндукции верен. Индуктивный переход: пусть утверждение верно для всех графов с nвершинами. Рассмотрим граф G = (V, E) с n + 1 вершинами. Выберем v ∈ V с dG (v) <∆(G). Положим G0 = G − v.

Очевидно, что ∆(G0 ) ≤ ∆(G). Рассмотрим 2 случая.Случай 1. Если ∆(G0 ) ≥ 3 и в G0 найдется такая вершина u ∈ V \{v}, что dG (v) < ∆(G0 ),то для графа G0 верно предположение индукции, и χ(G0 ) ≤ ∆(G0 ). Перенесем раскраскувершин графа G0 в χ(G0 ) цветов на вершины графа G. При этом вершина v останетсянеокрашенной. Окрасим вершину v в цвет, который не встречается среди цветов вершин,смежных с ней. Тогда χ(G) ≤ ∆(G), т.к. вершина v смежна не более, чем с ∆(G) − 1вершинами.Случай 2.

Если ∆(G0 ) = 2 или в графе G0 для каждой вершины u ∈ V \ {v}, верноdG (v) = ∆(G0 ), то ∆(G0 ) ≤ ∆(G)−1. По предыдущей теореме раскрасим вершины графа G0в ∆(G0 )+1 цветов. Перенесем раскраску вершин графа G0 в χ(G0 ) цветов на вершины графаG. При этом вершина v останется неокрашенной. Окрасим вершину v в цвет, которыйне встречается среди цветов вершин, смежных с ней. Тогда χ(G) ≤ ∆(G), т.к. χ(G0 ) ≤∆(G0 ) + 1 ≤ ∆(G) и вершина v смежна не более, чем с ∆(G) − 1 вершинами.Теорема 3.4 (Брукса). Если граф G не является полным графом или циклом с нечетнойдлиной, то χ(G) ≤ ∆(G).54Наследственные свойства графов.

Экстремальные графы.Свойство P графов называется наследственным, если из его выполнения для графа G следует его выполнение и для любого подграфа графа G. Пусть P (n) обозначает наибольшеечисло ребер в графах с наследственным свойством P , содержащих n вершин.Теорема 4.1. Если P — наследственное свойство графов, то P (n) ≤n·P (n−1),n−2n ≥ 3.Доказательство. Пусть G = (V, E) — граф с наследственным свойством P , |V | ≥ 3, иV = {v1 , . . . , vn }. Тогда каждый из графов Gi = G − vi также с наследственным свойствомP . Если Gi = (Vi , Ei ), то|E| − dG (vi ) = |Ei | ≤ P (n − 1)для всех i = 1, . . .

, n. Сложим все неравенства:n · |E| −nXdG (vi ) ≤ n · P (n − 1).i=1По формуле Эйлера для степеней вершинnPdG (vi ) = 2 · |E|, откудаi=1|E| ≤n· P (n − 1).n−2Неравенство выполняется для любого графа с наследственным свойством P , а значит, идля графа G = (V, E) с |E| = P (n).Граф G = (V, E) называется планарным, если его можно нарисовать на плоскости безпересечений ребер, при этом вершинам соответствуют точки плоскости, а ребрам — линии,соединяющие соответствующие точки. Такое изображение планарного графа называетсяего укладкой на плоскости. Области плоскости, определяемые укладкой планарного графа, называются его гранями, неограниченная область называется внешней гранью.Теорема 4.2 (формула Эйлера для планарных графов).

Если G = (V, E) — связныйпланарный граф с p вершинами и q ребрами, то для для каждой его укладки на плоскостиверно равенство p − q + r = 2, где r — число граней в этой укладке.Доказательство. Доказательство проведем индукцией по q при заданном p. Базис индукции: если q = p − 1, то G — дерево. Каждое дерево — планарный граф с одной гранью,поэтому формула верна. Индуктивный переход: пусть в графе G q ≥ p ребер. Тогда в Gесть хотя бы один цикл, пусть e — ребро из какого-то его цикла. Граф G0 = G − e — связный и планарный с p вершинами и (q − 1) ребрами, и его укладка на плоскости содержит(r − 1) граней. Для графа G0 верно предположение индукции, т.е.

p − (q − 1) + (r − 1) = 2,откуда p − q + r = 2.Отметим, что планарность графов является наследственным свойством.Теорема 4.3. Наибольшее число ребер в связном планарном графе с p, p ≥ 3, вершинамиравно 3p − 6.6Доказательство. Пусть G = (V, E) — связный планарный граф с p вершинами и q ребрами. Рассмотрим укладку G на плоскости, и пусть qi — число ребер в цикле, ограничиваюrPщем i-ю грань в этой укладке, i = 1, . . . , r. Тогдаqi = 2q, т.к. каждое ребро разделяетi=1две грани. Наименьшее число ребер в цикле равно трем, поэтому 3r ≤ 2q, или r ≤ 32 q. Потеореме 4.2 получаем r = q − p + 2, откуда q ≤ 3p − 6.Эта оценка достигается на графах, которые можно построить индуктивно. При p = 3подходит граф Gp = K3 .

Пусть уже построен связный планарный граф Gp с p вершинамии 3p − 6 ребрами, каждая грань которого ограничена треугольником. Тогда граф Gp+1 получается из Gp добавлением новой вершины внутри какой-то грани и ребер, соединяющихэту вершину с тремя вершинами этой грани.Следствие 4.3.1. Наибольшее число граней в укладке связного планарного графа с p,p ≥ 3, вершинами равно 2p − 4.Пусть ex(p, Kn ) обозначает наибольшее число ребер в графах с p вершинами, не содержащих подграф Kn .

Отметим, что отсутствие в графах подграфа Kn является наследственным свойством.Теорема 4.4. Справедливо равенство ex(p, K3 ) = bp2 /4c, p ≥ 1.Доказательство. Доказательство верхней оценки проведем индукцией по числу вершинp. Сначала рассмотрим случай четного p. Базис индукции p = 2 верен. Индуктивныйпереход: пусть утверждение верно для всех графов с p = 2s вершинами.

Рассмотрим графG = (V, E) с p + 2 вершинами. Выберем в графе G две смежные вершины v, w ∈ V ирассмотрим граф G0 = G − {v, w}. Граф G0 = (V 0 , E 0 ) не содержит треугольников и длянего верно предположение индукции, т.е. |E 0 | ≤ s2 . Тогда|E| ≤ s2 + (dG (v) − 1) + (dG (w) − 1) + 1,где единица в сумме соответствует ребру (v, w) ∈ E.Граф G0 — без треугольников, поэтому вершины v и w не могут быть смежны c какой-товершиной u ∈ V 0 , откуда (dG (v) − 1) + (dG (w) − 1) ≤ p. Следовательно,|E| ≤ s2 + 2s + 1 = (s + 1)2 .Случай нечетного p доказывается аналогично.Графы без треугольников Ks,s и Ks,(s+1) при четном p = 2s и нечетном p = 2s + 1соответственно показывает достижимость верхней оценки.Теорема 4.5 (Турана). При p ≥ 1, n ≥ 3 справедливо равенство ex(p, Kn ) =Cr2 , где r — остаток от деления p на n − 1.5(n−2)(p2 −r2 )2(n−1)+Числа Рамсея.Пусть R(m, n) такое наименьшее число x, что для любого графа G с x вершинами верно,что либо в G есть подграф Km , либо в Ḡ есть подграф Kn .

Раскраской ребер графаG = (V, E) в два цвета называется отображение ρ : E → {1, 2}. Число R(m, n) является7таким наименьшим числом x, что при любой раскраске ребер полного графа Kx в двацвета либо в нем найдется подграф Km с ребрами цвета 1, либо в нем найдется подграфKn с ребрами цвета 2. Отметим, что R(1, n) = R(m, 1) = 1 и R(m, n) = R(n, m).Теорема 5.1. При 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. Случаи аналогичны,рассмотрим первый из них. Пусть 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 .m−1Следствие 5.1.1. При m, n ≥ 1 справедливо неравенство R(m, n) ≤ Cm+n−1.Доказательство. Докажем индукцией по m. Базис индукции m = 1 верен.

Индуктивныйпереход: по теореме 5.1 получаемm−2m−1m−1R(m − 1, n) ≤ R(m − 1, n) + R(m, n − 1) ≤ Cm+n−2+ Cm+n−2= Cm+n−1.Теорема 5.2 (Эрдеша). При k ≥ 2 справедливо неравенство R(k, k) ≥ 2k/2 .Доказательство. Рассмотрим k ≥ 3, т.к. R(2, 2) = 2. Оценим долю γ(p, k) графов с pпомеченными вершинами, в которых найдется полный подграф с k вершинами. Возможных ребер в графах с p вершинами ровно Cp2 , откуда графов с p вершинами в точности22Cp .