Главная > Математика > Введение в прикладную комбинаторику
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 34. Клика. Максимальная клика

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

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

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

Например, на рис. 146 выделен полный подграф графа на рис. 143 с кликой

Рис. 143.

Рис. 144.

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

Нахождение максимальной клики в графе сводится к нахождению максимального внутренне устойчивого подмножества в графе дополнительном к графу

Рис. 145.

Рис. 146.

Действительно, дополнительный граф определяется согласно (25.23):

Для каждой клики имеем

и, таким образом, максимальному внутренне устойчивому подмножеству в соответствует максимальная клика в

Пример. Пусть граф изображен на рис. 143, граф изображен на рис. 144. Максимальное внутреннее устойчивое подмножество графа изображено на рис. 145. Это подмножество соответствует клике графа изображенной на рис. 146, его достаточно для образования полного неориентированного графа с вершинами

УПРАЖНЕНИЯ

(см. скан)

<< Предыдущий параграф Следующий параграф >>
Оглавление