Что ж, давайте перейдем к разбору задач, которые,
как нам кажется, полезны для лучшего понимания второй лекции.
И первую из этих задач, которую мы сейчас разберем — это то,
что называется «классический критерий двудольности графа».
Ну просто совершенно классический, который, конечно, не знать тоже,
в какой-то мере, грех.
Значит, задача звучит следующим образом: давайте докажем,
что граф двудолен,
сейчас я это тоже поясню, на всякий случай, значит, докажем,
что граф двудолен тогда и только тогда,
когда в нем
нет простых циклов нечетной длины.
Простых циклов нечетной длины — совершенно классический факт,
который сейчас надо максимально аккуратно откомментировать постараться.
...простых циклов нечетной длины.
Ну что значит граф двудолен?
По определению это просто означает,
что хроматическое число этого графа равняется двойке.
Ну или, другими словами, граф выглядит каким-то вот таким вот образом.
Есть две доли, в одной содержится какое-то количество вершин, в другой
содержится тоже какое-то, может быть отличное от первого количество вершин.
И вот эти доли между собою как-то там соединены ребрами.
Я вовсе не утверждаю, что это полный двудольный граф, я просто говорю,
что можно одну долю покрасить, условно, в красный цвет, другую, условно,
в синий цвет, и не будет ребер, у которых концы имеют один и тот же цвет.
Потому что внутри доли ребер не предполагается, а вот между долями ребра
могут и даже должны идти, ну уж в каком количестве это совершенно неважно.
Так вот утверждается, что граф такой, то есть его хроматическое
число действительно равняется двойке тогда и только тогда,
когда очень просто: в нем нету циклов, простых циклов нечетной длины.
Ну смотрите: в одну сторону все совершенно очевидно.
Если есть цикл
нечетной длины, то,
конечно же, хроматическое число такого
графа оно не меньше, чем хроматическое число этого цикла.
Давайте я этот цикл нечетной длины обозначу буквой 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 соединены ребром,
но покрашены в один и тот же цвет.
Так.
ну что значеть они не покрашины в один тот же цвет это значет что если мы
просмотрем кратчайший маршрут от у де в и рассмотрим
кратчайший маршрут от дубель в да в они могут как то хитро
переплетаться между собой эти кратчайшие маршруты но в любом случии
мы получим что у них одинакавая четность длинны тоисть либо
длина маршрута от у до в четная и тогда длина маршрута от дубля в до в тоже четная
раз уж они получили одинаковые цвета либо оби длины являются нечётными ну
тогда тут вершины синие замечательно замечательно
замечательно значеть обе четные или обе нечетные но
понятно что сумарная длина сума длин
сумарная длина вот всего этого маршрута давайте я так напишу от
в до у потом поребру до дубель в и потом сново
по маршруту до в вот сумарная длина такого перехода прошли сначала
от в от в до у да вот так вот от в до у поэтой волнистой линии потом от у до
дубель в прошли поребром а потом от дубель в дов прошли по маршруту который
их соеденяет понятно что сумарная длина вот такого большого маршрута
от в и до себе же обратно вот это сумарная длина является конечно не четным
чеслом потомучто либо четное плус четное плус один либо нечетное плус нечетное плус
один но в любом случаи сумарная длина такого маршрута нечетная вот эта
длина вот этого маршрута это нечесное число
но этот маршрум конечно простым то цыклом не является с другой старана вот я
картинку не совсем улистративно нарисовал лутше было бы где небуть нарисовать
что тут могут быть какиете ребра каторые сначала пройдены по маршруту от в до у
а потом пройдены обратно по маршруту от дубель в до в я здесь их как то
трансверсально пересекаю как будто бы они могот пересекатся только по вершином ну
они могут в принцепе проходить и пообщем ребрам давайте я вот такой какой нибуть
пример нарисую в там потом пошли пошли пошли пришли в
у потом пошли сразу пришли в дубель в а дальшо мы могли
вот как нибуть так пойти скажем вот так потом вот так потом
вот так там скажу и вот так ну что нибуть такое
возможно тоисть могли сначала пройти сюда а потом по какимто общим
ребрам вернутся обратно так вот смотрите если выкинуть вот такие
то общие ребра ребра каторые пройдены дважды общие
ребра маршрутов в у и в дубель в если из вот этого
большого маршрута каторый здесь нарисован выкиныть такие ребра которые пройдены
дважды то в результате останется просто набор вот тахи
вот нересекающих простых цыклов даже веднее вот один
простой цыкол вот второй простой цыкол потом может быть где то какието были ребра
которые пройдены дважды мы их выктнули возник следущий простой цыкол и так далее
тоисть вся вот это вот канструцыя вес этот маршрут если
удалить из него повтаряю очередной раз если удалить из него те ребра
которые встречаются на пути туда так сказать и на пути обратно вес этот маршрут
без таких ребрах разпадается вобедение простых цыклов но если сумарная
длина этого маршрута була бы не четным чеслом выкидывали мы все
скатностью двояка значет сумма длин вот этих оставшихся
простых цыклов давайте так сумма
длин оставшихся простых цыклов на которых все
распалось оставшихся простых цыклов
тоже нечетно общая самма была нечетной мы удаляли
скратностью два значит туда значип удаляли удаляли всякие числа кратные двойки
и получили что сумма длин этих простых цыклов тоже нечетные ну значет что если
сумма длин простых цыклов тоже нечетная значет есть всреди
этих простых цыклов простой цыкол нечетной длины в графе
есть простой цыкоц нечетной длины если бы все они были четные то в сумме
они бы полочили бы нечетное но четное число есть простой
цыкол нечетной длины а это проворечет
нашему призначальному предположению веть мы та работаем в сотвержением именно в
такую сторону мы придпалагаем что цыклов нет после этого организуем раскраску и вот
хотим утверждать что она правельная мы предположили что нет она неверная что есть
какието две вершины одного цветы которые соедены реброт и в результате пришли к
тому что обезательно тогда найдётся простой цыкол нечетной длины но это
протеворечет означательному придположению и значет помтрояная нами краска
дествительно правельная хроматеческая число не больше двойки гравное удолен