2017-2018-1A卷¶

2016级

科目: 算法导论

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

一、深度优先搜索、强连通分支和顶点覆盖 (20分)¶

以字典序，对下图做深度优先搜索，请给出每个结点的发现时间和完成时间（直接标注在结点上）。

该图中有几个强连通分支？
请画出将每个强连通分支收缩后的图 \(G^{SSC}\)。
证明：若对连通的无向图进行深度优先搜索，得到的DFS树的内部结点构成该图的一个顶点覆盖。（此题与上图无关。）

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

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

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

三、线性规划 (20分)¶

反馈顶点覆盖问题：给定一个无向图 \(G=(V,E)\) 以及每个顶点上的非负权重 \(w_{i} \ge 0\)，返回一个最小权重顶点子集 \(S \subseteq V\)，使得图中任一个环(cycle) C都至少包含一个S中的顶点。

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

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

给定图 \(G=(V,E)\)，若顶点子集 \(S \subseteq V\) 满足以下条件则称为支配集：对任意顶点 \(u \in V\) 满足：\(u \in S\) 或者存在 \((u,v) \in E\) 的顶点 \(v \in S\)。

支配集问题：给定图G和整数K，判定图G中是否存在不超过K个顶点的支配集。

简单解释支配集问题是NP问题。
证明支配集问题是NP难问题，要求给出并证明从顶点覆盖(vertex cover)问题到支配集问题的多项式归约(reduction)。

五、近似算法 (20分)¶

已知独立集(Independent Set)问题是NP-hard问题，以下是一个求独立集的近似算法：

Greedy(G): // G=(V,E)
    S = ∅
    while G is not empty do
        Let v be a node of minimum degree in G
        S <- S ∪ {v}
        Remove v and its neighbors from G
    end while
    Output S

记 \(\Delta = \max_{v \in V} deg(v)\)。证明：\(|V \setminus S| \le \Delta|S|\)。
由(1)证明：\(|S| \ge |V|/(\Delta+1)\)
记 \(S^*\) 为某个最大独立集，证明：\(|S| \ge |S^*|/\Delta\)，即以上算法的近似度为 \(1/\Delta\)。