CSCI3160 Special 12：顶点覆盖、随机子句与 TSP

原件：Sp12 题目（本地课件） p.1–2，两幅无向图均已视觉核对。每题先题解后解析，所有解法为自行推导。

Problem 1：顶点覆盖的三问（p.1）

题解

(a)最小覆盖大小3，例如{a,d,e}。(b)算法可能返回4点：先选边ab，再选df，得到{a,b,d,f}。(c)也可能返回6点：依次选ab、cd、ef。

具体解析

原图边为ab、ac、bd、cd、de、df、ef。集合{a,d,e}覆盖它们全部；另一方面ab、cd、ef是三条两两不共端点的匹配边，每条至少要一个不同覆盖点，所以任何覆盖至少3，最优值确为3。

课堂算法每次选剩余边的两个端点并删除其所有关联边。选ab后剩cd、de、df、ef；若再选df，所有剩余边都被覆盖，输出4点。若改选cd，剩ef，再选其两端，输出全部6点。答案不唯一是算法允许任意选边导致的，不是计算错误。

不能由“最优3”断言算法不可能输出4：算法输出数为2×某个极大匹配大小，并不保证匹配最大，也不保证覆盖最小。

Problem 2：任意非空独立变量子句至少一半概率为真（p.1）

题解

若子句含k≥1个不同变量上的literal，每个literal为假的概率1/2，且独立。OR只有全部假才为假，所以为真概率 $1-2^{-k}\ge1/2$ 。

具体解析

否定literal与正literal都一样公平：x均匀时¬x也均匀。不同变量保证这些真假事件独立，故可相乘。k=1取到下界1/2；k=3得到7/8。

题目“任意数量”需理解为至少一个。若允许空子句，空OR为假，概率0，命题不成立，应补非空条件。不能把“每个事件概率1/2”单独当作独立性的理由；同一变量重复出现会破坏乘积计算。

变量重复时，至少一半与精确概率要分开。 补充子句 $(x\lor x\lor x)$ 的真概率是 $1/2$ ，不是 $7/8$ ； $(x\lor\neg x\lor y)$ 恒真，真概率为 1。重复变量让三次独立抛硬币的乘法失效，却没有推翻“非空子句至少一半”的较弱结论：任选其中一个 literal，其为真时整句一定为真，已提供概率 $1/2$ 的事件。

自测：两个子句共享变量，还能把各自满足概率相加得到期望满足数吗？

可以。设每个子句的满足指示量为 $I_i$ ，则 $E[\sum I_i]=\sum E[I_i]$ 不要求子句间独立。独立性仅在计算某个子句内部“所有 literal 都假”的乘积时使用，不是期望线性的前提。

Problem 3：在五点图上执行二倍TSP算法（p.1）

题解

取MST边ac(2)、cd(3)、db(2)、be(2)，总权重9。沿路径形MST往返的游走为a,c,d,b,e,b,d,c,a；跳过重复顶点得环a,c,d,b,e,a，总代价13，是本图的最优环，也当然满足二倍保证。

具体解析

原图十条边：ab=5、ac=2、ad=3、ae=4、bc=4、bd=2、be=2、cd=3、ce=4、de=3。权重2的三条边全部可选，连接成{a,c}与{b,d,e}两个分量；再选任意可连通两分量的最轻权重3边，例如cd，得到MST9。

沿树每边往返一次代价18；shortcut后环权重2+3+2+2+4=13。原图满足三角不等式，所以shortcut不增加长度。MST≤OPT，故输出≤18≤2OPT，已足够证明要求；额外枚举固定a的24个排列核验最优值为13，不依赖这个枚举来证明一般二倍界。

有些最轻边和平局选择可以产生另一棵MST或另一个环，本题不规定唯一输出。必须给出具体树、游走和删重复后的环，不能只列总长度。

Problem 4：线性时间产生树的往返游走（p.1）

题解

任选根DFS：首次到节点时输出它；每次递归一个孩子返回后，再输出当前节点。这样每条树边下行一次、上行一次，总时间O(n)，输出序列2n−1个顶点。

具体解析

Walk(u,parent)：
    输出u
    对u的每个邻居v，若v≠parent：
        Walk(v,u)
        输出u

树无环，跳过父节点足以防止返回边触发重复递归。遍历用邻接表，不要每次扫描全部顶点来找孩子。根r有孩子a、b时，输出r,a,r,b,r；只输出首次到达会得到r,a,b，但a到b未必有树边，不能叫作原树游走。

Problem 5：欧氏TSP二倍近似（p.1–2）

题解

把每个输入点作顶点，任意两点间连欧氏距离权重，形成完整图。求MST、沿树往返，再按首次访问顺序shortcut成环。输出点顺序连接的线段，总长度≤2OPT。

具体解析

最优环删去任意一条边是生成路径，MST不比它更重，所以w(T)≤OPT。树往返长度2w(T)。欧氏距离满足三角不等式，一次用直接线段跳过中间点不会增加长度；逐次删重复，仍访问每个输入点恰好一次，再回起点，得到合法题目所定义的线段环。

自取单位正方形四角，MST可取三条边总长3；往返长6，shortcut可得外圈长4，最优也为4。二倍是最坏保证，不要求每例刚好比值2。

构造O(n²)边，MST和遍历都是多项式；题目明确允许距离多项式时间计算。n=1可返回零长度退化闭行程，若严格要求非退化环则另限定n≥3，不影响一般构造。

来源与证据

Sp12 p.1–2。两幅图的边集、覆盖下界和TSP数值已独立核验。