美文网首页
图匹配问题系列（六）子图同构

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

作者: 四碗饭儿 | 来源:发表于2021-01-26 05:18 被阅读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 使得

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

    相关文章

      网友评论

          本文标题：图匹配问题系列（六）子图同构

          本文链接：https://www.haomeiwen.com/subject/nvvwzktx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|图匹配问题系列（六）子图同构|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！