增量發現在簡化圖中的

Question

我找的不相交集的圖形G數，然後我刪除圖形G的一些頂點，使圖形G'，我想找到G'的獨立集合的數量不相交集的數目，沒有像G那樣對G'做同樣的事情嗎？

Answer 1

我會推薦以相反的順序來做這件事。

我的意思是：

1. 開始用最小的圖形G」和使用union查找算法找出不相交的集合。
2. 然後加入G中的新元素，並通過繼續使用從輸出開始聯合查找算法，從第1步
3. 重複添加新的頂點，尋找獨立集合必要
多次加入一些額外的套在一起

逆序更好的原因是因爲您只需訪問第2步中的新頂點，因此您不必爲每個新圖形重複大量工作。