二部圖最大匹配

Question

假設有兩個圖形這樣的擴展：

我們的目標是找到兩者graph.And之間的匹配對應現在我們使用的方法來計算相似度兩個圖之間的兩個節點。 （A，1）表示節點A與右圖中節點1之間的左圖的相似度。然後我們就可以有表是這樣的：

我們的目標是計算最大重量匹配所有這些節點。我們可以使用Kuhn-Munkras算法來解決這個問題。

但現在的問題是，如果我們添加兩張圖的邊之間的相似度，我們如何計算最大權重匹配。這意味着該表變成這樣：

AA意味着節點A和AB意味着從A到B的邊緣的限制是，如果最後的結果是，節點A相匹配的節點1，邊緣AB必須匹配12或13.所以我們可以使用像Kuhn-Munkras這樣的算法來解決這個問題嗎？如果不是，我們如何找到多項式時間內的最大權重匹配？

Answer 1

假設我們想知道兩個圖是否是同構的，例如，在你的例子中的兩個。

在我們有第一圖表邊緣AC和CB，而在第二圖表我們具有邊緣13和32。

我們可以設置權重矩陣，使得有一個高獎勵在映射任何邊緣第一個到第二個邊緣。

即AC-> 13和AC-> 32和CB-> 13和CB-> 32都將具有權重1，而所有其他匹配都具有權重零。

當且僅當存在與等於邊數的權重匹配的最大權重時，圖之間存在同構。

因此，您的問題至少與圖同構一樣困難，所以庫恩算法不可能有效地擴展到這種情況。