2.6   Экстремальные задачи, алгоритм Краскаля. Задача о четырех красках

Пусть у нас есть несколько деревень а, 6, с,..., которые нужно соединить сетью асфальтированных дорог; при этом стоимость /(а, 6) дороги для ка­ждой пары деревень {а, 6} известна. Как построить самую дешевую сетьдорог, выполнив условие, что из любой деревни можно проехать в любую другую по такой дороге Если у нас три деревни

д-2 дз

и /(01,02) < /(й2>яз) < /(аь аз); т0 ясно, что /(сц, аг) + /(а2, &з) является минимальным.

В случае 6 деревень, с указанным на рисунке распределением стоимости,

з

 

решение уже не является очевидным.

Пусть Є = (V, Е) - конечный связный граф и / : Е -4 И+. Укажем ал­горитм нахождения связного подграфа Т = (У, Е') графа Є, для которого значение

}(т)= £ /({*,»})

{ж,у}є£"

является минимальным из возможных.

Если такой подграф существует, то он является деревом, т.к. если а\а2 ■ ■ ■ ак-і - некоторый цикл в нем, то удаление ребра {ак-і, а\\ не нарушает его связ­ности, но уменьшает значение /(Г). Итак, если Т существует, то Т - де­рево. Алгоритм нахождения такого дерева (его предложил Д.Краскаль (Л.В.Кгшкаї, 1956)) назовем правилом экономичности, а само дерево назо­вем экономичным деревом. Алгоритм Краскаля:

Шаг 1. Выберем вершины а\:а2 Є V такие, что /({а\:а2}) - минимальное из возможных значений.

Шаг 2. Присоединим к вершинам а\:а2 и ребру е\ = {01,02} ребро е2 и соответствующую вершину) с минимальным значением /(е2) таким, чтополученные ребра не образуют цикла.

Предположим, что мы построили вершины {ах,..., а^+г} и соответству­ющие звенья (ребра) в1, ег,..., е&. Выберем самое дешевое ребро из Е \ {в1,..., е^} такое, что его присоединение не приводит к появлению цикла.

Докажем, что так построенное экономичное дерево Т действительно явля­ется минимальным из возможных. Так как среди подграфов С существуют деревья с числом вершин, равным порядку С, и их общее число является конечным, то, очевидно, существует и минимальное дерево То, т.е. /(То) является минимальным из возможных. Занумеруем ребра {е\, е2:..., еп^\} экономичного дерева Т в порядке их присоединения. Если То ф Т, то пусть в{ = {а, 6} - первое ребро, не принадлежащее Е(То). Пусть Р - цепь дерева То, соединяющая (в То!) вершины а и Ъ :

Так как Т не содержит циклов, то найдется ребро е- в пути Р такое, что е- 0 Е(Т). Рассмотрим дерево Тд = (71) + {с/})\ {с-} (это связный граф сп = |С| вершинами и (п — 1) ребрами!). Так как /(Тд) = /(То) + /(е^) — /(е-) > /(То), то /(е^) > /(е-)- Так как /(е^) было минимальным, то /(е-) = /(е^) и /(Тд) = /(То). Но дерево Тд имеет с Т одним общим ребром больше, чем То. Рассуждая аналогично, мы докажем, что /(То) = /(Тд) = /(Т).

Во второй половине XIX века в Англии математиками Ф.Гутри, А.Де Морганом и А.Кэли была поставлена задача о возможности раскраски про­извольного многоугольного графа на плоскости при помощи четырех кра­сок так, что соседние страны имеют различный цвет. Следующий пример показывает, что 3-х красок может быть недостаточно

Ргде К, Б, 3, С - начальные буквы соответственного красного, белого, зеленого и синего цветов. В 1892 г. английский математик Хивуд доказал, что любую карту можно раскрасить пятью красками (см. теорему ниже). В 1976 г. американские математики К.Аппель и В.Хакен с помощью ЭВМ установили положительное решение данной проблемы.

Сначала уточним понятие многоугольного графа С(У, Е). Это конечный плоский связный граф, в котором ни один многоугольник не лежит вну­три другого. Граничные ребра многоугольника образуют цикл, внутренняя часть которого называется грань графа. Цикл графа, окружающий весь граф, называется максимальным, а его внешняя часть называется беско­нечной гранью (-Роо).

Пример (многоугольного графа).

 

Теорема 7(Хжвуд).Каждый многоугольный граф С = (У, Е) можно рас­красить пятью красками.

Замечание 1. Можно считать, что граф Є не содержит вершин степени два.

ДОКАЗАТЕЛЬСТВО. Действительно, если существует такая вершина а Є У, что р(а) = 2е

то, удаляя эту вершину и объединяя инцидентные с ней два ребра еі, е2 в одно ребро е, мы получим многоугольный граф С. Раскрашивание графа С пятью красками влечет за собой искомое раскрашивание графов С

Замечание 2. В силу замечания 1 степень каждой вершины графа Є не меньше 3. Оказывается, мы можем свести нашу задачу к однородным графам степени 3.

ДОКАЗАТЕЛЬСТВО. Действительно, если существует вершина а £ V такая, что р(а) > 4, то проведя достаточно малую окружность с центром в точке а и удаляя вершину а с частями ребер, лежащими внутри этой окружности, мы получим новый граф С, в котором вместо вершины а появились вершины аі,..., ак(к > 4) степени 3 (см. рис.)

 

