15.082其中考试 (闭卷，除了一张两面纸) 1.回答所有的在考试薄中损供的间愿，除了序号3，其部分答案在考试薄上 2预算您的时间。如果句题花贵时间太长，您可以继续下一个问题。您可以考忠不按丽顺 序做问题。把耗时的问题放到考试的最后， 3.分数总计105
15.082 其中考试 (闭卷, 除了一张两面纸) 1. 回答所有的在考试薄中提供的问题，除了序号 3，其部分答案在考试薄上。 2. 预算您的时间。如果问题花费时间太长，您可以继续下一个问题。您可以考虑不按照顺 序做问题，把耗时的问题放到考试的最后。 3. 分数总计105
1.(1 points)这是R-堆的某次迭代的桶.算法又被称为发现最小(find-min) 运算的部分。当发现最小计算结束的时候，也就是当结点2从桶中 别除且成为水久性后，桶的状态是什么？（桶的范围是什么？在这些 桶中的结点是什么？)您能写出范围，把元素放到以下的桶中。 node 1 2 4 5 6 d(node) 0 71 93 78 120 2.34-78.15 16-31 32-63 64-127 0000000 00000000 为回答句题1的桶。 2(10分)给出在图2的流分解。在弧上的数字表示流，题常，任何在流分解中的路径应 该从供应结点折向需求结点
1. (10 points) 这是R-堆的某次迭代的桶。算法又被称为发现最小(find-min) 运算的部分。当发现最小计算结束的时候，也就是当结点 2 从桶中 删除且成为永久性后，桶的状态是什么？ (桶的范围是什么？在这些 桶中的结点是什么？) 您能写出范围，把元素放到以下的桶中。 为回答问题 1 的桶。 2. (10分) 给出在图 2 的流分解。在弧上的数字表示流。照常，任何在流分解中的路径应 该从供应结点指向需求结点
5 2 3 2 图2问题2的网络 3.(10分)。考感在图3中的最大流列题. 2 图3问题3的屑络 使用Fcd-Fulkerson算法，使用广度优先艘索发现增广路径. a(10分)增广路径是什么？说明每次增广后的利余网络。您可以在下面的纸上面出剩余 网络。 b.(5分)最小切割是什么7
图 2 问题 2 的网络 3. (10 分)。考虑在图 3 中的最大流问题。 图 3 问题 3 的网络 使用Ford-Fulkerson 算法，使用广度优先搜索发现增广路径。 a. (10 分) 增广路径是什么? 说明每次增广后的剩余网络。您可以在下面的纸上画出剩余 网络。 b. (5 分) 最小切割是什么?
⑥ ⑦ ② ⑤ ⑥ ⑦ ② 3 4 6 ⑥ ⑦ ② 3 4 5
4.(15分，每部分3分).◆G=(N.A)是有n个结点和m条弧的网络。假设m>n。以 下问题表示的算法的运行时间是什么？根据和m表示运行时间。 温，进行深度优先搜索， b.确定路径的无向组件。 c.判定流分解。 .寻找在网络中从一结点到其他结点的最路径，其中弧的长度可能是非正，但是没 有负长圈， e,通过首先把它转换成最大流问题和使川Ford Fulkerson增广路径算法，寻找最大有 2结点n在每期网络上的最大基匹配。（也给出增广数目的上界。） 5.(15分)几个家庭一起出去吃饭。为了提高社会的交互作用，他们坐在桌边以便没有同 一家庭中的两个成员在同一桌边。说明如何靶寻找可行坐次安排（调足以上条作的一个）公 式化为最大流间题。假设晚宴中有P个家庭，假设第〡家庭有0成员。假设有t张桌 子，第j张桌子有座容量为b0): &.20分，每条5分)对以下问避回答真成假，简要证明您的回答，每个问题军在网络G= N,A)上定义。除了对b富分，您可以眼设网络是连通的。通常，C表不氧》的长度。 a.判定拓扑排序的运行时间是Onm). b.假设在无向网络G=N,A)上考感最大流问题。假设我们用每条氧有同样的容量 U的两条有向弧00和0).替换容量为U每条弧D·然后，此变换H题的流值和原间 恩的渣值一样。假设所有下界都是0。 C.假设在G■(N,A)中的所有路径最多有K条或。那么对FFO标号校正算法的运行 时同是Omk灯， .如果在网络中的弧代价都是互质。那么网络有唯一的最小代价树。（如果两整数的是 大公约数是1，那么这两个整数互质。例如10和21互质，但是6和9不是。) 7.(10分，每部分5分)多选。给出每个国题的最住答案。 a考虑判定从结点1到其他结点的最短路径问题。令①表示到结点」的最短路径。 假设从结点1到结点k的量短路径恰好有三条弧。◆c是按题如下方法从C获得的：G =G+10对每个0》EA且令d①表示使用代价c'的到结与的最短路径，以下哪个是 最佳答案： 1.dk)=d0+30 .d')≤d(k)+30 ii.d≥d"+30 V,设有足够的信息 b.假设D是有向图，令D表示在圈D上的数。令CD)表示圈D的代价，令图D的 平均代价定义为μ(D)■CD1D,假设现在对网络中的每条氧增加10个单位，令μ'D)是 改变后的圈D的平均值。以下哪个是最佳答案： 1.'(D)=(D)+10
4. (15分, 每部分 3 分)。 令G = (N, A) 是有 n 个结点和 m 条弧的网络。假设m > n。以 下问题表示的算法的运行时间是什么？根据 n 和 m 表示运行时间。 a. 进行深度优先搜索。 b. 确定路径的无向组件。 c. 判定流分解。 d. 寻找在网络中从一结点到其他结点的最短路径，其中弧的长度可能是非正，但是没 有负长圈。 e. 通过首先把它转换成最大流问题和使用Ford Fulkerson 增广路径算法，寻找最大有 2n 结点(n 在每侧)网络上的最大基匹配。 (也给出增广数目的上界。) 5. (15 分) 几个家庭一起出去吃饭。为了提高社会的交互作用，他们坐在桌边以便没有同 一家庭中的两个成员在同一桌边。说明如何把寻找可行坐次安排(满足以上条件的一个) 公 式化为最大流问题。假设晚宴中有 p 个家庭，假设第 i 家庭有q(i) 成员。 假设有t 张桌 子，第 j 张桌子有 座容量为 b(j)。 6. (20分, 每条 5 分) 对以下问题回答真或假，简要证明您的回答。每个问题都在网络 G = (N,A)上定义。除了对 b 部分，您可以假设网络是连通的。通常， cij 表示弧(i,j)的长度。 a. 判定拓扑排序的运行时间是O(nm)。 b. 假设在无向网络 G = (N, A) 上考虑最大流问题。假设我们用每条弧有同样的容量 u ij 的两条有向弧(i,j)和(j,i)， 替换容量为u ij 每条弧(i,j) 。然后，此变换问题的流值和原问 题的流值一样。假设所有下界都是 0 。 c. 假设在G = (N, A) 中的所有路径最多有K 条弧。那么对FIFO 标号校正算法的运行 时间是O(mK)。 d. 如果在网络中的弧代价都是互质，那么网络有唯一的最小代价树。(如果两整数的最 大公约数是 1，那么这两个整数互质。 例如10 和 21 互质，但是6 和 9 不是。) 7. (10 分, 每部分5 分) 多选。给出每个问题的最佳答案。 a. 考虑判定从结点 1 到其他结点的最短路径问题。令 d*(j) 表示到结点 j 的最短路径。 假设从结点 1 到结点 k 的最短路径恰好有三条弧。令c’是按照如下方法从 c 获得的： c’ij = cij + 10 对每个 (i,j) ∈ A, 且令d’(j) 表示使用代价c’ 的到结点j 的最短路径。以下哪个是 最佳答案： i. d’(k) = d*(k) + 30. ii. d’(k) ≤ d*(k) + 30 iii. d’(k) ≥ d*(k) + 30 iv. 没有足够的信息 b.假设 D 是有向圈，令|D| 表示在圈D上的弧数。令 c(D) 表示圈 D 的代价。令圈 D 的 平均代价定义为 μ(D) = c(D)/|D|。假设现在对网络中的每条弧增加 10 个单位，令μ’(D) 是 改变后的圈 D 的平均值。以下哪个是最佳答案。 i. μ’(D) = μ(D) + 10
L.μ'(D)gμ(D)+10 m.μD)2D)+10 N.以上都没有 8.(10分，每部分5分)考虑在网储G=(N.A)上的最短路径，在此网溶中负弧长度是允许 的，（是所有在弧上的负弧的长度是在指向结点4的弧上的长度。说明通过求解两个最知路 径问恩，每个最短路径有非负代价，如何发现从结点1到其能结点的最短路径。我们在 部分a和部分b做这件事情. 说明如何通过在有非负弧长的网格上求解一个最短路径问题米判定在原图中是否存在 负代价圈。 b.假设没有负代价圈。使用部分的结果，以及为了发现从结点1到其他结点的最短路 径的在有非负弧长的网络上额外的最师路径计算。提示：“即的代价
ii. μ’(D) ≤ μ(D) + 10 iii. μ’(D) ≥ μ(D) + 10 iv. 以上都没有 8. (10分, 每部分 5 分) 考虑在网络G = (N, A) 上的最短路径，在此网络中负弧长度是允许 的，但是所有在弧上的负弧的长度是在指向结点4的弧上的长度。说明通过求解两个最短路 径问题，每个最短路径有非负代价，如何发现从结点 1 到其他结点的最短路径 。我们在 部分 a 和部分 b 做这件事情。 a. 说明如何通过在有非负弧长的网络上求解一个最短路径问题来判定在原图中是否存在 负代价圈。 b. 假设没有负代价圈。使用部分 a的结果， 以及为了发现从结点 1 到其他结点的最短路 径的在有非负弧长的网络上额外的最短路径计算。提示：“即约代价