1

我想知道是否存在算法在給定所有這些根頂點之間的一組根頂點的情況下計算有向圖中的最小生成樹(最佳分支)但不是圖中的一個根頂點和所有其他頂點。具有多個根頂點的圖中的最小生成樹

給定一組頂點根[1,4,6]和喜歡的一個,如下圖圖G:

enter image description here

...的algorighm應該返回類似綠子在同一張照片上。

我想得到這樣一個MST,它連接提供給算法的所有根頂點。我傾向於認爲,將要成爲算法的結果是包含從G.

所有根頂點和一些其他頂點

說明圖G的子圖:

  1. 我知道,有對有向圖不是MST,但有Chu–Liu/Edmonds algorithm
  2. 我想這樣一個算法的結果(如果它實際上是可能的話)將返回一個最佳分支,其中包括圖的頂點和所有根頂點。

回答

1

最小生成樹應該跨越所有的頂點。我想你可能實際上是在處理Steiner Tree問題,因爲你只需要連接它們的一個子集。不幸的是,帶有無向邊的傳統斯坦納樹問題已經完成,所以你有一條艱難的道路。

相關問題