《图与网络分析_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,
