Задача декомпозиции графов
Заказчик
[no-member:pro]Анатолий[/no-member:pro]
Параметры проекта
Вариант сотрудничестваОдноразовый проект
РазделОбучение и Консультации
Предоплатабез предоплат
Способы оплатыБанковский перевод
Приём заявокот 2022-06-27 до 2022-07-07
Описание проекта
Предложение удаленной работы. Нужно сделать декомпозицию графов. Макс-мин задача розбиения графа:
Дано
Неориентированный граф G(V,E,w), где v - непустое бесконечное множество вершин, v={1,...,n}
E={(i,j)єVxV} - множество дуг
W: E->R - функция, которая каждому ребру ставит в соответствие вес
(Wij > 0 - вес дуги(i,j)єE)
Найти
Такое дихотомическое разбиения графа G, при котором максимума достигает минимальный вес ребер разреза, которые соединяют вершины с разных подграфов
Дано
Неориентированный граф G(V,E,w), где v - непустое бесконечное множество вершин, v={1,...,n}
E={(i,j)єVxV} - множество дуг
W: E->R - функция, которая каждому ребру ставит в соответствие вес
(Wij > 0 - вес дуги(i,j)єE)
Найти
Такое дихотомическое разбиения графа G, при котором максимума достигает минимальный вес ребер разреза, которые соединяют вершины с разных подграфов
