子圖中提取基於節點

我想找到什麼是獲取節點上的一個子築底的方法.. 我們已經有了一個大的圖形（定向或不），我們已經有了一個節點列表，我們想從圖表中提取，但我們還想提取中間節點...子圖中提取基於節點

當我們看子提取基於2個節點，問題是很容易的......我們可以在所有簡單地提取所有的中間節點之間的決定這些2個節點，或從最短路徑只有中間節點之間的路徑...

，但如果有超過2個節點提取的...怎麼能解決這一問題？

我苦苦尋找這樣一個問題的任何出版物......可能是因爲我不知道什麼是它的確切名稱。（如果它真的出現在圖論中的問題）

來源

2013-11-28 marcinh

你究竟想要什麼？你想要跨越一組頂點的最小子樹嗎？ –

問題，你問我解決了我的問題（不同的觀點）:)我找到了問題的名稱 - 斯坦納樹發現... thx Jan :) – marcinh

正如Jan所評論的，問題並不具體是什麼目標。

如果你希望儘量減少重樹問題稱爲generalized Steiner tree。

如果您想要在這些節點之間生成任何種類的生成樹，您可以在圖上使用您希望連接的一組節點來創建最小生成樹，並使用它們之間最短路徑連接每對節點的邊。這是一個完整的圖表，創建起來很昂貴。我認爲可以通過同時傳播每個節點來加速它，並且當兩個「氣泡」第一次接觸時創建這兩個點之間的路徑（同樣最短）。所有節點將逐漸連接。可能有些路徑重疊，這可以用來縮短樹。

來源

2013-11-29 08:14:06 Ante

子圖中提取基於節點

回答

相關問題