Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 28
Текст из файла (страница 28)
Любой другой связный плоский граф может быть порожден из графа с меньшим количеством вершин или ребер одной из следующих операций. 1. Добавление вершины сте цен и 1. Вне связного плоского графа 6, т. е. в некоторой области г, ставится вершина р и соединяется ребром д с некоторой вершиной графа 6, расположенной на границе области г (рис. 4.24). Ясно, что в других областях ничего не меняется, но то, что 1~ область г остается связной, г требует доказательства (хотя и очевидно). Мы его не приводим, так как оно требует довольно глубокого знания топологии плоскости. У нового связного плоского графа 6' количества вершин й ребер на Рис. 4.Я 1 больше, чем у графа 6, а ко- личество областей — такое же. 2.
Добавление верш и ны степе н и 2. Внутри некоторого ребра д связного плоского графа 6 ставится вершина р. Таким образом,это ребро разбивается на два— д' и д" (рис. 4.25), т. е. в новом связном плоском графе 6' на одну вершину и на одно ребро больше. Вне графа ничего не меняется, значит, число областей остается тем же. 3. Разбиение области. Новое ребро д соединяет вершины р' и р", расположенные на границе области г, и лежит в этой области (рис. 4.26). Из известной теоремы Жордапа следует, что область разбивается на две — г' и г". Рис. 4.26 Значит, в графе 0' на одно ребро и на одну область больше, чем в графе 6, а количество вершин то же.
Для доказательства возможности породить при помощи указанных операций любой связный плоский граф используем обратные операции: удаление вершин степени 1 и 2, а также разрыв цикла. Пусть дан не минимальный связный плоский граф 0' с о' вершинами и е' ребрами. Если в нем есть вершина р' степени 1 или 2, то можно произвести операцию ее удаления, причем получится связный плоский граф 0. Обратно граф 0' может быть получен из графа 0 операцией добавления вершины степени 1 или 2.
Пусть теперь степени всех вершин графа 6' не меньше, чем 3. Сложим все эти степени ар (р'ен0'). Сумма равна удвоенному числу ребер 2е', так как каждое ребро увеличивает на 1 степени двух вершин. С другой стороны, она не меньше утроенного числа вершин, так как степень каждой вершины не меньше, чем 3.
Таким образом, 2е'=~)3о'. Р'~п Цикломатическое число графа 6' равно е' — о'+1~ ~)3/2о' — о'+1)О, значит, в нем есть некоторый цикл 2. Если удалить из 0' какое-нибудь ребро д' цикла Е, то граф останется связным. Обратно граф 6' может быть получен из связного плоского графа 0 операцией соединения вершин р' и р" ребром д', Так как при этом возникает новый цикл Л, область г, по которой проходит ребро д', разбивается на две. Теорема Эйлера (о многогранниках).
Пусть Р— выпуклый многогранник. Эйлер доказал, что количества его вершин о, ребер е и граней я связаны соотношением о — е+ ,+у=2. Выпуклый многогранник можно спроектировать из внут- 1З9 ренней точки На поверхность сферы, а с последней — на плоскость. При атом его вершины перейдут в вершины некоторой карты, ребра — в ее ребра, грани — в области (одна область будет внешней). Оказывается, соотношение Эйлера справедливо для количеств вершин, ребер и областей любого связного плоского графа.
Теорему Эйлера легко доказать по индукции. В минимальном связном плоском графе бз одна вершина, одна область и нет ребер. Соотношение Эйлера для него выполняется. Пусть оно выполняется для всех связных плоских графов с е ребрами, и 6' — произвольный связный плоский граф с и' вершинами, е'=е+1 ребрами и г' областями. Уже было показано, что он может быть получен из некоторого связного плоского графа б с е ребрами при помощи одной из указанных выше операций.
Пусть о — количество вершин графа 6, г — количество его ребер. Если граф б' порожден из него при помощи первой или второй операции, то и'=и+1, я' д; если при помощп третьей, то и'=и, д'+1. В обоих случаях и' — е'+а'=и — е+И= =2.
С) Неизбегаемые наборы конфигураций. Можно показать, что в любой триангуляции плоскости б есть вершина, степень которой не больше, чем 5. Пусть о — число вершин триангуляции, е — число ребер, д — число областей. Последние имеют Зп граничных ребер, но каждое ребро является границей двух областей. Следовательно, 2е=Зу, т.е. у=2)Зе. С другой стороны, как уже отмечалось, 2е= = ~чг~ п„где лг — степени вершин триангуляции.
Кроме тогяа го, и= »",1. Подставим эти значення о, е и д в соотношение ебв Эйлера 2 = и — е+ д = о — е+ 2!Зя = о — 1/Зе = '~~1 — 1Я ~~~~~п = 1!5 ~~!У ~(5 — и ) Р~--6 Р(=6 г~а Отсюда ~ (6 — и„) =12. гяе В левой части положительны только члены суммы с 2— 5 степенями (можно показать, что вершины степени 1 в триангуляции нет), и, так как вся сумма положительна, такие члены существуют, что и требовалось доказать. Таким образом, набор конфигураций, состоящий из вершин степеней 2 — 5 (рис. 4.27), обладает тем свойством, что 140 Рис. 4.27 Рис.
4,28 141 в любой триангуляции плоскости есть хотя бы одна конфигурация нз этого набора (на самом деле их больше). Такие наборы конфигураций называются неизбегаемыми. Приведенный выше набор — не единственный. Ниже будут приведены еше два примера. В оба входят вершины степс- т/к пей2,3и4. Каждая вершина р триангуляции О дает в приведен- т/ Ь ную выше сумму, полученную из соотношения Эйлера, вклад, равный (6 — и„), где ир — ее степень. Эти вклады можно различным образом перерас- У/~ «/б пределить между соседними вершинами.
Например, оставим при каждой вершине степеней 6, 7... их вклады, а вклады вершин степени 5 перенесем в соседние вершины, распределив их поровну (рис. 4.28). Пусть т — количество вершин степени 5, соседних с вершиной р триангуляции 6. Новый вклад вершинбя р равен тр/5, если ее степень равна 5, и 6+та/5 — ир, если она больше. Легко видеть, что 12 = ")' (6 — ир) = "~' ур/5+. )' (6+ ур/5 — ир) = рба б Р(=о,бр — — б реб,п >5 р ~~Р тр/5 + ')~~ (6 + тр!5 — ир). р~й,бр<с Р~с,п >б Значит, в последней сумме есть положительные члены, Все члены первой суммы положительны, но они присутствуют только в случаях, когда в триангуляции б есть расположенные рядом две вершины степени 5 или степеней 5 и 6 (рис.
4.29). Для исследования слагаемых первой суммы заметим, что т„я.=пр. Значит, 6+чл/5 — пр~6 — 4пр/5. При п„~8 6 — 4п,/5 О. Остается исследовать случай па=7 6+т„/5— — ир О, т.е. т„/5)1, откуда следует тр~б. Однако, если среди соседей вершины степени 7 есть шесть вершин степени 5, то среди последних есть соседи между собой, До- Рис. 4,29 Рис 4.80 статочно даже, чтобы были четыре соседние вершины степени 5 (вообще, когда у вершины степени й больше, чем й/2 соседних вершин имеют степень 5, среди них есть соседние между собой). Итак, в триангуляции 6 есть либо вершины степеней 2, 3 или 4, либо конфигурации, изображенные на рис. 4.29.
Можно указать несколько иной набор конфигураций: вместо двух соседних вершин степеней 5 и 6 он содержит конфигурацию из трех взаимно соседних вершин степеней 5, 6 и 6 (рис. 4.30). Если в триангуляции нет вершин степеней 2, 3 и 4, двух соседних вершин степени 5 и указанной выше конфигурации, то у каждой вершины степени 5 не менее трех соседей имеют степени, большие, чем 6. Будем переносить положительные вклады вершин степени 5 только в соседние вершины со степенями 7, 8, ., причем поровну. Значит, в каждую из этих вершин перенесем ие больше, чем тр/3, т. е.
новые вклады вершин будут не больше, чем 6 — пр+тр/3. Среди ннх должны быть положительные, но условие 6 — пр+тр/3)0 при пр —— 7 дает тр~3, при ар — — 8 тр)6, а при пр)9 оно невозможно. Таким образом, в триангуляции б есть либо вершина сте. пени 7, у которой четыре соседа имеют степень 5, либо 142 вершина степени 8, у которой есть семь таких соседей. Однако в обоих случаях две вершины степени 5 должны быть соседними.
Основная идея. Если бы существовал нецзбегаемый набор, состоящий только из редуцируемых конфигураций, то минимальным нераскрашиваемым графом, о котором уже говорилось, мог бы быть только граф б, с единственной вершиной. Однако его можно раскрасить даже в один цвет. Значит, минимального нераскрашиваемого графа не существовало бы. Но тогда все связные плоские графы можно было бы раскрасить в четыре цвета.
Таким образом, чтобы доказать гипотезу о четырех красках, достаточно найти неизбегаемый набор редуцируемых конфигураций. Приведенные выше примеры не подходят: вершины степеней 2, 3 и 4 редуцируемы, но редуцировать остальные конфигурации не удается. Однако нужно искать неизбегаемые наборы не для всех триангуляций, а только для тех, в которых степени всех вершин не меньше 5. Аппель и Хакен строили такие наборы, состоящие из большого количества конфигураций, при помощи разнообразных перераспределений вкладов вершин в сумму ~ч~(6 — пр). Но как проверить, что все входящие в набор р~в конфигурации редуцируемыу Методы редукции аналогичны тем, которые использовались при исследовании конфигурации, изображенной на рис. 4.22.
Из-за многочисленности вариантов применения этих методов рассмотреть их все удалось только с помощью машины. Была создана программа, производившая многочисленные попытки редуцировать предъявленные ей конфигурация, Все же она прекращала эти попытки, если ей не удавалось произвести редукцию за заранее заданное время. Тогда Аппель и Хакен строили новый набор, который такую конфигурацию не содержал (хотя, возможно, исключаемая конфигурация была редуцируемой). Так весьма быстродействующие машины проработали около 1500 ч, пока не был построен набор из !932 конфигураций, и машина показала, что !931 из них редуцируема. Оставшуюся конфигурацию исследовали вручную, применив более тонкие методы редукции. Она оказалась тоже редуцируемой.
Таким образом, проблема четырех красок была решена. Графы — язык дискретной математики. При формулировке задач дискретной математики или описании методов 143 их решений часто употребляется язык теории графов. Ряд примеров этого приведен ниже. Здесь же укажем лишь один достаточно общий способ постановки задач дискретной математики, при котором естественным образом возникает граф. Пусть рассматривается множество г' объектов и, каждый из которых может находиться в состояниях х, из заданного для этого элемента а множества состояний Х,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
