2017-2018-1B卷¶

2016级

科目: 算法导论

主讲教师: 胡卉芪 出卷人: 沙朝锋

一、最短路径问题 (20分)¶

给定下图，从结点A开始运行Dijkstra算法，依次画出算法运行过程的中间步骤，并画出最终的最短路径树。

写出在下图上进行深度优先搜索的结果，要求使用字典序（即从顶点A开始）、对每个顶点需写出发现时间和完成时间。

二、网络流和最小割 (20分)¶

给定以下流网络，其中每条边上的数字为这条边的容量(capacity)。

找到一个S到T的最大流，并写出最大流量值。
将该流分解为多条S-T路径和环。
画出达到最大流时的剩余网络(residual network) \(G_{f}\)，并标注上每条边的容量。
找到一个S-T最小割。最小割的值为多少？

三、线性规划 (20分)¶

某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？

产品 \ 设备	A	B	C	D	利润(元)
甲	2	1	3	1	2
乙	2	2	1	3	3
可用台时	12	8	16	12

用整数线性规划对此问题进行建模。（要求先定义决策变量，再写出目标函数和约束）
给出将上述整数规划问题松弛为线性规划问题后的对偶形式。

四、NP完全问题 (20分)¶

给定图 \(G=(V,E)\) 和 \(V\) 的子集 \(S\)，如果 \(S\) 中任意两个顶点之间不存在边，则称 \(S\) 为 \(G\) 的一个独立集(Independent Set)。

独立集问题：给定图 \(G\) 和正整数 \(K\)，\(G\) 是否存在顶点个数不超过 \(K\) 的独立集？

简单解释独立集问题是NP问题。
给出从3-SAT问题到独立集问题的多项式归约(reduction)，即证明独立集问题是NP难问题。

五、近似算法 (20分)¶

顶点覆盖问题：给定一个无向图 \(G=(V,E)\)，找到图 \(G\) 的最小覆盖。以下为求解顶点覆盖问题的一个多项式时间近似算法：

Approx-Vertex-Cover(G)
(1) C <- ∅, A <- ∅
(2) E' <- E[G]
(3) while E' != ∅
(4)     do 选取E'中任意一条边 (u,v)
(5)        C <- C ∪ {u, v}, A <- A ∪ {(u, v)}
(6)        将E'中与u或者v相连的边删除
(7) return C

证明 Approx-Vertex-Cover 算法总是返回图 \(G\) 的一个顶点覆盖。
对于下图，给出 Approx-Vertex-Cover 算法可能返回的一个解，以及最优解。

证明 Approx-Vertex-Cover 算法是2-近似度的近似算法。