姜咏江 将图的每个顶点用 1 表示，而与其相邻的顶点用 0 表示，这样形成的表就表示了一个顶点与周围顶点的相邻关系。全部顶点相邻关系的 01 表示就形成了一张行列数相同的表。 1. 图 01标准表 例如，图 1 的两个图直观来看，它们根本不相同。其实按照图的定义来看，除了对顶点标注的名称不同，根本就是同一个图。如果我们能够将 H 图的顶点名称用 G 图的对应名称一一替换，就说明 G 和 H 是一个图。这就是图同构的意思。 图 1 同构图 如何找到同构图顶点所有顶点的一一对应关系？这就是判断图同构要解决的问题。据说直观问题的处理十分复杂，被许多人认为是一个 NP 问题。 图的 01 表示可以将同构图用一张表来表示。也就是说，不同构的图不能够表示成同一张表。这里说的同一张表不包括表头文字。 G 图的 01 表示如表 1 所示。 表 1 图 G 的 01 表示 1 2 3 4 5 6 7 8 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 不改变表 1 的内容，可以将表头用 H 的顶点标识替换，且使图 H 顶点的相邻关系不变。若替换后恰是表达了图H的各顶点相邻关系 ，则找到了图 G 和图 H 的同构对应，说明它们是同一个数学定义的图。 下面的表2，就是将表 1 的表头用对应的 H 顶点标识替换，且满足顶点的相邻关系 。这说明图 G 和图 H 是同构图。 表 2 图 H 与 G 同构的 01 表示 c a b d g e f h 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 任何一个有 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求对应 a e （ d ） f b （ f ） d h g 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 从图 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
标签: 图同构
