остовное дерево с ровно k цветными краями

Question

У меня есть связанный, неориентированный граф с ребрами, каждый из которых является либо черным, либо белым, и целым числом k.Я пытаюсь написать алгоритм, который говорит, существует ли остовное дерево с ровно k черных ребер (необязательно, чтобы найти фактическое дерево).

Я использовал алгоритм Крускала, чтобы найти минимум имаксимально возможное количество черных ребер в остовном дереве.Если k находится за пределами этого диапазона, связующее дерево с k ребрами не может существовать.

Но у меня возникают проблемы, когда я не могу понять, существует ли обязательно связующее дерево для каждого k в этом диапазоне.Моя интуиция говорит да, и это работает для каждого примера, который я пробовал, но я не могу понять, как это доказать.

Есть совет?Заранее спасибо.

Answer 1

Пусть G_min = остовное дерево с минимумом # черных ребер.

Пусть G_max = остовное дерево с максимальным # черных ребер.

Пусть k_min = # черных ребер в G_min

Пусть k_max = # черных ребер в G_max

Доказательство выполняется следующим образом.Установите G = G_min.Повторите для каждого черного ребра в G_max:

  1) If the edge is already in G, do nothing.
  2) If the edge is not in G, add it to G and remove another edge
     from the cycle thus induced in G.  Remove one not in G_max.

Шаг 2 всегда возможен, потому что в каждом цикле есть хотя бы одно ребро, отсутствующее в G_max.

Этот алгоритм поддерживает связующее дерево-Несомненно, G как бы то ни было.Он добавляет не более одного черного края на шаг, поэтому G демонстрирует остовное дерево с k черными краями для всех k между k_min и k_max по ходу.

Answer 2

Крускал найдет для вас минимальное остовное дерево - так что, чтобы найти Гмина, вам нужно сделать это наоборот. gmin = case все черные края дают уайт 1, а белые - 0, как алгоритм сначала использует все белые края, а затем черные. таким образом мы получим гмин.