Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 45
Текст из файла (страница 45)
Положительный ответ на этот вопрос независимо друг от друга дали А.А. Зыков [19), Дж. и Л. Келли [42], Татт [37Цэту статью опубликовали Брукс, Смит, Стоун, Тахт нод псевдонимом мадам Бланш Декарт), Я. Мыцельсиий [44). Автор настоящего учебника "заразился" этой проблемой, будучи студентом Московского энергетического института, в 1962 г. получил ее доказательство н отослал в ведущий тогда журнал в области естественных наук АН СССР— "Журнал экспериментальной физики и вычислительной математики". В марте 1964 г. автор сделал доилад [5] о минимальной раскраске графа на научна-технической конференции МЭИ и опубликовал его [4).
В этой статье было введено понятие квазиполного графа, доказано, чта распределение квазнполных графов определяет его хроматическое число, и доказаны основные свойства, из которых следует: — доказательство проблемы четырех красок; — оценка хроматического класса Н(С) графа С при раскраске его ребер Я < Н(С) < р+ Я, где р — максимальное число параллельных ребер, 5 — степень графа; для обыкновенного графа С о < Н(С) < о + 1; — взаимосвязь между о' и р о = 0(пюс)р), в фр; 1 3.10. лУогорифмические оценки хромав1ическоео числа 253 Гл. 3.
Теория графов и мографов 252 — оценка хроматического класса К. Шеннона Н(С) < ~-',~1 Проблему четырех красок стали изучать с разных сторон, эквивалентируя ее формулировки. Наиболее полный обзор эквивалентных формулировок (13 формулировок) привел Т. Свахи [45]. Несмотря на многочисленные публикации по раскраске графов (Г.А. Дирак, О. Оре [26,38), Ф. Харари [31), Г. Биркгоф [35), А.А. Зыков [20), Я.
Мыцельский [44), Дж. и А. Келли [42), В.А. Горбатов [35), Г. Уитни [36], Г. Ходвигер [41] и др.), не все математические школы графистов "осознали" опубликованные результаты. Рнс. З.б4 Примером такой школы является английская школа Н. Крнстофидеса; в гл. 4 нз [36] приводится граф С (рис. 3.64) с плотностью р(С), равной 2, и утверждается, что его хроматическое число. равно 5.
Согласно (3.52в) имеем Ь(С) < пнп 2+ 1обз — +1, 2.~.1|ч о.35 — 1~(, — [+1) = ~ в+ 2, 2+3, 3+ 1)= 4, 135( 1п~ А(С) < 4. Действительно, имеем раскраску этого графа в четыре краски: а=11,3,13,15), ~9=(2,4,5,12,14~, 7=16,7,8,9,10,16), б=(11); а, 13, 7, б — краски. Однажды в сентябре 1976 г.
жители разных городов США получили письма с марками, погашенными специальным штемпелем, на котором было указано, что жители США К. Аппель и У. Хайкин решили проблему четырех красок [33]. Решение основывалось на результатах многочасовой работы мощного компьютера. Приведем доказательство проблемы четырех красок, полученное автором в 1964 г. Теорема 3.52. Квазиполныб граф 1в(д) квазиплотности д содержит подграф, гомсоморфныб полному подграфу, плотность которого равно д. Доказательство. Основанием(д — 1) квазиплотного графа Я(д) и их разность Жу) ' Фч — 1) = (Ю(9 — 1)) ~О[=-%(9 — 1))) (д — 1)-вершинно связаны. Докажем это утверждение от противного. Пусть подграфы Я(д — 1) и Я(д) ~ Я(д — 1) (д — 2)-вершинно связаны. Тогда существуьт множество (разрез 5'), содержащее (9-2) вершины, после расщепления которых получаем две компоненты связности, Я(д — 1) и фд) 1Я(д — 1).
В наихудшем случае в разрезе 5' не найдется и двух соцветных вершин, т. е. вершины разреза будут окрашены в д — 2 краски. Тогда в основании Ч(д — 1) найдется вершина, окрашенная в (д-1)-ю краску, так как его квазиплотность равна д — 1, а в разности св(д) ~ Я(д — 1) найдутся две вершины, окрашенные в (д — 1)-ю и д-ю краски, так как для любой вершины и; Е сВ(д) найдется его раскраска сс(сд(д)), при которой вершины ее сечения Г(ст) окрашены в д — 1 различные краски К=11,2,...,9 — 2,9 — Ц, ('уи; 6 С)(д)) Щд(д))) [[К(Г(и;))] = д 1).
Следовательно, как основание Я(д — 1), так и разность Ц(д) 1Я(д — 1) содержат вершины, окрашенные в одну и ту же (д — 1)-ю краску. Удаление одной из этих вершин не изменит хроматического числа, что противоречит опрелелению квазиполного графа. Следовательно, эти вершины равны друг другу, и эта вершина, естественно, принадлежит основанию Я(д — 1). Но тогда вершина основания Ч(д), окрашенная в (д — 1)-ю краску, и вершина разности ь)(д) 1Ч(д — 1), окрашенная в д-ю краску, смежны, что противоречит принятому попущению.
Следовательно, основание Я(д — 1) квазиполного графа фд) и их разность Я(д) Я(д-1) (д — 1)-вершинно связаны. Согласно теореме 3.7 любые две вершины о;, оя, и; Е ьв(д — 1), и Е 1в(д) ~ сВ(д — 1), соединены по крайней мере д — 1 вершинно йепересекающимися цепями. Будем 13.11. Задачи и упроэкяеиия 255 254 Гл.З. Теория графов и магри ов рассматривать полный полграф Г(р) плотности р как квазиполный граф ф2, р — 2), в котором основания и замещающие слои совпадают, а вершины замыкающих слоев конусируют соответствующие основания.
Учитывая свойство включаемости квазиполных графов (3.32) и выбрав ребра Я(2, О), вершины замыкающих слоев й(ж(ф2, 0))), й(~ф(2, 1))), й(=-(б)(2, 2))),..., й(=-(б~(2, д-2))) н соединяющие их цепи, получим полграф С, солержащийся в Я(2, а — 2), С СС Я(2, а — 2) С Я(д).
На основании вышелоквзанного утверждения о Я(д — 1)-связности полученный граф С является гомеоморфным полному подграфу Г(д) плотности а. Теорема 3.53. Граф С(р, й), й >1, р>2, невлажим в плоскосгль. Действительно, граф С(р, ус) содержит квазиполный полграф Я(3, 2), который в сваю очередь содержит подграф С,(Г(5)), гомеоморфный полному попграфу плотности 5: С(р, й) ~ Я(3, 2) Э Сг(Г(5)). Следовательно, согласна теореме 3.18 граф С невложим в плоскость, Теорема 3.54. Граф С(р, 1с), р>З, Й>0, нгвлажим в плоскость. Действительно, граф С(р, 1с) содержит полграф Я(4, 1), кохорый содержит подграф Сг((Г(5)), гомеоморфный полному попграфу плотности 5: С(р, Й) Э ф4, 1) Э С„(Г(5)). Следовательно, согласно теореме 3.18 граф С невложим в плоскость. Теорема 3.55.
Граф С(р, й), р=2, ус>2, невложим в плоскость. Действительно, С(р, 1с) Э Я(р, Ус) Э Я(2, 3) Э С,(Г(5)). Следовательно, согласно теореме 3.18 граф С невложим в плоскость. На основании теорем 3.53-3.55 аолучвем следующее показательство проблемы четырех красок. Теорема 3.56. Хроматическое число плаяариого графа не превыитает 4. Согласно теореме 3.18 планарный граф С не содержит подграф С„(Г(5)), гомеоморфный полному подграфу плотности 5: С 2~ Сг(Г(5)). Следовательно, этот граф не содержит попграфы сд(2 3) Ю(З 2) и Я(4, 1).
Отсюда хроматическое число Ь(С) со гласно теореме 3.48 не превышает 4. Рис. З.бб На рис. 3.65 приведены порожденные квазиполные графы квазиплотности 4, при этом в графах первого ряда выделены подграфы, гомеоморфные полному подграфу плотности 4. 33.11. Задачи и упражнения ЗА. Доквввть равенство Я=(А+)' Р(А ), где Я вЂ” мвтридв смеииости; Ат и А — соответствеиио ивчвльивя и конечная мвтриды кицидеидий; Р— диегоивльивя метрике весов дуг; — викк транскоиироввиия. 3.3. Доквввть, что Ям~ бь В', ь 1 где Я вЂ” метрика смеииости, Вь — метрике переходе во аутам с весом бь. 3.3.
Доказать, что лолгрвф гУ является ляклом тогда и только тогда, котла логическое матричное яроивведеяие (дрввило умиоиеиия строки ив столбед Гл.З. Теорил графов и мографав 3 3.12. Комменщлрии 256 257 0 1 0 0 1 0 1 1 0 1 0 0 0 1 0 1 0 1 0 О 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 О 0 О 1 О 1 1 1 1 0 0 1 0 0 0 1 1 1 0 1 2 0 0 0 0 0 О 0 0 0 7 0 0 0 0 0 О 0 0 1 0 0 О 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 0 1 0 0 1 1 1 О 1 1 0 1 0 1 О 0 0 0 0 0 0 0 О 0 О 0 О 2 0 0 О 9 0 0 0 5 О О 4 О О О 0 0 0 3 0 0 О О 0 О 1 О 0 0 0 0 0 9 О 0 О О О О 0 0 0 0 0 0 О 0 0 0 О 0 Р(С) = аз. и гры определена череа обычное умножение и словепие па молулю 2) матрицы инпн- ленцийи транспаннрованнойцикломатичеспайматрнцы равнонулевойматрице. 3.4. Дакааагь, что простые пути длины! (! < д) графа, заданного матрнцей е сменности Я, определяютсл матрицей Я = 1 Б .
ь=г 3.5. Пусть задан передатчик, который мажет передавать пять сигналаз: а, Ь, с, а, е. Прн приеме каждый иа этих сигналоз может быть истолкован двояко: сигнал а как р нли 9, сигнал Ь как д илн г, сигнал с как г нли з, сигнал Ы как э нли С сигнал з как р нли й Какое наибольшее число сигналов можно принять, не рискуя спутать нх друг с прутом? 3.6. Показать, что о(С х Сь) ) о(С,) п(Сь), где о(С;) — число внутренней устойчивости графе С, = С, Сь. 3.7. Опрелелить число внешней устойчивости графа С, эаданнога матрнцей смежности З.В.
Сколько ферзей достаточно расставить на шахматной доске хак, чтобы каждая клетка доски находилась под "ударам" хотя бы одного иа иих? Считать, чта клетка, занимаемая фигурой, такие находится под ее "ударом". 3.9. Докааать, что число различных деревьев, которые монна построить на п ланных вершянах, равно и" 3.10.
Найти связный подграф С' завешенного графа С, заданного матрицами, сумма весов ребер которого минимальна; 3.11. Вершина графа, удаление которой вместе с янцндентными ей ребрами делает граф несзяаным, называется тоской сочлеиеяал. Блоком называется связный нетривнвльиый граф, не имеющий точек сочленения. Может ли быть блоком граф, дипломатическое число которого и(С) = 2? Привести пример блею, удзлейие одного ребра из юнорого приводит к появлению точки сочленения.
Сушествуег ли блок, в котором удаление любого его ребра приводит к появлению точки сочленения? 3.13. Привести примеры свюных графов, для которых существуют разрезы, число ребер которых разно числу хард остовов. 3.13. Доказать, что удаление алного ребра, которое принадлежит каюму-то циклу связнша графа, не делает этот граф несвязным. 3.14. Эйлераеым называется связный граф, в катером существует замкнутая цепь, прохоляшая через каждое его ребро (все ребра цевн различны). Показать, чта граф, содержащий мает, не может быть эйлеравым. 3.15.
Граф называется гамальщомоеым, если он содервит простой остовиый цикл. Привести примеры графов, которые одновременно н гамильтоновы, и эйлеровы. 3.16. Определить число неизоморфных остовов двудольного графа Кз, з. 3.17. Докааать, что есдн граф я-связен, то существует пара несмежных вершин, между которыми имеется я вершшпю непересекающихся простых цепей. Пояэаать такие, что эта условие выполняется для любых двух несмежных вершин я-свяаного графа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