Раскрашивание графа О' пятью красками влечет за собой очевидное ис­комое раскрашивание графа С

Замечание 3. Итак, мы можем считать, что С = (V. Е) это связный плоский (конечный) однородный степени 3 граф.

Докажем, что он содержит грань, ограниченную не более 5 ребрами. Рассмотрим равенства: 2 + р = Ь + г (формула Эйлера), 36 = + 3<^з+ +4(^4 + ..., где ірк - число граней с к ребрами и к вершинами. Выразим число ребер р и число граней через ір2, <^з,... следующим образом:

2р = 2ио2 + 3(^з + 4У", + ...,

Г = Ц>2 + Ц>3 + Щ + • • • •

Подставив выражения г,р, Ъ через (р2, <рз, • • • в формулу Эйлера, имеем

Следовательно, одно из чисел у->. у-л- ^і- V"» больше нуля.

ДОКАЗАТЕЛЬСТВО теоремы. Минимально возможное число граней для однородного графа степени 3 равно 4 и, следовательно, для такого графа теорема справедлива. Предположим, что теорема верна для графов с числом граней, меньшим числа \Е(Є)\. Случай 1. Граф Є содержит кратные ребра, т.е. ір2 > 1 :

Исключив вершины а, 6 и ребро е\, а ребра ез,е2,в4 заменив на един­ственное ребро е (см. рис.), мы получим новый граф:

а

Ясно, что раскраска нового графа (а она существует по предположению индукции) влечет искомую раскраску графа С

Случай 2. ір2 = 0, ірз > 1. Т.е. граф Є не содержит кратных ребер, но содержит треугольную грань:

12 = 4У"2 + 3(^з + 2(р4 + (р5 - (р7 - 2(р8

ас

Удаляя из Є\ ребро еі, вершины а и 6, а также "склеивая" ребра Є2,Є4 в ребро е', а ребра ез,Є5 в ребро е", мы придем к новому (однородному степени 3) графу С с меньшим числом граней. Из раскраски С, очевидно, следует искомая раскраска графа С

Случай 3. у-> = = 0. щ > 1. Т.е. граф Є содержит четырехугольную грань, но не содержит кратных ребер и треугольных граней:

При этом можно считать, что грани В и В не являются частями одной грани и не граничат друг с другом. Исключим ребра {а, 6}, {с, а7}, объеди­ним {аі, а}, {с, сі} и {а, с} в одно ребро {аі, сі}, а ребра {6і, 6}, {6, (ї7}, {оі, о1\} в ребро {6і,с?і}. Мы получим однородный (степени 3) граф Є\ с меньшим числом граней. По предположению индукции, для него существует иско­мая раскраска. Пусть, например, грани А я С раскрашены в цвета а и /3, а грань В + Я + В в цвет 7. Возвращаясь к графу Є, мы грани В я В оставляем окрашенными в цвет 7, а грань Я закрашиваем в 4-й цвет 5.

Случай 4. (р2 = (рз = <Р4 = 0, <£>5 > 1.

га

Рассмотрим фрагмент графа О

Е

 

Можно считать, что грани Л и С не являются частями одной и той же грани и не имеют общей границы. Исключим ребра {а, 6}, {с, а7} :

По предположению индукции, новый граф можно раскрасить в 5 цве­тов: а, /3,7, 5, р. Пусть, например, грани В, В,Е и (А + Т + С) раскрашены соответственно /3,7,5, а цветами. Восстанавливая граф С, мы оставляем раскраску прежней, кроме грани Т, которую закрашиваем в цвет р. Теоре­ма доказана.

Задача 32. Пусть С - многоугольный однородный степени 4 граф. То­гда С содержит либо 4 двухкратных ребра, либо треугольную грань. УКАЗАНИЕ. Имеем

^2п{р'^ 2р=^2 п{рт б+г = 2+р, г = ^2

п>2

п>2

п>2

ти

Откуда следует, что 46 + 4г = ^ (п + 4)<рп = 8 + ^ -" ' "г

п>2 п>2

8 = 2(^2 + <Рз ~~ ^5 ~~ 2(^6 — .... Если у-.>, = 0, то у-> > 4.

Задача 33. Исследовать возможные значения <^2, ^з, ^4 для многоуголь­ного однородного степени 5 графа.

Задача 34. Пусть С - планарный конечный граф. Число х((2) = (Ь — р) называется эйлеровой характеристикой графа С Доказать, чтоа) если С - связный граф, то х((2) < 1;

б) если С - связный граф, то х{@) = 1 тогда и только тогда, когда С -дерево;

в) если С - лес, то число деревьев в нем равно х(С).

Задача 35 (алгоритм выбора экономичного дерева в связном графе).

Пусть С = (У, Е) - конечный связный граф и / : Е -4 И+. Выберем любую вершину х\ £ У и выберем вершину #2, инцидентную #1, имеющую минимальное значение /({#!, жг}). Затем выберем жз, инцидентную одной из вершин х\,Х2 и имеющую с ними самое "дешевое" ребро. Пусть мы выбрали вершины Выберем среди вершин, инцидентных ука-

занным, вершину хк+1 0 {х\,..., хк}, имеющую самое "дешевое" ребро {хк+1,Х{},1 < к. Наш алгоритм останавливается на (п — 1) шаге. Про­верить, что в результате мы действительно получаем экономичное дерево.

УКАЗАНИЕ. Воспользоваться доказательством теоремы Краскаля.