EssayAI
Блог
Блог
Естественные науки

Задача о клике: пример и поиск в графе

8 ноября 2026Время чтения: 8 минут
Задача о клике: пример и поиск в графе

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

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

Что такое клика в графе

Пусть дан простой неориентированный граф G=(V,E)G=(V,E): VV - множество вершин, EE - множество рёбер. Подмножество S⊆VS\subseteq V называется кликой, если любые две различные вершины из SS смежны:

∀u,v∈S,u≠v ⇒ {u,v}∈E.\forall u,v\in S,\quad u\ne v\ \Rightarrow\ \{u,v\}\in E.

Иначе говоря, подграф на выбранных вершинах полный. Каждая отдельная вершина образует клику размера один, каждое ребро - клику размера два, а треугольник - размера три. Для четырёх вершин нужны все шесть возможных рёбер. Форма рисунка значения не имеет: пересечение линий без отмеченной вершины не создаёт новую вершину или ребро.

Удаление ребра В–Г разрушает клику из четырёх вершин: наибольший размер снижается до трёх, а при возвращении ребра снова становится равным четырём.

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

Постановка задачи: найти или ответить «да»

У задачи есть две близкие формы. Оптимизационная: найти наибольшую клику и её размер. Это число называют кликовым числом графа и обозначают ω(G)\omega(G):

ω(G)=max⁡{∣S∣:S⊆V, S - клика}.\omega(G)=\max\{|S|: S\subseteq V,\ S\text{ - клика}\}.

Задача распознавания получает граф и целое kk и спрашивает: существует ли клика хотя бы из kk вершин? Если известна наибольшая клика размера четыре, ответ для k=3k=3 положительный, а для k=5k=5 отрицательный. При положительном ответе достаточно предъявить подходящие вершины: проверяющий посмотрит все пары и убедится, что нужные рёбра есть.

При решении обязательно уточняйте, что требуется в ответе. Число ω(G)\omega(G) не перечисляет вершины; один найденный набор не доказывает, что большего нет; а перечисление всех клик - отдельная задача с потенциально большим выводом.

Пример: пять вершин и восемь рёбер

Возьмём вершины А, Б, В, Г, Д и рёбра АБ, АВ, АГ, БВ, БГ, ВГ, АД, БД. Удобно сначала выписать соседей: у А это Б, В, Г, Д; у Б - А, В, Г, Д; у В - А, Б, Г; у Г - А, Б, В; у Д - только А и Б.

  1. Рассмотрим множество {А,Б,В,Г}\{А, Б, В, Г\}. У него шесть пар, и все шесть соответствующих рёбер присутствуют. Значит, это клика размера четыре.
  2. Единственный набор из пяти вершин - всё множество VV. Он не является кликой: рёбер ВД и ГД нет.
  3. Следовательно, клики размера пять нет, а найденная клика размера четыре наибольшая: ω(G)=4\omega(G)=4.

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

Граф с выделенной кликой из четырёх вершин и подсчёт числа клик каждого размера
Граф с выделенной кликой из четырёх вершин и подсчёт числа клик каждого размера

Для контроля перечислим количества: пять одиночных вершин, восемь рёбер, пять треугольников и одна клика размера четыре. Пятивершинных клик нет. Треугольники - АБВ, АБГ, АВГ, БВГ и АБД. Если убрать ВГ, исчезнут треугольники АВГ и БВГ и единственная четвёрка. Останутся три треугольника: АБВ, АБГ, АБД; кликовое число станет равно трём.

Максимальная и наибольшая клика

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

В исходном примере {А,Б,Д}\{А, Б, Д\} максимальна по включению: добавить В или Г нельзя, поскольку у Д нет ребра ни с одной из этих вершин. Но она не наибольшая: {А,Б,В,Г}\{А, Б, В, Г\} содержит четыре вершины. Любая наибольшая клика обязательно максимальна по включению: возможность добавить вершину противоречила бы её наибольшему размеру. Обратное утверждение неверно.

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

Как искать клику перебором и отсечениями

Для маленького графа подходит полный перебор подмножеств. Для каждого набора проверяем все пары вершин; если хотя бы одного ребра нет, набор отбрасываем. Из оставшихся выбираем набор наибольшего размера. При nn вершинах всего 2n2^n подмножеств, включая пустое, а проверка одного набора требует до (n2)\binom n2 проверок пары. Простой вариант имеет оценку O(2nn2)O(2^n n^2) и быстро становится дорогим.

