Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 104
Текст из файла (страница 104)
Значит, сумма ребер всех граней должна быть меньше, чем 2е. Объединяя эти неравенства, получаем, 4 Г < 2е, поэтому 4~ < 16. Но это противоречит тому, что Г = 5. Следовательно, мы пришли к противоречию, и граф Кз з не является планарным. Теперь докажем, что полный граф Кз, изображенный на рис. 14.33, не является планарным. Для этого нам необходима лемма (так называется теорема, которую используют для доказательства другой теоремы).
а Ь 4 Рис, 14.33 ЛЕММА 14.47. В произвольном связном планарном графе С с количеством вершин не менее трех имеет место неравенство Зи — е > 6. ДОКАЗАТЕЛЬСТВО. Если граф С не имеет циклов, то в нем количество ребер меньше количества вершин: е < и. Учитывая также, что и > 3, 2и — 6 > О, получаем, е < и + 2и — 6 = Зи — 6 или Зи — е > 6. Если граф С содержит цикл, опять суммируем ребра, ограничивающие грани.
Поскольку граница каждой грани включает не менее трех ребер, то сумма ребер всех граней должна быть больше Зг". Но каждое ребро может быть границей не более двух граней (см. предыдущее доказательство), поэтому количество ребер должно быть меньше 2е. Следовательно, 3 1' < 2е и 2 = и — е+ г", откуда 6 = Зи — Зе+3 Г < Зи — Зе+2е = Зи — е иЗи — е>6. ТЕОРЕМА 14.48. Полный граф Кз не является планарным. ДОКАЗАТЕЛЬСТВО. Граф Кз имеет пять вершин и десять ребер, Зи — е = 3 5— 10 = 5, поэтому, согласно предыдущей лемме, граф Кз не является планарным.
° РАЗДЕЛ 14.2. Планарные графы 583 Используя предыдущую лемму, докажем еще одну теорему, которая будет использована в следующем разделе для доказательства того, что планарный граф можно раскрасить, используя не более пяти цветов. ТЕОРЕМА 14.49. Каждый планарный граф С содержит вершину степени 5 или менее. ДОКАЗАТЕЛЬСТВО. Для каждого ребра имеется две вершины (см.
главу 2), каждое ребро вносит число 2 в сумму степеней вершин. Поэтому сумма степеней вершин равна 2е. Если в графе С не более двух вершин, то, очевидно, вершины имеют степень 5 или менее. Отсюда предположим, что имеются три и более вершин. Тогда по предыдущей лемме имеем е < Зи — 6, поэтому 2е < 6о — 12. Но если степень каждой вершины больше или равна 6, то сумма степеней вершин больше или равна бо. По условию сумма степеней вершин равна 2е, поэтому 2е > бо. А это невозможно, поскольку 2е < би — 12. Следовательно, существует вершина со степенью не более 5. Доказательство следующей теоремы предоставляется читателю. ТЕОРЕМА 14.50. Если два связных графа гомеоморфны, то они либо оба планарны, либо оба непланарны.
Из этой теоремы вытекает непосредственно следующая теорема. ТЕОРЕМА 14.51. Произвольный граф, гомеоморфный графу Кз 3 или Кз, не является планарным. Поскольку любой граф, содержащий непланарный подграф, является непланарным, это доказывает часть приведенной ниже теоремы. Остальную часть утверждения примем без доказательства. ТЕОРЕМА 14.52. (Куратовскмй) Граф является планарным тогда и только тогда, когда он не содержит подграф, гомеоморфный Кз 3 или Кы ПРИМЕР 14.53. Покажем, что граф, изображенный на рис.
14.34, является планарным. Учитывая, что граф состоит из двух компонент, можем отделить их и образовать граф, изображенный на рис. 14.35, который, очевидно, является планарным. Рис. 14.33 Рис. 14.34 ПРИМЕР 14.54. Покажем, что граф, изображенный на рис. 14.36, является планарным. Передвигая вершину г(, получаем более простой граф, изображенный на рис. 14.37. Передвигая вершину с, получаем граф (рис. 14.38), который, очевидно, является планарным. 584 ГПАВА 14. Некоторые специальные вопросы теории графов а Ь Рис. !4.38 Рис. !4.3б Рис. !4.37 ПРИМЕР 14.55. Покажем, что граф Петерсена, изображенный на рис. 14.39, не является планарным.
Покажем, что граф содержит подграф, гомеоморфный Кз з. Единственная трудность — выбрать правильное множество вершин. Если в качестве верхних вершин выбрать е, ! и д, а в качестве нижних — 3, а, и 1 и соединить каждую верхнюю вершину с каждой нижней вершиной, получим граф, изображенный на рис. 14.40.
Отсюда видим, что вершина с не нужна, поэтому вершину и все ребра, инпидентные ей, удаляем. Все остальные ребра пока присутствуют. Теперь можем удалить вершины 6, Ь и Ы, формируя ребра ( 7,31, (а, 91, (е,1), соответственно, и получить граф, изображенный на рис. 14.41, который является гомеоморфным предыдущему графу.
Но этот граф может быть изображен как Кз з. Следовательно, граф Петерсена содержит подграф, гомеоморфный Кз з, и поэтому не является планарным. / а ! а Рис. !4.4! П Рис. !4.39 Рис. !4.40 ° УПРАЖНЕНИЯ 1. Каждый из приведенных ниже графов проверить на планарность. Ответ аргументируйте. а) б) ,Д РАЗДЕЛ 14.2.
Планарныа графы 685 в) г) д) 2. Для каждого планарного графа из предыдушего упражнения проверить, что ю — е + 1" = 2. 3. Каждый из приведенных ниже графов проверить на планарность. Аргументировать решение. а) б) а Ь с И г) 686 ГЛАВА 14. Некоторые специальные вопросы теории графов д) 4. Для каждого планарного графа из предыдущего упражнения проверить, что и — е+г"=2. 6.
Если планарный граф содержит 12 вершин со степенью 3, то сколько у него ребер и граней ? 6. Если планарный граф имеет вершины со степенями 2, 2, 2, 3, 3, 3, 4, 4, 4 и 5, соответственно, то сколько у него ребер и граней? 7. Найдите значение величины и — е + 7" для графа, у которого а) две компоненты; б) три компоненты; в) й компонент.
8. Если С вЂ” планарный граф, у которого и вершин и каждая грань графа С ограничена циклом длины 3, найдите зависимость количества граней и ребер от числа п. 9. Докажите, что произвольный граф с четырьмя вершинами является планар- ным. 1О. Докажите, что граф с пятью вершинами, одна из которых имеет степень 2, является планарным. 11. Используя метод индукции, докажите, что дерево является планарным гра- фом. 12. Докажите теорему 14.50.
Если два связанных графа гомеоморфны, то они или оба планарны, или оба непланарны. 14.3. РАСКРАСКА ГРАФОВ Одной из наиболее известных нерешенных проблем на протяжение многих лет оставалась так называемая проблема четырех красок. Она возникла в связи с раскрашиванием географических карт и заключается в следующем: карту нужно раскрасить, используя только четыре цвета, так, чтобы любые две граничащие страны были раскрашены разными цветами. Известно, что для раскрашивания карты пяти красок достаточно, а трех — нет. Для карты, нанесенной на тор, минимальное количество красок было определено, но проблема четырех красок оставалась нерешенной. На сегодняшний день она решена, но, возможно, не самым лучшим способом.
Решение потребовало длительной проверки компьютером огромного числа случаев, которые иначе проанализировать не удавалось. Хотя сам по себе метод является выдающимся достижением и вполне достаточен, чтобы прекратить поиски контрпримера, было бы неплохо, если бы кому-то удалось РАЗДЕЛ 14.3. Раскраска графов 887 найти более элегантное доказательство гипотезы. Самое замечательное в этом доказательстве — то, что оно расширило наше представление о математическом доказательстве. Рассмотрим карту, изображенную на рис, 14.42. Рис. 14.42 Если левая часть карты закрашена красным цветом, то при закрашивании примыкающих центральных граней чередуются синий и зеленый цвета. Правую грань снова можно закрасить красным цветом, поскольку, как следует из рис.
14.43, она не граничит с левой гранью. з к с к Рис. 14.43 При изображении карты с помощью графа естественно использовать ребра в качестве границ, а грани — в качестве стран, так что карта, изображенная на рис. 14.44, А В С0 Рис. 14.44 превращается в граф, изображенный на рис. 14.45. Рис. 14.45 Однако, вместо использования такого графа лучше сделать некоторые изменения.
Гораздо удобнее работать с двойственным графом С' планарного графа С, который формируется путем замены граней (или стран) вершинами и соединения их ребрами, если грани в исходном графе смежные. Следовательно, в двойственном графе С' вершины являются смежными тогда и только тогда, когда соответствующие грани являются смежными в исходном графе С. Таким образом, двойственным к рассматриваемому графу становится граф, изображенный на рис.
14.46. Внешняя грань будет включаться как вершина в том случае, если она раскрашена. Рис. 14.4б 588 ГЛАВА 14. Некоторые специальные вопросы теории графов ПРИМЕР 14.56. Для графа С, изображенного на рисунке 14.47, двойственным является граф С' (рис. 14.48), поэтому в данном случае граф С изоморфен графу С! дфва а е Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
