6.11. Клики, независимые множества

• Определение доминирующего множества. Пусть ориентированный или неориентированный граф.

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

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

В качестве примера рассмотрим вариант этой игры, когда расстановка ферзей выполняется на доске (рис. 6.27). На рис. 6.28 представлен граф данной игры. Вершины 1 и 9 соединены ребром, так как ферзь в клетке 1 держит под боем клетку с номером 9. Вершины 1 и 8 не соединены, так как ферзь в клетке 1 не может угрожать клетке 8 и т.д. Вершины 1 и 8 (рис. 6.29) составляют доминирующее множество так как из этих вершин по ребрам графа можно за один ход попасть в любую другую вершину. Одна вершина с номером 5 (рис. 6.30) также составляет доминирующее множество Ясно, что для графа этой игры число доминирования равно

Рис. 6.27

Рис. 6.28

Рис. 6.29

Рис. 6.30

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

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

• Определение независимого множества ребер. Подобно независимым множествам вершин рассматриваются независимые множества ребер, состоящие из ребер, не имеющих общих вершин. Каждое независимое множество ребер содержится в некотором максимальном независимом множестве. Число ребер в максимальном независимом множестве называется числом реберной независимости

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

• Утверждение 6.11.1. Независимое множество максимально тогда и только тогда, когда оно доминирующее, а значит, число (вершинной) независимости не может быть меньше числа доминирования.

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

• Определение. Клика есть полностью зависимое множество, которое теряет это свойство после добавления любой вершины. Клики графа представляют «естественные» группировки вершин в максимальные полные подграфы. Определение клик графа полезно в кластерном анализе в таких областях, как информационный поиск, в социологии и др. В качестве примера на рис. 6.31 показан граф и его клики.

Рис. 6.31. Граф и его клики

• Замечание. Если предположить, что граф простой, то полностью зависимые множества (клики) в становятся максимально независимыми множествами в дополнительном графе верно и обратное.

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

Заметим, что каждая клика порождается много раз: клика порождается 3! раз, клики порождаются 2! раз. В общем случае клика размера порождается раз. Все тонкие ребра на рис. 6.32 исследования дерева поиска можно оборвать, они не приводят к новым кликам. Следующие два утверждения позволяют обрывать такие «тонкие» ребра (не исследовать их), обеспечивая целенаправленный проход по дереву поиска клик графа.

Рис. 6.32. Граф и полный перебор дерева поиска клик

• Утверждение 6.11.2. Пусть исходный граф, узел в дереве поиска ( — подмножество вершин графа). Вершина дерева поиска уже обработана и первой вершиной, которую надо исследовать, является множество как на рис. 6.33, вершина х смежна с каждой вершиной из Пусть все поддеревья узла в дереве уже исследованы и порождены все клики, включающие Тогда необходимо исследовать только те из вершин для которых (рис. 6.33).

Рис. 6.33 Поддеревья с корнями (эти вершины смежны с 5)

• Утверждение 6.11.3. Пусть узел в дереве поиска и пусть предок Если все поддеревья узла уже исследованы, так что порождены все клики, включающие то все неисследованные поддеревья с корнями можно игнорировать.

Алгоритм 6.13 порождения клик графа представляет собой процедуру поиска с возвращением и является наиболее сложным из всех ранее рассмотренных алгоритмов. Рекурсивная процедура тлеет два параметра: Для рассматриваемого узла

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

Алгоритм 6.13. Порождение клик графа

(см. скан)

Процедура выбирает произвольную вершину удаляет ее из и исследует поддерево обращаясь к процедуре Далее, согласно утверждениям 6.11.2 и 6.11.3, при помощи процедуры исследуются только поддеревья где что соответствует условию Множество

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

Второй параметр процедуры представляет собой множество вершин, смежных со всеми вершинами из но таких, которые не надо добавлять к на предмет продолжения формирования клик.

По алгоритму множество является полным подграфом графа множество всех вершин, смежных с каждой вершиной в

Множество будет кликой тогда и только тогда, когда

Условие обозначает, что все клики, включающие уже ранее порождались.

• При могут оставаться клики, включающие которые еще не порождались. Исследование таких поддеревьев необходимо продолжить.

Основные усилия алгоритма 6.13, порождения клик графа, направлены на поддержание множеств текущее состояние которых, согласно перечисленным выше условиям, предопределяет исследования по дереву поиска.

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

Алгоритм 6.14. Программа порождения клик графа

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

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

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

Рис. 6.34

Пример порождения клик графа

Для программы алгоритма 6.14 исходные данные структуры смежности этого графа задаются в текстовом файле Структура (правило) заполнения файла совпадает с той, которая описана в примере поиска в глубину при расчете по программе алгоритма 6.2.

Данные файла для примера на рис. 6.34:

Результаты расчетов сохраняются в выходном файле со следующей структурой:

Строки файла это номера вершин соответствующих клик «симпатичного» графа на Отсюда видно, что в данном случае на вечер могут быть приглашены лишь четыре близких друга генерала.