The Problem of the Maximal K-Subgraph

Abstract

We introduce the notion of a K-subgraph as a subgraph, each component of which contains at most K vertices. The problem is to determine the maximal K-graph, that is, the K-graph with the maximum number of vertices. The solution of the problem for a tree is given. For the case K = 2 two heuristic algorithms are proposed. An example of the applied task of portfolio formation is given taking into account the interdependence of projects, the algorithm for solving which includes the stage of determining the maximum K-subgraph.