Описание проекта
Предложение удалённой работы. Нужно сделать декомпозицию графов. Макс-мин задача разбиения графа:
Дано
Неориентированный граф G(V,E,w), где V — непустое конечное множество вершин, V={1,...,n}
E={(i,j)∈V×V} — множество рёбер
W: E→R — функция, которая каждому ребру ставит в соответствие вес
(Wij > 0 — вес ребра (i,j)∈E)
Найти
Такое дихотомическое разбиение графа G, при котором максимума достигает минимальный вес рёбер разреза, которые соединяют вершины из разных подграфов.
Дано
Неориентированный граф G(V,E,w), где V — непустое конечное множество вершин, V={1,...,n}
E={(i,j)∈V×V} — множество рёбер
W: E→R — функция, которая каждому ребру ставит в соответствие вес
(Wij > 0 — вес ребра (i,j)∈E)
Найти
Такое дихотомическое разбиение графа G, при котором максимума достигает минимальный вес рёбер разреза, которые соединяют вершины из разных подграфов.
Обучение и Консультации Банковский перевод
