2.3. Построение всех максимальных независимых множеств

Вследствие упомянутой выше связи между кликами и максимальными независимыми множествами методы, рассматриваемые в данном разделе и описываемые на «языке максимальных независимых множеств», могут быть непосредственно использованы для построения клик. На первый взгляд кажется, что нахождение всех максимальных независимых множеств графа — очень простая задача, которую можно решить последовательным перебором независимых множеств с одновременной проверкой каждого множества на максимальность (последнее осуществляется путем добавления к исследуемому множеству дополнительной, не принадлежащей ему, вершины и выяснения того, сохраняется ли

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

В этом разделе будет описан систематический метод перебора Брона и Кэрбоша [14], который позволяет обходить указанные выше трудности. В этом методе не нужно запоминать генерируемые независимые множества для проверки их на максимальность путем сравнения с ранее сформированными множествами.

2.3.1. Обоснование алгоритма.

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

и порождение новых множеств:

и

Шаг возвращения алгоритма состоит в удалении вершины из чтобы вернуться к изъятии из старого множества

и добавлении к старому множеству для формирования новых множеств и

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

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

является достаточным для осуществления шага возвращения, поскольку из при всяком дальнейшем ветвлении уже не получится максимальное независимое множество.

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

уменьшится на единицу (по сравнению с тем значением, которое было до выполнения прямого шага и шага возвращения), так что условие (3.8) теперь станет выполняться раньше.

Таким образом, одйн из возможных способов выбора вершины для расширения множества состоит, во-первых, в нахождении вершины с возможно меньшим значением величины

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

Следует отметить, что поскольку на шаге возвращения вершина попадает в то может оказаться, что при этом новом входе значение величины меньше, чем для ранее фиксированной вершины х. Значит, надо проверить, не ускорит ли эта новая вершина выполнение условия (3.8). Это особенно важно в начале ветвления, когда

2.3.2. Описание алгоритма

Начальная установка

Шаг 1. Пусть

Прямой шаг

Шаг 2. Выбрать вершину как упоминалось ранее, и сформировать оставляя нетронутыми. Положить

Проверка

Шаг 3. Если удовлетворяется условие (3.8), то перейти к шагу 5, иначе к шагу 4.

Шаг 4. Если напечатать максимальное независимое множество и перейти к шагу 5. Если то перейти к шагу 5. Иначе перейти к шагу 2.

Шаг возвращения

Шаг 5. Положить Удалить из чтобы получить Исправить удалив вершину из и добавив ее к Если остановиться. (К этому моменту будут уже напечатаны все максимальные независимые множества.) Иначе перейти к шагу 3.

Комментарий по применению описанного выше алгоритма приведен в [14] вместе с программой, написанной на Алголе. Эта программа была опробована для большого числа графов (в частности, для графов Муна-Мозера, см. задачу 10) и было установлено, что время, необходимое для построения максимального независимого множества, почти постоянно и не зависит от размера графа. Все это говорит о том, что данный алгоритм является одним из лучших.