Bod论文报告.pdfVIP

Section2:一些基本定义 若存在边(v, w) ∈E 且f(v, w) = c，则称颜色c 邻接顶点v 。（显然c 可能邻接很多 定点） DEF2.2 任意一条边的两个顶点一定会同时在某个X 中，每个X 中最多有k+1 个顶i i 点。 Section3: Graph Isomorphism 用一系列k-separators 来分解图G，若图H 也能以同样的方法来分解，则说G 和 H 同构。 因此需要判断H 的所有k-separators 对应的分量、G 的一个确定分解方式所对应 的所有分量、相应的 k-separator 之间的所有映射，来判断这个映射是否可以被 扩展到一个图的映射。 总的思路：使用DP 的方法记录规模小的子图结果，后面判断大的时会用到前面 的这些结果。 LEMMA3.1: G 是partial k-tree 当且仅当存在一个k-vertex separator C ，使得所有r 的子图G(r, j) 是partial k-tree 。（n = k+2） LEMMA3.2: 给出了判断G(i, j)是partial k-tree 的条件。其中Cm相当于用v 替换C 中i 满足条件1 和2 的点或者就是Ci本身。 LEMMA3.3: 给出了判断G 和H 同构的条件。 j f j′ LEMMA3.4: 给出了判断(C , C )≡(D , D )的条件。 i i i’ i′ Step1: 运行REF[2]中的算法来判定G 是否是partial k-tree ，同时获得下列信息： 1. k-vertex separator C ，使得所有的子图G(r, j)是partial k-tree 。r 2. 所有的G(i, j)均可以被分解为G(m, l)，满足G(m, l)最多含有k+1 个顶点； 或者对G(m, l)进行递归处理必然会得到这样的结果。 这些信息称为G 的partial k-tree 表示。 有Ο(n)个这样的G(i, j)和C 。ji Step2: 找到所有的D 和Dj （O(nk+1) ）。 i i j j′ k+1 现在需要对所有的(C , C ) （Ο(n) ）、所有的(D , D ) （Ο(n ) ）和所有的映射 i i i’ i′ j f j′ f: C D （k! =Ο(1) ），判断是否(C , C )≡(D , D )成立。 i i’ i i i’ i′ 以如下方式进行： 先对(Di, D )排序，然后按大小顺序进行处理。ji Case1 （|Dj′ j′ j |=1）: 对每个Triple((D , D ), (C , C ), f)，其中f: C D ，需要 i′ i’ i′ i i i i’ j f j′ O(1) （尝试所有的可能的映射方案，共 k!种）的时间来判断(C ,