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

子图同构问题（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 使得

  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))
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容