《运筹学》第八章图与网络分析习题试卷及答案

《运筹学》第八章图与网络分析习题试卷及答案考试时间：90分钟总分：100分姓名：__________学号：__________得分：__________一、单项选择题（每题3分，共15分）1.以下关于图的基本概念，说法错误的是（）A.图由顶点和边组成，边可以是有向的，也可以是无向的B.度数为1的顶点称为悬挂点，与悬挂点相连的边称为悬挂边C.简单图是指没有环和多重边的图D.连通图是指任意两个顶点之间都存在唯一一条路径的图2.求解无向连通图最小生成树的方法不包括（）A.克鲁斯卡尔（Kruskal）算法B.普里姆（Prim）算法C.迪杰斯特拉（Dijkstra）算法D.破圈法3.迪杰斯特拉（Dijkstra）算法的核心作用是（）A.求解无向图的最小生成树B.求解有向图或无向图中某顶点到其他所有顶点的最短路径C.求解网络最大流问题D.判断图的连通性4.关于网络最大流问题，以下说法正确的是（）A.最大流的流量等于最小割集的容量B.增广链是指从汇点到源点，且每条边的流量都小于容量的链C.福特-富尔克森（Ford-Fulkerson）算法只能用于求解整数容量的最大流问题D.最小割集是指切断后使源点和汇点不再连通的边集合中，容量之和最大的集合5.以下属于有向图特有的概念是（）A.顶点度数B.路径C.回路D.入度与出度二、填空题（每题3分，共15分）1.设无向图G有n个顶点、m条边，若G是连通图，则其边数m至少为__________。2.最小生成树的核心性质是：包含图中所有顶点，且__________最小。3.迪杰斯特拉算法要求图中所有边的权值必须为__________，否则算法无法正常运行。4.网络流问题中，源点的净流出量等于汇点的净流入量，且等于__________。5.若一个有向图中存在从某顶点出发，经过若干条边后能回到该顶点的路径，则称该图存在__________。三、简答题（每题10分，共20分）1.简述克鲁斯卡尔（Kruskal）算法求解无向连通图最小生成树的基本步骤。2.简述最大流问题中“增广链”和“最小割集”的定义，并说明二者之间的关系。四、计算题（每题25分，共50分）1.已知无向连通图G的顶点集合V={v₁,v₂,v₃,v₄,v₅}，边集合及各边权值如下：e₁(v₁,v₂)=3，e₂(v₁,v₃)=5，e₃(v₂,v₃)=2，e₄(v₂,v₄)=4，e₅(v₃,v₄)=1，e₆(v₃,v₅)=6，e₇(v₄,v₅)=3。要求：分别用普里姆（Prim）算法（以v₁为起点）和克鲁斯卡尔（Kruskal）算法求解该图的最小生成树，并计算最小生成树的总权值。2.已知有向网络如图所示（顶点为v₁（源点）、v₂、v₃、v₄（汇点）），各边的容量（括号内为容量）如下：v₁→v₂（5），v₁→v₃（4），v₂→v₃（2），v₂→v₄（3），v₃→v₂（1），v₃→v₄（5）。要求：用福特-富尔克森（Ford-Fulkerson）算法求解该网络的最大流，并写出每次增广链的选择及流量调整过程，最终给出最大流的流量及各边的最终流量。参考答案及解析一、单项选择题（每题3分，共15分）1.D解析：连通图是指任意两个顶点之间都存在至少一条路径的图，而非唯一一条；存在唯一一条路径的是树（无环连通图）。2.C解析：迪杰斯特拉算法用于求解最短路径问题；克鲁斯卡尔、普里姆算法、破圈法均用于求解最小生成树。3.B解析：A选项是最小生成树算法的作用，C选项是福特-富尔克森等算法的作用，D选项是图的连通性判断方法（如深度优先搜索）的作用。4.A解析：B选项错误，增广链是从源点到汇点，且正向边流量<容量、反向边流量>0的链；C选项错误，福特-富尔克森算法可用于非整数容量的最大流问题；D选项错误，最小割集是容量之和最小的割集。5.D解析：入度（顶点接收的有向边数）与出度（顶点发出的有向边数）是有向图特有的概念；A、B、C均是无向图和有向图共有的概念。二、填空题（每题3分，共15分）1.n-1解析：无向连通图的最少边数为n-1（此时图为树，无环且连通）。2.边权之和解析：最小生成树的定义是包含所有顶点、边数为n-1（无环），且所有边的权值之和最小的子图。3.非负数解析：迪杰斯特拉算法的前提是边权非负，若存在负权边，需使用贝尔曼-福特（Bellman-Ford）算法。4.网络的最大流流量解析：网络流的守恒性，源点净流出量=汇点净流入量=最大流流量。5.回路（或环）解析：有向回路是有向图中特有的，无向图中的回路称为无向回路。三、简答题（每题10分，共20分）1.克鲁斯卡尔算法求解最小生成树的基本步骤（10分，每步2分）：（1）将图中所有边按权值从小到大进行排序，剔除环（若有）；（2）初始化最小生成树T为空集，顶点集合与原图一致；（3）按排序后的顺序，依次选取每条边，若该边的两个顶点分别属于T中的两个不同连通分量，则将该边加入T中；（4）重复步骤（3），直到T中包含n-1条边（n为顶点数），此时T即为最小生成树；（5）若选取完所有边后，T中边数不足n-1，则说明原图不连通，不存在最小生成树。2.增广链与最小割集的定义及关系（10分）：（1）增广链定义（4分）：在网络流中，从源点s到汇点t的一条链，若链上的正向边（与链的走向一致的边）满足流量<容量，反向边（与链的走向相反的边）满足流量>0，则称该链为增广链。增广链的作用是可通过调整链上各边的流量，增加网络的总流量。（2）最小割集定义（4分）：将网络的顶点集合分为两个互不相交的子集S和T（s∈S，t∈T），所有从S指向T的边构成的集合称为割集；割集中所有边的容量之和称为割集容量，容量最小的割集称为最小割集。（3）二者关系（2分）：根据最大流-最小割定理，网络的最大流流量等于最小割集的容量；当且仅当网络中不存在增广链时，当前流量即为最大流，此时对应的割集即为最小割集。四、计算题（每题25分，共50分）1.最小生成树求解（25分，Prim算法12分，Kruskal算法12分，总权值1分）（1）普里姆（Prim）算法（以v₁为起点）：①初始化：选取起点v₁，已选顶点集合S={v₁}，未选顶点集合V-S={v₂,v₃,v₄,v₅}，最小生成树边集T=∅；②选取S到V-S中权值最小的边：v₁→v₂（权3），加入T，S={v₁,v₂}，T={e₁}；③选取S到V-S中权值最小的边：v₂→v₃（权2），加入T，S={v₁,v₂,v₃}，T={e₁,e₃}；④选取S到V-S中权值最小的边：v₃→v₄（权1），加入T，S={v₁,v₂,v₃,v₄}，T={e₁,e₃,e₅}；⑤选取S到V-S中权值最小的边：v₄→v₅（权3），加入T，S=V，T={e₁,e₃,e₅,e₇}（4条边，n-1=5-1=4）；⑥最小生成树边集为e₁(v₁,v₂)、e₃(v₂,v₃)、e₅(v₃,v₄)、e₇(v₄,v₅)。（2）克鲁斯卡尔（Kruskal）算法：①边按权值从小到大排序：e₅(1)、e₃(2)、e₁(3)、e₇(3)、e₄(4)、e₂(5)、e₆(6)；②初始化T=∅，连通分量均为单个顶点；③选e₅(v₃,v₄)（权1），连通分量合并为{v₃,v₄}，T={e₅}；④选e₃(v₂,v₃)（权2），连通分量合并为{v₂,v₃,v₄}，T={e₅,e₃}；⑤选e₁(v₁,v₂)（权3），连通分量合并为{v₁,v₂,v₃,v₄}，T={e₅,e₃,e₁}；⑥选e₇(v₄,v₅)（权3），连通分量合并为V，T={e₅,e₃,e₁,e₇}（4条边）；⑦最小生成树边集与Prim算法一致。（3）最小生成树总权值：1+2+3+3=9。2.最大流求解（福特-富尔克森算法，25分，增广过程每步6分，最终结果1分）已知：源点v₁，汇点v₄，边容量：v₁→v₂(5)、v₁→v₃(4)、v₂→v₃(2)、v₂→v₄(3)、v₃→v₂(1)、v₃→v₄(5)；初始流量均为0。第一步：寻找增广链，调整流量增广链：v₁→v₂→v₄（正向边，均满足流量<容量）；增广量θ=min(5-0,3-0)=3；调整流量：v₁→v₂流量=3，v₂→v₄流量=3；当前总流量=3；各边剩余容量：v₁→v₂(2)、v₂→v₄(0)，其余边不变。第二步：寻找增广链，调整流量增广链：v₁→v₂→v₃→v₄（正向边，v₁→v₂剩余2，v₂→v₃剩余2，v₃→v₄剩余5）；增广量θ=min(2,2,5)=2；调整流量：v₁→v₂流量=3+2=5，v₂→v₃流量=2，v₃→v₄流量=2；当前总流量=3+2=5；各边剩余容量：v₁→v₂(0)、v₂→v₃(0)、v₃→v₄(3)，其余边不变。第三步：寻找增广链，调整流量增广链：v₁→v₃→v₄（正向边，v₁→v₃剩余4，v₃→v₄剩余3）；增广量θ=min(4,3)=3；调整流量：v₁→v₃流量=3，v₃→v₄流量=2+3=5；当前总流量=5+3=8；各边剩余容量：v₁→v₃(1)、v₃→v₄(0)，其余边不变。第四步：寻找增广链，调整流量增广链：v₁→v₃→v₂→v₄（v₁→v₃正向边剩余1，v₃→v₂反向边流量=2>0，v₂→v₄正向边流量=3>0）；增广量θ=min(1,2,3)=1；调整流量：v₁→v₃流量=3+1=4，v₃→v₂流量=2-1=1，v₂→v