Задачи о покрытии множеств. Поиск минимальных разбиений, страница 6

Метод  последовательной   раскраски. Будем окрашивать вершины последовательно, анализируя возникающие ситуации и решая каждый раз, какую вершину следует выбрать в качестве очередной и в какой именно цвет ее следует окрасить — так определяется содержание элементарного шага. Текущая ситуация будет характеризоваться тем, что часть вершин окажется уже окрашенной в определенные цвета, остальные — нет. Ситуация может оказаться такой, что для того, чтобы не потерять возможности нахождения минимальной раскраски, будет необходимо рассмотреть несколько вариантов выбора очередного шага, т. е. потребуется расщепить текущую ситуацию. Однако может встретиться и такая ситуация, которую можно редуцировать, окрашивая некоторую из вершин с гарантией того, что при этом не будет допущена какая-то ошибка и возможность нахождения оптимального решения не будет утрачена. Сформулируем соответствующие правила редуцирования ситуации.

Правило ввода нового цвета. Если существует неокрашенная вершина, которую нельзя окрасить ни в один из уже использованных цветов, то ее следует окрасить в новый цвет.

Правило это весьма тривиально, но эффективно. Например, из него следует, что решение задачи в целом целесообразно начинать с раскраски вершин некоторого полного подграфа. Очевидно, что такая раскраска однозначна: все вершины полного подграфа должны быть окрашены в различные цвета, а в какие именно, неважно, поскольку другие вершины еще не окрашивались. Чем больше вершин будет при этом окрашено, тем лучше, откуда следует, что для раскраски стоит выбирать наибольший из полных подграфов, т. е. содержащий максимальное число вершин.

По правилам раскраски, вершину нельзя окрашивать в те цвета, которые уже использованы для окраски соседних с нею вершин. Поэтому, окрашивая некоторую вершину, мы одновременно вводим запрет на использование выбранного цвета для окраски соседних вершин. Однако такой запрет может быть наложен ранее — при окраске некоторых других вершин.

Правило использования старого цвета. Для окраски некоторой вершины можно применить старый (уже использованный) цвет, если это не приводит к сокращению числа вариантов возможной окраски соседних неокрашенных вершин.

Применение этих двух правил редуцирования может носить цепной характер, когда предшествующие акты редуцирования будут создавать условия для последующих. При отсутствии таких условий применяется следующее правило.                

Правило расщепления. Рассматриваются все допустимые окраски некоторой вершины в старые цвета и в один из новых.

С целью сокращения возникающего при этом перебора рекомендуется применять это правило к таким вершинам, число возможных окрасок которых максимально ограничено. Естественно искать такие вершины в непосредственном соседстве с уже окрашенными.

Пример. Покажем применение сформулированных правил к раскраске графа, изображенного на рис. 22, а, попутно уточняя метод. Отыскивая в графе вершины с интересующими нас свойствами, будем организовывать перебор вершин в порядке номеров и при прочих равных условиях останавливать выбор на вершинах, наиболее связанных с уже окрашенными, а среди одинаковых и по этому признаку — с максимальным числом исходящих из них ребер.

Допустим, что мы обладаем достаточным запасом красок: красной (к), зеленой (з), синей (с), желтой (ж) и т. д. В исходной ситуации все вершины не окрашены, множество использованных красок пусто.

1-й шаг. Применяя правило ввода нового цвета, выбираем вершину 1, обладающую максимальным числом исходящих из нее ребер, и окрашиваем ее в красный цвет, представляя символически это действие как 1к.

2-й шла. Следуя этому же правилу, окрашиваем вершину 10 в зеленый цвет: 10з.

3-й шаг. В возникшей ситуации применимо правило использования старого цвета. Окрасим вершину 3 в зеленый цвет, поскольку у нее только одна соседняя вершина 7, для окраски которой зеленый цвет все равно нельзя использовать — в этот цвет окрашена соседняя с ней вершина 10. Итак: Зз.

4-й шаг. Опять применяем правило использования старого цвета. Окрашиваем вершину 6 также в зеленый цвет. У единственной неокрашенной соседней вершины 9 уже имеется запрет на использование этой краски. Таким образом: 6з.

5-й шаг. Аналогично: 8з.