图同构

2021-03-09 13:55:59 浏览:537

定义

如果两个图具有相同的顶点数、边数以及相同的边连通性,这样的两个图完全等价,被称为同构图[1]。如下图1所示,左右两侧图属于同构图:

图 1 同构图

图同构的问题一般可以分为四个不同的研究类型:精确图完全同构、精确子图同构、不精确图完全同构、不精确子图同构。

与图同构问题类似的是图匹配问题,图匹配(graph matching)是判断两个图是否同构,如果同构,找出至少一个使得两者做成同构的节点间的一一对应关系。图同构和图匹配问题的计算负责度都属于NP问题[2],近期有很多学者就计算复杂度的挑战提出一系列的近似方法[3]

参考文献

[1] McKay B D. Practical graph isomorphism[J]. 1981.
[2] László Babai. Groups, Graphs, Algorithms: The Graph Isomorphism Problem. ICM 2018.
[3] Lyzinski, Vince, Information Recovery in Shuffled Graphs via Graph Matching, 2016, arXiv:1605.02315.

作          者: 泮桥成像光电商城

出          处: https://www.ipanqiao.com/entry/422

版          权:本文版权归泮桥成像光电商城所有

免责声明:本文中使用的部分文字内容与图片来自于网络,如有侵权,请联系作者进行删除。

转          载:欢迎转载,但必须保留上述声明;必须在文章中给出原文链接;否则必究法律责任。

Copyright © 2019-2022 南京超维景生物科技有限公司 版权所有 www.ipanqiao.com苏ICP备20009590号-1
联系我们
立即做合同
微信客服
电话咨询

400-998-9826

17302548620

快速留言

泮桥成像光电商城专业人员会在24小时之内联系您

关闭 提交