第八章-图与网络分析-课件

ABＣＤ第六章图与网络分析例1、哥尼斯堡七桥问题BCAD1一、图的概念：1、图：点和线所组成的图形，记为G=(V,E)，其中V是点的集合，E是边的集合。2、端点、关联边：联结点vi,vj的边记作e=(vi,vj)，称vi,vj为e的端点，也称e为vi,vj的关联边。３、相邻点、相邻边：具有同一条关联边的点为相邻点，具有公共端点的边为相邻边。4、环：一条边的两个端点相同，则称该边为环（自回路）。§6.1图与网络的基本概念25、多重边：若两端之间有多于一条边相关联，称这些边为多重边。6、简单图与多重图：不含环和多重边的图称为简单图，无环但含有多重边的图称为多重图。7、次：点v的关联边个数称为点v的次，记作d(v)。8、悬挂点、悬挂边：称次为1的点为悬挂点，悬挂点所关联的边为悬挂边。v4v3v1v2e1e2e3e4e5e63定理１：

图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。点边序列中没有重复的点称为初级链。若链首尾两端点重合，则称为圈。v6v5v4v3v2v1e1e5e4e3e2e6e7e8e9e10S1={v6,v5,v1,v5,v4,v3}S2={v6,v5,v1,v4,v3}42、连通图：如果图Ｇ中任意两点间至少有一条链相连，则称此图为连通图。任何一个连通图都可以分为若干个连通子图，每个连通子图称为由原图的分图。5例2、有5名运动员参加游泳比赛，问如何安排比赛，才能使每位运动员都不连续地参加比赛？运动员50m仰泳50m蛙泳100m蝶泳100m自由泳200m自由泳甲√乙√√√丙√√丁√√戊√√6§6.2树与最小生成树一、树的概念：树：无圈的连通图。二、树的性质：（1）树枝数等于顶点数减1；（2）树的任意两个顶点之间有且仅有一条初级链。（3）去掉树的任一树枝，便得到一个非连通图；（4）在树中任意两个顶点间添上一条边，恰好得到一个初级圈。（5）在所有连通的生成子图中，生成树的边数最少。9三、根树（有向树）：D=(V,A)中，v到D的任一顶点都有路，则v称为D的根，D称为以v为根的根树或有向树。四、图的生成树：v6v5v4v3v2v1v6v5v4v3v2v110定理2：

图G有生成树的充要条件是图G是连通图。寻找生成树的方法：１、破圈法：在连通图Ｇ中任取一个圈，去掉圈上的任意一条边，对余下的图重复这个步骤，直至无圈为止。２、避圈法：每次增加一条边，且与已有边不构成圈，直至恰有p-1条边为止。v6v5v4v3v2v111例１、下图是某建筑物的平面图，要求在其内部从每一房间都能走到别的所有的房间，问至少要在墙上开多少门？试给出一个开门的方案。一二三四五六七八九一二三四五六七八九一二三四五六七八九12§6.3最小树问题一、赋权图：与点或边有关的某些数量指标，通常称之为“权”。定义：图G中,如果每条边(弧)(vi,vj)都被赋予一个权数wij,则称G为赋权图.

权可以表示为：距离、费用、通过能力（数量）等。与无向图和有向图相对应，赋权图可分为无向赋权图和有向赋权图，分别记为G=(V,E,W)和D=(V,A,W)。13二、最小生成树（最小树）：定义：在给定连通赋权图G=(V,E,W)中，求G的生成树T=(V,E

)，使E

各边权Wij(

0)的总和最小的问题称为最小树问题。其数学模型为：其中T*称为最小树。许多网络问题都可归结为最小树问题，如设计长度最小的公路网把若干城市联通；设计用料最省的电话线网把有关单位联系起来。14求最小树的方法：１、破圈法(管梅谷算法)：（１）先从图G任取一个圈，并从圈中去掉一条权最大的边。若在同一圈中有几条都是权最大边，则任选其中一边去掉。（２）在余下的子圈中，重复上述步骤，直至没有圈止。２、避圈法(Kruskal算法)：开始选一条权最小的边，以后每步从未选的边中选取一条权最小的边，使它与已选边不构成圈，直至选够q－1条边止。v2v1v4v322344546v5v2v1v4v32234v515例１、今要在七个城市之间修筑一个公路网，每个城市之间的公路修筑费用就是各条边上的权，试求总修筑费用最小的公路网。v1v4v7v6v5v3v28567632445310v1v4v7v6v5v3v232445316§6.4最短路问题

最短路问题是网络理论中应用最广泛的问题之一，许多优化问题可以使用这个模型，如管道铺设，设备更新，线路安排等。给定D=(V,A,W)，其中wij

W，表示弧(vi,vj)的权（可以是费用、时间、距离等）。设vs和vt是D中任意两顶点，求一条路，使它是从vs到vt的所有路中总权最小的路。其数学模型为：17求最短路的狄克斯特Dijkstra标号法（Wij

0）1、基于以下原理：若序列{vs,vi1,…vik,…vt}是从vs到vt的最短路，则序列{vs,vi1,…vik}必为从vs到vik的最短路。

2、Dijkstra标号法的基本思想是采用两种标号：T标号与P标号，T标号为临时性标号(TemporaryLabel)，P标号为永久性标号(PermanentLabel)。从vs开始，逐步向外探寻最短路。给vi点P标号时，表示从vs到vi点的最短路权，vi的标号不再改变。给vi点T标号时，表示从vs到vi点的最短路权上界的估计。凡没有得到P标号的点都有T标号。标号法每一步都是把某一T标号点改为P标号，当终点vt得到P标号时，计算全部结束。如果点vj不能由T标号变为P标号，则说明vs到vj不存在路。183、步骤：(1)给vs以P标号，P(vs)=0，其余各点给T标号，且T(vi)=+

。(2)若vi点为刚得到P标号的点，考虑T标号点vj,(vi,vj)

A。对vj的T标号进行如下的更改：T(vj)=min{T(vj),P(vi)+wij} (3)比较所有具有T标号点，把最小者改为P标号，即：P(vjo)=min{T(vj)}vj为T标号若全部点均为P标号。则停止。否则以vjo代vi，返回(2)19v6v5v4v3v2v1v8v7356117423521695（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)=3T(v3)=min{5,3+1}=4，k(v3)=v2T(v5)=min{+,3+7}=10，k(v5)=v2T(v6)=min{+,3+4}=7，k(v4)=v220v6v5v4v3v2v1v8v7356117423521695（3）P(v3)=4T(v4)=min{6,4+1}=5，k(v4)=v3T(v6)=min{7,4+2}=6，k(v6)=v3（4）P(v4)=5T(v6)=min{6,5+3}=6，k(v6)=v3T(v7)=min{+,