|||
证明两个图同构的例题
姜咏江
下面的这两个图同构,用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
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-10-19 22:50
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社