Разбиение графа
От: m.a.g. Мальта http://dottedmag.net/
Дата: 24.03.03 04:15
Оценка: 15 (1)
Приветствую.

Недавно попалась на тренировке интересная задача (ИФМОшникам — прошу не пинать):

имеется неориентированный граф. Требуется разбить его на N подграфов, так чтобы суммарное количество ребер внутри подграфов было максмальным, и каждый подграф содержал по крайней мере 2 вершины.
Re: Разбиение графа
От: mihoshi Россия  
Дата: 26.03.03 11:23
Оценка:
Здравствуйте, m.a.g., Вы писали:

MAG>Приветствую.


MAG>Недавно попалась на тренировке интересная задача (ИФМОшникам — прошу не пинать):


MAG>имеется неориентированный граф. Требуется разбить его на N подграфов, так чтобы суммарное количество ребер внутри подграфов было максмальным, и каждый подграф содержал по крайней мере 2 вершины.


Точнее формулируй. Что значит внутри?
Re[2]: Разбиение графа
От: Andy77 Ниоткуда  
Дата: 26.03.03 16:12
Оценка:
Здравствуйте, mihoshi, Вы писали:

M>Точнее формулируй. Что значит внутри?


Я так понял, что просто суммарное количество ребер подграфов... хорошая задача.
Re[2]: Разбиение графа
От: m.a.g. Мальта http://dottedmag.net/
Дата: 27.03.03 03:55
Оценка:
Здравствуйте, 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 поставить...
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.