您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 质量控制/管理 > 第十章-(图和网络分析)
第十章-(图和网络分析)1/54第十章图与网络分析精典习题10.1证明如下序列不可能是某个简单图的次的序列:(1)7,6,5,4,3,2(2)6,6,5,4,3,2,1(3)6,5,5,4,3,2,110.2已知9个人921,,,vvv中,1v和两个人握过手,32,vv各和四个人握过手,7654,,,vvvv各和五个人握过手,98,vv各和六个人握过手,证明这九个人中一定可以找出三个人互相握过手。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、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。由于疏忽,该旅行者忘了在图上标明各城市的位置,请应用图的基本概念及理论,在图10—1中标明各城市A~P的位置。10.5十名研究生参加六门课程的考试。由于选修的课程不同,考试门数也不一样。表10—1给出了每个研究生应参加考试的课程(打Δ号的)。规定考试应在三天内结束,每天上下午各安排一门。研究生们提出希望每人每天最多考一门,又课程A必须安排在每一天上午考,课程F安排在最后一门,课程B只能安排在中午考,试列出一张满足各方面要求的考试日程表。图10-1第十章-(图和网络分析)2/54e1v1v2v3v4v5v6v7v8v9v10e2e3e7e4e5e6e8e9e10e11e12e13e14e15图10-2表10-1考试课程研究生ABCDEF1ΔΔΔ2ΔΔ3ΔΔ4ΔΔΔ5ΔΔΔ6ΔΔ7ΔΔΔ8ΔΔ9ΔΔΔ10ΔΔΔ10.6用破圈法和避圈法找出图10-2的一个支撑树。10.7用破圈法和避圈法求图10—3中各图的最小树。(a)728232443613654174312223425(b)第十章-(图和网络分析)3/5410.8已知世界6大城市:(Pe)、(N)、(Pa)、(L)、(T)、(M)。试在由表10—1所示交通网络的数据中确定最小树。表10-2城市PeTPaMNLPe×1351776850T13×60706759Pa5160×57362M777057×2055N68673620×34L505925534×10.9有九个城市921,,,vvv,其公路网如图10—4所示。弧旁数字是该段公路的长度,有一批货物从1v运到9v,问走那条路最短?223221533522422536474536321(c)(d)图10-3343323122.5542V1V2V3V4V5V6V7V8V93图10-4第十章-(图和网络分析)4/5410.10用标号法求图10—5中V1到各点的最短路。10.11用Dijksrea方法求图10—6中V1到各点的最短距离。10.12求图10-7中从V1到各点的最短路。10.13在图10—8中(1)用Dijkstra方法求从V1到各点的最短路;(2)指出对V1来说那些顶点是不可到达的。V12847615129143216317924V2V3V4V5V6V7V8V9V10V11图10-62261304202047105101515751030420V1(a)(b)图10-5V1985218374310712445331222V1V2V4V323V5V6图10-7第十章-(图和网络分析)5/5410.14已知八口海上油井,相互间距离如表10-2所示。已知1号井离海岸最近,位5浬。问从海岸经1号井铺设油管将各油井连接起来,应如何铺设使输油管线长度为最短(为便于计算和检修,油管只准在各井位处分叉)。表10-2各油井间距离单位:km从到234567811.32.10.90.71.82.01.520.91.81.22.62.91.132.61.72.51.91.040.71.61.50.950.91.10.860.61.070.510.15设某公司在六个城市c1,…,c6有分公司,从ci到cj的直达航线票价记在下面矩阵的(i,j)位置上(∞表明无直达航线,需经其他城市中转)。请帮助该公司设计一张任意两城市的票价最便宜的路线表。05525251055010202525100102040201001525201505010254050010.16在如图10-9所示的网格中,每弧旁的数字是(cij,fij)。(1)确定所有的数集;V4413341624367V1V2V7V5V6V8V3图10-8第十章-(图和网络分析)6/54(2)求最小截集的容量;(3)证明指出的流是最大流。10.17求如图10-10所示的网络的最大流(每弧旁的数字是(cij,fij)。10.18用Ford-Fulkerson的标号算法求图10-11中所示各容量网络中从Vs到Vt的最大流,并标出个网络的最小割集。图中各弧旁数字为容量,括弧中为流量。svVstvVt(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-105(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)svtv1(1)tvsv2(1)2(2)1(2)2(1)2(1)2(2)2(0)1(0)2(2)2(0)1(1)(a)(b)svtv(2,2)(4,3)(3,3)(1,0)(2,2)(5,2)(3,1)图10-9第十章-(图和网络分析)7/5410.19某单位招收懂俄、英、日、德、法文的翻译各一人。有5人应聘。已知乙懂俄文,甲、乙、丙、丁懂英文,甲、丙、丁懂日文,乙、戊懂德文,戊懂法文。问最多有几人能得到招聘,有分别被聘任从事那一文种的翻译。10.20求图10-12中从s→t的最小费用最大流,各弧旁数字为(,)。10.21图10-13中,A、B为出发点,分别有50和40单位物资往外发运,D、E为收点,分别需要物资30和60单位,C为中转点,各弧旁数字为(,)。求满足上述收发量要求最小费用流。ABCDE(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)st(a)(b)(7,7)(5,3)(5,1)(7,2)(10,9)(5,3)(8,4)(10,10)(7,2)st图10-123(2)5(5)3(3)3(3)2(0)6(4)4(4)2(2)5(4)2(0)8(6)6(6)tvsv(c)tvsv12(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/5410.22设G=(V,E)是一个简单图,令δ(G)=(称δ(G)为G的最小次)。证明:(1)若δ(G)2,则G必有图;(2)若δ(G)2,则G必有包含至少δ(G)+1条边的图。10.23设G是一个连通图,不含奇点。证明:G中不含割边。10.24给一个联通赋权图G,类似于求G的最小支撑树的Kruskal方法,给出一个求G的最大支撑树的方法。10.25下述论断正确与否:可行流f的流量为零,即v(f)=0,当且仅当f是零流。第十章-(图和网络分析)9/54习题答案及详解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又是简单图的次的序列。(2)由定理知,任一个图G=(V,E)中,所有点的次数之和是边数的两倍,即图中点次的和为偶数。序列6,6,5,4,3,2,1的和为27,所以它不可能是一个图的次的序列,更不可能是某个简单图的次的序列。【或者】假设6,6,5,4,3,2,1为某个简单图的次的序列,则图中存在7个点,不妨设为1V,2V,3V,4V,5V,6V,7V,其中1V,2V次为6,表明1V,2V与除自身外的剩余6个点均相连。即3V,4V,5V,6V,7V的次不少于2,与7V的次为1矛盾。所以,6,6,5,4,3,2,1不是某个简单图的次的序列。(3)假设6,5,4,3,2,1为某个简单图的次的序列,则图中存在7个点,不妨设为1V,2V,3V,4V,5V,6V,7V,,因为1()dV=6,7()dV=1,所以1V与其他6个点相连,而7V仅与1V相连,又因为23()()5dVdV,则2V,3V与除7V和自身之外的所有点相连,则6V必须与2V,3V相连,所以6V与1V,2V,3V相连,与6()2dV矛盾,所以6,6,5,4,3,2,1不是某个简单图的次的序列。10.2解:设9个人1V,2V,…9V为9个点,两人握手设为两点之间存在相连边,握手问题转化为一个简单图,其中,1V,2V,…9V次的序列为2,4,4,5,5,5,5,6,6。这9个人中一定可以找到3个互相握过手,转化为在图中一定存在3个点彼此相连。因为,4567()()()()5dVdVdVdV,4V,5V,6V,7V之间一定存在两点相连。假如,4V,5V,6V,7V互相均不相连,因为次均为5,所以4V,5V,6V,7V均与剩余的4个点1V,2V,3V,8V,9V相连,这与1()dV=2矛盾。第十章-(图和网络分析)10/54不妨设4V,5V,6V,7V,中存在4V,5V之间相连。必可以找到第三点均与4V,5V相连。假设不存在第3点均与4V,5V相连,4V,5V分别与定义不同的4个点相连,即存在8个不同的点分别与4V或5V相连,加上4V,5V共计10个点,这与图中9个点矛盾。所以在图中,必存在3个点彼此相连。10.3解:将8种化学药品A,B,C,D,P,R,S,T设定为8个点,两种药品不能贮存同一室内状态,设定为两点之间存在一边相连,画出药品关系图如下:(图10-3(a))在图(a)中,两点之间相连的药品均不能存贮在一起。对于由点A,B,C,D,P,R,S,T的完全图,求图(a)的补图,得图(b),在(b)图中,彼此相连的药品均可以为存贮庄点,因为()()2dSdD,从S,D开始搜索,(S,A,B)彼此相连,(D,R)相连,(T,C,P)彼此相连。所以至少需要3间贮存室,存效组合为(S,A,B),(T,C,P),(D,R)。10.4解:依据旅行者的路线统计城市间的相互关系。点(城市)相邻城市(相邻点)次点相邻点次AJ,M2IM,E,F3BG,M,F,J4JA,N,B3CF,I,O,G4KH,G,O3DL,O2LC,D,P3EL,P2MB,I,A3FP,C,I,B4NJ,H,G3(a)BATCRPSD(B)BATCRPSD图10-3第十章-(图和网络分析)11/54GK,M,C,N4OD,C,K3HM,K2PE,F,L3由点的次可知,A,D,E,H为2,则为4个顶点;B,C,F,G的次为4,则为4个顶点;某系为边点,城市布局图为图10-4。10.5解:将课程A,B,C,D,E,F设定为6个点,同时学生选某课程认为存在相邻边。依据学生1-10的选课划分课程关系图10-5(a),要求学生一天最多考1门,即图(a)中相连的课程不能排在同一天。对于点ABCDEF的关系图,求图(a)的补图(b)。那么,图(b)中相邻的课程可以安排在同一天,可保证学生一天最多考一门,所以(A,E),(F,D),(C,B)分别各为一天,安排如下:天上午下午123ACDEBFAMIEJBFPNGCLCKOD图10-4CABDEF图10-5
本文标题:第十章-(图和网络分析)
链接地址:https://www.777doc.com/doc-5802028 .html