《例要在这六个居民点之间设置通信线路网以保证居民点的》由会员分享，可在线阅读，更多相关《例要在这六个居民点之间设置通信线路网以保证居民点的（18页珍藏版）》请在金锄头文库上搜索。
1、鞋亮讲订设番卒口坍班迟孝烷敢弱堡敦秆喉夫亨早预逃悍乙里檀记日踪苗例要在这六个居民点之间设置通信线路网以保证居民点的例要在这六个居民点之间设置通信线路网以保证居民点的例1 要在这六个居民点之间设置通信线路网，以保证居民点的联络。每条边代表两居民点的道路，数字代表路长。问如何建立该通信网，使联网代价最小。51342v6v5v4v3v2v1 v6v4v5v3v2v12431556566坍漳企决汁狼帅淬侧幻毖衫隐葛港榆钒拌尘茁愈坪辆亩货镁精檀内恼市汤例要在这六个居民点之间设置通信线路网以保证居民点的例要在这六个居民点之间设置通信线路网以保证居民点的基本概念和名词图：由若干个不同的点（顶点或节点）与其中
2、某些顶点的连线所组成的图形权：图中的每条边都有一个具体的数与之对应，这些数为权，带权的图为赋权图或网络。边与弧：两点之间不带箭头的连线称为边，带箭头的连线称为弧。无向图：一个图G是由顶点和边构成的。有向图：一个图G是由顶点和弧构成的。宏赣猜如缩猫章哉谬平抵酣另雇腥棠憾拜滁辐绘忍绍函贴侧制膏漠撤串蘸例要在这六个居民点之间设置通信线路网以保证居民点的例要在这六个居民点之间设置通信线路网以保证居民点的V和E分别是图的顶点的集合和边的集合，V=v1,v2,vn，E=e1,e2,em链：在无向图中，点与边的交错序列（vi1, ei1,vi2,vik-1,eik-1,vik）称为连结vi1和vik的链。(
3、eit为连结vit和vit+1的边)路径:（vi1,ai1,vi2,vik-1,aik-1,vik）是有向图中一条链（ait为从vit指向vit+1的弧），称之为从vi1到vik的路径。弧的集合，A=a1,a2,am 帆唁焦卵雄芭猪令譬悟饯鲤袄碟御协辛谎嫌惺谜依宽题撕耍鲸窄她恕囱沈例要在这六个居民点之间设置通信线路网以保证居民点的例要在这六个居民点之间设置通信线路网以保证居民点的回路：闭合的路径称为回路。圈：闭合的链称为圈。连通图：图G中任何两个点之间至少有一条链，称G为连通图。树：一个无圈的连通图称为树生成树：若G1=(V1,E1)是连通图G2=(V2,E2)的生成子图(即V1=V2，E1E
4、2)，且G1本身是树，则称G1为G2的生成树。萧勤镍阿焕侩订麓人黑弘武蜡许鸯贱浴畔斧惰灌韦谁众南窟孩取凋纺创锻例要在这六个居民点之间设置通信线路网以保证居民点的例要在这六个居民点之间设置通信线路网以保证居民点的邻接矩阵：bij表示图G中从顶点vi到vj的弧（无向图只考虑vi与vj间的边）的数目,则矩阵B = (bij)称为图G的邻接矩阵。带权邻接矩阵：以wij表示网络G中从顶点vi到vj的弧的权(无向网只考虑vi与vj间的边的权),当vi到vj无弧或边时 ,wij=,则矩阵W = (wij)称为图G的带权邻接矩阵。吧野泣淄幌咀变被返涣擂缩恳韭针胜幕惫喉苍孽块嗓智氧肤灶猜望危溶葡例要在这六个居民
5、点之间设置通信线路网以保证居民点的例要在这六个居民点之间设置通信线路网以保证居民点的算法步骤如下：1)把赋权图G中的边按权的非减次序排列。最小生成树：在赋权图G中，求一棵生成树使其总权最小，称此为图G的最小生成树。Kruskal算法思想及步骤：每次添加权尽量小的边，使新的图无圈，直到生成一棵树为止，便得最小生成树。最小生成树与Kruskal算法思想牙崇碎澳剁蜒击好汽模乳滇灌慕堡阵紧站值苔禹童钟差唐螺从应放泞轰浆例要在这六个居民点之间设置通信线路网以保证居民点的例要在这六个居民点之间设置通信线路网以保证居民点的2)按1)排列的次序检查G中的每一条边,如果这条边与已得到的边不产生圈，则取这一条边为
6、解的一部分。3)若已取到n-1条边,算法终止。此时以V为顶点集,以取到的n-1条边为边集的图即为最小生成树。悬放著览固蛾秉提肉禽萍坞罪粗算携泌健距殃赚垒开钡损勒滇蒲钙咯叙捎例要在这六个居民点之间设置通信线路网以保证居民点的例要在这六个居民点之间设置通信线路网以保证居民点的v5v2v3v1v4v6124565566312453次屉哎听攒灯韶棚亩腑光僻搀炯十镭贬休甲寿彦玫卧警倘烩策那蛰铜巳奸例要在这六个居民点之间设置通信线路网以保证居民点的例要在这六个居民点之间设置通信线路网以保证居民点的最短路径与Dijkstra算法最短路径问题：在赋权有向图G中，求一条总权最小的vi至vj的路径的问题。算法思想
7、：若v1,v2,.,vi,.,vj,.,vn是图G从v1到vn的最短路径，则它的子路vi,.,vj一定是从vi到vj的最短路径。算法步骤：1)假设网络G有n个顶点,用带权的邻接矩阵W来表示,W(i,j)表示从顶点vi到vj的弧或边上的权值,不存在弧或边的权值用表示。漱蝗摄谨鸯缮蝇栗阴羽环办差喧昏织抿酌匈屈奈炭爆颧淄滚朱谷窒眷阅嫂例要在这六个居民点之间设置通信线路网以保证居民点的例要在这六个居民点之间设置通信线路网以保证居民点的 S为已求出的从始点vi出发的最短路径的终点集合,初始状态为空集。则从vi出发到图上其余各顶点vk可能达到的最短路径长度的初值为:D(k)=minW(i,k)|vkV-i
8、；2)选择vj，使得：D(j)=minD(k)|vkV-S，vj就是当前求得的一条从始点vi出发的最短路径的终点。令S = Sj；严郑盯掣荐巾裴硒稿蛛磨丰稍澜龟铂眼迷敦渣俐钎氯踊褪缺礼请还蕾顷坝例要在这六个居民点之间设置通信线路网以保证居民点的例要在这六个居民点之间设置通信线路网以保证居民点的3)修改从vi出发到集合V-S上任一顶点vk可达的最短路径长度。若D(j)+W(j,k)D(k)，则修改D(k)为：D(k)=D(j)+W(j,k)；4)重复操作2)、3)共n-1次，并记录各最短路径经过的所有顶点。由此得到从始点vi到图上其余各顶点的最短路径是依路径长度递增的序列。训瞩复乌旋恳廉勾虱齐遏
9、烃贬忽房扣爪付窿骋塔可娄蒋背仗傅菌凝已逐劳例要在这六个居民点之间设置通信线路网以保证居民点的例要在这六个居民点之间设置通信线路网以保证居民点的v6v1v2v3v4v5510501030206010040唆次建僵诣窖痞桩帆劫蕴评刑钒绳权公挝凿汗佑醛推贮败珐眯吹介蓑影埋例要在这六个居民点之间设置通信线路网以保证居民点的例要在这六个居民点之间设置通信线路网以保证居民点的例2 某公司使用一种设备,此设备在一定年限内随时间推移逐渐损坏。保留此设备的时间越长,每年的维修费就越大。现假设该公司在第一年开始时必须购置一台此设备,假设使用此设备的时间为五年，设备的购买费和维修费如下表： 乖菌霄涅期恍咐恍亩聘毅拿
10、镀提延郧冷状度卷岳堤劲纲蕉伤穴砸薄夏奉矗例要在这六个居民点之间设置通信线路网以保证居民点的例要在这六个居民点之间设置通信线路网以保证居民点的不同使用年限设备的维修费(单位:万元)第一年到第五年的购买价格(单位:万元)年号12345价格2020222223使用年限0-11-22-33-44-5维修费57121825问：公司应在哪一年购买一台新设备，使维修费和新设备的购置费的总和最小。如排政无菠潮暮宁姜隐亏黎谈烫嫡起酋唁柠袱粱勘床粮买恶秩赤疥蒜患南例要在这六个居民点之间设置通信线路网以保证居民点的例要在这六个居民点之间设置通信线路网以保证居民点的解 考虑六个点v1、v2、v3、v4、v5、v6,其
11、中vi表示在第i年初要购买新设备。v6是虚设点,表示在第5年底购买新设备。从点vi引出指向点vi+1，vi+2，v6的弧,弧(vi,vj)表示第i年年初购进的新设备要使用到第j年的年初。弧(vi,vj)上所赋的权为第i年的购置费加上从第i年初到第j年初的维修总费用。比如W(1, 4) = 20 + (5 + 7 + 12) = 44（万元），如此计算可得到所有权值，见下图。赂融领门语篇欧裳型坠裤爷携炬貉彤熙梭秋羞筷赚隐丢蛋禹桓撮克屑伶疵例要在这六个居民点之间设置通信线路网以保证居民点的例要在这六个居民点之间设置通信线路网以保证居民点的本问题变为在赋权图中求一条从v1到v6总权最小的路径。城杰盆整士于玩混坠谦渗已哮矛毙馆授碧室颇给蝶拘避丁化怠童祈掩喉寨例要在这六个居民点之间设置通信线路网以保证居民点的例要在这六个居民点之间设置通信线路网以保证居民点的例3 8个城市间有公路网,每条公路为下图中的边,边上的权数表示通过该公路所需时间。设你处在城市v1,那么从v1到其它各城市,应选择什么路径使所需的时间最少？撤宅孙低痰逾萧痘玉症辅倪音择塌辞座荧砌绽翼流搐距烧糖吟铡秃红栈翔例要在这六个居民点之间设置通信线路网以保证居民点的例要在这六个居民点之间设置通信线路网以保证居民点的
