2.2. Максимальные полные подграфы (клики)

Понятие, противоположное максимальному независимому множеству, есть максимальный полный подграф. Таким образом, максимальный полный подграф (клика) графа G есть порожденный подграф, построенный на подмножестве S вершин графа и являющийся полным и максимальным в том смысле, что любой другой подграф графа G, построенный на множестве вершин Н, содержащем S, т. е. Н S, не является полным. Следовательно, в противоположность максимальному независимому множеству, в котором не могут встретиться две смежные вершины, в клике все вершины попарно смежны. Совершенно очевидно, что максимальное независимое множество графа G соответствует клике графа G и наоборот, где G - дополнение графа G.

Вполне очевидно также, что понятие клики для неориентированного графа подобно понятию клики для графа; однако эта аналогия более глубокая, чем та, которая существует между понятиями клики и сильной компоненты (см. гл. 2). Клику в действительности можно рассматривать как такую сильную компоненту, в которой достижимость ограничена путями единичной длины (см. разд. 5 в гл. 2).

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

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

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

В оригинале - <idensity .- Прим. ред.

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

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

2.3.1. Обоснование алгоритма. Этот алгоритм является существенно упрощенным перебором, использующим дерево поиска. В процессе поиска - на некотором этапе к - независимое множество вершин iSft расширяется путем добавления к нему подходящим образом выбранной вершины (чтобы получилось новое независимое множество Sf + i) на этапе /с + 1, и так поступают до тех пор, пока добавление вершин станет невозможным, а порождаемое множество не станет максимальным независимым множеством. Пусть будет на этапе к наибольшим множеством вершин, для которого Sft П Cfe = 0 т. е. после добавления любой вершины из Qk к Sk получается независимое множество S+i. В некоторый произвольный момент работы алгоритма множество Qf состоит вообще говоря, из вершин двух типов: подмножества Qk тех вершин, которые уже использовались в процессе поиска для расширения множеств Sfi, и подмножества Qt таких вершин, которые еще не использовались. Тогда дальнейшее ветвление в дереве поиска включает процедуру выбора вершины 6 Qt, добавление ее к 6ft для построения множества

5ft+i = 5ftUK} (3.4)

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

<??+i=<?S-r(XiJ (3.5)

и

г+1=-(Г(хдиК}). (3.6)

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

И добавлении Хг к старому множеству Qi для формирования новых множеств Qj и Qu.

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

Qt = Ql=0. (3.7)

Теперь совершенно очевидно, что если очередной этап работы алгоритма наступает тогда, когда существует некоторая вершина х 6 Qh, для которой Г (а:) П *?h = 0, то безразлично, какая из вершин, принадлежащих Q, используется для расширения 5, и это справедливо при любом числе дальнейших ветвлений; вершина X не может быть удалена из Qp на любом следующем шаге р >к. Таким образом, условие

IxQl, такая, что T{x)f\Qt=0, (3.8)

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

Как и во всяком методе, использующем дерево поиска, здесь выгодно стремиться начать шаги возвращения как можно раньше, поскольку это ограничит размеры ненужной части дерева поиска. Следовательно, целесообразно сосредоточить усилия на том, чтобы возможно раньше добиться выполнения условия (3.8) с помощью подходящего выбора вершин, используемых при расширении множеств Sk- На каждом следующем шаге процедуры можно выбирать для добавления к Sk любую вершину Xi 6 Qk, на шаге возвращения Xi будет удалена из Qk и включена в Qk. Если вершину Xk выбрать так, чтобы она принадлежала множеству Г (х) при некоторой вершине х из Ql, то на соответствующем шаге возвращения величина

A{x) = \T{x)[]Qi\ (3.9)

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

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