圖匹配問題系列（六）子圖同構(gòu)

子圖同構(gòu)問題（Subgraph Isomorphism Problem）

1） 給定一個待查詢多重圖 Q = (V^q, E^q, L^q_E, T^q), 其中V^q是頂點集合，E^q是邊集合，注意每個頂點對之間可能存在多重邊，T^q是邊類型集合，L^q_E:V \times V \to 2^{T^{q}}是頂點對的標簽函數(shù)，由于有T^q種邊的類型，所以任意頂點對之間的多重邊要從2^{T^{q}}種可能選擇。

2） 給定一個被查詢的多重圖G=(V, E, L_E, T)
3） 我們要找的子圖同構(gòu)函數(shù)是一個單射函數(shù)(injective function)\psi : V^q \to V 使得

  1. \forall (u_m, u_n) \in E^q, \exists (\psi(u_m), \psi(u_n)) \in E \text{ and } L_E^q (u_m, u_n)\sqsubseteq L_E(\psi(u_m), \psi(u_n))
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容