图同构问题综述.pdfVIP

图同构问题综述 数据科学与计算机学院 黄 1 3 2016.05.26 1 概述 芝加哥大学计算机科学教授László Babai 在 2015 年 11 月宣布了一个能在拟多项式时 间内解决图同构问题的新算法，该算法还有待进一步审查以确定其正确性. 如果最终被证 明是正确的，那么这将是计算机理论领域的一项非常重要的成果. 图的同构问题可以分为四类：精确图同构问题、精确子图同构问题、不精确图同构问 题和不精确子图同构问题. 其中后三个问题已经被证明是 NP 完全问题，而对于精确图同 构问题的复杂性问题，目前还没有明确的结果，即尚不清楚它是 P 问题还是NP 完全问 题，但至少知道它是NP 问题. 本文是图同构问题的一个综述，首先给出图同构问题的定义，接着介绍了图同构问题 判定算法的研究现状和应用，最后介绍一些具体的判定算法. 2 图同构的概念 一个图可以存在多种不同的形式，这些不同形式的图都具有相同数目的顶点、边，而 且边还具有相同的连接性. 这些不同形式的图就是同构. 直观上地说，如果两个图 和 有相同数目的顶点和边，并且边的连接性也相同， 那么就说这两个图是同构的. 我们可以把一个图看做是另一个图经过扭曲得到的. 下面给 出图同构的严格定义. 给定两个无向简单图 和 ，如果存在一个双射 → ，使得对于任意 的 ∈ ，有 ⟨ ⟩ ∈ 当且仅当 ⟨ ⟩ ∈ ，则称图 和 是同构 的，记为 ≃ . 如果 ≃ ，那么： (1) | || |. (2) | || |. (3) 和 的度序列相同. (4) 如果 { } 是 的长度为 的圈，那么{ } 是 长 度为 的圈. 上述的条件是两个图 和 同构的必要条件，下面给出几个充分条件： (1) ≃ 当且仅当 ≃ ，其中 和 都是简单图. (2) ≃ 如果它们有相同的邻接矩阵. (3) ≃ 当且仅当它们相应的子图也同构. 1 图1: 图同构的例子 图2: 、 的补图 例如，如图 1所示，图 的顶点的度为3，而图 和 的所有顶点的度都为2， 因此 均不同构于 和 . 考虑图 和 的补图，如图2所示，我们有 ≃ ，所以 ≃ . 在这里我们还要介绍一下平面图的概念. 如果图 可以画在平面内并且任意两条边不 交叉，则称 为平面图. 似乎不是平面图，但实际上只要把 的一条对角线移出去 就可以了，如图3. 图3: 平面图 完全图 和完全二分图 是最小的非平面图，如图4. 任何一个平面图都将平面分成若干个区域. 对于区域