算法來檢查給定的圖是否是另一個圖的子圖

我假設我們有2個帶標記的圖G和T，並且該算法確定G的子圖是否與主圖T和子圖G中的對應頂點應該有相同的標籤算法來檢查給定的圖是否是另一個圖的子圖

2011-03-11 fayza

只需要注意一點，[Subgraph isomorphism problem]（http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem）是NP-complete。 – miku

該問題被稱爲"subgraph isomorphism"，它是NP完整的（因此可能很難）。你需要一個通用的解決方案嗎？或者只是爲了特定的圖形G？第二種情況要容易得多。有一些關於算法here的一般信息。在Boost Graph Library中有一個算法的版本（實際上，對於更一般的問題）（參見文檔here）。

來源

2011-03-11 23:42:15

+1首先引用關於此事的1993年線索:) – phooji

@ phooji：很多結果都沒有改變，很可能;我知道Nauty至少仍然在使用，儘管我從完整的圖同構問題中聽說過它。我從我的編輯中提到的算法是從1982年開始的。 –

@Jeremiah Willcock：1993 ... 1982 ...接下來是什麼？ 1971年？ ;） – phooji

一般問題的一般答案：你想解決的問題被稱爲「子圖同構」。看看這裏的進一步參考：http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem。

來源

2011-03-11 23:43:14 phooji

算法來檢查給定的圖是否是另一個圖的子圖

回答

相關問題