图匹配问题系列（六）子图同构

2021-01-26 本文已影响0人四碗饭儿

子图同构问题（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}}$ 是顶点对的标签函数，由于有 $T^q$ 种边的类型，所以任意顶点对之间的多重边要从 $2^{T^{q}}$ 种可能选择。

2）给定一个被查询的多重图 $G=(V, E, L_E, T)$
3）我们要找的子图同构函数是一个单射函数(injective function) $\psi : V^q \to V$ 使得

$\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))$

图匹配问题系列（六）子图同构

猜你喜欢

热点阅读