正好有k個顏色邊緣的生成樹

我有一個連接的無向圖，邊緣分別是黑色或白色，並且是一個整數k。我想寫一個算法，告訴是否有一個生成樹只有k個黑色邊緣（不一定要找到實際的樹）。正好有k個顏色邊緣的生成樹

我使用Kruskal算法來查找生成樹中黑色邊緣的最小和最大可能數量。如果k超出此範圍，則不能存在具有k個邊的生成樹。

但是我不知道是否有必要爲該範圍內的每個k生成一棵生成樹。我的直覺說，是的，它適用於我嘗試過的每個例子，但我無法弄清楚如何證明它。

有什麼建議嗎？提前致謝。

來源

2010-12-06 Rupert

如何使用Kruskal算法找到最小和最大黑邊數量？ – 2010-12-06 05:53:18

對不起，我認爲節點是黑色或白色，你說邊緣。 – 2010-12-06 06:56:01

讓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.

第二步總是可能的，因爲至少有一個邊緣不G_max在每個週期。

該算法保持了G的生成樹的性質。它每步最多添加一個黑邊，所以G演示了k_min和k_max之間的所有k都具有k個黑邊的生成樹。

來源

2010-12-06 07:57:33

克魯斯卡爾會找到你最小的生成樹 - 所以爲了找到Gmin你需要以相反的方式做到這一點。 gmin =案例中所有的黑邊都給予了懷特1，白色給予了懷特0.算法首先使用所有白色邊緣，然後是黑色邊緣。這樣我們會得到gmin。

來源

2012-05-18 07:52:09 shai

正好有k個顏色邊緣的生成樹

回答

相關問題