在我从事的一个项目中,主题是同构与单态的出现 http://depth-first.com/articles/2008/11/13/one-of-these-things-is-not-like-the-other.
一点背景知识:我不是图论方面的专家,也没有接受过正式的培训。但这个主题在化学中非常重要,化学家期望在他们使用的结构搜索系统中发生特定类型的子图匹配。
如果目标图 A 有 n 个节点和 m 个边,那么化学家将接受其中查询图 B 有 n 个节点和 m-1 个边的子图匹配。唯一的要求是 B 中的每条边都应出现在 A 中。例如,6 个节点的线性链应与 6 个节点的循环匹配。
这种匹配是同构还是单态呢?也许完全是别的什么?
设G1、G2分别是由顶点和边V1、V2和E1、E2的集合组成的图。
G2 与 G1 的子图同构,当且仅当 V2 的每个顶点与 V1 中的顶点之间以及 E2 中的每条边与 E1 中的某些边之间存在一对一映射。因此,要实现同构,您需要精确匹配,包括图是否在节点之间包含多个边。
G2 is 单态iff 顶点之间存在这样的映射,并且 V2 中的所有顶点之间存在一条边,而 V1 中也有一条对应的边。但只要至少存在一条边,就足够了。
这是来自的一个很好的包描述.
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)