Ric*_*aca 8 isomorphism monomorphism subgraph
在我参与过的一个项目中,出现了同构与单态的主题.
一点背景:我不是图论的专家,也没有正式的培训.但是这个主题在化学中非常重要,化学家期望在他们使用的结构搜索系统中进行特定类型的子图匹配.
如果目标图A具有n个节点和m个边,则化学家将接受子图匹配,其中查询图B具有n个节点和m-1个边.唯一的要求是B中的每个边都应该存在于A中.例如,6个节点的线性链应匹配6个节点的循环.
这种匹配是同构还是单态？也许还有别的东西？
Cha*_*tin 10
设G1,G2分别是由顶点组和边V1,V2和E1,E2组成的图.
如果V2的每个顶点与V1中的顶点之间存在一对一映射,并且在E2中的每个边缘与E1中的某个边缘之间存在一对一映射,则G2与G1的子图同构.因此,要进行同构,您需要具有完全匹配,包括图形是否包含节点之间的多个边.
如果在顶点之间存在这样的映射,则G2是单态的,并且在V2中的所有顶点之间存在边缘,其中V1中存在对应的边缘.但只要存在至少一个边缘,那就足够了.
这是comp.lang.python中的一个很好的包描述.