Максиминной задача дихотомического разбиения графа
Дано неориентированный граф G (V, E, w),
где v непустое конечное множество вершин,  v={1,...,n};
E={(i,j)єVxV} множество дуг;
w: E &#8594; R - весовая функция, которая каждому ребру ставит в соответствие вес (wij> 0- вес дуги(i,j)єE).
Определение. Дихотомическим разбивкой (V1, V2) будем называть такое разбиение множества вершин V на два подмножества V1, V2, что:
V1 &#8834; V, V2 &#8834; V, V1 &#8800; &#8709;, V2 &#8800; &#8709;
V1 &#8746; V2 = V, V1 &#8745; V2 = &#8709;
| V1 | = N1, | V2 | = n2
n1 + n2 = n
  n1 &#8804; t, n2 &#8805; b
где t, b - целые положительные числа (1 <t, b <n).
Найти такое дихотомическое разбиение графа G, при котором достигает максимума минимальный вес ребр разреза, соединяющих вершины из разных подграфов.

Гость guest_1589806910955

Задача с графами