Задача о максимальном K-подграфе

Аннотация

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