姜咏江

将图的每个顶点用1表示，而与其相邻的顶点用0表示，这样形成的表就表示了一个顶点与周围顶点的相邻关系。全部顶点相邻关系的01表示就形成了一张行列数相同的表。

1.             图 01标准表

例如，图1的两个图直观来看，它们根本不相同。其实按照图的定义来看，除了对顶点标注的名称不同，根本就是同一个图。如果我们能够将H图的顶点名称用G图的对应名称一一替换，就说明G和H是一个图。这就是图同构的意思。

图1  同构图

如何找到同构图顶点所有顶点的一一对应关系？这就是判断图同构要解决的问题。据说直观问题的处理十分复杂，被许多人认为是一个NP问题。

图的01表示可以将同构图用一张表来表示。也就是说，不同构的图不能够表示成同一张表。这里说的同一张表不包括表头文字。G图的01表示如表1所示。

表1  图G的01表示

不改变表1的内容，可以将表头用H的顶点标识替换，且使图H顶点的相邻关系不变。若替换后恰是表达了图H的各顶点相邻关系，则找到了图G和图H的同构对应，说明它们是同一个数学定义的图。

下面的表2，就是将表1的表头用对应的H顶点标识替换，且满足顶点的相邻关系。这说明图G和图H是同构图。

表2  图H与G同构的01表示

任何一个有n个顶点的图都可以表达成对角线对称的n×n表。其中左上右下的对角线上全是1，其它位置是0或空格。其中与1同行或同列的0表示这两点相邻，空格表示不相邻。

我们将左上右下对角线全是1的图01表叫标准表。显然，同构图一定有相同的标准表。

2.               标准表的性质

我们将一个顶点相邻的顶点数称为关联度。首先，同构图对应顶点的关联度一定相同。其次，每个对应顶点的相邻关系必然相同。在标准表上找到满足这两点是用标准表确定图同构的关键。

容易想到，如果两个图同构，那么就应该有相同的标准表。如此，我们只要先作出一个图的标准表，并将其复制一个，去掉表头标识，就可以用该表来安排了另一个图的顶点对应位置。

一般来说，安排n个顶点的排列，这是一个n个标识的排列问题，是一个n！的问题。但实际上在这里并非如此。

图的标准表有如下的性质：

（1）标准表是一个对角线对称表。

（2）只有对角线上有“1”，其余数码只有“0”。

（3）每个“1”的第 i 行和第 i 列如果有一个是“0”，那么另一个也是“0”，这种0和1都表示的对应，都表示着图顶点的相邻关系。

3.               利用标准表的性质确定图的对应关系

表G和H的顶点关联度都是3，当我们将c放到第一个位置时，从图H看，我们只要确定a、d、e的位置即可。因而这最多有3！的排列。其实我们并不会这样做。我们可以先试着将a、d、e的位置方在第1行0的上方，然后看它们是否满足各自相邻的关系。

由图H可见a与d共同和c或b相邻，c已经确定，故在表2的a与d之间添b。之后，通过a的邻点，将g写在d的右面。余下的通过d和e的相邻关系，确定出f和h的位置。

为了确保对应的正确性，要一一对每个顶点的相邻关系检查，确定无误，就证明了图G和图H是同构图。

4.               图不同构检验

并不是具有顶点数相同和顶点关联度相同的图就是同构图。下面图2 所示的两个图就因为找不到相同的标准表，因而不是同构图。

图2  不同构图

由于图T的每个顶点属性相同，故用图G的标准表来选择图T任意一个顶点开始的排列，结果的关系应是相同的。我们不妨就从a顶点开始（见表3）。

表3  复制的G标准表对T求对应

从图T可见，和e相邻的另外两个点是d和f。可以试着将d放在e和b之间，那么f就自然要放到b和h之间。如此一来，从表3可见e和b都是d的邻点，但由图T可知这是否定的。为此，将d与f的位置进行交换，那么由图T的f点可见表3的最后一列应是g，但从d点的相邻关系可见这一列应标注c，如此产生的矛盾说明图G和图T没有共同的标准表。由图T各顶点关联属性的一样性，可知图G与T不可能产生相同的标准表，因而不可能同构。

2016-04-11