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