algorithm - 線形時間で赤/青で色付けされたエッジを持つグラフで正確に k 個の赤いエッジを使用してスパニングツリーを見つける

Question

赤と青のエッジを持つグラフGと定数Kが与えられた場合、正確にK個の赤のエッジを持つGのスパニングツリーを見つける決定論的線形時間アルゴリズムを考案します (または、そのようなスパニングツリーが存在しない場合は戻ります)。False

これまでに行ったこと:

すべての赤いエッジの重みを -1 にし、すべての青いエッジの重みを 0 にします。

最小スパニングツリーを見つけます (標準の線形時間アルゴリズムを使用)。したがって、重みが最小のスパニングツリーTがあります。つまり、赤いエッジは重みを減らすだけなので、できるだけ多くの赤いエッジを使用しました。

Tの赤いエッジがK未満の場合、を返します。False

ちょうどK個の赤のエッジがある場合、完了です。Tが答えです。

K個以上の赤のエッジがある場合、それらを青のエッジに置き換える必要があります。

これが私たちの問題です。線形時間でそれを行うにはどうすればよいでしょうか?

青いエッジが追加されるたびにサイクルが作成されるため、サイクルから赤いエッジを 1 つ削除すると機能しますが、この方法で線形性を確保するにはどうすればよいでしょうか? これも良いアプローチですか？

score 3 · Accepted Answer

ヒント

プリムのアルゴリズムの2 つのパスを使用して線形時間でこれを行うことができます。(通常、Prim のアルゴリズムは線形時間ではありませんが、2 種類のエッジしかない場合は、エッジの並べ替えに時間を費やす必要はありません)。

最初のパスでは、赤いエッジの前に青いエッジをたどり、強制的に取らなければならない赤いエッジをマークします。

このプロセスで C エッジをマークすると、どのスパニングツリーソリューションにも少なくとも C レッドエッジが必要であることがわかります。したがって、C>K の場合は不可能です。

最初のパスで C ( < K ) マークされたエッジを見つけたとします。

2 番目のパスでは、追加の赤のエッジの総数が KC に達するまで、青の前に赤のエッジをたどります。2 番目のパスでは、最初のパスでマークされた赤いエッジをたどることもできます (これらは合計にはカウントされません)。

追加の赤いエッジが KC に到達しない場合、それは不可能です。