第六章 图与网路分析.pptx

第六章图与网络分析;;一个图是由点集V={vj}和V中元素的无序对的一个集合E={ek}构成的二元组，记为G=(V,E),其中V中的元素vj叫做顶点，V表示图G的点集合；E中的元素ek叫做边，E表示图G的边集合。;如果一个图是由点和边所构成的，则称其为无向图，记作G=(V,E)，连接点的边记作[vi,vj],或者[vj,vi]。;环：两个端点相同的边。

多重边：两个端点之间有两条以上的边。;定义4;;有向图中，以vi为始点的边数称为点vi的出度，用表示；以vi为终点的边数称为点vi的入度，用表示；

vi点的出度和入度之和就是该点的度。所有顶点的入度之和等于所有顶点的出度之和。;图G=(V,E)，若E′是E的子集，V′是V的子集，且E′中的边仅与V′中的顶点相关联，则称G′=(V′,E′)是G的一个子图。特别是，若V′=V，则G′称为G的生成子图(支撑子图)。;实际应用中，给定一个图G=（V,E）或有向图D=（V,A）,在V中指定两个点，一个称为始点（或发点），记作v1，一个称为终点（或收点），记作vn，其余的点称为中间点。对每一条弧，对应一个数，称为弧上的“权”。通常把这种赋权的图称为网络。;无向图G中，连结vi0与vik的一条链，当vi0与vik是同一个点时，称此链为圈。圈中既无重复点也无重复边者为初等圈。;对于网络(赋权图)G=(V,E),其中边

有权，构造矩阵，其中：

称矩阵A为网络G的权矩阵。;例;§2树;定理3;一个图G有生成树的充要条件是G是连通图。;（一）避圈法;e5;（二）破圈法;用破圈法求出下图的一个生成树;定义15;最短路的概念：设为连通图，图中各边有权（表示之间没有边），为图中任意两点，求一条路，使它为从到的所有路中总权最短。即：;算法步骤：(P:永久标号；T:临时标号)

1.给始点vs以P标号，这表示从vs到vs的最短距离为0,其余节点均给T标号，

2.设节点vi为刚得到P标号的点，考虑点vj，其中且vj为T标号。对vj的T标号进行如下修改：

3.比较所有具有T标号的节点，把最小者改为P标号，即：

当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用vk代替vi，返回步骤（2）。;例:用Dijkstra算法求下图从v1到v8的最短路;比较所有T标号，T(v3)最小，令P(v3)=6,并记录路径(v1,v3);比较所有T标号，T(v7)最小，令P(v7)=14,并记录路径(v5,v7);（二）逐次逼近法

适用于网络中存在wij≤0的情况，略;§4最大流问题;问题引入;网络D上的流，是指定义在弧集合E上的一个函数：

其中f(vi,vj)=fij叫做弧(vi，vj)上的流量。;称满足下列条件的流为可行流：

（1）容量条件：对于每一个弧（vi,vj）∈E

有0≤fij≤cij。

（2）平衡条件：

对于发点vs，有

对于收点vt，有

对于中间点，有;可行流f是最大流的充分必要条件是不存在从vs到vt的关于f的一条可增广链。;33;设已有一个可行流f，标号的方法可分为两步：

第1步是标号过程，通过标号来寻找可增广链；

第2步是调整过程，沿可增广链调整f以增加流量。;一、标号过程：

1．给发点vs标号（0，+∞）。

2．取一个已标号的点vi，对于vi一切未标号的邻接点vj按下列规则处理：

（1）如果边，且，那么给vj标号其中：

（2）如果边,且,那么给vj标号其中：

3．重复步骤2，直到vt被标号或标号过程无法进行下去，则标号结束。若vt被标号，则存在一条增广链，转调整过程；若vt未被标号，而标号过程无法进行下去，这时的可行流就是最大流。;二、调整过程

设

1．令

2．去掉所有标号，回到第一步