Учитывая неориентированный граф. Как проверить, можно ли его разделить на два набора, где каждый узел одного набора подключается ко всем другим узлам своего собственного набора (полный график). Набор может быть пустым или только одним узлом. Ни один узел не должен оставаться. Спасибо.Число полных компонентов графа
РЕДАКТ. Кромки между двумя наборами не запрещены.
В основном мы должны проверить, если граф можно разделить на две клики
Как прокомментировал @Damien, проверяя ли вершины данного графа можно разбить на две кликами на самом деле проблема решения clique cover с k = 2. Для общего k (даже при k = 3) проблема покрытия клики известна как NP-полная. При k = 2 существует алгоритм O (n), основанный на приведенном ниже наблюдении.
Учитывая граф G = (V, E), обозначим его дополнение как G '. Тогда V можно разбить на два клика тогда и только тогда, когда G '2-кратно.
Доказательство прост и поэтому опущено здесь. Эскиз алгоритма показан ниже.
01. construct G' from G;
02. if G' is bipartite
03. return true;
04. else
05. return false;
Обратите внимание, что первая строка требует вывода времени (п), при тестировании ли G»двудольный требует только O (N + M) времени с использованием BFS, где п является # вершин и м является # ребер. Поэтому общая сложность составляет O (n).
Вы также запрещаете края между двумя наборами? (Ваша текущая фраза * не запрещает их.) Если это так, это легко можно сделать в O (n^2) времени для n вершин: Рассмотрим вершины в некотором порядке и пусть i - первая вершина, которая не имеет край к любой более ранней вершине (если он имеет ребра для некоторых, но не для всех, ответ НЕТ). Тогда каждая последующая вершина должна быть связана либо с каждой вершиной = i. –
Вы должны быть более конкретными, я думаю: ваша проблема выглядит как проблема с минимальной (вершиной) k-clique, но неясно, хотите ли вы найти эту обложку и k, или если вы просто хотите сказать, возможно или нет для k = 2. Обращайте внимание также на то, что крышка клики вершин и крышка клинка края очень отличаются по параметризованной сложности. –
Да, я просто хочу знать, возможны ли такие два набора или нет. и каждая вершина должна находиться в одном из этих множеств. –