如何以最少的步驟刪除圖表？

給定一個有向圖，我如何找到刪除最小數量的節點以刪除整個圖所需的順序？我假設如果一個節點被刪除，連接到它的所有外部節點（任何程度）也被刪除。如何以最少的步驟刪除圖表？

例如，在二叉搜索樹中，刪除樹中所有節點的最快方法（假定是）將刪除根節點。但是，給定任何圖表，如何確定要刪除哪個節點？

我心目中的（很慢）什麼：

生成所有可能的子圖，並與最外邊找到子。
刪除該子圖。
重複，直到沒有剩餘的節點。

爲什麼它是一個很好的問題： 假設我們得到與代表世界所有問題的節點有向圖，而所有這些節點與代表的原因/效果的邊緣（即一些問題進行了連接造成他人）。我們如何才能找到擺脫所有問題的最少數量的問題？

2015-09-07 Mico Abrina

歡迎使用stackoverflow。從問題的複製/粘貼性質來看，這是一個分配問題。我們不介意幫助那些人，但目前格式化的方式是「爲我做」，我們不在這裏做。如果我們是，我們最終會獲得學位;）。用你試過的一些例子更新你的問題，如果可以的話，我們會提供幫助。 – ScottMcGready

我已經添加了我對這個問題的答案，但我不得不承認這是一個非常慢的算法。另外，請記住，這不是一個分配問題。我只是想知道是否有人能想出解決這個問題的更好方法。 –

好得多。你現在會收到一個體面的迴應。 – ScottMcGready

一個頂點可以有：

未連接邊緣或出站連接邊緣只（即路徑的第一頂點）;
僅限入站連接邊（即路徑的最後一個頂點）;或
傳入和外發連接邊緣 - 在這種情況下，它可以是：
1. 一個strongly connected component（SCC）的部分 - 即一個週期a->b->c->a或在兩個方向上a->b->c + c->b->a連接邊緣的頂點;或
2. 部分有向非循環子圖 - 即b在簡單路徑a->b->c中或在一組分支路徑a->b->c + b->d->e + f->b中。

頂點匹配情況（1）可以被平凡搜索和刪除 - 無呼入邊緣的頂點不能被刪除任何其他頂點所以必須包含刪除所需的最小集合的頂點的內刪除圖表。

匹配情況（2）和（3.2）的頂點可以忽略;刪除路徑頂部的頂點將刪除路徑中間的所有頂點（情況3.2）和路徑末尾（情況2），因此這些頂點將永遠不會包含在要刪除的最小頂點集合中圖表。

刪除包含在SCC中的任何頂點（案例3.1）將刪除SCC中的所有頂點（以及從SCC分支出來的所有後代子樹）。通過將SCC摺疊成單個僞頂點（其中連接到包含在SCC中的頂點的所有邊被替代地視爲與僞頂點具有相同的方向性連接），可以（簡單地）減小圖。對所有SCC重複此操作會將該圖減少爲連接有向無環圖（DAG）的集合。每個DAG將具有一個或多個根頂點（沒有出邊），它們可以是實際的頂點，情況（1）或僞頂點，代表情況（3.1）。最小刪除集合是這組根頂點 - 即情況（1）的所有根頂點和每個根假頂點（表示情況3.1）任何一個包含在該SCC內的實際頂點。

Stronly連接的組件可使用Tarjan's Strongly Connected Components Algorithm被發現和一次減少到DAG根頂點可以通過入站邊沿進行計數找到。

刪除這些頂點的順序並不重要 - 刪除這些頂點中的任何一個都不會刪除最小刪除集中的任何一個，以便它們可以按任意順序刪除，並且必須全部刪除以刪除整個圖。（最小刪除集合中的頂點可能會共享它們的部分或全部後代，刪除的順序會影響這些後代的刪除順序，但在問題中沒有問到這一點。）

來源

2015-09-08 14:25:16 MT0

如何以最少的步驟刪除圖表？

回答

相關問題