1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 28
Текст из файла (страница 28)
Уменьшение числа ребер па Ркс. ЗЛ2. Примеры склеиваний. одно будет иметь место а) С исчезновением рейер. б) Без исчезкоке- для любой вершины„ кия реоер. разделяющей а, и и, Таким образом, можно ааключить, что уменьшекне числа ребер графа 6 будет иметь место только при склеивании вершин, находящихся на расстоянии 2, при атом число исчезающих ребер равно числу разделяющих вершин. Все, что мы сейчас написали, есть просто аккуратное наблюдение процесса склеивания вершин, которое, быть. может, пригодится нам в будущем.
Для читателей, любящих наглядность, мы покажем на рис. 3.12 два варианта склеивания верпшн, а для педантичного читателя педчеркнем, что мы определяем понятие разделяющей вершины только для вершин, находящихся друг от друга на расстоянии 2. Возвращаясь к последовательным склеиваниям, мы обнаруживаем, ч о преобразования каждого очередного графа С продол-. 5 3.«.
РАскРАскА ВБРшин ГРАФА. поиск АЛГОРитмА 1зз »каются до тех пор, пока в нем не окажется ни одной пары несмежных вершин, т. е. пока 6 не окажется некоторым К-полным графом. Очевидно, что К-полный граф допускает только одну тривиальную раскраску: каждая из К вершин и красится своей краской, которая одновременно оказывается краской для всех вершин исходного графа, вклеенных в ш Поскольку зсе они попарно не смежны, такая раскраска оказывается допустимой, при этом порядок К результирующего полного К-графа есть число красок. Задача получения минимальной раскраски становится задачей построить такую последовательность склеиваний вершин исходного графа (еще одно замечание для любителей строгости: говоря о преобразовании исходного графа 6 в д р у г о й граф 6' мы тем пе менее можем «узнавать» в «другом» графе вершины исходного графа, при этом неважно, склеенные или не склеенные друг с другом), при котором порядок результирующего К-полного графа будет минимальным среди всех возможных, другими словами, будет равен д(6) (напоминаем: )~(6) — хроматическое число графа 6).
Продолжая наш анализ, мы усматриваем, что трактовка раскраски как попарного склеивания годится вполне и для второго подхода к алгоритму раскраски. Здесь мы тоже ищем какую-то пару незмежиых вершин и склеиваем ее. Разница между первым и вторым подходом теперь лишь в том, что в первом подходе мы вклеиваем все возможные вершины в одну, пока она не станет звездой, а во втором подходе мы, задавшись заранее некоторым порядком вершин, идем от одной вершины к другой, подыскивая ей подходящего напарника для склеивания. Сводя раскраску вершин графа к их последовательному склеиванию, нам нужно убедиться, что на этом пути мы ие утрачидаем потенциальной воэможности получить минимальную раскраску исходного графа.
Конечно, можно сразу сообразить, что если ваять некоторую минимальную раскраску в Х красок и склеить между собой все вершины, окрашенные одним цветом, то в результате у нас получится т-полный граф, однако на самом деле нам требуется болев сильное утверждение, которое мы оформим в виде теоремы.
Те о р е м а 7. Для всякого графа с хроматическим числом д существует последовательность попарних склеиваний вершин, приводяща к д-полному графу. Д о к а з а т е л ь с т в о. Назовем две вершины графа 6 соцветними, если существует минимальная раскраска вершин графа 6, в которой эти вершины окрашены одной краской. Л е м м а 1. В любом неполном графе 6 существует по крайней мере пара соц ещных вершин. Пусть в графе 6 содержится и вершин.
Если ни в одной минимальной раскраске нет двух вершин, окрашенных одной краской, значит, т(6) = и. Так как 6 — неполный граф, в нем есть хотя бы гл. ». хлго»итмизхция пара несмежных вершин п, и и». Склеим эти две вершины. Получившийся граф С' будет иметь и — 1 вершину, а стало быть, у(6') ( и — 1.
Взяв любую раскраску графа 6' в и — 1 'краску или менее, найдем в ней вершину, в которую были склеены о и и». Расклеив зти вершины «обратно», сохранив на их следы краски из раскраски 6', получим раскраску графа 6 в и — 1 или менее красок, что противоречит предположению т(6) = и. хг . Л е м м а 2. Если граф 6' получается иг графа С склеиванием пары соиветных в нем вершин, то у(6') = д(6). Действительно, взяв минимальную раскраску графа С, в которой указанные вершины окрашены одной краской, и сохранив как эту краску на вершине графа С', получившейся после склеивания, так и краски на остальных вершинах, получаем раскраску графа С' в у(6) красок.
Отсюда имеем, что д(6 ) ~ (~(6). Неравенство я«е )~(6 ) ~ )~(6) не может выполняться в силу рассуждения, проведенного в докааательстве леммы 1. ~7 На основе этих двух лемм получаем нужную последовательность склеиваний: в исходном графе С ищем пару соцветных вершин н склеиваем. В силу леммы 2 мы «не испортили» граф в том смысле, что его хроматическое число осталось неизменным.
В силу леммы 1 такое склеивание можно делать до тех пор, пока очередной граф не станет полным. Опять-тани в силу леммы 2 в нем ке может быть более, чем у(6) вершин. сус7 На этом мояшо считать законченным поиски общей организации алгоритма раскраски. Если бы мы умели легко находить соцветные вершины, то у нас был бы способ получения минимальных раскрасок. Мы еще не имеем прямого подхода к этому, но именно на это сейчас будет нацелен поиск подходящей эвристики выбора склеиваемых пар вершин. Теорема о соцветности.
Еще одно авторское отступление перед кульминацией нашего исследования. Деловой читатель, мгновенно усвоив основные определения и последующие за этим абзацем конкретные конструкции алгоритма, может счесть предыдущие несколько страниц каким-то невнятным текстолц тривиальнымк переформулнровками, топтанием на месте. Автор хочет защитить эту часть изложения. В меру своих литературных способностей он хочет показать ту подспудную работу, которую совершает исследователь в поисках решения. Во время таких хождений вокруг да около созревают идеи и наблюдения «второго плана», которые как раз-то и обеспечивают успех дела, когда найденный алгоритм или доказательство нанизывает эти предварительные находки на стержневую ось рассуждения или действия.
На самом деле в нашем, может быть, расплывчатом и повторяющемся изложении мы незаметно собрали все, что нам нужно для эффективных алгоритмов раскраски. Вот ключевые идеи н наблюдения: % 3 а РАскРАскА ВИРшиы ГРАФА. пОиск АлГОРитмА' 135 Л ° -кваска а а) + -краска/ Рнс. 3.13. Случаи доказательства теоремы 8. и Лг(о). Читателю легко проверить, что если в связном графе вер. шина — не звезда, то ее окрестности 1-го и 2-го порядков не пусты. Рассмотрим некоторую минимальную раскраску графа 6, в которой о получает краску а.
Если в этой раскраске некоторая вершина ю из Л,(о) тоже получает ату краску (рис. 3.13, а)), то теорема выполнена. Рассмотрим теперь случай, когда ни одна вершина из Лг(о) не имеет краски а. Возьмем в этом случае любую вершину ю из Л,(о), окрашенную некоторой краской р, и сосредоточим наше внимание на окрестности В,(о). Здесь опять-таки возможны два случая.
Если ни одна из вершин, принадлежащих Л,(о), не имеет краски р(рис. 3.13, б)), то тогда ничто не мешает нам перекрасить о краской (д, добившись тем самым въшолнения теоремы. Наконец, возможен случай, когда в Л,(и) есть несколько вершин, окрашенных в (). Обозначим эту подокрестность вершины о через Л'. Заметим, что для любой вершины и~Лд(о) ее окрестность Лд(и) с:. (Р) О Лд(о) Ц Вд(о) (рис. 3.13, в)).
Отсюда становится — направленность раскраски (не перекрашивать вершины); — отказ от гарантии получения минимальной раскраски; — понятие окрестности вершины 1-го и 2-го порядков; — раскрашивание как склеивание вершин; — разделяющие вершины как источник склеиваемых ребер. Сейчас мы покажем, как они, взаимодействуя друг с другом, помогут решить нам проблему раскраски. Мы начнем,с рассмотрения одной замечательной теоремы. 'д" е о р е м а 8. Для любой вершины о связного графа д, не яоляюисейся звездой, в окрестности Л,(о) имеется по крайней мере одна соцветная вершина.
Д о к а з а т е л ь с т в о. Будем иллюстрировать рассужде нне рис. 3.13, показывающего вершину о и ее окрестности Лд(о) Гл. 3. Алгоэитмизхция ясным, что для шобой вершины из Л' вершина л является ее единственной смежной вершиной, окрашенной краской а. Снимем «на минутуе краску а с вершины и. Тогда нам ничто не мешает перекрасить все вершины из Л' в краску а, убрав тем самым краску ~) пз окрестности В,(и). В таком случае красим вершину и в краску р, получив раскраску, удовлетворяющую условию теоремы. ~7~7 Важность атой теоремы для нас очевидна. Она поаволяет существенно ограничить область поиска соцветных вершин, гарантируя воаможность найти соцветную вершину в пределах окрестности 2-го порядка рассматриваемой вершины.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
