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

Максиминной задача дихотомического разбиения графа

Дано неориентированный граф G (V, E, w),

где v непустое конечное множество вершин, v={1,...,n};

E={(i,j)єVxV} множество дуг;

w: E → R - весовая функция, которая каждому ребру ставит в соответствие вес (wij> 0- вес дуги(i,j)єE).

Определение. Дихотомическим разбивкой (V1, V2) будем называть такое разбиение множества вершин V на два подмножества V1, V2, что:

V1 ⊂ V, V2 ⊂ V, V1 ≠ ∅, V2 ≠ ∅

V1 ∪ V2 = V, V1 ∩ V2 = ∅

| V1 | = N1, | V2 | = n2

n1 + n2 = n

  n1 ≤ t, n2 ≥ b

где t, b - целые положительные числа (1

Найти такое дихотомическое разбиение графа G, при котором достигает максимума минимальный вес ребр разреза, соединяющих вершины из разных подграфов.