Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 106
Текст из файла (страница 106)
ДОКАЗАТЕЛЬСТВО. Поскольку непустой планарный граф С не может быт раскрашен О цветами, то Са(О) = О. Если граф С имеет две или более вершин, то поскольку граф С связный, существуют две смежные вершины и граф С не может быть раскрашен одним цветом. Поэтому Са(1) = О. Но значение Со(1) равно сумме коэффициентов многочлена С~(Л), поэтому сумма коэффициентов многочлена Сс(Л) равна О. Использование равенства Сск(Л) = Со(Л)+Си, (Л) используется двумя способами. Предположим, имеется граф С;, тогда можно найти многочлен Сак(Л), выраженный как сумма многочленов Со(Л) и Сд, (Л). Но граф С по сравнению с С; имеет дополнительное ребро и, таким образом, увеличивает количество ребер, а граф Су„в котором две вершины графа С; отождествлены, уменьшает количество вершин. В конце концов получим полные графы.
Теоретически — это ответ, но, возможно, не самый простой. 692 ГЛЯВЯ 14. Некоторые специапьные вопросы теории графов Предположим, например, что требуется найти хроматический многочлен для графа, изображенного на рис. 14.57. Если положить е = (а,б), а Се будет вышеупомянутым графом, в этом случае С вЂ” граф, изображенный на рис. 14.58, а С1, — граф, изображенный на рис. 14.59. о б о а Ь а Ь Рис. 14.5В Рис.
14.57 Рис. !4.5д Следовательно, Сс/г (Л) = Сс/ (Л) + С1,. Если 7 — РебРо (с,/!) и С = С'-, тогда С' — граф, изображенный на рис. 14.60, С11 — граф, изображенный на рис. 14.61, аа — — вЬ Рис. 14.50 Рис. 14.б1 и С~, (Л) = Сс (Л) + Сс/ (Л). Но С' является графом Кв, поэтому ! // С (Л) = Л(Л вЂ” Ц(Л вЂ” 2ИЛ вЂ” 3).
Граф С11 является графом Кз, поэтому Са, (Л) = Л(Л вЂ” 1)(Л вЂ” 2). Следовательно, Сс/(Л) = С~, (Л) = Сс/ (Л) + Сс, (Л) = = Л(Л вЂ” 1)(Л вЂ” 2)(Л вЂ” 3) + Л(Л вЂ” 1)(Л вЂ” 2) = = Л (Л вЂ” 1) (Л вЂ” 2) (Л вЂ” 2) . Пусть д = (с,И) н С1, — граф С'-'. Тогда граф Си изображен на рис.!4.62, граф С11 — на рис. 14.63, сгс — уо а Рис.
14.бЗ Рис. 14.б2 РЯЗДЕЛ 14.3. Раскраска арафоа 693 и С~„(л) = Со (Л) + Со, (Л). Но Си является графом Кз, поэтому Сс" (Л) = Л(Л вЂ” 1)(Л вЂ” 2). С4и является графом Кз, поэтому с~„(л) = л(л — ц. Следовательно, Со.=с~ (Л)=со (Л)+Со (Л)= = Л(Л вЂ” 1)(Л вЂ” 2) + Л(Л вЂ” 1) = = Л(Л вЂ” 1)(л — 1). Таким образом, Со.
(Л) = Со(Л) + С, = = Л(Л вЂ” 1)(Л вЂ” 2)(Л вЂ” 2) + Л(Л вЂ” 1)(Л вЂ” 1) = = Л(Л вЂ” 1))(Л вЂ” 2)(Л вЂ” 2) + (Л вЂ” 1)] = = л(л — 1)(л' — зл+ з). Второй метод использования равенства Со,(Л) = Сс(Л) + Со, (Л) является рекурсивным, в котором данное равенство записывется в виде Со(Л) = Сст,(Л) — Ссг,.(л). Согласно этому методу удаляем ребра и склеиваем вершины, уменьшая количество ребер и вершин в графе до тех пор, пока это возможно, и, если необходимо, получаем изолированные вершины.
Рассмотрим тот же граф на рис. 14.64. Если предположить, что С является этим графом, и удалить ребро (а,4, то Са — граф, изображенный на рис. 14.65, а С~, — на рис. 14.66. а~ — юЬ с с Ь Рис. 44.66 Рис. 14.66 Рис. 14.64 Если для раскраски графа Са используется Л цветов, то и для раскраски вершины а можно использовать Л цветов, а для раскраски любой другой вершины можно использовать Л вЂ” 1 цветов, поскольку каждая из оставшихся вершин может быть окрашена в любой цвет, отличный от цвета предыдущей вершины. Таким образом, с ,.(л) = л(л — 1) .
Граф Су, = Кз, так что са,.(л) = л(л — 1)(л — 2) 694 ГЛАВА 14, Некоторые специальные вопросы теории графов и С~г(Л) — Сд,,(Л), С~(л) = С~г(л) — С~, (Л) = Л(Л 1)з + Л(Л 1)(Л 2) = л(л — ццл — ц' — (л — 2)) = Л(Л вЂ” 1)(Лз — ЗЛ + З), и этот результат, к счастью, совпадает с вычисленным ранее. Проблема четырех красок эквивалентна утверждению, что для каждого планарного графа С значение Са(4) ф О. Как уже отмечалось, проблема четырех красок в течение долгого времени оставалась нерешенной. На это были две весомые причины. С одной стороны, проблема столь проста, что ее можно было объяснить любому, и все же она оставалась нерешенной.
Проблема впервые была сформулирована в 1852 Фрэнсисом Гутерье (Егапс!з Оцйег!е), учеником Огюста де Моргана (Ацдцз!цз Ре Могдап). Некоторые математики посвятили жизнь решению этой проблемы. Существовало достаточно много "доказательств" проблемы четырех красок, найденных любителями и профессиональными математиками. В 1880 году казалось, что Альфред Бэй Кэмпе (А!!геб Вау Кегпре) [60] решил проблему. Однако, в 1890, П. Дж, Хивуд (Р. 3. Неаюооб) (42) нашел в его доказательстве ошибку. Модифицировав доказательство Кемпе, П. Дж. Хивуд смог доказать, что произвольную плоскую карту можно раскрасить пятью цветами. ТЕОРЕМА 14.67. Произвольный планарный граф С можно раскрасить, используя только пять цветов.
ДОКАЗАТЕЛЬСТВО. В соответствии с доводами, принятыми ранее, предположим, что граф С связный. Помимо этого будем считать, что граф С изображен так, что никакие из его ребер не пересекаются. В доказательстве используется индукция по количеству вершин. Если граф включает только одну вершину (фактически пять или менее), то, несомненно, такой граф можно раскрасить, используя только пять цветов.
Предположим, что при раскрашивании произвольного графа с й вершинами используются только пять цветов. Пусть С вЂ” граф с й+ 1 вершиной. По теореме !4.49 граф имеет вершину степени 5 или менее. Пусть и — такая вершина. Пусть С' — подграф графа С, в котором удалена вершина и и все инцидентные ей ребра. Поскольку в графе С' только й вершин, то по индуктивному предположению граф С' можно раскрасить, используя только пять цветов. Если степень вершины и меньше пяти, тогда в графе С она является смежной с четырьмя или менее вершинами и, следовательно, может быть раскрашена цветом, отличным от цветов смежных вершин.
Раскраска завершена. Поэтому предположим, что степень вершины и равна 5. В этом случае вершина и смежная с пятью вершинами графа С, назовем их иыиз,из,иг и иь. Если какие-либо вершины из этих пяти имеют одинаковый цвет, то для их окраски использовано только четыре цвета, и можно снова выбрать неиспользованный цвет для окрашивания вершины и, в результате раскраска завершена. Поэтому предположим, что вершины и,,из,из,иг и из окрашены различными цветами.
Пусть 1,2, 3,4 и 5 — номера красок, которыми окрашены вершины им из,из, иг и из соответственно. Предположим для определенности, что вершины иыиз,из,и4 и из РЛЗДЕП 14.3. Раскраска графов 595 ч, ч Р~з чг ч„ чз ч Ч, Ч, ~к 3 Рис. 14.б7 Рис. 14.бб Во втором случае вершина о4 находится внутри цикла, а вершина оз— вне цикла. В каждом из случаев в графе С' не существует путь от вершины оз к вершине ок, проходящий через вершины цвета 2 или 4.
Дело в том, что граф С планарный, поэтому его вершины не пересекаются, и переход из вершины оз в вершину о4 требует прохождения через вершину цикла оо1Р1зозо, а все эти вершины окрашены цветом 1 или 3, за исключением, возможно, вершины о, которая не принадлежит графу С'. Поэтому можно повторить изложенную выше процедуру, формируя граф Сзк вместо С13, и раскрасить вершину о. ° УПРАЖНЕНИЯ 1.
Найдите графы, двойственные данным: а) 6) расположены по часовой стрелке вокруг вершины о. Начиная с вершины ч1 графа С', будем строить подграф Сш графа С' следующим образом; множество вершин подграфа ч1з графа Сш состоит из вершины о1 и всех вершин графа С', которые могут быть связаны с о1 путями, проходящими только через вершины с цветом 1 или 3. Предположим сначала, что оз ф К1з. По построению графа Сш граф С' не содержит вершины, которые имеют цвет 1 или 3, не принадлежат множеству Ъгз и являются смежными с вершинами из 1'1з.
Поэтому в графе С1з цвета 1 и 3 можно поменять местами, не меняя цвета остальных вершин. Теперь вершины о1 и оз окрашены одним цветом и, согласно результатам, полученным ранее, граф С можно РаскРасить. Если оз е Ъ'гз, то сУществУет пУть из о1 в изб, котоРый проходит только через вершины, окрашенные цветом 1 или 3. Назовем этот путь Р,з.
Тогда путь оо,Ршозч является циклом и имеет форму, изображенную на рис. 14.67 или рис. 14.68. В первом случае вершина оз находится внутри цикла, а вершина ьа — вне цикла. 698 ГЛАВА 14. Некоторые специальные вопросы теории графов 6) а) г) в) д) 5.
Покажите, что двудольный граф К „всегда можно раскрасить двумя цве- тами. Определите хроматический многочлен графа К „? 6. Чему равно хроматическое число гиперкуба? 7. Используя теорему14.64, найдите хроматический многочлен каждого из приведенных графов: б) а) Л. с РАЗДЕЛ 14.3. Раскраска графов 599 в) г) а с Ь д) 8. Используя теорему 14.б4, найдите хроматический многочлен каждого из приведенных графов: б) а) 600 Гт1ЯВЛ 14.
Некоторые специальные вопросы теории грефое д) 9. Докажите, что если произвольный планарный граф с п вершинами изомор- фен своему двойственному графу, то он имеет 2п — 2 ребер. 10. Докажите, что если хроматическое число связного графа, имеющего, по крайней мере, одно ребро, равно 2, то он является двудольным. 14.4. ПУТИ И ЦИКЛЫ ГАМИЛЬТОНА В 1857 году математик Уильям Роуэн Гамильтон (%1Шагп йоиап Нагп1йоп) придумал игру. Существует несколько версий того, как это произошло.
По одной из версий он описал эту игру в письме к другу. Согласно другой, он действительно изобрел игру и продал ее производителю игрушек. В любом случае она, по-видимому, включала додекаэдр, т.е. правильный многогранник, 12 граней которого представляли собой конгруэнтные правильные пятиугольники. В каждом из 20 углов, или вершин тела, просверливалась дырка, в которую вставлялся колышек, изображавший город. Используя веревку, требовалось найти путь через города, посетив каждый город один раз, и вернуться в исходный город.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
