科学网 › 标签 › 图同构

标签: 图同构

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

图同构01表示的多项式时间证明方法: accsys 2016-4-7 21:05; 图同构01表示的多项式时间证明方法姜咏江人们一直认为图同构的证明是一个 NP 类问题（见附录），果真如此吗？运用本人发明的图 0 和 1 表示法（参阅 http://blog.sciencenet.cn/blog-340399-958453.html ），通过对一个图顶点的排列，就能够证明两个顶点和边数都相同的图是否同构。下面给个例子说明证明方法。例题，证明下面图（ 1 ）和图（ 2 ）同构。图 1 同构图 1. 表格式图同构的证明要点要点：图 1 （ 1 ）的 0 和 1 表示如表 1 所示。图 1 （ 2 ）的 0 和 1 表示如表 2 所示。表 1 和表 2 看上去不相同。如果不改变图的顶点与边的相互关系，能够将表 1 的转换成表 2 ，或者将表 2 转换成表 1 ，那么就说明这两个图是同构图。表 1 图（ 1 ）的 0 和 1 表示 x1 x2 x3 x4 X5 x6 x7 x8 1 0 　 0 　 0 　　 0 1 0 　 0 　　　　 0 1 0 　　　 0 0 　 0 1 　 0 　　　 0 　　 1 0 0 0 0 　　　 0 1 0 　　　 0 　 0 0 1 0 　　 0 　 0 　 0 1 由图的定义可知，只改变顶点的位置，而不改变它们之间相邻的关系，那么不论如何移动顶点，所得到的图都是同一个图。这种图与视觉无关的属性自然成为了证明图同构的依据。反过来说，如果我们能够将视觉上不同的图，在顶点数量和边的关联关系不变的条件下，转化成视觉一致的图，就说明这两个图同构。图的 0 和 1 表示法将图固定在了二维的表中，因而可以做到视觉上的统一。对于视觉上不同的图，我们可以在图的 0 和 1 表示的二维表中，适当地移动顶点，那么同构的图一定会转换成相同视觉的二维表，而不同构的图一定不会有完全相同的表格式的表示。表 2 图（ 2 ）的 0 和 1 表示 a b c d e f g h 1 0 　 0 0 　　 0 0 1 0 　　　 0 　　 0 1 0 　 0 　　 0 　 0 1 0 　　　 0 　　 0 1 0 　 0 　　 0 　 0 1 0 　　 0 　　　 0 1 0 0 　　　 0 　 0 1 2. 表格式图同构证明根据表格式并试图的定义，表中每一行都是一个顶点与其相邻的顶点的关联关系。显然，左右移动顶点的相对位置或上下移动各顶点关联关系的相对位置，并不会改变图的定义。依据这一原理，以及顶点关联的边数，对照表 1 来左右变动表 2 的顶点，并上下移动编排顶点关联行，最终可以得到的结果如表 3 所示。表 3 图（ 2 ）转换成了图（ 1 ）的视觉 c f g b a d e h 1 0 　 0 　 0 　　 0 1 0 　　　 0 　　 0 1 0 　　　 0 0 　 0 1 0 　　　　　　 0 1 0 0 0 0 　　　 0 1 0 　　 0 　　 0 0 1 0 　　 0 　 0 　 0 1 由于表 3 是对照表 1 变动得到的，而且 0 和 1 表示完全相同，如此就建立起来的图（ 1 ）和图（ 2 ）顶点的一一对应，结果如表 4 所示。表 4 图（ 1 ）和图（ 2 ）顶点的一一对应关系 x1 x2 x3 x4 x5 x6 x7 x8 c f g b a d e h 3. 多项式时间讨论我们可以看到由表 2 通过移动行和列得到表 1 的过程并不是一个多项式时间复杂度的算法。两图如果同构，那么图 1 （ 2 ）最终要能够成为与表 1 完全一样的一个表。所以，我们就可以将表 1 复制一个，然后将表头清空（表 5 ）。如果我们能够选择图 1 （ 2 ）的顶点按照顶点相邻的关系，刚好将表头添写好，那么即是说，图 1 （ 2 ）就可以表达成表 1 ，进而也就说明了图 1 （ 1 ）和图 1 （ 2 ）同构。我们先选择边数最多的顶点 e 和顶点 x7 对应，根据相邻顶点，我们可以找到表 5 的 badeh 的选择。然后根据与 e 相邻的 d 点，可以确定 c 点的位置；在依据 b 点确定出 g 点，再依据 a 点确定出 f 点的位置，这样就证明了例题的两个图同构。表 5 未确定顶点的情况 c f g b a d e h 1 0 　 0 　 0 　　 0 1 0 　 0 　　　　 0 1 0 　　　 0 0 　 0 1 　 0 　　　 0 　　 1 0 0 0 0 　　　 0 1 0 　　　 0 　 0 0 1 0 　　 0 　 0 　 0 1 为了具有一般性，我们设图顶点的关联度（通过边相邻的顶点数）最大为常数 k n 。那么每次选择相邻顶点时不超过 k ！次。图若有 n 个顶点，那么选择排列的次数不超过 (k!) n 次。 k 是常数， n 是变量数， n 增大的过程中，计算次数不会超过 (k!) n 。 4. 结论通过表 1 、表 2 和表 5 的对照，你一定会理解表格式表示的图，证明图同构的方便简单的特点。如果我们不能够用排列图顶点的方法，使具有相同顶点和边的图得到一样的 0 和 1 表示表，那么它们就不是同构图，反之，它们一定都是同构图。 2016-4-7 修改附录：见蒋迅 - 《数学都知道》 http://blog.sciencenet.cn/blog-420554-967358.html; 个人分类: P/NP问题|5348 次阅读|0 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: 图同构

相关帖子

相关日志

关闭安全验证