证明两个图同构的例题

姜咏江

下面的这两个图同构，用01同表法给出证明。提示：当前顶点用1表示，与其相邻顶点用0表示。

1. 用0和1表示图1

图1的01表示如表1所示。复制表1的01表示，并去除表头顶点编号（见表2），然后寻找两图顶点的一一对应关系。

表1  图1的01表示

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格式相同的对应

此后，再由顶点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的不变关系给出。

证毕。

2016-4-9