基于格思想的图结构相似问题的算法

• 作者: 王晓敏 苏静 姚兵
• 来源期刊: 计算机科学
• 关键词: 格 图结构相似 撕裂运算 连通度
• 年，卷（期）: 2021,（z1）
• 所属期刊栏目: 交叉&应用|Interdiscipline & Application
• 页码范围: 543-551
• 页数: 9页
• 分类号: TP311|O.157.5
• 语种: 中文
• DOI: 10.11896/jsjkx.201100167

摘要

文中首先给出了顶点撕裂运算与顶点重合运算的定义,基于顶点撕裂连通度的定义证明了连通图的顶点撕裂连通度等价于连通图的连通度;给出了图的W-相似的定义.其次,给出了图撕裂组以及同构子图相似的定义,介绍了一种特殊图撕裂组和特殊图撕裂组匹配方法.再次,讲述了有关图和图撕裂组的运算和算法,主要有确定图撕裂组的算法、图撕裂收缩算法、图的顶点扩展和收缩算法.然后,给出了图的同构子图相似的基本定理.最后,总结全文并提出了几个值得以后深入研究的问题.