第十章(图与网络分析)要点.pdf
《第十章(图与网络分析)要点.pdf》由会员分享,可在线阅读,更多相关《第十章(图与网络分析)要点.pdf(54页珍藏版)》请在三一文库上搜索。
1、1 第十章图与网络分析 精典习题 10.1 证明如下序列不可能是某个简单图的次的序列: (1)7,6,5,4,3,2 (2)6,6,5,4,3,2,1 (3)6,5,5,4,3,2,1 10.2 已知9 个人 921 ,vvv中, 1 v和两个人握过手, 32,v v各和四个人握过手, 7654 ,vvvv各和五个人握过手, 98,v v各和六个人握过手,证明这九个人中一定可以找出 三个人互相握过手。 10.3 有八种化学药品A、B、C、D、P、R、S、T 要放进储藏室保管。出于安全原因,下 列各组药品不能储存在同一室内:A-R、A-C、A-T、R-P、P-S、S-T、T-B、 T-D、B-D
2、、D-C、 R-S、R-B、P-D、S-C、S-D 问储存这八种药品至少需要多少间储藏室。 10.4 已知有十六个城市及他们之间的道 路联系(见图10-1) 。某旅行者从城市A 出发, 沿途依次经过J、N、H、 K、G 、B、M 、I 、E、P、 F、C、L、D、O 、C、G、N、H、K、O 、D、L、P、E、 I 、F、B、J、A,最后到达城市M 。由于疏忽,该 旅行者忘了在图上标明各城市的位置,请应用图 的基本概念及理论, 在图 101 中标明各城市AP 的位置。 10.5 十名研究生参加六门课程的考试。由于选修的课程不同,考试门数也不一样。表 10 1 给出了每个研究生应参加考试的课程(
3、打 号的) 。规定考试应在三天内结束,每天 上下午各安排一门。研究生们提出希望每人每天最多考一门,又课程 A必须安排在每一天上 午考, 课程 F 安排在最后一门,课程 B只能安排在中午考,试列出一张满足各方面要求的考 试日程表。 图 10-1 2 e1 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 e2 e3 e7 e4 e5 e6 e8 e9 e10 e11 e12 e13e14 e15 图 10-2 表 10-1 考试课程 研究生 A B C D E F 1 2 3 4 5 6 7 8 9 10 10.6 用破圈法和避圈法找出图10-2 的一个支撑树。 10.7 用破圈法和
4、避圈法求图103 中各图的最小树。 (a) 7 2 8 2 3 2 4 4 3 6 1 3 6 5 4 1 7 4 3 1 2 2 2 3 4 2 5 (b) 3 10.8 已知世界6 大城市:(Pe) 、 (N) 、 (Pa) 、 (L) 、 (T) 、 (M ) 。试在由表101 所示交 通网络的数据中确定最小树。 表 10-2 城市Pe T Pa M N L Pe 13 51 77 68 50 T 13 60 70 67 59 Pa 51 60 57 36 2 M 77 70 57 20 55 N 68 67 36 20 34 L 50 59 2 55 34 10.9 有九个城市 921
5、 ,vvv, 其公路网如图104 所示。弧旁数字是该段公路的长度, 有一批货物从 1 v运到 9 v,问走那条路最短? 2 2 3 2 2 1 5 3 3 5 2 2 4 2 2 5 3 6 4 7 4 5 3 6 3 2 1 (c) (d) 图 10-3 3 4 3 3 2 3 1 2 2.5 5 4 2 V1 V2 V3 V4 V5 V6 V7V8 V9 3 图 10-4 4 10.10 用标号法求图105 中 V1到各点的最短路。 10.11 用 Dijksrea方法求图106 中 V1到各点的最短距离。 10.12 求图 10-7 中从 V1到各点的最短路。 10.13 在图 108
6、中 (1) 用 Dijkstra 方法求从V1到各点的最短路; (2) 指出对 V1 来说那些顶点是不可到达的。 V1 2 8 4 7 6 1 5 1 2 9 1 4 3 2 1 6 3 1 7 9 2 4 V2 V3 V4 V5 V6 V7 V8 V9 V10 V11 图 10-6 2 2 6 1 30 4 20 20 4 7 10 5 10 15 1 5 7 5 10 30 4 20 V1 (a) (b) 图 10-5 V1 9 8 5 2 1 8 3 7 4 3 10 7 1 2 4 4 5 3 3 1 2 2 2 V1 V2 V4 V3 2 3 V5 V6 图 10-7 5 10.14
7、 已知八口海上油井,相互间距离如表10-2 所示。已知1 号井离海岸最近,位5 浬。问从海岸经1 号井铺设油管将各油井连接起来,应如何铺设使输油管线长度为最短(为 便于计算和检修,油管只准在各井位处分叉)。 表 10-2 各油井间距离单位: km 从到 2 3 4 5 6 7 8 1 1.3 2.1 0.9 0.7 1.8 2.0 1.5 2 0.9 1.8 1.2 2.6 2.9 1.1 3 2.6 1.7 2.5 1.9 1.0 4 0.7 1.6 1.5 0.9 5 0.9 1.1 0.8 6 0.6 1.0 7 0.5 10.15 设某公司在六个城市c1, , c6 有分公司,从ci到
8、 cj的直达航线票价记在下 面矩阵的( i ,j )位置上(表明无直达航线,需经其他城市中转)。请帮助该公司设计一 张任意两城市的票价最便宜的路线表。 055252510 550102025 25100102040 2010015 252015050 102540500 10.16 在如图 10-9 所示的网格中,每弧旁的数字是(cij,fij) 。 (1) 确定所有的数集; V4 4 1 3 3 4 1 6 2 4 3 6 7 V1 V2 V7 V5 V6 V8 V3 图 10-8 6 (2) 求最小截集的容量; (3) 证明指出的流是最大流。 10.17 求如图 10-10 所示的网络的最
9、大流(每弧旁的数字是(cij,fij) 。 10.18 用 Ford-Fulkerson的标号算法求图10-11 中所示各容量网络中从Vs 到 Vt 的最 大流,并标出个网络的最小割集。图中各弧旁数字为容量,括弧中为流量。 s v t v (1,1 ) (4,3 )(7,6 )(4,3 )(3,2 ) (3,2 ) (3,2 ) (4,3 ) (4,2 ) (5,3 ) (8,3 ) (2,2 ) 图 10-10 5(5) 4(3) 3(2) 2(2) 1(1) 5(4) 5(5) 5(2) 1(1) 2(2) 3(3) 4(4) 5(3) s v t v 1(1 ) t v s v 2(1
10、) 2(2 ) 1(2 ) 2(1 ) 2(1 ) 2(2 ) 2(0 ) 1(0 ) 2(2 ) 2(0 ) 1(1 ) (a) (b) s v t v (2,2) (4,3) (3,3) (1,0) (2,2) (5,2) (3,1) 图 10-9 7 10.19 某单位招收懂俄、英、日、德、法文的翻译各一人。有 5 人应聘。 已知乙懂俄文, 甲、乙、丙、丁懂英文,甲、丙、丁懂日文,乙、戊懂德文,戊懂法文。问最多有几人能得 到招聘,有分别被聘任从事那一文种的翻译。 10.20 求图 10-12 中从 st 的最小费用最大流,各弧旁数字为(,) 。 10.21 图 10-13 中,A、B为出
11、发点, 分别有 50 和 40 单位物资往外发运,D、E为收点, 分别需要物资30 和 60 单位, C为中转点,各弧旁数字为(,) 。求满足上述收发量要 求最小费用流。 A B C D E (20,90) (80,10) (10,30) (30,20) (40,30) (50,40) (10,20) 图 10-13 (4,1 )(7,6 ) (5,2 ) (2,3 )( 3,2 ) (8,4 ) (6,1 ) s t (a)( b) (7,7 ) (5,3 ) (5,1 ) (7,2 ) (10,9 ) (5,3 ) (8,4 ) (10,10 ) (7,2 ) s t 图 10-12 3(
12、2) 5(5) 3(3) 3(3) 2(0) 6(4) 4(4) 2(2) 5(4) 2(0) 8(6) 6(6) t v s v (c) t v s v 12(10) 6(5) 3(3) 5(4) 4(3) 3(3) 5(4) 4(4) 2(2) 5(4) 2(2) 9(9) 9(6) (d) 图 10-11 8 10.22 设 G= (V,E)是一个简单图,令(G )=( 称(G)为 G的最小次 ) 。 证明: (1)若 ( G)2,则 G 必有图; (2)若 (G) 2 ,则 G必有包含至少 (G)+1条边的图。 10.23 设 G是一个连通图,不含奇点。证明:G中不含割边。 10.24
13、 给一个联通赋权图G,类似于求G的最小支撑树的Kruskal方法,给出一个求G 的最大支撑树的方法。 10.25 下述论断正确与否:可行流f 的流量为零,即v(f)= 0,当且仅当f 是零流。 9 习题答案及详解 10.1 证明 (1)由图的性质定理知,任一个图中,奇点的个数为偶数。7,6,5,4,3,2 中存在 3 个奇数,所以不可能是某个图的次的序列,更不是某个简单图的次的序列。 【或者】假设7,6,5,4,3,2 为某个简单图的次的序列,则图中有6 个点,作为简 单图点的最大次数为n-1 ,即最大次数为5,显然与存在点的次数为7 矛盾。 所以, 7,6,5, 4,3,2 又是简单图的次的
14、序列。 (2)由定理知,任一个图G=(V,E)中,所有点的次数之和是边数的两倍,即图中点次 的和为偶数。序列6, 6,5,4,3,2,1 的和为27,所以它不可能是一个图的次的序列, 更不可能是某个简单图的次的序列。 【或者】假设6,6,5,4,3,2,1 为某个简单图的次的序列,则图中存在7 个点,不 妨设为 1 V, 2 V, 3 V, 4 V, 5 V, 6 V, 7 V,其中 1 V, 2 V次为 6,表明 1 V, 2 V与除自身外的 剩余 6 个点均相连。即 3 V, 4 V, 5 V, 6 V, 7 V的次不少于2,与 7 V的次为 1 矛盾。所以, 6, 6,5,4,3,2,1
15、 不是某个简单图的次的序列。 (3)假设 6,5,4,3,2,1 为某个简单图的次的序列,则图中存在7 个点,不妨设为 1 V, 2 V, 3 V, 4 V, 5 V, 6 V, 7 V, ,因为 1 ()d V=6, 7 ()d V=1, 所以 1 V与其他6 个点相连, 而 7 V仅与 1 V相连,又因为 23 ()()5d Vd V,则 2 V, 3 V与除 7 V和自身之外的所有点相连, 则 6 V必须与 2 V, 3 V相连,所以 6 V与 1 V, 2 V, 3 V相连,与 6 ()2d V矛盾,所以6, 6,5, 4,3,2,1 不是某个简单图的次的序列。 10.2 解:设 9
16、个人 1 V, 2 V, 9 V为 9 个点,两人握手设为两点之间存在相连边,握手 问题转化为一个简单图,其中, 1 V, 2 V, 9 V次的序列为2,4,4,5,5,5, 5,6,6。 这 9 个人中一定可以找到3 个互相握过手,转化为在图中一定存在3 个点彼此相连。 因为, 4567 ()()()()5d Vd Vd Vd V, 4 V, 5 V, 6 V, 7 V之间一定存在两点相连。 假如, 4 V, 5 V, 6 V, 7 V互相均不相连,因为次均为5,所以 4 V, 5 V, 6 V, 7 V均与剩余的 4 个点 1 V, 2 V, 3 V, 8 V, 9 V相连,这与 1 ()
17、d V=2 矛盾。 10 不妨设 4 V, 5 V, 6 V, 7 V,中存在 4 V, 5 V之间相连。必可以找到第三点均与 4 V, 5 V相 连。假设不存在第3 点均与 4 V, 5 V相连, 4 V, 5 V分别与定义不同的4 个点相连,即存在8 个不同的点分别与 4 V或 5 V相连,加上 4 V, 5 V共计 10 个点,这与图中9 个点矛盾。 所以在图中,必存在3 个点彼此相连。 10.3 解 : 将 8 种化学药品A, B, C,D,P,R,S,T 设定为 8 个点, 两种药品不能贮存同一室内状态, 设定为两点之间存在一边相连,画 出药品关系图如下: (图 10-3(a) )
18、在图( a)中,两点之间相连的 药品均不能存贮在一起。对于由点 A,B,C,D,P,R,S, T 的完全 图,求图( a)的补图,得图(b), 在( b)图中,彼此相连的药品均可以 为存贮庄点,因为( )()2d Sd D, 从 S,D 开始搜索,(S,A,B)彼此 相连, (D,R)相连,(T,C,P)彼 此相连。 所以至少需要3 间贮存室,存效 组合为( S,A,B) , (T,C,P) , ( D, R) 。 10.4 解:依据旅行者的路线统计城市间的相互关系。 点(城市)相邻城市(相邻点)次点相邻点次 A J, M 2 I M, E,F 3 B G,M,F,J 4 J A,N,B 3
19、C F,I,O,G 4 K H,G,O 3 D L,O 2 L C,D,P 3 E L,P 2 M B, I,A 3 F P,C,I,B 4 N J,H,G 3 (a) B A T C R P S D (B) B A T C R P S D 图 10-3 11 G K,M,C,N 4 O D,C,K 3 H M,K 2 P E,F,L 3 由点的次可知,A,D, E,H 为 2,则 为 4 个顶点; B,C,F,G 的次为4,则为 4 个顶点;某系为边点,城市布局图为图 10-4。 10.5 解 :将课程 A,B,C,D,E,F 设定为 6 个点,同时学生选某课程认为存在相邻 边。依据学生1-
20、10 的选课划分课程关系图10-5(a) ,要求学生一天最多考1 门,即图( a) 中相连的课程不能排在同一天。对于点ABCDEF 的关系图,求图(a)的补图( b) 。 那么, 图(b)中相邻的课程可以安排在同一天,可保证学生一天最多考一门,所以(A, E) , (F,D) , (C,B)分别各为一天,安排如下: 天上午下午 1 2 3 A C D E B F A M I E J B F P N G C L C K O D 图 10-4 C A B D E F 图 10-5 (a) C D A E B F 图 10-5 (b) 12 v1 v2 v3 v4 v5 v6 v7 v8 v9 v1
21、0 e2 e3 e7 e5 e6 e8 e9 e10 e11 e12 e14 e15 (b) e1 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 e2 e3 e7 e4 e5 e6 e8 e9 e10 e11 e12 e13e14 e15 (a) v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 e2 e3 e7 e8 e10 e11 e12 e14 e15 (b) 10.6 解: (破圈法) 寻找图中的圈,去掉圈中的一边。 (1)圈( 1 123321 v ev e v e v)去掉 1 e;圈( 2 4 4 8 5 6 2 v ev ev ev)去掉 4 e;圈
22、( 8 1 3 9 1 4 1 0 1 5 8 v v v e v e v) 去掉 13 v。 (2)圈( 1 23325571 v e v e v e v e v)去掉 5 e;圈( 48510 694 v e v e v e v)去掉 9 e, 得到支撑树 (c)。 13 e1 v1 v2 v3 v5 e2 e7 (d) (e) e1 v1 v2 v3 v4 v5 v10 e12 e2 e7 e6 v6 v8 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 e2 e3 e7 e8 e10 e11 e12 e14 e15 (f) (避圈法 ) (1) 从 1 v点 出 发 ,
23、边 相 邻 边 增 加 边 和 点 , 保 证 不 构 成 回 路 。 1 v出 发 , 增 加 122375 ,;,;,e v e v e v。 (2) 3 v相邻边 6 e,增加 4 v, 5 v相邻边 10 e, 12 e,增加点 6 v, 8 v。 (3) 6 v相邻边 11 e,增加 7 v, 8 v相邻边 13 e, 15 e,增加点 9 v, 10 v。 将 1210 .v vv点均包含在图中,且不存在回路,构成一个支撑树(f) 。 10.7 解:a) (破圈法) 在图中寻找圈,去除圈中权值最大的边 (V1 ,V2 ,V3)去除( V1 ,V 3 )边; (V1 ,V4 ,V7)
24、去除( V4 ,V7 )边; (V2 ,V5 , V8)去除( V2 ,V8 )边;(V6 ,V8 ,V9)去除( V7 ,V8 )边,得到图( a2) (V2 ,V5 ,V3)去除( V2 ,V5 )边; (V3 ,V6 ,V4)去除( V3 ,V6)边; ( V5 ,V6 , V8)去除( V5 ,V6 )边,得到图( a3) (V1 ,V2,V3 ,V4)去除( V1 ,V2)边,( V3 ,V4,V6 ,V8,V5) 去除( V4 ,V6)边 , 得 到图( a4) 。 14 ( V1 ,V4,V3 ,V5,V8,V7)去掉( V3 ,V4)边,得到图( a5),图中不再有回路,则为
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第十 网络分析 要点
链接地址:https://www.31doc.com/p-5229366.html