Нахождение остовного дерева с использованием ровно k красных ребер в графе с ребрами, окрашенными красным / синим в линейное время

Question

Учитывая граф G с красными и синими ребрами и константой K, разработайте детерминированный линейный алгоритм времени, который находит остовное дерево G с ровно K красными ребрами (или возвращает False если такого остовного дерева не существует).

Что мы сделали до сих пор:

Пусть каждое красное ребро имеет вес -1, а каждое синее ребро имеет вес 0.

Найти минимальное остовное дерево (используя стандартный алгоритм линейного времени). Итак, у нас есть остовное дерево T с минимальным весом, то есть мы использовали столько красных ребер, сколько могли, потому что красные ребра только уменьшат вес.

Если в T меньше чем K красных ребер, мы возвращаем False,

Если есть ровно K красных ребер, мы закончили, T - ответ.

Если есть больше чем K красных краев, нам нужно заменить их на синие.

Это наша проблема, как мы можем сделать это за линейное время?

Каждое добавленное синее ребро создаст цикл, поэтому удаление одного красного ребра из цикла будет работать, но как мы можем добиться линейности таким образом? Это даже хороший подход?

Answer 1

HINTS

Вы можете сделать это за линейное время, используя два прохода алгоритма Прима. (Обычно алгоритм Прима не является линейным временем, но когда у вас есть только два типа ребер, вам не нужно тратить время на сортировку ребер).

Пропуск 1

В первом проходе следуйте за синими краями перед красными и отметьте все красные края, которые вы вынуждены взять.

Если вы пометите C ребер в этом процессе, то мы знаем, что в любом решении связующего дерева должно быть по крайней мере C красных ребер, поэтому, если C>K, это невозможно.

Пасс 2

Предположим, что мы нашли C (

Во втором проходе следуйте красным краям перед синим, пока общее количество дополнительных красных краев не достигнет KC. Во втором проходе вам также разрешено следовать красным краям, отмеченным в первом проходе (и они не учитываются при расчете общего количества).

Если ваши дополнительные красные края не достигают KC, то это невозможно.