《图与网络分析graphtheoryandnetworkanaly》由会员分享，可在线阅读，更多相关《图与网络分析graphtheoryandnetworkanaly（75页珍藏版）》请在金锄头文库上搜索。
1、图与网络分析 (Graph Theory and Network Analysis),图与网络的基本知识,最短路问题,树及最小树问题,最大流问题,最小费用最大流问题,哥尼斯堡七空桥,一笔画问题,一、 图与网络的基本知识 （一）、图与网络的基本概念,1、一个图是由点和连线组成。（连线可带箭头，也可不带，前者叫弧，后者叫边）,一个图是由点集 和 中元素的无序对的一个集合 构成的二元组，记为G =(V，E)，其中 V 中的元素 叫做顶点，V 表示图 G 的点集合；E 中的元素 叫做边，E 表示图 G 的边集合。,例,图1,2、如果一个图是由点和边所构成的，则称其为无向图，记作G = (V，E)，连接
2、点的边记作vi , vj，或者vj , vi。,3、如果一个图是由点和弧所构成的，那么称它为有向图，记作D=(V, A)，其中V 表示有向图D 的点集合，A 表示有向图D 的弧集合。一条方向从vi指向vj 的弧，记作(vi , vj)。,图2,4、一条边的两个端点是相同的,那么称为这条边是环。 5、如果两个端点之间有两条以上的边，那么称为它们为多重边。,6、一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。,7、每一对顶点间都有边相连的无向简单图称为完全图。 有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。,度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的关联
3、边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。,8、以点v为端点的边的个数称为点v 的度（次），记作 。,图中 d(v1)= 4，d(v6)= 4（环计两度）,9、设 G1=（ V1 , E1 ），G2 =（ V2 ,E2 ）如果 V2 V1 , E2 E1 称 G2 是G1 的子图；如果 V2 = V1 , E2 E1 称 G2 是 G1 的部分图或支撑子图。,在实际应用中，给定一个图G=（V，E）或有向图D=（V，A），在V中指定两个点，一个称为始点（或发点），记作v1 ，一个称为终点（或收点），记作vn ，其余的点称为中间点。对每一条弧 ，对应一个数 ，称为弧上的“权”。通常
4、把这种赋权的图称为网络。,10、由两两相邻的点及其相关联的边构成的点边序列称为链。 如:v0 ，e1，v1，e2，v2，e3 ， v3 ,vn-1 , en ， vn，记作（ v0 ， v1 ， v2， v3 , , vn-1 ， vn ），,11、图中任意两点之间均至少有一条通路，则称此图为连通图，否则称为不连通图。,其链长为 n ，其中 v0 ，vn 分别称为链的起点和终点 。若链中所含的边均不相同，则称此链为简单链；所含的点均不相同的链称为初等链 , 也称通路。,（二）、 图的矩阵表示 对于网络（赋权图）G=（V，E），其中边 有权 ，构造矩阵 ，其中： 称矩阵A为网络G的权矩阵。,设图
5、G=（V，E）中顶点的个数为n，构造一个 矩阵 ，其中： 称矩阵A为网络G的邻接矩阵。,例,权矩阵为：,邻接矩阵为：,二、 树及最小树问题 已知有六个城市，它们之间 要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。,1、一个连通的无圈的无向图叫做树。 树中次为1的点称为树叶，次大于1的点称为分支点。,树 的性质： （1）树必连通，但无回路（圈）。 （2）n 个顶点的树必有n-1 条边。 （3）树 中任意两个顶点之间，恰有且仅有一条链（初等链）。 （4）树 连通，但去掉任一条边， 必变为不连通。 （5） 树 无回路（圈），但不相邻的两个点之间加一条边，恰得到一个回路（圈）。
6、,2、 设图 是图G=(V , E )的一支撑子图， 如果图 是一个树,那么称K 是G 的一个生成树（支撑树），或简称为图G 的树。图G中属于生成树的边称为树枝，不在生成树中的边称为弦。,一个图G 有生成树的充要条件是G 是连通图。,用破圈法求出下图的一个生成树。,（一）破圈法,（二）避圈法,在图中任取一条边e1，找一条与e1不构成圈的边e2，再找一条与e1，e2不构成圈的边e3。一般设已有e1，e2，ek，找一条与e1，e2，ek中任何一些边不构成圈的边ek+1，重复这个过程，直到不能进行为止。,某六个城市之间的道路网如图 所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度
7、最短。,v1,v2,v3,v4,v5,1,4,2,3,1,3,5,2,最短路的一般提法为：设 为连通图，图中各边 有权 （ 表示 之间没有边）， 为图中任意两点，求一条路 ，使它为从 到 的所有路中总权最短。即： 最小。,(一)、 狄克斯屈拉(Dijkstra)算法 适用于wij0，给出了从vs到任意一个点vj的最短路。,三 、最短路问题,算法步骤： 1.给始点vs以P标号 ，这表示从vs到 vs的最短距离为0，其余节点均给T标号， 。 2.设节点 vi 为刚得到P标号的点，考虑点vj，其中 ，且vj为T标号。对vj的T标号进行如下修改： 3.比较所有具有T标号的节点，把最小者改为P标号，即：
8、 当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用vk代替vi，返回步骤（2）。,例一、 用Dijkstra算法求下图从v1到v6的最短路。,解 （1）首先给v1以P标号，给其余所有点T标号。,（2）,（3）,（4）,（5）,（6）,（7）,（8）,（9）,（10）,反向追踪得v1到v6的最短路为：,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,求从1到8的最短路径,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1, w1=0,min c12,c14,c16=min
9、 0+2,0+1,0+3=min 2,1,3=1 X=1,4, p4=1,p4=1,p1=0,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,4,min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2 X=1,2,4, p2=2,p1=0,p4=1,p2=2,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,min c13,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3 X=1,2,
10、4,6, p6=3,p2=2,p4=1,p1=0,p6=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3 X=1,2,4,6,7, p7=3,p2=2,p4=1,p1=0,p6=3,p7=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6 X=
11、1,2,4,5,6,7, p5=6,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8 X=1,2,3,4,5,6,7, p3=8,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,min c38,c58,c78=mi
12、n 8+6,6+4,3+7=min 14,10,11=10 X=1,2,3,4,5,6,7,8, p8=10,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,8,1到8的最短路径为1，4，7，5，8，长度为10。,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,求从V1 到 V8 的最短路线。,由此看到，此方法不仅求出了从V1 到 V8 的最短路长，同时也求出了从V1 到 任意一点 的最短路长。将从V1 到
13、 任一点的最短路权标在图上，即可求出从V1 到 任一点的最短路线。本例中V1 到 V8 的最短路线是： v1 v2 v5 v6 v8,（二）、 逐次逼近法 算法的基本思路与步骤： 首先设任一点vi到任一点vj都有一条弧。 显然，从v1到vj的最短路是从v1出发，沿着这条路到某个点vi再沿弧(vi,vj)到vj。则v1到vi的这条路必然也是v1到vi的所有路中的最短路。设P1j表示从v1到vj的最短路长，P1i表示从v1到vi的最短路长，则有下列方程： 开始时，令 即用v1到vj的直接距离做初始解。 从第二步起，使用递推公式： 求 ，当进行到第t步，若出现 则停止计算， 即为v1到各点的最短路长
14、。,例二、,求图中v1到 各点的最短路,（0，0）,（ v3 ，-5）,（ v1 ，-2）,（ v3 ，-7）,（ v2 ，-3）,（ v4 ，-5）,（ v3 ，-1）,（ v6 ，6）,例三、求：5年内，哪些年初购置新设备，使5年内的总费用最小。 解：（1）分析：可行的购置方案（更新计划）是很多的， 如： 1） 每年购置一台新的，则对应的费用为： 11+11+12+12+13 +5+5+5+5+5 = 84 2 )第一年购置新的，一直用到第五年年底，则总费用为： 11+5+6+8+11+18 = 59 显然不同的方案对应不同的费用。,（2）方法：将此问题用一个赋权有向图来描述，然后求这个赋
15、权有向图的最短路。 求解步骤： 1）画赋权有向图： 设 Vi 表示第i年初，(Vi ,Vj )表示第i 年初购买新设备用到第j年初（j-1年底），而Wi j 表示相应费用，则5年的一个更新计划相当于从V1 到V6的一条路。 2）求解 （标号法）,W12 =11+5=16 W13 =11+5+6=22 W14 =11+5+6+8=30 W15 =11+5+6+8+11=41 W16 =11+5+6+8+11+18=59,W23 =11+5=16 W24 =11+5+6=22 W25 =11+5+6+8=30 W26 =11+5+6+8+11=41,W45 =12+5=17 W46 =12+5+6=23 W56 =13+5=18,W34 =12+5=17 W35 =12+5+6=23 W36 =12+5+6+8=31,例四、 某工厂使用一种设备，这种设备在一定的年限内随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否更新。若购置设备，每年需支付购置费用；若继续使用旧设备，需要支付维修与运行费用，而且随着设备的老化会逐年增加。计划期（五年）内中每年的购置费、维修费与运行费如表所示，工厂要制定今后五年设
