《运筹学》第八章图与网络分析习题运筹学》
1思考题1解释下列名词并说明相互之间的区别与联系①顶点相邻关联边②环多重边简单图③链初等链④圈初等圈简单拳⑤回路初等路⑥节点的次悬挂点孤立点⑦连通图连同分图支撑子图⑧有向图基础图赋权图⑨子图部分图真子图2通常用记号GVE表示一个图解释V及E的涵义及这个表达式的涵义3通常用记号DVA表示一个有向图解释V及A的涵义及这个表达式的涵义4图论中的图与一般几何图形的主要区别是什么5试述树与图的区别与联系6试述求最短路问题的Dijkstra算法的基本思想及其计算步骤7试述寻求最大流的标号法的步骤与方法8简述最小费用最大流的概念及其求解的基本思想和方法9通常用记号NVAC表示一个网络试解释这个表达式的涵义10在最大流问题中为什么当存在增广链时可行流不是最大流11试叙述最小支撑树最大流最短路等问题能解决那些实际问题2判断下列说法是否正确1图论中的图是为了研究问题中有哪些对象及对象之间的关系它与图的几何形状无关2一个图G是树的充分必要条件是边数最少的无孤立点的图3如果一个图G从V1到各点的最短路是唯一的则连接V1到各点的最短路再去掉重复边得到的图即为最小支撑树4图G的最小支撑树中从V1到V
的通路一定是图G从V1到V
的最短路5fij0总是最大流问题的一个可行流6无孤立点的图一定是连通图7图中任意两点之间都有一条简单链则该图是一棵树8求网络最大流的问题总可以归结为求解一个线性规划问题9在图中求一点V1到另一点V
的最短路问题总可以归结为一个整数规划问题10图G中的一个点V1总可以看成是G的一个子图3证明在人数超过2的人群中总有两个人在这群人中恰有相同的朋友数
v4已知九个人1
v2v9v1和两个人握过手v2v3各和四个人握过手v4v5v6v7各和五个人握过手v8v9各和六个人握过手证明这九个人中一定可
V2C1C4V1C3V4C6V5C2V3C8C5C7C9C11C10V7C13C12C14V9V6V8
以找出三个人互相握过手
5用破圈法和避圈法求下图的部分树
fV1V6
V4V5
V2
V313V1V2V3
V52
V4
86373471753242521423
42546221943
6写出下面各图中的顶点数边数及顶点的次数哪些是简单图7完全图K
有多少条边8求下列各图的最小树
3
v9用标号法求下图中从1到各顶点的最短距离
5312463875321
fV22V1365V37V4
52137
V5
21
V86V93V10748V11
3V64V7
431
10在下图中r