非常密集的無向簡單圖中的Hamilton路徑數

Question

計算極其密集的無向簡單圖（連接大約99.99％的邊）的Hamilton路徑數的最快方法（算法）是什麼？

我想的方式如下：

首先，計算完全圖的哈密爾頓路徑的數量。

一次刪除一條邊，但我無法弄清楚去除邊緣會減少多少條路徑。另外如何防止重複計數，同時刪除邊緣？

我在Math.SE上遇到了類似的問題，但那是關於漢密爾頓循環而不是路徑，我希望能夠顯着改變這個問題。此外，答案不是很清楚，因此這篇文章。

Answer 1

我不認爲你可以計算沒有 實際生成路徑或計算時單獨考慮每個路徑 漢密爾頓路徑的數量。對於特殊的圖表 - 如完整的圖表 - 這個 肯定是可能的，但不是一般的。

您可以在完整圖中生成所有漢密爾頓路徑，並在每個圖形中使用 （如果它使用圖中邊的子集）。當然 你可以通過修剪某些分支來加快速度，而 可以在完整的圖形中生成Hamilton路徑。

由於您的圖形非常大，這種方法肯定不是 可行。但是，您可以計算完整圖中包含缺失邊的其中一個的所有路徑的數量，然後減去此編號的 。

我不認爲這是微不足道的。關於它的一些想法：讓我們考慮最簡單的情況，即只有一條邊缺失。我們可以用一系列邊或節點來描述路徑 。假設你的圖有n個 節點。在完整的圖中，有n-1漢密爾頓路徑中的缺失邊緣的可能位置。邊緣可以在兩個方向上穿過 ，並且不與邊緣相鄰的節點可以穿過 ,(n-2)!不同的順序。因此，我們可以通過完整的曲線圖中減去

2 * (n-1) * (n-2)! = 2 * (n-1)! 

從漢密爾頓路徑的總數

到 獲得期望的結果。

如果正好有兩條邊缺失，我們不能只減去兩倍的 數字，因爲我們要計數兩條路徑，即包含兩條邊的路徑 。所以我們必須計算這個數字並且再次加上 。但現在它變得複雜了：重要的是邊緣 是相關的。如果它們相鄰，則數字小於 。因此，一般來說，您不能只計算包含k缺失邊的 哈密爾頓路徑的數量，但重要的是您正在考慮的邊和它們是否爲 相鄰或不相鄰。

但是，假設您可以計算通過選擇邊（所有排列，遍歷方向和路徑中的 位置）的路徑的數量。我們進一步假設k邊緣缺少 。您可以計算路徑的數量，包括至少一個這樣的邊緣的一個 ：

計算通過任何一個k邊緣的路徑數量，然後將其總和。

對於每一對邊緣，您都計算了兩次穿過 對的路徑，所以再次減去這些路徑（分別考慮每對 ）。

現在考慮包含三條邊的路徑。他們已經被計數了六次並且扣除了三次（三對不同），所以 你必須減去它們兩次。

包含四條邊的路徑必須被減3次（因爲 它們在包含3條邊的路徑中被表示4次）。等 上。

但是，您必須單獨考慮邊緣 的每個組合。甚至可能由於某個節點出現三次而導致某些邊緣集合不兼容。同時考慮到邊緣被穿越的方向。

所以沒有簡單的公式，但如果缺少邊緣的數量非常小，則可以計算路徑。