《2011年5月9日网络规划》由会员分享，可在线阅读，更多相关《2011年5月9日网络规划（35页珍藏版）》请在金锄头文库上搜索。
1、第五章 网络规划,本章内容,图与网络的基本概念 最小支撑树问题 最短路径问题 网络最大流问题 网络最小费用流问题,问题的提出,德国哥尼斯堡七桥问题,一个人如何一次连续走过七座桥且每座桥只走一次回到出发点?,在图中某点出发，经过每边一次且仅一次回到出发点（1736）。,“中国邮路问题”某一邮递员负责某街区的邮件投递工作，每次都要从邮局出发走遍他负责的所有街道，再回到邮局，那么他该如何安排投递路线，使所走过的总路程最短？,在图中找一条经过每边的最短路类似带权的欧拉回路。,“环球旅行”问题 哈密尔顿在1859年提出了一个所谓周游世界问题：用一个正十二面体的20个顶点表示全世界的20个大城市，要从某一
2、城市出发，沿着多面体的棱旅行，并且每个城市恰好经过一次，最后回到出发的城市，问这样的旅行路线是否存在。,在图中找一条经过每个点一次且仅一次的路哈密尔顿回路。,“货郎担问题” 一个货郎要去若干城镇售货，已经知道各城镇之间的距离（设各城镇之间都有交通线相联接），那么货郎应如何选择行走路线，使每个城镇恰好经过一次，并回到原出发地，并使总行程最短。这一问题也称旅行售货员问题。,在图中找一条经过每个点一次且仅一次的最短路带权的哈密尔顿回路。,在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。 例1（铁路交通图）图1是我国北京、上海、重庆等十四个城市之间的铁路交通
3、图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。,例2:（球队比赛图）有六支球队进行足球比赛，我们分别用点v1v6表示这六支球队。它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用图2所示的有向图反映出来。,一、图与网络的基本知识,1.图的基本概念,例 1: 铁路交通图 例 2: 球队比赛图1、点: 表示研究对象. 2、连线：表示两个对象之间的某种特定关系。 3、图(Groph):点(vertex)和连线的集合. 4、不带箭头的连线称为边(edge).带箭头的连线称为弧(Arc).,5、无向图：连线不带箭
4、头的图，简称图，表示为： G=（V，E）V-点集合 E-边集合 例：右图,V=v1，v2，v3，v4E=e1，e2，,e7,1.图的基本概念,5、如果一个图是由点和弧所构成的，那么称它为有向图，记作D=(V, A)，其中V 表示有向图D 的点集合，A 表示有向图D 的弧集合。,1.图的基本概念,6、边的端点：e是连接u,v两点的一条边， 则称u,v 是边e的两个端点，并称点 u和v是相邻的。,7、点的关联边： e是连接u,v两点的一条边， 则称e是u或v的关联边，或者说e与u和v相关联,点与边的关联情况如下,8.相邻: (1)边相邻:两条边有公共的端点,如图中e1,e2,e5,e6有公共端点v
5、1. (2)点相邻:两点有公共的关联边,如图中v1,v4有公共关联边e5.,1.图的基本概念,9.环:两端点相重的边（若u=v, e是环）如图中e7. 10.多重边:两条以上边所连的端点相同（两点之间多于一条边）,如图中e1,e2.,1.图的基本概念,11.简单图:无环、无多重边的图(如图b).,1.图的基本概念,今后我们所研究的图如果没有特别说明，一般都指简单图,12.次(也称为度)(degree): 某一点具有的关联边的数目（以点v为端点的边的个数称为点v 的次）,表示为: d(v) 如图中d(v1)=4， d(v2)=3 ，d(v4)=4(环记两度),1.图的基本概念,v5,13.孤立点
6、:次为“0”的点,如图中v5;,1.图的基本概念,16.奇点:次为奇数的点,如图中v2 17.偶点:次为偶数的点;,14.悬挂点:次为“1”的点,如图中v6;,15.悬挂边:与悬挂点相连的边,如图中e8.,孤立点,悬挂边,定理1 所有顶点度数之和等于所有边数的2倍。定理2 在任一图中，奇点的个数必为偶数。,所有顶点的入次之和等于所有顶点的出次之和。,有向图中，以 vi 为始点的边数称为点vi的出次，用 表示 ；以 vi 为终点的边数称为点vi 的入次， 用 表示；vi 点的出次和入次之和就是该点的次。,子图:设有图G1=（V1，E1）， G2=（V2，E2）若V2V1， E2E1，则称G2是G
7、1的一个子图。,支撑子图：若V2=V1， E2 E1 中，则称G2是G1的一个支撑子图，即包含原图全部顶点的子图。,点全部保留,支撑子图,1.图的基本概念,子图,网络,若对图G=（V，E）或有向图D=（V，A）中每条边vi,vj赋予一个数wij，则称wij为边vi,vj的权，并称图G为网络（或赋权图）。,权可以代表距离、费用、时间、通过能力（容量）等,v4,v5,v2,v1,v3,2,3,4,5,6,7,8,9,4,v1,v3,2,3,4,5,6,7,8,9,4,网络：无向网络、有向网络。,1.图与网络的基本概念,链: 图G中的一个点、边交错序列称为链（由两两相邻的点及其相关联的边构成的点边序
8、列称为链）。如（v1，e1，v3，e2，v5，e6，v6， e5， v3， e4， v4）也可记为（ v1，v3，v5，v6， v3， v4）,v1,v3,v5,e1,e2,v2,v4,v6,e3,e4,e5,e6,e8,e9,圈：首尾相连的链称为圈。如（v3,v5,v6,v3）,1.图与网络的基本概念,v1,v3,v5,e1,e2,v2,v4,v6,e3,e4,e5,e6,e8,e9,v1,v3,v5,e1,e2,v2,v4,v6,e3,e4,e5,e6,e8,e9,简单链：没有重复的边的链。如（v2,v1,v3,v6,v4,v3,v5）,初等链：没有重复的点的链。也称通路。 如（v2，v1
9、，v3，v5）,图中S=（v6 ,e6 ,v5 ,e7 ,v1 ,e8 ,v5 ,e7 ,v1 ,e9 ,v4 ,e4 ,v3 ）为一条连接v6，v3的链。,S1=（v6 ,e6 ,v5 ,e5 ,v4 ,e4 ,v3 ）为初等链,图中（v1 ,e7 ,v5 ,e8 ,v1 ,e9 ,v4 ,e10 ,v2 ,e2 ,v1）为一个圈。,链的概念不考虑弧的方向，既用于无向图也适合有向图。当链（圈）上的方向相同时，称为道路（回路）,图中S1=（v6 ,e6 ,v5 ,e7 ,v1 ,e9 ,v4 ,e4,v3 ）为一条道路。,S3=（v1 ,e2 ,v2 ,e10 ,v4 ,e5 ,v5 ,e7,
10、v1 ）为一个回路。,无向图中，链与路的概念是一致的。有向图中，路一定是链，但链不一定是路。当链上弧的方向一致时是路,连通图：任意两点之间可由一条链直接链起来相通的图叫连通图。否则，称为非连通图。,树(Tree)无圈的连通图称为树树中只与一条边关联的节点称为悬挂节点,5.2 树图及图的最小支撑树,定义:一个无圈的连通图称为树.,例某工厂的组织机构图就是一个树.,树的性质：（1）树必连通，但无回路（圈）。（2）n 个顶点的树必有n-1 条边。（3）树 中任意两个顶点之间，恰有且仅有一条链（初等链）。（4）树 连通，但去掉任一条边， 必变为不连通。（5） 树 无回路（圈），但不相邻的两个点之间加一
11、条边，恰得到一个回路（圈）。 若图G=V,E是一个树,且p(G)2,则G中至少有两个悬挂点. 式中:p(G)为图G点数,如图中有10个悬挂点.,树图及图的最小支撑树,6.2.2 图的最小支撑树1.支撑树的概念和性质,定义:设T=V,E为G=V,E的子图,如果T是一个树,则称为G的一个支撑树.,【定理】 图G有支撑树的充分必要条件是图G=V,E是连通的.,定义:给图G的每一条边vi,vj,相应地赋予一个数wij,则称这样的图G为赋权图,wij称为vi,vj的权.,定义:如果T=V,E是G的一个支撑树,称E所有边的权之和为支撑树T的权,记为w(T),即,如果T*的权w(T*)是G的所有支撑树的权中
12、最小者,则称T*为G的最小支撑树(简称最小树).即,网络的支撑树,若G=(V,E)是图G=(V,E) 一个子图。当V=V，则G成为网络G的生成子图，若G是一棵树，则称G 为网络G的支撑树。网络中不属于生成树的边称为支撑树的弦,支撑树的变换,网络的一个支撑树，增加一条弦，形成唯一的圈，去掉支撑树的一条边，得到一个新的网络的生成树,生成树2,生成树3,生成树1,/,/,最小支撑树的定义一颗支撑树上所有树枝上权的总和，称为这个支撑树的权。具有最小权的支撑树为最小支撑树。,最小支撑树问题,最小支撑树的应用设计长度最小的公路网把若干城市联系起来；设计用料最省的电话线网把有关单位联系起来等等。,最小支撑树
13、问题的特点已知图中若干点，求把已知点联系起来的边，使各边的权取值之和最小。,最小支撑树的求法Kruskal算法,开始将G的所有边按权从小到大的次序排列出来，然后逐边检查。首先把最短的一条边留下来，然后在检查每一条边时，若它不与已留下的边形成圈，就留下来，否则就去掉，直至所有被留下来的边形成支撑树时，计算终止。,最小支撑树的求法Kruskal算法,例1.一个乡有9个自然村，其间道路各长度如图所示，各边权表示距离，问如何拉线才能使电话线最短。,最小支撑树的求法Kruskal算法,1、所有边按权从小到大的次序排列出来，,(1,8),(2,0),(2,3),(3,4),(1,0),(0,6),(6,5),(0,3),(6,7),(0,8),(0,4),(0,5),(1,2),(7,8),(0,7),(4,5),2、检查每一条边，若它不与已留下的边形成圈，就留下来，否则就去掉，直至所有被留下来的边形成支撑树,最小支撑树已形成，其权为 1+1+1+1+2+2+2+3=13,最小生成树的求法 Prim算法,v1,v2,v3,v4,v5,v6,v7,v8,v0,4,1,1,2,2,2,1,1,3,最短线长为13,六.所有边检查完毕，得到n1条边。 即得到最小生成树,
