管理运筹学 - 第九单元自测

课程名称：管理运筹学 发布教师：吴骁远 作业来源：第九单元 渝粤题库 图与网络分析 作业满分：100.0分 发布时间：2025-06-23 作业要求：本次作业不计分，可根据自身的时间和学习情况，选择性完成。

单选题

1. 一个无向图G由哪些基本元素组成？ （分值：2.0分）

A. 点和线

B. 只有边

C. 顶点和边

D. 只有顶点

2. 在有向图中，弧的出次和入次之和等于什么？ （分值：2.0分）

A. 边数

B. 点数

C. 2倍边数

D. 顶点数

3. 简单图的定义是什么？ （分值：2.0分）

A. 既有环又有多重边（弧）的图

B. 有环但无双重点（弧）的图

C. 无环且无双重点（弧）的图

D. 无双重点（弧）但可能有环 国家开放大学 的图

4. 完全图的定义是什么？ （分值：2.0分）

A. 各对顶点之间都有一条边相连接的图

B. 各对顶点之间都有多条边相连接的图

C. 广东开放大学 只有顶点没有边的图

D. 只有边没有顶点的图

5. 树的定义是什么？ （分值：2.0分）

A. 不连通且含圈的无向图

B. 不连通且不含圈的无向图

C. 连通且含圈的无向图

D. 连通且不含圈的无向图

6. 最小生成树的定义是什么？ （分值：2.0分）

A. 包含所有顶点的生成树

B. 权最大的 成人学历 生成树

C. 只包含树枝的树

D. 权最小的生成树

7. 最大流问题主要应用于 渝粤文库 哪些领域？ （分值：2.0分）

A. 交通运输系统

B. 城市给排水系统

C. 金融系统

D. 所有上述领域

8. 最大流-最小割定理的内容是什么？ （分值：2.0分）

A. 最大流总是大于最小割集的容量

B. 最小割集的容量总是大于最大流

C. 最小割集的容量等于最大流

D. 最大流等于最小割集的容量

9. 可增广链的定义是什么？ （分值：2.0分）

A. 一条关于某个可行流的链，其上的每条前向弧都是饱和弧，每条后向弧都是零流弧

B. 一条连接源点和汇点的链

C. 一条不包含任何弧的链

D. 一条关于某个可行流的链，其上的每条前向弧都是非饱和弧，每条后向弧都是非零流弧

10. 哥尼斯堡七桥问题是图论中的哪个问题？ （分值：2.0分）

A. 二分图问题

B. 一笔画问题

C. 网络流问题

D. 最短路径问题

判断题

1. 二分图是图的一个子集，其中每条边的两个顶点分别属于两个不同的集合。 （分值：2.0分）

2. 树是一种特殊的图，它包含圈。 （分值：2.0分）

3. 在树中，任意两点之间恰有唯一链相连。 （分值：2.0分）

4. 最小生成树是权最小的生成树。 （分值：2.0分）

5. Dijkstra算法可以用于有负权边的网络中求最短路径。 （分值：2.0分）

6. Floyd算法可以求出从单一起点到所有点的最短路径。 （分值：2.0分）

7. 最大流-最小割定理表明，最大流的流量等于最小割集的容量。 （分值：2.0分）

8. 标号法只能用于求最大流问题。 （分值：2.0分）

9. 中国邮递员问题要求邮递员经过每条边恰好一次。 （分值：2.0分）

10. 欧拉图是存在欧拉回路的图。 （分值：2.0分）

简答题/计算题

1. 描述什么是树，并说明其性质。 （分值：6.0分）

2. 解释什么是最小生成树，并说明其重要性。 （分值：6.0分）

3. 描述什么是Dijkstra算法，并说明其适用条件。 （分值：6.0分）

4. 解释什么是Floyd算法，并说明其功能。 （分值：6.0分）

5. 描述什么是最大流-最小割定理，并说明其意义。 （分值：6.0分）

6. 已知有16个城市及它们之间的道路联系(见图1)。某旅行者从城市 A出发，沿途依次经J,N,H,K,G,B,M,I,E,P,F,C,L,D,0,C,G,N,H,K,O,D,L,P,E,I,F,B,J,A,最后到达城市M 。由于疏忽，该旅行者忘了在图上标明各城市的位置。请应用图的理论，在图8-1中标明A～P各城市位置。 图1 （分值：15.0分）

7. 有4个立方体，在各自的6个面上分别涂上红、白、 蓝、绿4种颜色，如把4个立方体一个压一个堆起来，如何做到使堆成的4侧每一侧面恰好包含红、白、蓝、绿4种 渝粤教育 颜色? 已知4个立方体各个面颜色如表4所示。 表4 立方体 北 南 东 西 上 下 1 红 红 红 白 白 白 2 蓝 白 蓝 绿 绿 绿 3 红 白 白 绿 红 蓝 4 蓝 白 蓝 绿 蓝 绿 （分值：15.0分）