博文
图同构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
https://m.sciencenet.cn/blog-340399-968548.html
上一篇：限位数用于运算器设计原理知多少(续）
下一篇：哈密顿图同构的证明
