Недавно попалась на тренировке интересная задача (ИФМОшникам — прошу не пинать):
имеется неориентированный граф. Требуется разбить его на N подграфов, так чтобы суммарное количество ребер внутри подграфов было максмальным, и каждый подграф содержал по крайней мере 2 вершины.