Остовное дерево с ровно 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

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