В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 46
Текст из файла (страница 46)
Пусть в я М, с~и М„. Рассмотрим цепь Ь, начинающуюся в вершине о, ребра которой попеременно окрашены в цвета в и 1 и которая имеет нанболыпую длину среди таких цепей. Вершина и не входит в Ь, иначе (и, и)-подцепь цепи Л вместе с ребром е образовала бы в графе С цикл нечетной длины, что невозможно в двудольпом графе. Переставив цвета в н 8 в цесш Л, монссю затем окрасить ребро е в цвет в, что противоречит исходному предполоскешпо. 0 Типичная ситуация отраясается следусопсей теоремой, приводимой боз доказательства (см.
обзор [21) ). Теорема 50.4. Для почти каждого градса С верно равенство в 57. Связь матроидных разложепийс графов с раскрасками Отметим простые связи, существующие между матроидными разлонсепиями графов и раскрасками. Напомним, что матроидкым разложением графа С называется продставлепие ого в виде объедссссопссн 6=6 НС с)...ПС„ М-графов, т.
е. графов, все связные компопепты которых суть полные графы; минимальное число сс компонент в матропдных разложениях графа С вЂ” матропдиоо число )с(6). 252 Пафккснруом правильную раскраску ребер графа 6 и рассмотрим разбиение множества ребер на цветные классы: Е10 Ез0... 0 Е„=Е6. (1) Очевидно, что граф 6ь для которого У6, = У6, Е6, = Еь является М-графом, п 6 = 61 0 6г 0 ... 0 6„ (2) — матроидное разложение. Итак, разбиение на цветные классы (1) определяет матроидное разложение (2) графа 6.
Тем самым доказано Ут в е р ж д е н и е 57.1. Для любого графа 6 верно неравенство ~ (6) = К'(6). Учитывая это неравенство и теорему 56.3, получаем Утверждение 57.2. Если граф 6 ае содержит треугольников, то д(6) = Х'(6) Для любого двудольного графа 6 верно равенство д(6) = А(6). 1> Если граф 6 пе содержит треугольников, то его робсрпый граф Ь(6) и граф клик ч(6) могут различаться только изолированными вершинами. Следовательно, если уе(6) — хроматическое число графа 6(6), то ул(6)= К'(6), так что для графа 6 без троугольпиков р(6) =ул(6)=Х'(6). Применяя теорему 56.3, получим второе равенство.
З Для матроидного числа произвольного графа хроматическое число его графа клик является верхней границей. А именно, верно Утв еригдение 57.3. Для любого графа 6 справедливо неравенство р(6)-=- Х (6). (3) > Подграф, порожденный в 6 объединением клик, входящих в один цветной класс при правильной вершинной раскраске графа клик 6(6), является ЛХ-графом, по. скольку все ого связные компоненты — полныс графы. Следовательно, осли Р ~ Р в ... и Р = )'6(6) — разбиение на цветные классы мпоясества вершин графа клик, а 6г получается из пороясденного подграфа 253 6()т,) в результате присоединения всех вершин из й'6~)т, как изолированных, то С = С~ 0 Сг 0...
0 ф— матроидкое разложение. Тем самым неравенство (3) доказало. <~ В качестве иллюстрации рассмотрим граф 6, изображенный на рпс. 57.1; для ного Ч(6) = Кп т„(6) = = Х'(6) = 4, И (6) = 3. Утворждеппе 57.4. Для произвольного граЯа С равгнства д(6) = 2 и уч(6) = 2 равносильны. 1> Если аз(6) =2, то 1г(6) < 2. Но пРи и(6)= 1 никакие две максимальные клики графа С пе пересекаются, и потому (т(6) — пустой граф, уч(6)=1.
Итак, при 11ч(6) = 2 и и(6)= 2. Остается доказать истинность пмплпкации 1г(6)=2 Хч(6) =2 (4) Доказательство основало на следующей очевидной комбппаторпой лемме. Лемма 57.5. Пусть Ь' — конечное многксство, казкдому из злсмсггтов которого приписан один из двух фиксированньях цветов или оба эти цвета. Если для любой пары элементов множества Я существует общий приписанный им цвет, то тогда и все элементы мнолссства имеют общий прпппсанный им цвет, Пусть теперь 6=6~ 0 Сг (5) — матропдпое разложение графа С. Достаточпо доказать, что лгобой полный подграф графа С целиком содерятится в каком-либо яз Сб осли зто так, то разложение (5) определяет правильную 2-раскраску графа клик и истинность импликации (4) доказана. Каждому из ребер графа С следую- щим образом припишем один из цвеРпс 57т тов (1, 2) или оба эти цвета. Именно, всем ребрам графа С~ (1 = 1, 2) приписывается цвет й Пусть теперь Ч вЂ” клика графа С, еп сг ~ЕСТ).
Еслгг робра с~ и сг смежны, то в порождеппом подграфе 6(Д) существует третье ребро с, смеягпое с ними обопмп. Какие-то два пз этой тройкк ребер имеют общий цвет, поскольку цветов только два. По копцы этих трех ребор вместе входят в одну из связных компопепт графа Сп являющихся полпымп графамп, следовательно, и третье ребро имеет тот же цвет. Итак, для любой пары 254 смежных ребер графа 6(6) существует общий приписанный нм цвет.
Если же ребра е> = и>о> и ее = изот не смежны, то в графе 6(6) есть еще четыре ребра ее=и>иг, е>=о>ог, ег = и>о>ь ее =-о>иг. Для кан>дой пары смежных пз этих ребер сущоствует общий цзот, откуда очевидно вь>текает, что существует цвет, общгйу для ребер е> и ег. ~[оказано, что любые дза ребра графа 6((7) пме>от общий цвет, В силу леммы 57.5 существует общий цвет, например 1, прпппсанный всем ребрам графа 6(>>).
Последнее означает, что 6(ч) содержится в одной из компонент графа 6>. 'З Из утверждения 57.4 вытекает Следствие 576. Если т(6)= 3, то и р(6) =3. й 58. Раскраска планарных графов Проблема раскраски планарпых графов является одной из самых знамо>штык проблем теории графов. Возникшая в середине прошлого века, опа до спх пор привлекает внимание специалистов и любителей.
Первоначально вопрос формулировался в следующем виде: достаточно ли четырех красок для такой раскраски произвольной географической карты, прн которой любые две соседние страны окрашены в различные цвета? Прн этом рассматриваются лишь те карты, в которых граница любой страны состоит из однои замкнутой линии, а соседними счита>отея страны, имеющие общую границу ненулевой длины. Позднее понятия карты н ее раскраски были формализованы следующим образом. Связный плоский мульти- граф без мостов называется картой.
Грани карты, имеющие общее ребро, называются смежными. Функция >', ставящая в соответствие каждой грани Г карты натуральное число >'(Г)~ (1, 2, ..., к) — цвет грани Г,— называется Й-раскраской, если цвота смежных граней различны. Карта называется К-раскрашиваемой, если для псе существует Й-раскраска. В 1879 году британский математик А. Кэл>г опубликовал в первом томе Трудов Лондонского географического общества статью, посвященную проблеме раскраски карт, в которой сформулировал гипотезу четырех красок (сама задача была известна и ранее). Гипотеза четырех красок: вслкал карта 4- раскрашиваема. 255 »1асто пользуются другой формулировной гипотезы четырех красок: всякий пленарный граф 4-раскрашс»ваем.
Поскольку плапарный граф по определению изоморфен некоторому плоскому, то эквивалентность этих двух формулировок гипотезы четырех красок вытекает из следуюгцей теоремы. Теорема 58.1. Карта С является к-раскрашиваемой тогда и только тогда, когда геолсетрически двойственный граф С" вершит»о сс-раскрашиваем. ~> Поскольку граф С плоский и но имеет мостов, то двойственный граф С* — плоский граф (без петель). Пусть задана некоторая правильная Й-раскраска карты С. Построим Й-расссраску графа С*, приписав каждой его вершине цвет той грани, в которой находится эта вершина. Так как вершины графа С* смежны тогда и только тогда, когда смежны ведер»кащие их грани, то полученная раскраска оказывается правильной.
Лпалогичпым образом можно перейти от правильной раскраски графа С* к ссравильной раскраске карты С. » Замотим, что существуют плоские графы, которые нельзя раскрасить правильно менее чем четырьмя цветами. Таков, например, граф К». Первоначально гипотеза четырех красок пе показалась слссшком слонсиой н появилось несколько ее «доказательства, в которых позднее были обнаружоньс пробелы.
В дальнейшем эту проблему, сбивающую с толку простотой формулировки, пытались решить многие известные математики. Боль»с»ой интерес к теории графов, возникший в связи с гипотезой четырех красок, способствовал открытксо многих важных результатов, поскольку опи казались полезпымн для решения проблемы. До сих пор эта проблема остается мощным стимулом исследования различных свойств графов. Сначала рассмотрим раскраски планарных графов двумя и тремя цветами.
Согласно теореме 11енига ~(С)= 2 для пепустого графа С тогда и только тогда, когда оп не содержит циклов нечетной длины, откуда несложно получить следующее утверждение. Утверждение 58.2. Плоский двревягный граф является бихроматичееким тогда и только тогда, когда грани»»а каждой его гропи содержит сетное число ребер. о Достаточно доссазать, что плоский двусвязный граф, граница каждойс грани которого состоит из четного числа ребер, является двудольпым. Рассмотрим произвольный 256 простой цикл С такого графа.
Этот цикл делит плоскость на две части — внутреннюю (по отношению к циклу) н внешнюю. Считаем, что сам цикл принадлежит каждой из частей. Пусть внутренняя часть плоскости содержит грани Гп Гг,, Г, с числом ребер в их границах )н )м ..., 1, соответственно. Так как любое из чисел Ц четное, то их сумма также четная. Но каждое ребро, не принадлежащее циклу С„входит в эту сумму дважды, откуда следует, что длина цикла С четная.
Из теоремы 9.1 следует, что рассматриваемый граф является двудольным. 0 Аналогичное утверждение верно и для односвязных графов, только в этой сытуации наждый мост, входящий в границу грани, учитывается дважды. Утверждение 58.3. Карта 6 является 2-раскрашиваемой тогда и только тогда, когда граф 6 эйлеров. Учитывая теорему 58Л, нужно лишь доказать, что геометрически двойственный граф 6* является двудольпым тогда и лишь тогда, когда граф 6 эйлеров. Последнее оставлено читателю. < Теорема 58.4 (М.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
