《图与网络分析_2ppt培训课件》由会员分享,可在线阅读,更多相关《图与网络分析_2ppt培训课件(22页珍藏版)》请在金锄头文库上搜索。
1、1,第六章 图与网络分析,例1、哥尼斯堡七桥问题,2,一、图的概念: 1、图:点和线所组成的图形,记为G=(V,E),其中V是 点的集合,E是边的集合。 2、端点、关联边: 联结点vi,vj的边记作e=(vi,vj),称vi,vj为e的端点,也称e为vi,vj的关联边。 、相邻点、相邻边: 具有同一条关联边的点为相邻点,具有公共端点的边为相邻边。 4、环: 一条边的两个端点相同,则称该边为环(自回路)。,6.1 图与网络的基本概念,3,5、多重边: 若两端之间有多于一条边相关联,称这些边为多重边。6、简单图与多重图:不含环和多重边的图称为简单图,无环但含有多重边的图称为多重图。 7、次: 点v
2、的关联边个数称为点v的次,记作d(v)。 8、悬挂点、悬挂边: 称次为1的点为悬挂点,悬挂点所关联的边为悬挂边。,4,定理: 图G=(V,E)中,所有点的次数之和等于边数的两倍。 二、连通图 1、链、圈: 在无向图G=(V,E),称一个点和边交替的序列 vi1,ei1,vi2,ei2,vit-1,vit为连接vi1和vit的一条链。 简记为vi1,vi2,vit。其中eik=(vik,vik+1),k=1,2,t-1。 点边序列中没有重复的点称为初级链。 若链首尾两端点重合,则称为圈。,S1=v6,v5,v1,v5,v4,v3 S2=v6,v5,v1,v4,v3,5,2、连通图:如果图中任意两
3、点间至少有一条链相连,则称此图为连通图。 任何一个连通图都可以分为若干个连通子图,每个连通子图称为由原图的分图。,6,例2、有5名运动员参加游泳比赛,问如何安排比赛,才能使每位运动员都不连续地参加比赛?,7,三、子图:,e4,8,四、有向图: 1、弧、有向图: 带有方向的边称为弧,记作a= (vi,vj)。 由一些点和弧组成的集合称为有向图,记作D=(V,A) 。A表示G中弧的集合。 、路: 在有向图D=(V,A)中,称链vi1,vi2,vit为一条从vi1到vit的路。若vi1=vit,则称之为回路。,S1=v6,v5,v1,v5,v4,v3 S2=v1, v5,v1,9,6.2 树与最小生
4、成树,一、树的概念: 树:无圈的连通图。 二、树的性质: (1)树枝数等于顶点数减1; (2)树的任意两个顶点之间有且仅有一条初级链。 (3)去掉树的任一树枝,便得到一个非连通图; (4)在树中任意两个顶点间添上一条边,恰好得到一 个初级圈。 (5)在所有连通的生成子图中,生成树的边数最少。,10,三、根树(有向树): D=(V,A)中,v到D的任一顶点都有路,则v称为D的根,D称为以v为根的根树或有向树。 四、图的生成树:,11,定理2: 图G有生成树的充要条件是图G是连通图。 寻找生成树的方法: 、破圈法:在连通图中任取一个圈,去掉圈上的任意一条边,对余下的图重复这个步骤,直至无圈为止。
5、、避圈法:每次增加一条边,且与已有边不构成圈,直至恰有p-1条边为止。,12,例、下图是某建筑物的平面图,要求在其内部从每一房间都能走到别的所有的房间,问至少要在墙上开多少门? 试给出一个开门的方案。,13,6.3 最小树问题,一、赋权图: 与点或边有关的某些数量指标,通常称之为“权”。 定义:图G中,如果每条边(弧) (vi,vj)都被赋予一个权数wij, 则称G为赋权图. 权可以表示为:距离、费用、通过能力(数量)等。 与无向图和有向图相对应,赋权图可分为无向赋权图和 有向赋权图,分别记为G=(V,E,W)和D=(V,A,W)。,14,二、最小生成树(最小树): 定义:在给定连通赋权图G=
6、(V,E,W)中,求G的生成树T=(V,E),使E各边权Wij(0)的总和最小的问题称为最小树问题。其数学模型为:,其中T*称为最小树。许多网络问题都可归结为最小树问题,如设计长度最小的公路网把若干城市联通;设计用料最省的电话线网把有关单位联系起来。,15,求最小树的方法: 、破圈法(管梅谷算法) : ()先从图G任取一个圈,并从圈中去掉一条权最大的边。若 在同一圈中有几条都是权最大边,则任选其中一边去掉。 ()在余下的子圈中,重复上述步骤,直至没有圈止。 、避圈法(Kruskal算法) :开始选一条权最小的边,以后每 步从未选的边中选取一条权最小的边,使它与已选边不构成圈,直至选够q1条边止
7、。,16,例、今要在七个城市之间修筑一个公路网,每个城市之间的公路修筑费用就是各条边上的权,试求总修筑费用最小的公路网。,17,6.4 最短路问题,最短路问题是网络理论中应用最广泛的问题之一,许多优化问题可以使用这个模型,如管道铺设,设备更新,线路安排等。给定D=(V,A,W),其中wijW,表示弧(vi,vj)的权(可以是费用、时间、距离等)。设vs和vt是D中任意两顶点,求一条路,使它是从vs到vt的所有路中总权最小的路。其数学模型为:,18,求最短路的狄克斯特Dijkstra标号法(Wij0) 1、基于以下原理:若序列vs,vi1,vik,vt是从vs到vt的最短路,则序列vs,vi1,
8、vik必为从vs到vik的最短路。2、Dijkstra标号法的基本思想是采用两种标号:T标号与P标号,T标号为临时性标号(Temporary Label),P标号为永久性标号(Permanent Label)。从vs开始,逐步向外探寻最短路。给vi点P标号时,表示从vs到vi点的最短路权,vi的标号不再改变。给vi点T标号时,表示从vs到vi点的最短路权上界的估计。凡没有得到P标号的点都有T标号。标号法每一步都是把某一T标号点改为P标号,当终点vt得到P标号时,计算全部结束。如果点vj不能由T标号变为P标号,则说明vs到vj不存在路。,19,3、步骤:(1)给vs以P标号,P(vs)=0,其余
9、各点给T标号,且T(vi)=+。(2)若vi点为刚得到P标号的点,考虑T标号点vj,(vi,vj)A。对vj的T标号进行如下的更改: T(vj)=minT(vj),P(vi)+wij (3)比较所有具有T标号点,把最小者改为P标号,即:P(vjo)=minT(vj) vj为T标号若全部点均为P标号。则停止。否则以vjo代vi,返回(2),20,(1) P(v1)=0 , T(vi)=+ , i=2,3,4,5,6,7,8T(v2)=min+,0+3=3, k(v2)=v1T(v3)=min+,0+5=5, k(v3)=v1T(v4)=min+,0+6=6, k(v4)=v1 (2) P(v2)
10、=3 T(v3)=min5,3+1=4, k(v3)=v2T(v5)=min+,3+7=10, k(v5)=v2T(v6)=min+,3+4=7, k(v4)=v2,21,(3) P(v3)=4 T(v4)=min6,4+1=5, k(v4)=v3T(v6)=min7,4+2=6, k(v6)=v3 (4) P(v4)=5T(v6)=min6,5+3=6, k(v6)=v3T(v7)=min+,5+5=10, k(v7)=v4 (5) P(v6)=6T(v5)=min10,6+2=8, k(v5)=v6T(v7)=min10,6+1=7, k(v7)=v6T(v8)=min+,6+9=15, k(v8)=v6,22,(6) P(v7)=7 T(v8)=min15,7+5=12, k(v8)=v7 (7) P(v5)=8T(v8)=min12,8+6=12, k(v8)=v7 (8) P(v8)=12 (9) 反向追踪找最短路径:vvvvvv,