Можно начать с наборов большого размера и остановиться, как только найден первый подходящий: все большие размеры к тому моменту уже проверены. При ручной работе удобно использовать пересечение соседств. Если в текущей клике уже есть А и Б, следующая вершина обязана быть соседом и А, и Б. После добавления каждой вершины круг кандидатов снова пересекают с её соседями. Это отсечение не исключает правильный ответ: всякая новая вершина клики обязана соединяться со всеми выбранными.

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

Почему задача сложна и где применяется

Проверить предложенную клику просто: для kk вершин достаточно проверить k(k−1)/2k(k-1)/2 пар. Найти её среди множества возможных наборов может быть намного труднее. Решательная версия CLIQUE NP-полна: она принадлежит NP, и к ней сводятся другие задачи этого класса. Лекции Университета Карнеги - Меллона формулируют обе версии и показывают сведение от 3-SAT. NP-полнота не доказывает, что полиномиального алгоритма не существует: вопрос P=NPP=NP остаётся открытым.

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

Дополнение графа и независимое множество

В дополнении G‾\overline G те же вершины, но ребро между различными вершинами есть ровно тогда, когда его нет в GG. Поэтому клика исходного графа становится набором попарно несмежных вершин дополнения, то есть независимым множеством. Отсюда ω(G)=α(G‾)\omega(G)=\alpha(\overline G), где α\alpha - размер наибольшего независимого множества. Подробнее саму конструкцию и её связь с покрытием разбирает статья о независимом множестве.

Есть и связь с раскраской: вершинам одной клики нужны разные цвета, поэтому χ(G)≥ω(G)\chi(G)\ge\omega(G). Это полезная нижняя оценка числа цветов, но равенство выполняется не для каждого графа. О подсчёте допустимых раскрасок рассказывает хроматический полином графа.

Частые ошибки

  • Считать путь прямым ребром. Для клики проверяют каждую пару выбранных вершин, а не только связность всей группы.
  • Принимать максимальную клику за наибольшую. Отсутствие подходящей вершины для добавления не исключает большего набора в другой части графа.
  • Предъявлять только пример как доказательство оптимума. Нужна также верхняя оценка или исчерпывающая проверка больших наборов.
  • Путать простоту проверки с простотой поиска. Проверка готового сертификата занимает полиномиальное время, но вариантов выбора может быть экспоненциально много.
  • Забывать исходную модель. Рёбра должны означать именно то попарное отношение, которое нужно в задаче.

FAQ

Может ли вершина сама быть кликой?

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

Всегда ли наибольшая клика единственна?

Нет. Например, после удаления ребра ВГ в нашем графе есть три наибольшие клики размера три: АБВ, АБГ и АБД. Их общий размер один, но состав разный.

Клика и полный граф - одно и то же?

Клика - выбранное множество вершин внутри исходного графа; подграф, образованный этими вершинами, полный. Весь исходный граф при этом может быть неполным.

Коротко

Клика - множество попарно смежных вершин. Наибольшая клика задаёт кликовое число, а максимальная по включению не обязательно самая большая. В разобранном графе ω(G)=4\omega(G)=4: четвёрка АБВГ существует, а все пять вершин не образуют клику. Для доказательства ответа нужны как найденный пример, так и обоснование, почему большего нет.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Доминирующее множество в графе: определение и примеры

Доминирующее множество в графе: определение и примеры

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

8 ноября 20268 минут
Гиперграф: что это такое и как его построить

Гиперграф: что это такое и как его построить

Гиперграф простыми словами: вершины, гиперрёбра и матрица инцидентности. Разбираем пример, степени вершин, связь с обычным графом и области применения.

8 ноября 20268 минут
Классы P и NP: проверка решения и сложность поиска

Классы P и NP: проверка решения и сложность поиска

Классы P и NP простыми словами: чем поиск отличается от проверки, как работают свидетель и полиномиальное сведение, что означает NP-полнота и почему вопрос P против NP открыт.

8 ноября 20268 минут
Лемма о рукопожатиях: формула, доказательство и примеры

Лемма о рукопожатиях: формула, доказательство и примеры

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

8 ноября 20267 минут
Рёберный граф: построение, свойства и примеры

Рёберный граф: построение, свойства и примеры

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

8 ноября 20268 минут
Алгоритм Хопкрофта-Карпа: паросочетание по фазам

Алгоритм Хопкрофта-Карпа: паросочетание по фазам

Алгоритм Хопкрофта-Карпа находит максимальное паросочетание в двудольном графе. Разбираем поиск кратчайших цепей, BFS и DFS, пример двух фаз и оценку сложности.

8 ноября 20268 минут