Связанные компоненты в неориентированном графе заданного количества вершин (алгоритм)

Question

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

Пример: K=3 и мы приведены по следующему графику:

Для этого графика мы имеем 2 компонент связности, где все вершины четные числа. Первый подключенный компонент состоит из следующих вершин: 8, 2, 4; а второй подключенный компонент состоит из следующих вершин: 2, 4, 6.

Есть ли алгоритм поиска связанных компонентов в неориентированном графе заданного количества вершин? Или может кто-нибудь помочь мне с идеей о том, как я должен подойти к проблеме? Я попытался сделать это с помощью алгоритма DFS, но я нигде не оказался.

Answer 1

Грубая сила:

Перерыв задачи на две подзадачи:

1) определить все подключенные компоненты (CC), которые содержат все четные числа, и произвольного размера. В приведенном выше примере будет только один CC: (8,2,4,6). Это можно сделать в O(e+n) времени, где e - это число ребер и n количество узлов, использующих BFS или DFS. (Это быстрый шаг.)

2) Внутри каждого ЦК с шага 1) перечислите все подключенные подграфы размера k. Это медленная часть. Решение грубой силы для CC размером m узлов - это O(k* (m choose k)) = O(k m^k) путем перечисления всех m choose k возможных k узлов из m и с использованием k операций для определения, связаны ли они.

Учитывая, что (1) быстро и (2) медленно, вы, вероятно, недостаточно понимаете проблему достаточно, чтобы знать, как обойти необходимость вычисления (2). Может быть более быстрый способ вычислить (2), то, что я предложил, вероятно, так же близко, как и для грубой силы.