科学网 › 标签 › 图01表示法

标签: 图01表示法

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

没有相关内容

相关日志

证明两个图同构的例题: accsys 2016-4-9 21:47; 证明两个图同构的例题姜咏江下面的这两个图同构，用 01 同表法给出证明。提示：当前顶点用 1 表示，与其相邻顶点用 0 表示。 1. 用 0 和 1 表示图 1 图 1 的 01 表示如表 1 所示。复制表 1 的 01 表示，并去除表头顶点编号（见表 2 ），然后寻找两图顶点的一一对应关系。表 1 图 1 的 01 表示 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 0 　　　 0 　　　　 0 　　　　　 0 1 0 　　 0 　　　　　　　　　　　 0 1 0 　　　 0 　　　　　　　　　　 0 1 0 　 0 　　　　　　　　　　　　 0 1 0 　 0 　　　　　　　　 0 0 　　 0 1 　　 0 　　　　　　　　　　 0 　　 1 0 　　　　　　　　　　 0 　 0 　 0 1 　 0 　　　　　　　　　　　 0 　　 1 0 0 　 0 　　　　　　　　　　 0 0 1 　 0 　　　 0 0 　　　　　　　 0 　 1 　 0 　　　　　　　　　　　　 0 　 1 　　 0 　　　　　　　　　 0 　 0 　 1 0 　　　　　　　　　　　　　　 0 1 0 0 　　　　　　　　　　　 0 　 0 1 0 　　　　　　　　　 0 　　　 0 0 1 2. 确定图 2 顶点位置依据图 2 ，选中关联度最高的顶点之一 k 。 k 相邻的顶点共有 4 个。有 2 个关联度为 4 ，一个关联度为 2 ，另一个关联度为 3 。依据这些特点，在表 2 的第 10 行有个 1 ，其右面的 0 向下 2 行是 1 ，表示它们是邻点且关联度为 2 ；而左面向上有两个关联度为 4 的顶点相邻；最后一行顶点的关联度为 3 ，且与第 10 行的顶点相邻，故可将第 10 行值为 1 的列表头定位 k 。由于顶点 l 的关联度为 2 ，与 k 和 o 相邻，则 12 行为 1 的列是 l 。依据 l 相邻的关系，第 15 列应是 o 。此外，与 k 相邻的关联度为 3 的顶点只有 n ，故 n 在 16 列。剩下的问题是 k 顶点左面 2 列如何放置 b 和 m ？若将 b 放在 k 的左面，依图 2 知其应连接一个关联度为 2 的顶点。由第 9 行的 0 纵向对应为 1 的行来看，它没有这样的邻点。所以这个位置应放置 m 。再由于图 2 的顶点 a 关联度为 2 ，且与 b 相邻，所以可由 b 来确定 a 的位置。添写的结果如表 2 表头绿色所示。表 2 寻找图 2 与图 1 格式相同的对应 h g e d c f a b m k i l j p o n 1 0 　　　 0 　　　　 0 　　　　　 0 1 0 　　 0 　　　　　　　　　　　 0 1 0 　　　 0 　　　　　　　　　　 0 1 0 　 0 　　　　　　　　　　　　 0 1 0 　 0 　　　　　　　　 0 0 　　 0 1 　　 0 　　　　　　　　　　 0 　　 1 0 　　　　　　　　　　 0 　 0 　 0 1 　 0 　　　　　　　　　　　 0 　　 1 0 0 　 0 　　　　　　　　　　 0 0 1 　 0 　　　 0 0 　　　　　　　 0 　 1 　 0 　　　　　　　　　　　　 0 　 1 　　 0 　　　　　　　　　 0 　 0 　 1 0 　　　　　　　　　　　　　　 0 1 0 0 　　　　　　　　　　　 0 　 0 1 0 　　　　　　　　　 0 　　　 0 0 1 此后，再由顶点 a 的相邻关系，可以确定 d 的位置。由 n 可以确定 p 的位置。由 p 可以确定出 j 的位置。由 j 可以确定 i 的位置。由 m 的邻点关系，能够确定出 f 的位置。因为 d 、 f 、 b 都与 c 相邻，故可确定出 c 的位置。由 d 又可确定出 e 的位置。由 e 又可确定出 g 的位置。由 g 、 f 、 i 能确定出了 h 的位置。最后我们依据图 2 的顶点相邻关系，对表 2 中放置的每个顶点的相邻关系进行检查，如果完全没有错误，便知图 1 与图 2 是同构图。顶点对应关系如下，边的对应由表中0和1的不变关系给出。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 h g e d c f a b m k i l j p o n 证毕。 2016-4-9; 个人分类: P/NP问题|11469 次阅读|0 个评论

图同构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 个评论

更多...

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

关闭 安全验证

标签: 图01表示法

相关帖子

相关日志

关闭安全验证