Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день. Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. Этот курс служит введением в современную теорию графов. Мы, конечно, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов. Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики. Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.
Хроматическое число графа и его дополнения
Loading...
来自 Moscow Institute of Physics and Technology 的课程
Теория графов
261 个评分
从本节课中
Экстремальная теория графов. Теорема Турана
На этой неделе мы начнем разговор про экстремальную теорию графов, которая ставит вопросы про то, с какого момента графы начинают обладать тем или иным свойством. В частности, мы выясним, сколько ребер должен иметь граф, чтобы он гарантированно содержал треугольник. В конце лекции мы узнаем, что графы на плоскости в экстремальных задачах ведут себя несколько по-другому, нежели графы абстрактные.
与讲师见面
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Андрей Купавскийкандидат физико-математических наук
Кафедра дискретной математики ФИВТ МФТИ
Вот ещё одно несложное замечательное утверждение о раскрасках графов,
которое мы тоже докажем, в конечном счёте, по индукции.
Ну давайте так, вот есть у нас какой-то граф G, как обычно равный (V, E),
хотя я уж не знаю, в данном случае, может быть, эти обозначения не так важны.
Понятно, что по этому графу можно построить двойственный к нему граф G
с чертой, у которого то же самое множество вершин,
но рёбра проведены ровно там, где нет рёбер у графа G.
И наоборот, там, где есть рёбра, они не проведены.
То есть, если мы...
Ну можно вот так написать: например,
множество рёбер полного графа на n вершинах, если считать,
что мощность V равняется n, минус рёбра исходного графа.
Ну то есть мы действительно выкинули все рёбра,
которые были в графе G, а наоборот те рёбра, которых в графе G не было, провели.
Вот такой двойственный граф.
Ну и, действительно, совершенно не зря я ввёл обозначение мощность V равняется n,
потому что утверждение, которое мы сейчас докажем состоит в том,
что хроматическое число исходного графа плюс хроматическое
число его дополнения всегда не больше, чем n + 1.
Вот на покраску обоих графов – как исходного,
так и дополнительного к нему – заведомо хватит не больше чем n + 1 цвета.
Вот давайте докажем это по индукции.
Индукция, естественно, по числу вершин.
Индукция по величине n.
Ну давайте так, для n = 1 и 2 даже здесь всё очевидно, например,
если у графа одна вершина, то двойственный к нему граф – это,
понятно, он же сам, потому что там изначально никаких рёбер нету.
Ну и нам хватает вообще одного цвета для того, чтобы правильно покрасить этот граф.
Но если n всё-таки равняется 2, то вот здесь как раз вполне себе оценка
достигается, потому что ну вот, например, возьмём такой исходный граф,
состоящий просто из одного ребра, граф на двух вершинах, это G,
соответствующий G с чертой это тоже граф на двух вершинах,
но у которого наоборот ребра нет, то есть такое независимое множество мощности 2.
Понятно, что на этот граф требуется 2 цвета, на этот граф требуется 1 цвет,
суммарно получается 3, ну это как раз n + 1, то есть опять всё подтверждается.
База индукции у нас в кармане.
Давайте предположим, что для какого-то n больше или равного
ну можно считать двойке, можно считать единице, предположим,
что для какого-то n ну и для всех предшествующих значений тоже всё доказано,
то есть сумма хроматического числа графа,
имеющего n вершин и его дополнений не превосходит n + 1.
Докажем это дело в случае, когда у нас есть произвольный граф,
имеющий уже не n, а n + 1 вершину.
Ну то есть рассмотрим теперь произвольный
граф G
равняется (V, E), такой, что мощность V = n + 1.
Нужно доказать, давайте я это всё-таки зафиксирую.
Нужно доказать, что в этом случае, каков бы ни был наш граф χ(G)
+ χ(G') не превосходит, внимание, n + 2.
Потому что у нас n + 1 вершина, и когда мы к n + 1 единицу прибавляем,
естественно, получается n + 2.
Нужно доказать, что сумма хроматических чисел не превосходит n + 2.
Так.
Ну давайте, как водится, как водится,
выделим какую-нибудь, на самом деле, совершенно произвольную вершину графа G.
Ну давайте я вот здесь это напишу.
Возьмём какую-нибудь любую совершенно вершину v,
принадлежащую множеству V и нарисуем соответствующую картину,
только рисовать я её буду, чтоб не ютиться в уголках, не здесь, а на следующей доске.
Так.
Ну вот у нас эта выделенная вершина v и традиционное блюдо,
называемое «сарделькой»,
которое остаётся в нашем графе, коль скоро из него вершина v удалена.
Значит, это блюдо мы обозначим G'.
Ещё раз, это тот граф, который получается из графа G удалением вершины v.
Ну а кроме того, конечно, есть какие-то рёбра из этой вершины, которые соединяют
вершину с оставшимся графом G', с «сарделькой», с блюдом вкусным.
Так.
Замечательно.
Замечательно.
Что мы с вами знаем?
Мы знаем, что у графа G' конечно же, n вершин.
В частности, это, разумеется, означает что χ(G') плюс
χ(G') с чертой не превосходит
n + 1 в виду сделанного нами предположения индукции.
Это граф с меньшим числом вершин, ну, значит,
сумма соответствующих хроматических чисел, мы уже точно знаем, не превосходит n + 1.
И вот наша цель как-то теперь докрасить вот эту вершину v, чтобы было хорошо.
Чтобы получилось не больше, чем n + 2 цвета суммарно и на граф G,
и на граф G с чертой — на его дополнение.
На его двойственный граф.
Как бы это нам сделать?
Ну давайте рассмотрим два случая.
Может, конечно, так случиться, ну нам лафа полная,
нам совсем повезло, и на самом деле χ(G')
+ χ(G' с чертой) меньше строго, не не превосходит даже,
а строго меньше, чем n + 1, то есть не превосходит n.
Ну может такое случиться.
Лафа на самом деле.
Потому что если это так, тогда мы просто берём и,
абсолютно не задумываясь ни о чём, нашу вершину v в исходном графе
G красим ещё в какой-то один цвет, отличный вот от этих n цветов,
а ту же самую вершину v, но в исходном же графе G с чертой
в дополнении до G, красим в ещё какой-то n + 2-й цвет.
Ну и всё очевидно.
Естественно, в этом случае, χ(G) + χ(G с
чертой) не превосходят n + 2, потому что, повторяю,
мы просто тупо добавим два новых цвета, и никто от этого не развалится,
всё будет замечательно, все рёбра будут иметь концы разных цветов.
Вот. Ну второй случай, это тот,
в котором такой лафы нет, в котором так вот за здорово живёшь ничего не получится.
Ну давайте, стало быть, предположим, что χ(G')
+ χ(G' с чертой) равняется в точности n + 1.
Равняется в точности n + 1.
А теперь давайте вот какую вещь заметим.
Вот я здесь нарисовал какие-то рёбра, да,
идущие из вершины v внутрь нашей «сардельки».
Ну я, конечно, понятия не имею, сколько этих рёбер,
но давайте степень в графе G нашей вершины v,
ну то есть сколько рёбер из нашей вершины v внутри графа G
выходит из неё, обозначим просто буковкой d.
А те рёбра, которые из неё не выходят, ну такие, в принципе, могут быть,
то есть те рёбра, которые выходят из этой вершины в дополнительном графе,
графе G с чертой, обозначим, соответственно, d с чертой.
Что, по-моему, очень естественно.
Так, товарищи, если вы понимаете, чего происходит, ещё не отрубились, то,
наверное, надо вот что спросить у вас: чему равняется d + d с чертой?
Ну это очевидный вопрос, конечно.
d + d с чертой – это просто сколько вершин вот в этой «сардельке».
В этой «сардельке», как мы знаем, n вершин.
Понятное дело, d + d с чертой в точности равняется n.
А теперь смотрите, как интересно: χ(G') + χ(G' с чертой) в точности равняется n + 1,
в рамках текущего случая, а сумма вот этих чиселок в точности равняется n.
Что бы это значило?
Вот если вместе посмотреть на эти два условия.
Если вместе посмотреть на эти два условия, то становится понятно, что либо,
либо χ(G') строго больше,
чем d, либо χ(G' с чертой) строго больше, чем d с чертой.
Ну понятно, не может быть сумма двух чисел равна n + 1, а сумма двух вот этих чисел
равна n, и при этом чтобы χ(G') равнялось d и χ(G' с чертой) равнялось d с чертой.
Просто какая-то нелепость.
Нонсенс.
Понятно, что либо выполнено вот это неравенство, либо вот это.
Ну, как водится, никакой общности я не ограничу,
если рассмотрю только вот этот случай,
ну а вам вольно, в принципе, при желании рассмотреть этот случай тоже,
но, повторяю, он ничем не отличается от того, который мы сейчас изучим.
Итак, ну давайте считать, что произошло вот именно это.
Хроматическое число графа G' строго больше, чем вот эта величина d.
Строго больше, чем величина d.
Ну что это значит?
Это значит, что в графе G, это значит, что в графе G вершину v,
внимание, можно спокойно покрасить в один из тех цветов,
которые задействованы в определении этого хроматического числа.
Мы уже не раз таким пользовались.
Если мы знаем, что хроматическое число строго больше, чем d,
то количеством вот этих вот рёбер, это вот это самое d,
оно строго меньше, чем количество цветов, которые здесь присутствуют.
Ну значит мы спокойно можем выбрать такой цвет из вот этого числа цветов,
в которые ни один, в который ни один сосед вершины v не попал,
выбрать какой-то из этих цветов,
в который ни один сосед вершины v не попал и в него покрасить вершину v в графе G.
То есть не задействовать при этом никакого нового цвета.
Ну замечательно.
А в графе G', а наплевать на граф G',
в нём мы вершину v покрасим просто в какой-то новый цвет.
Ну всего вместе мы сколько цветов получим?
У нас вот здесь суммарно n + 1 цвет,
ещё один цвет добавился за счёт графа G',
ну а в графе G никакого добавления не произошло.
Поэтому опять получаем,
что χ(G) + χ(G с чертой) не превосходит n + 2.
Я, кажется, сказал в графе G', не в графе G',
а в графе G с чертой добавления нового цвета не произошло.
Ой. Нет, здесь произошло одно добавление,
а здесь ничего не добавили.
Поэтому в сумме получилось, ну даже не не больше, чем n + 2,
а можно написать в точности равно n + 2.
Ну, во всяком случае, тем самым шаг индукции завершён,
и наше утверждение полностью доказано.
