64最大流问题 6.5最小费用流问题 知识要求 ①知道网络图在管理中的应用 ②掌握图与树的基本概念。 ③掌握避圈法和破圈法的基本原理 ④熟练掌握求解最短路问题的 Dijkstra算法(标号法)的基本步骤与适用条件, ⑤了解求解最短路问题的逐次逼近法和 Floyd法的适用条件 ⑥掌握可行流、增广链、最大流、最大流一最小割等网络流基本概念。 ⑦理解最小割的经济意义, ⑧了解最小费用最大流问题的求解原理 能力要求: ①会用避圈法和破圈法求一个图的最小支撑树。 ②会用 Dijkstra算法求解最短路问题 ③能够判定一个网络链是否为增广链。 ④在适当条件下,能够建立实际问题对应的最短路/最大流模型, ⑤会用标号法求解最大流问题,并能够给出最小割、最小割量 教学重点 图与树的基本概念、最小树算法、最短路问题、网络流的相关概念(包括可行流、最大 流、增广链)最大流问题、最大流一最小割 教学难点 最短路算法、最大流算法、最小费用最大流的求解原理、实际问题建模。 七、评价方式与成绩 总评构成(1+X) 评价方式 占比评测的毕业要求/指标点编号 期末闭卷考试 50% LO352/LO1 12 平时表现 10 LO2 12/LO1 12 Ⅹ2 阶段测验 20% LO352/LO1 12 X3 课程报告 20% LO362/LO212 撰写人:队喘 系主任审核 时间:2021年9月2号 时间:2021年9月2日6.4 最大流问题 6.5 最小费用流问题 知识要求： ① 知道网络图在管理中的应用。 ② 掌握图与树的基本概念。 ③ 掌握避圈法和破圈法的基本原理。 ④ 熟练掌握求解最短路问题的Dijkstra算法（标号法）的基本步骤与适用条件。 ⑤ 了解求解最短路问题的逐次逼近法和Floyd法的适用条件。 ⑥ 掌握可行流、增广链、最大流、最大流—最小割等网络流基本概念。 ⑦ 理解最小割的经济意义。 ⑧ 了解最小费用最大流问题的求解原理。 能力要求： ① 会用避圈法和破圈法求一个图的最小支撑树。 ② 会用Dijkstra算法求解最短路问题。 ③ 能够判定一个网络链是否为增广链。 ④ 在适当条件下，能够建立实际问题对应的最短路/最大流模型。 ⑤ 会用标号法求解最大流问题，并能够给出最小割、最小割量。 教学重点： 图与树的基本概念、最小树算法、最短路问题、网络流的相关概念（包括可行流、最大 流、增广链）最大流问题、最大流—最小割。 教学难点： 最短路算法、最大流算法、最小费用最大流的求解原理、实际问题建模。 七、评价方式与成绩 撰写人： 系主任审核： 时间：2021 年 9 月 2 号 时间：2021 年 9 月 2 日 总评构成（1+X） 评价方式 占比 评测的毕业要求/指标点编号 1 期末闭卷考试 50% LO352/LO112 X1 平时表现 10% LO212/LO112 X2 阶段测验 20% LO352/LO112 X3 课程报告 20% LO362/ LO212