1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 29
Текст из файла (страница 29)
Мы уже получаем некоторую ориентацию: далее если мы будем склеивать вершины в графе наудачу, мы будем иметь больше шансов на успех, если ограничим наш проиввол окрестностями 2-го порядка. Ограничение, требующее связности графа, нас, по-видимому, не смущает: будем красить каждую компоненту отдельно одними и теми >ко красками. Читатель может сразу проверить эффективность этой эвристики (склеивать с любой вершиной, находящейся на расстоянии 2), нарисовав серию графов и раскрасив их таким способом. Для ориентации на рис.
3.54 приведен граф, нарисованный в свое вре- 5 мя автором наудачу с един- г ствекным условием, чтобы 1 он был плоским. Здесь мы опять немного отвлечемся, чтобы сделать ряд практических замечений 5 к поиску примеров на рас- Ю краску графов.
Нам желай тельно знать, насколько 1 хороши наши раскраски. ! 9 В некоторых случаях изве- 18 6 « стен принципиальный пижз 6 ний предел числа красок 15 1« лля графов того или иного тП г вида (оценка снизу). В частности, для плоских графов, а 11« т. е. которые можно изебрарвс. 3.14. удачаое применение 1-й вить на плоскости без пере- эвристики. сечения ребрами друг друга, иавестно, что их хроматическое число не больше пяти, но и не меньше четырех (смыкание этих оценок и есть знаменитая,не решенная до сих пор проблема «четырех красокэ).
Далее, если граф содержит в себе в качестве подграфа и-полный подграф, то число красок никак не моягет быть меньше п. % ЗА. РАскРАскА ВВРшин ГРАФА, позгск Алговитмя 137 Так вот, если взять граф с рис. 3.14 и раскрасить его по эвристике, подсказанной теоремой 8 (мы будем называть это 1-й эвристикой), то, следуя заданной нумерации вершин (начиная с 1-й вершины и в ее окрестности склеивая с вершиной с наименьшим номером и обоаначая результат склеивания меньшим из двух рассматриваемых номеров), мы получим раскраску этого графа в три краски, показанные на.фигуре римскими цифрами.
Тот факт, что эта эвристика нетривиальна, показывает уже простейший пример рис. 3.15. Исходный граф — это шестиугольник с четным числом вершин и (вспомним ЗЗ из 1-й главы), хроматическим числом, равным двум. Склеивание вершин, находящихся на расстоянии 3, приводит к появлению треугольников (рис. 3.15, а)), и, стало быть, к увеличению хроматического числа, в то время как склеи- б) ванне по правилам 1-й эвристики сохраняет его (рис. 3.15, 6)). Этот же пример помогает нам понять, как можно было бы додуматься до только что доказанной теоремы. Назначение краски а на вершину и образует вокруг нее «меРтвУю зонУ» ггг(Р), гДе 4 краска а уже не может быть использована.
Минималь- Рвс. ЗЛЗ. Пример яетряввальяостя 1-й ность раскраснп означает, а) Пря склеивании появляются треугольчто на каждую краску при- яякя.б)Хромвтическоечвслосохраняегся. ходится «наибольшее» количество вершин. Увеличение числа вершин, окрашенных данной краской, ведет к росту мертвых зон. Когда эти зоны охватят весь оставшийся граф, данной краске уже нет места для использования. Мы будем получать выигрыш, если мертвые зоны, расползаясь по графу, будут по возможности больше перекрываться. Перекрытие мертвых зон двух несмежных вершин имеет место только тогда, когда они находятся на расстоянии 2, а степень перекрытия определяется числом разделяющих вершин. Так мы приходим к идее теоремы 8.
Напомним тем, кто не забыл своего детства, что аналогичную ситуацию мы имеем в игре в морской бой. Там каждый выбитый корабль показывает противнику аналогичную мертвую зону— гл. э. алгогитмизация смежные клетки, где нельзя ставить корабли. Любой искушенный игрок знает, что если поставить корабли просторно — вдали от стенок и друг от друга, то его флот будет быстро выбит, так как даже если в начале игры они понесут равные потери, его противник на будущее будет иметь в своей акватории существенно болыпнй запас пространства, не покрытого выстрелами. Оценка хроматического числа.
Доказанная теорема дает нам не только обнадеживающую эвристику, но н простую оценку числа красок, расходуемых при раскраске по 1-й эвристике. Эту верхнюю оценку мы получим как функцию числа вершин п и ребер р связного графа. В основе получения оценки будет лежать тот факт, что при склеивании вершин, находящихся на расстоянии 2, из графа исчезает хотя бы одно ребро (имеется хотя бы одна разделяющая вершина). Легко сообразить, что в связном графе число ребер р удовлетворяет следующим неравенствам: п — 1(р( Максчмалькое число ребер характеризует п-полный граф.
Рассмотрим теперь процесс склеивания вершин. Мы склеиваем вершины одну за другой, пока не получим некоторый й-полный граф (й ( п). Он будет иметь й(й — 1)!2 ребер. Так как при склеивании вершин, находящихся на расстоянии 2, из графа удаляется по крайней мере по одному ребру, то з итоговом графе число ребер будет меньше исходного. Число исчезнувших ребер з = р — й(й — 1)!2.
В силу сделанного замечания з ь п — А., где (и — й) — общее число склеиваний. Отсюда получаем неравенство р — )п — й, ь (ь — 1) 2 которое после простых преобразований приобретает вид йд — Зй — 2 (р — и) (О, Положительный корень уравнения ) З+Уз+Вддд — пд 2 $ Отсюда мы видим, что лдобое положительное й, удовлетворяющее уравнению (1), не должно превышать целой части от й+, откуда мы получаем следующую оценку хроматического чнсйа т (яг) м числа красок йд(6~), получающегося при раскраске по первой эзристике (6„"— связный граф, имеющий и вершин и р ребер) хИ )(ь,(О )(( ~ 1. ~2~ В упрощенном виде, показывающем лишь степень роста оценивающей функции, оценка имеет вид Ьд(С"„) ж ЗР'(р — и)(2.
$3.4. РАСКРАСКА ВЕРШИН ГРАФА. ПОИСК АЛГОРИтмА' «зэ Пользуясь этой формулой, можно наглядно представить оценку эффективности описанного алгоритма раскраски в виде графика. Поскольку оценка является функцией двух переменных, мы приведем график?э, как функции п (охватив диапазон более или менее реальных масштабов задачи раскраски в интересах экономии памяти от п = 50 до п =- 500), взяв для р случай «плотных» графов, когда р, скажем, лишь вполовину не дотягивает до числа ре- л — э бер полного графа: р = —, и случай более разряженных гра- 4 фов, когда число ребер пропорционально числу верш«ш, например, 00 а~ 100 000 100 000 и Рис. ЗЛЭ.
Эффективность 1-й эвристики р = э0 п. Полученный график показывает (рис 3.$6), что экономия памяти, производимая раскраской графа несовместимости, может быть весьма существенной. Об исчезающих ребрах. На этом, однако, наша эксплуатацэя теоремы о соцветных вершинах не оканчивается. Ход рассуждений при доказательстве верхней оценки хроматического числа как функции числа вершин и ребер связного графа поаволяет нам еще раз взглянуть на проблему раскраски в целом. В чем состоит раскраска? В последовательности склеивания вершин графа.
Когда она аавершается? Когда при склеивании получится полный граф. Чем он характеризуется? Максимальным отношением числа ребер к числу вершин, равным (й — 1)!2. Во всех неполных графах это отношение меньше. Почему процесс склеивания вершин не доходит, как правило, до лредела? (Кстати говоря, каков этот предел для свяаного графа, имеющего более одной вершины?) Потому, что при склеивании вершин граф становится как бы «гуще», относительная доля ребер увеличивается, Гл.з. Алгогитмизлция достигая в какой-то момент насыщения (й()с — 1)/2 ребер на и вершин). Тем самым мы будем получать тем лучшие варианты г Ж0 сг ггггггг р гг Рис. ЗЛ7.
График убывания числа вершин и реоер прп склеивании вершви графа. г — первая эвристика, 2 — вторая овристика, 8 — третья евристика. раскраски, чем позже допустим образование полного графа при последовательных склеиваниях. Давайте в атом разберемся подт робнее. Будем иаображать баланс числа вершин и ребер при «3.«.
РАскРАскА ВеРшиы ГРАФА. пОиск АПГОРитмА 444 склеивании вершин графа в виде графика. По оси абсцисс (рис. 3,17) будем откладывать число й склеиваний вершин. На графике изобразим прежде всего число вершин в графе как функцию числа склеиваний. Это будет функция у = и — й. Затем для каждого й отложим вдоль оси ординат число ребер, которое имеет полный граф с и — й вершинами. Это будет нисходящая ветвь параболы у = ((и — й)г — и + к)I2, пересекающая ось ординат в точке п(п — 1)/2 и в точке и — (« = 3 пересекающая функцию числа вершин графа (в треугольнике число вершин и ребер равно). Отложим, наконец, на оси ординат число ребер р некоторого свяаного графа СР. При склеивании вершин будем для каждого 7« отмечать число ребер в получившемся графе.
У нас получится своего рода траектория убывания числа ребер. Как только эта траектория уткнется в ограничивающую параболу, процесс склеивания обрывается: мы достигли насыщения. Если при каждом склеивании у нас исчезает ровно одно ребро, траектория будет иметь зид прямой у = р — )г. Абсцисса )гв точки пересечения этой прямой с «параболой насыщенняз дает гарантируемую 1-й 'эвристикой оценку числа красок, равную и — й*. Отсюда сразу напрашивается вывод: Т е о р е м а 9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
