В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 48
Текст из файла (страница 48)
Поэтому без ограничения общности можно считать, что в графе 6 нет вершин второй степени. Пусть и — произвольная вершина степени 1~ 4, Й(»») =(о», ом ..., о») — окружение вершины и, причем вершины в»»»(и) так занумерованы, что обход ребер в последовательности ио», пою ..., ио» происходит в направлении движения часовой стрелки. Заменим вершину и простым циклом С=(и», и,, ..., и„и») и соединим и» и о, ребром, 1 1,1 (рис. 59.2). Проводя аналогичную процедуру для каждой вершины графа 6, степень которой больше трех, получим кубическую карту, которая, Рвс. 59.2 по предположению, 4-раскрашиваема. Искомая 4-раскраска граней карты 6 получается стягиванием как<доге добавленного цикла в точку.
Теперь докажем, что 1) ~ 3). Пусть произвольный плоский граф 4-раскрашиваем. Рассмотрим некоторуго кубическую карту 6. Согласно теореме 58.1 зта карта также является 4-раскрашнваемой. Фиксируем одну из ее 4-раскрасок н будем считать, что выбранные 4 цвета составляют абелеву группу А = (О, а, Ь, а+ Ь) (а)+ 262 -'ь(Ь) — прямую сумму двух циклических групп второго порядка. (Это коммутативная группа, в которой а + а = = Ь + Ь = 0.) Определив теперь цвет кансдого ребра графа 6 как сумму цветов двух разделяемых этим ребром граней, получим правильную раскраску ребер тремя цветами а, Ь, а+ Ь. Наконец, докажем, что 3)~ 2). Пусть 6 — кубическая карта и у'(6)= 3.
Фиксируем правильную реберную 3-раскраску графа 6 цветами а, Ь и с. Рассмотрим подграф графа 6, порожденный ребрами, окрашенными в цвета а и Ь. Очевидно, что этот подграф является объединением простых циклов. Припишем точкам плоскости, лежащим внутри циклов, цвет 1, а вне — цвет 2. Аналогично, точкам плоскости, лежащим внутри циклов, индуцированных ребрами, имеющими цвета а и с, припишем цвет 3, а вне таких циклов — цвет 4. Таким образом, каигдой грани карты 6 окажется приписаппой одна из следующих пар цветов: (1, 3), (1, 4), (2, 3), (2, 4). Эти пары определягот раскраску карты четырьмя цветами, поскольку смежным граням соответствуют разные пары. и В связи с проблемой четырех красок Г. Биркгоф в начале века поставил вопрос: какими свойствами должны обладать минимальные плоские графы, вершины которых нельзя правильно раскрасить четырьмя цветами7 Такие графы называготся неприводимыми.
Далее изучались графы, их называли приводимыми пон4игурауиями, которые не являются подграфами неприводимых графов. В дальнейшем многие математики изучалп гипотетические неприводимые графы и приводимые конфигурации. Эти исследования позволили довести число вершин в графах, для которых доказана их 4-раскрашиваемостгь до 96.
В 1969 году Х. Хееш свел проблему четырех красок к исследованию болыпого, но конечного множества У так называемых неустранимых конфигураций. Им было показано, что для любого максимального плоского графа 6 найдется подграф 6, изоморфный некоторой конфигурации из У и такой, что если граф 6 является 4-раскрашиваемым, то 4-раскрашиваем и граф 6. Позже число таких неустранимых конфигураций было уменьшено до 1482. В 1976 году коллективу математиков и программистов, возглавляемому К.
Аппелем и В. Хейкеном, удалось правильно раскрасить все графы из множества У 263 четырьмя цветами, затратив па зто около 2000 часов работы мощной ЭВМ, что позволило им заявить о доказательстве гипотезы чотырех красок. Тем пе менее трудно согласиться с таким доказатольством, поскольку и сведенио общего случаи к ноустранпмым конфигурациям, и раскраску последних очень слсикно повторить. Понятия (плоской) карты и ое раскраски естественно распространяются па другио поверхности.
Пусть К вЂ” некоторая поворхность, любая карта на которой допускает раскраску у(8) цветами, и существует карта па 8, пе допускак~щан раскраски у(К) — 1 цветами. Тогда у,(о) пазываетсн хроматическим числом поверхности К. Теорема 59.3 (Г. 1'ипгсль, Д. Япгс, 1968 г.). Если ог — сфера с р ) 0 ручками, то Подробно о раскраске карт, расположенных на произвольных поверхностях, см. в [26]. $60. Другие подходы к раскраске графов В Г943 г. Г. Хадвпгер выдвинул гипотезу, тесно свнзанную с проблемой четырех красок. Гипотеза Х ад нигер а. Любой связный и-хроматический граф стягиваем к К„. Длн и ~ 4 гипотеза подтверждаетсн. В самом деле, при п = 1 утверждоние тривиально.
При п= 2 кангдый связный граф стягивается к ребру, а при п = 3 — содернгит цикл и потому стягивается к Кг. Следующая теорема доказывает гипотезу длн и = 4. Т е о р е м а 60.1. Каждый связный 4-хроматический граф стягиваем к Кс Ь Пусть С вЂ” связный 4-хроматический граф. Если в С есть точки сочленения, то некоторый его блок должен быть 4-хроматичоским, иначе из теоромы 53.3 следовало бы, что у(С)(4. Стянем С к атому блоку. По той же причине блок останотсн 4-хроматическим после стягивании ребор, пнцидептных воршине степени 2. Таким образом, пе торин общности, можно считать С блоком со степенями вершин не менее трех.
Пусть С =(оп ои ..., о„, о1) — простой цикл максимальной длины р в С. Очевидно, что р)4. Простую цепь, связывающую две несоседние вершины цикла С и не содержащуго других вершин этого цикла, назовем С-хордой. Покажем, что для любой вершины и~ цикла С существует С-хорда, которой принадлежит зта вершина. Так как деди~ ~ 3, то имеется ребро е = о~и, не принадлежащее С. Если и~ )гС, то ребро е является С-хордой.
Пусть иФ РС. Тогда по теореме 34.1 суп1ествует простой цикл С~ =(пп и, ..., пм ..., и~), содержащий ребро е и Рпс. Сод вершину ии Цепь 1 =(пп и, ..., пз) должна иметь некоторую вершину оь отличную от пз и принадлежащую циклу С, иначе С пе был бы простым циклом максимальной длины. Пасть цепи Ь от и~ до первой вершины, принадлежащей циклу С, и будет искомой С-хордой. Предпологкнм, что существугот две С-хорды Т~ —— =(п„..., п,) и Тг =(ом ..., о,) с общей вершиной 1 впе С. Тогда часть графа, состоящая нз С, Т~ и Тм стягивается к К4.
Один из вариаптов стягивания изображен па рис. 60.1, а. Теперь рассмотрим случай, когда ле суп1ествует пересекающихся С-хорд. Любая С-хорда делит цикл С на две простые цепи. Выберем такую С-хорду Ть чтобы одна из этих цепей С'= — (оь ..., г,) была кратчашпей, и возьмем вершину г„па этой цепи (такая верптпна существует, поскольку С-хорда соедяпяст две несоседпяе вертпппы цикла). Рассмотрим некоторую С-хорду Та = =(о„, ..., и,).
Если при этом вершина о, будет располо'кояа на С', то цепь (гм ..., о,), принадлежащая циклу С, будет короче, чем С'. Следовательно, о, пе лежит на цепи С'. В этом случае часть графа, состоящан из С, Т~ и Тм стягивается к Кс Одпп пз вариантов стягивания показан на рис.
60.1, б. 285 После того как будет получен граф К», оставшуюся часть исходного графа стянем к К». 0 Известно, что утверждение гипотезы Хадвигера при п=.5 эквивалентно гипотезе четырех красок. А именно, верна следующая Теорема 60.2. Следующие два утверждения эквивалентны: 1) гипотеза четырех красок верна; 2) любой связный 5-хроматический граф стягиваем к Кз. В заключение этого параграфа рассмотрим один алгебраический подход к проблеме раскраски плоских графов. Детально об атом см. [14]. Пусть 6 — плоский граф, и »(ь: У6 — А (где А = =(О, а, Ъ, а+ И =(а)+(Ъ) — прямая сумма двух циклических групп второго порядка) — его раскраска. Тогда условием правильности выбранной раскраски окан»ется следующее условие: уц —— »г(о,)+»г(оь) Ф 0 для любого ребра о,оь графа 6.
Поэтому для произвольного цикла С ° (О1ю Оз~ ° ° р Олр Ул+1) ~ Ол.ь.! = Уь, ДОЛЖНЫ ВЫПОЛНЯТЬСЯ условия у»,1+ь Ф О, 1 = 1, п, ~~5 у;,1+1 = О, 1=1 Пусть теперь 6 — произвольный связный граф, каждому ребру о,о, которого поставлена в соответствие переменная уц. Получим систему уравнений о(6), записав соотношения вида (1) для каждого цикла графа 6, и систему К(6) — для каждого цикла из некоторого фиксированного базиса циклов. Лемма 60.3. Каждому решению системьь К(6) при фиксированной окраске»у(оз) некоторой вершиньь оз однозначно соответствует правильная раскраска графа 6 четырьмя цветами. с' Для заданной вершины о„»и т'6 рассмотрим произвольную цепь Р„=(оз, о„..., о„) и примем о-1 »(Ь (Оч) = »(Ь (Оо) + ЛЛ УМА+ М (2) А=в где уц составляют решение системы К(6). В силу (1) значение»р(о )' не зависит от выбора цепи Р, позтому оно определяет цвет вершины о .
Так как уцФО для оац»в Е6, то льобые смежные вершины имеют различные цвета. Таким образом, раскраска, задаваемая формулой (2), правильная. » 266 Т ак как граф может содержать большое число циклов, то перейдем от системы уравнений Я(С) к системе Я(С).
Теорема 60.4. Каждому решению системы Я(С) при фиксированной окраске ф(ог) некоторой вершины ог однозначно соответству- и ет правильная раскраска графа С четырьмя цве- и, »А тали. Ъ А В силу леммы 60.3 достаточно показать, что решение системы Я(С) ир,, является и решением си- Рис.
60.2 стемы Я(С). Для этого вначале рассмотрим произвольный простой цикл С=(оо~ о! ° -, о! — 1, оА, о!+1 ° ° о»-! о» оп+1, ° ° о о01 не принадлежащий базису циклов С графа С. Известно (з 21), что С можно представить в виде суммы по модул!о 2 нескольких циклов из С. Пусть С = С1 ~ Сг, С1, СгыС, С1 (ОО~ 1111 ° ° ° ~ ВЬ О»и!А ° ° и и +М итп ОР+1т ° ° А и ~ ОО) А Сг =(гь о!+1,, ои-ь ип о'Ам, о»+ь о!) (рис. 60.2)'. Тогда Х уц= Х уц+ Х уццрнсо црлес! цравсг 2 (У1,»+г + Уп+А,п-1-г + ° ° ° + Уп+й,р) = — 0. Аналогичные рассуждения можно привести и в том случае, когда цикл С является суммой не двух, а большего числа циклов из базиса циклов С. Значит, соотношение (1) выполняется для любого простого цикла.
Если же цикл С не простой, то необходимо представить его в видо объединения нескольких простых циклов, для каждого из которых выполняется (1). А э 61. Совершенные графы Как отмечалось выше, хроматическое число и плотность любого графа удовлетворяют очевидному неравенству т(С)) 1р(С). При этом, как свидетельствует теорема 54.5, разность )((С) — Ар(С)' может быть как угодно 267 велика. В этом параграфе изучаются графы, обладающие тем свойством, что хроматическое число и плотность не только самого графа, но и каждого его порожденного подграфа, равны. Граф называется совершенны 6 если у (Н) — ~р (Н) (1) для любого его порожденного подграфа Н.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
