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

.

5. Клика

Антиподом понятия независимого множества является понятие клики.

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

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

Число вершин в наибольшей клике графа G называется его плотностью (или кликовым числом) и обозначается через (G). Как и в случае независимых множеств, максимальная клика графа может оказаться не наибольшей.

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

Очевидно следующее утверждение: подмножество вершин графа G является кликой тогда и только тогда, когда оно является независимым множеством в дополнительном графе G^*.

7. Содержание

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