Приветствую.
Недавно попалась на тренировке интересная задача (ИФМОшникам — прошу не пинать):
имеется неориентированный граф. Требуется разбить его на N подграфов, так чтобы суммарное количество ребер внутри подграфов было максмальным, и каждый подграф содержал по крайней мере 2 вершины.
Здравствуйте, mihoshi, Вы писали:
MAG>>Недавно попалась на тренировке интересная задача (ИФМОшникам — прошу не пинать):
MAG>>имеется неориентированный граф. Требуется разбить его на N подграфов, так чтобы суммарное количество ребер внутри подграфов было максмальным, и каждый подграф содержал по крайней мере 2 вершины.
M>Точнее формулируй. Что значит внутри?
Точная формулировка:
Имеется граф <V,E>, E = E^-1, E and id(V) = null, задано число N.
Требуется построить множества V1,...,VN:
Vi and Vj = null <=> i != j,
forall i (|Vi| >= 2),
union(Vi, i = 1..n) = V
при условии, что E' = { e=(v1,v2) in E | exist k (v1 in Vk and v2 in Vk) }, |E'| -> max
and — пересечение множеств, union — объединение, in — принадлежность множеству, null — пустое множество, forall, exist — кванторы, id — диагональ.
ps: 2rsdn team: хочу [tex]!!! Ведь пробегала сдесь ссылка на tex2html! Не так уж и сложно MikTeX поставить...