Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
6.11. Клики, независимые множества• Определение доминирующего множества. Пусть Подмножество Минимальным доминирующим множеством называется такое доминирующее множество, что никакое его подмножество не обладает этим свойством. Числом доминирования В качестве примера рассмотрим вариант этой игры, когда расстановка ферзей выполняется на доске
Рис. 6.27
Рис. 6.28
Рис. 6.29
Рис. 6.30 • Определение независимого множества вершин. Пусть граф • Определение. Максимальное независимое множество есть независимое множество, которое становится зависимым после добавления к нему любой вершины. Заметим, что каждое независимое множество содержится в некотором максимальном независимом множестве. Максимальное число • Определение независимого множества ребер. Подобно независимым множествам вершин рассматриваются независимые множества ребер, состоящие из ребер, не имеющих общих вершин. Каждое независимое множество ребер содержится в некотором максимальном независимом множестве. Число ребер в максимальном независимом множестве называется числом реберной независимости При представлении игр графами независимые множества вершин являются такими множествами позиций, что никакая из них не может быть достигнута из другой за один ход. Примером является задача о расположении максимального числа ферзей на шахматной доске так, чтобы ни один них не мог побить другого. Это максимальное число равно • Утверждение 6.11.1. Независимое множество максимально тогда и только тогда, когда оно доминирующее, а значит, Доказательство. • Определение. Клика есть полностью зависимое множество, которое теряет это свойство после добавления любой вершины. Клики графа представляют «естественные» группировки вершин в максимальные полные подграфы. Определение клик графа полезно в кластерном анализе в таких областях, как информационный поиск, в социологии и др. В качестве примера на рис. 6.31 показан граф и его клики.
Рис. 6.31. Граф и его клики • Замечание. Если предположить, что граф При алгоритмическом подходе к выделению клик в графе применяют метод поиска с возвращением по специальному дереву поиска, устроенному следующим образом. Каждый узел в дереве поиска соответствует полному подграфу исходного графа, и каждое ребро дерева поиска соответствует вершине исходного дерева. Вершины (множества) дерева поиска определим рекурсивно. Корень дерева поиска — пустое начальное множество Заметим, что каждая клика порождается много раз: клика
Рис. 6.32. Граф • Утверждение 6.11.2. Пусть
Рис. 6.33 Поддеревья с корнями • Утверждение 6.11.3. Пусть Алгоритм 6.13 порождения клик графа представляет собой процедуру поиска с возвращением и является наиболее сложным из всех ранее рассмотренных алгоритмов. Рекурсивная процедура поиска объединение
Алгоритм 6.13. Порождение клик графа (см. скан) Процедура
Второй параметр
По алгоритму множество Множество Условие • При Основные усилия алгоритма 6.13, порождения клик графа, направлены на поддержание множеств Программная реализация алгоритма порождения клик графа представлена в алгоритме 6.14 на Алгоритм 6.14. Программа порождения клик графа (см. скан) (см. скан) (см. скан) (см. скан) (см. скан) (см. скан) Воспользуемся данной программой в качестве примера для решения следующей задачи. Задача. Симпатичный прием. Генерал желает устроить свой юбилей с максимальным числом гостей из своих знакомых. Стремясь сделать юбилейный вечер приятным, он должен организовать все так, чтобы на нем присутствовали люди, симпатизирующие друг другу. Для достижения цели ему придется находить максимальную клику графа своих знакомых. Этот граф устроен следующим образом. Вершины его — знакомые юбиляра. Две вершины смежные, если соответствующие знакомые симпатизируют друг другу. Нетрудно понять, что клика этого графа с максимальным числом вершин и представляет тот самый максимальный контингент приглашенных, который может позволить себе юбиляр. «Симпатичный» граф знакомых генерала представлен на рис. 6.34.
Рис. 6.34 Пример порождения клик графа Для программы алгоритма 6.14 исходные данные структуры смежности Данные файла
Результаты расчетов сохраняются в выходном файле
Строки файла
|
1 |
Оглавление
|