容斥原理與子集卷積（三）

這次介紹一個和最小生成樹問題很類似的，名叫斯坦納樹的問題。

斯坦納樹有很多版本，這裡我們說的是在圖論中的斯坦納樹問題。

斯坦納樹（Steiner Tree）

定義有點複雜，容我先編個故事。

國家A和國家B在打仗，國家B無情地對國家A發動了地毯式轟炸，破壞了國家A城市間的所有道路。

為了儘快恢復，國家A列出了某些重要城市的名單，並研究出了修復每條道路的成本。如下圖所示：

現在問，如何在最小成本的情況下，修復道路，使得這些重要城市保持連通。比如上圖中，按如下的選擇，就可以達到最小的成本：

顯然，我們最後的結果一定是棵樹。但和最小生成樹不同的是，我們不用保證所有店都連通，只需要保證部分點連通即可。這就是斯坦納樹問題。

定義：給一個連通無向圖 ，和邊權 。現在有一個點集 ，求一個邊權和最小的連通子圖 ，使得 。其中 就被稱為斯坦納樹。

斯坦納樹也是一個NPH問題。

下面給出斯坦納樹的若干種解法。

暴力解法

在一個放棄思考的情況下，不難得出一個暴力的解法：直接枚舉點子集，而後跑個最小生成樹。這樣做的複雜度是 ，其中 。

顯然暴力做法在 很大， 很小的時候，是非常不理智的。鑒於只需要考慮 中的點，我們可以從動態規劃的角度來解決。

動態規劃

動態規劃可以優美的做到 ，至於怎麼實現，由於我主要想介紹容斥原理（我懶），所以就留給大家做練習啦。

提示一下：狀態維護兩維，一維是當前的集合，一維是當前的根。

容斥原理做法

特別提示：這裡的介紹的容斥原理做法，只能解決邊權都是 的情況，即 ，無權圖。

為了方便處理，我們需要將問題定義成判定型問題：

定義（無權斯坦納樹）：給一個無向圖 ，一個點子集 ，和一個非負數 。我們的目的是判斷是否存在一棵最多 條邊的樹 ，使得 。

在本系列之前的文章中，我們用容斥原理統計了一個圖的哈密頓圈的個數。

我們發現，相比研究圈（circle）、路徑（path），通過研究遊走（walk），來進行容斥是個更不錯的主意。

於是，我們在這個問題中，也嘗試通過遊走來分析。

與之前的統計哈密頓圈不同，這裡我們研究的遊走是分支遊走（branching walk）。

定義（分支遊走）：一個無向圖 的分支遊走定義為一個二元組 ，其中 是一棵有根有序樹（rooted ordered tree），並且 是一個同態（homomorphism）映射，即， ，有 。通常稱 為 的長度。

舉個例子，如下圖所示：

定理4：拿出 中的任意一點 。如果圖 包含了一棵樹 ，並且 ， ，當且僅當，圖 包含一個從 開始的分支遊走 ，滿足 ， 。

定理4的是可以直觀感受到的。

事實上，由於一棵樹本身就是一個分支遊走，所以如果一棵邊數小於等於 的樹覆蓋了 中所有點，那麼就存在了一個長度不超過 的分支遊走（就是這棵樹本身）。如果一個長度大小等於 的分支遊走覆蓋了 中所有點，那麼這個分支遊走的生成樹就是邊數不大於 的一棵斯坦納樹。

如下圖所示：

有了定理4，我們就只需要統計，圖中有多少從 開始，並且長度為 的分支遊走，覆蓋了 中所有點。

我們照著葫蘆畫瓢：

• 令全集 表示從 開始，長度為 的所有分支遊走。
• 對 ，令 ，即訪問了 的所有 中的分支遊走。
• 我們的目標就是計算

根據定理2，我們有：

於是我們的目標就是計算 ，既是，從 出發，長度為 ，不訪問 中的任意一點的分支遊走的方案數。

定理5：對於 ， 可以在 的複雜度內計算出來，其中 。

證明：我們使用動態規劃來證明這個複雜度。令 。令 表示在 中從 出發，走長度為 的分支遊走的方案數。有轉移方程：

相當於枚舉了 作為 的第一個兒子。如下圖所示：

狀態數是 ，轉移數是 ，所以求解 的複雜度就是 。

綜上，我們便能通過統計分支遊走的數量，來判斷是否存在小於 的斯坦納樹。

定理6：無權斯坦納樹問題可以在 的時間內解決。

推薦閱讀：