如何表示線性規劃約束中的最小生成樹？

Question

假設我們得到了一個加權圖G和它的生成樹T，我們想改變邊的權重，使得T是一個最小生成樹和所有| w_i - w'_i |其中w_i是邊i_th的權重，w'_i是改變後的邊i_th的權重。

我認爲這很明顯，我們的目標是儘量減少| w_i - w'_i |對於所有我和我們的變量是w'_i，但我無法找到如何表示T是約束下的最小生成樹。

Answer 1

對於每個i，使得第i ^個邊緣不是T，對每個j，使得第j ^個邊緣從第i ^{的一個端點位於T中的唯一路徑在th}邊緣到其他，有一個約束w _i' - w _j'≥0.

Answer 2

您可以使用Prim's algorithm的修改版本。

該算法構建了一個連接組件，在每個點處將組件的權重最低的邊添加到組件外的頂點。

請注意，在每個階段，您的原始生成樹中都會有一條邊（稱爲e）將組件連接到組件外的頂點，但圖中可能存在其他邊。

您可以檢查所有可能的邊緣（從組件到組件外）並計算最小權重。然後，您需要將e的初始重量改變爲計算出的最小重量。

然後，您可以將邊e添加到組件並重復，直到您使用所有原始生成樹邊計算出最小生成樹。