Graph ProblemJune 22, 2017Jinkun Lin1 Outline• 顶点覆盖• 图着色• 团2 顶顶顶点点点覆覆覆盖盖盖 顶顶顶点点点覆覆覆盖盖盖定定定义义义：：： 给定一个无向图G = (V,E)，顶点覆盖是指图G顶点集的一个子集C ∈ V，使得G的每一条边都至少有一个点属于C3 顶顶顶点点点覆覆覆盖盖盖归归归约约约规规规则则则• Degree-0一个孤立点u不可能包含于最小顶点覆盖中，因此，删除u可以简化图G• Degree-1如果一个顶点u是叶子（度数为1)，那么存在一个最小顶点覆盖C，不包含u，且包含u的唯一邻居v 因此，v可以固定为最优解的一部分删除u和v可以简化图Guve要覆盖边e，u和v至少有一个包含于最优解C中u ∈ C,v < C ⇒ u < C,v ∈ Cu < C,v ∈ Cu ∈ C,v ∈ C ⇒ u < C,v ∈ C4 顶顶顶点点点覆覆覆盖盖盖归归归约约约规规规则则则• Degree-2如果一个顶点u的度数为2，其邻居为v和z，且v和z相邻，则存在一个最小顶点覆盖C，不包含u，且同时包含v和z 因此，v和z可以固定为最优解的一部分。
删除u、v和z可以简化图Gvzeu要覆盖三角形uvz，需要两个点最优解C中，uvz包含两个点（如果3个点都包含，可以把u去掉，得到一个更小的解）C中，如果选择的两个点有一个是u，假设另一个是v，那么可以交换u和z，仍然是最优解5 顶顶顶点点点覆覆覆盖盖盖归归归约约约规规规则则则• Domination给定两个顶点u和v，如果N[u] ⊆ N[v]，则存在一个最小顶点覆盖C，包含顶点v 因此，v可以固定为最优解的一部分删除v可以简化图Gvu若v < C，则N(v)（包括u）必然包含于C由于N[u]⊆ N[v]，则N(u)\v包含于C因此，C\{u} ∪ {v}仍然是合法的覆盖6 顶顶顶点点点覆覆覆盖盖盖归归归约约约规规规则则则• High degree若最小顶点覆盖C的顶点数|C| ≤ k，则任何度数大于k的顶点必定在C中因此，可以固定这些顶点为 最优解的一部分，删除这些顶点可以简化图GuVC of size |C| ≤ 3若存在度数大于k的顶点u，且u < C，则∀v ∈ N(u)，必有v ∈ C由于|N(v)| > k，则有|C| > k，与前提|C| ≤ k矛盾7 顶顶顶点点点覆覆覆盖盖盖归归归约约约规规规则则则定定定义义义：：： 一个crown是图G的一对有序顶点集(I,H)，满足：（1）I , ∅是G的一个独立集，即I中的顶点互不邻接。
2）H = N(I)3）在连接I和H的边中，存在一个匹配M，使得∀v ∈ H被匹配8 顶顶顶点点点覆覆覆盖盖盖归归归约约约规规规则则则• Crown给定一个crown (I,H)，则存在一个最小顶点覆盖，包含H中的所有顶点，且不包含I中的任何顶点因此，可以固定H为最优解的一部分，删除I,H可以简化图G为了覆盖M，任何一个顶点覆盖都必包含M中每条边的至少一个顶点，因此至少需要H个顶点选择H中所有的顶点，并且不选择I中的任何一个顶点，可以达到这个最小值同时由于I和H中，只有H的顶点有外部连接，这样的选择能够覆盖最多I和H外部的边9 图图图着着着色色色 问问问题题题定定定义义义1：：： 给定一个无向图G = (V,E)，着色α是对顶点V的颜色赋值，使得任意相邻的两个顶点的颜色不同 对图G着色所需的最少颜色数，称为色数χ命命命题题题：：： 给定图G = (V,E)，及其着色α，相同颜色的顶点组成一个独立集10 归归归约约约命命命题题题：：： 给定一个图G，及任意一个团C，如果C的大小为‘，则χ(G) ≥ ‘ps:什什什么么么是是是团团团11 归归归约约约定定定义义义2：：： 给定一个无向图G = (V,E)，独立集S是顶点V的一个子集，其中的元素互不邻接。
如果∀v ∈ S，其度数d(v) < ‘，则S称为‘-bound独立集规规规则则则：：： 给定图G的色数下界‘，从图G移除一个‘-bound独立集S总可以从简化后的图的最优解，有线性算法构造原图的最优解12 归归归约约约命命命题题题：：： 给定图G，其色数χ(G)的下界‘，以及图G的一个‘-bound独立集S， 令G0= G[V \ I]，则1) if χ(G0) < ‘, then χ(G) = ‘.2) if χ(G0) ≥ ‘, then χ(G) = χ(G0).证证证明明明：：： 假设我们有了G0的最优着色，即所使用的颜色数为χ(G0)1) χ(G0)< ‘的情况因为S是独立集，所以将S中的所有顶点都着色为χ(G0) +1，得到G的着色 因此，有χ(G)≤ χ(G0) +1 < ‘+1由于χ(G)≥ ‘，则χ(G) =‘2) χ(G0)≥ ‘的情况，由于∀v ∈ S,d(v)< ‘，因此N(v)所使用的颜色数|CN(v)| < ‘ ≤ χ(G0),则v可以被赋值为颜色c < CN(v)，且c ≤ χ(G0)同理，所有S中的顶点可以被安全的着色为小于等于χ(G0)的颜色 这样，我们从图G0的最优着色得到了图G的一种着色，故χ(G)≤ χ(G0)，又因为G0是G的子图，因此有χ(G) =χ(G0)。
13 课课课后后后习习习题题题独立集是必须的吗？规规规则则则：：： 给定图G的色数下界‘，从图G移除所有度数小于‘的顶点？14 团团团 团团团定定定义义义：：： 给定一个无向图G = (V,E)，团是指图G顶点集的一个子集C ⊆ V，其中的任意两个顶点都邻接 其中，顶点个数最多的团称为最大团团顶点覆盖（补图）15 最最最大大大加加加权权权团团团定定定义义义1：：： 给定一个加权无向图G = (V,E,ω)，ω是顶点V的权值函数，使得每个顶点v的权值为一个正整数ω(v) 一个团C的权值定义为ω(C) =Pv∈Cω(v)顶点权值之和最大的团，成为最大加权团定定定义义义2：：： 给定一个加权无向图G = (V,E,ω)，对于一个顶点v ∈ V，包含v的团的权值上界，记为UB(v)，即UB(v) ≥ max{ω(C) | C is a clique of G,v ∈ C}16 最最最大大大加加加权权权团团团归归归约约约规规规则则则规规规则则则：：： 给定一个加权无向图G = (V,E,ω)，以及G的一个团C，对于∀v ∈ V， 如果UB(v) ≤ ω(C)，则将v从G中移除17 最最最大大大加加加权权权团团团归归归约约约规规规则则则• 顶点v及其邻居的权值之和，可以作为所有包含v的团的权值上界。
UB0(v) = ω(N[v])• 令n∗是v的邻居中权值最大的点，则可以分为两种情况• 包含n∗：UB1a(v) = ω(N[v]) − ω(n∗)• 不包含n∗: UB1b(v) = ω(N[v]) + ω(n∗) + ω(N(v) ∩ N(n∗))UB1(v) = max{UB1a(v),UB1b(v)}18 最最最大大大加加加权权权团团团归归归约约约规规规则则则命命命题题题：：： 给定一个图G = (V,E)，以及G的一个着色方案α，则α所使用的颜色数是团的一个上界命命命题题题：：： 给定一个图G = (V,E,ω)，以及G的一个着色方案α，则各颜色中取权值最大的顶点，它们的权值之和是团的权值上界19 最最最大大大加加加权权权团团团归归归约约约规规规则则则• 对子图G(N(v))进行着色，对每种颜色，令n∗为其中权值最大的顶点，则UB2(v) = ω(v) +Xn∗ω(n∗)20 归归归约约约以上规则可以迭代进行。