资源描述：
《图与网络分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第四章图与网络分析4.1基本概念4.2网络最小费用流问题4.3网络最大流问题4.4最短路径问题4.1基本概念图G=(V,E),其中：V=v1,v2,……,vnE=e1,e2,……,en子图G1=(V1,E1),其中：V1,V,E1E1.图与子图多重边：两点之间有多于一条边。环：首尾相接的边简单图：无环、无多重边的图。2.有向图与无向图有向图：有方向的图。无向图：无方向的图。e1V2V1e2V3v1ev23.关联与相邻关联（边与点的关系）：若e是v1、v2两点间的边，记e=[v1，v2]，称v1、v2与e关联。相邻（边与边、点与点的关系）：点v1与v2有公共边，称点v1与v2相邻
2、；边e1与e2有公共点，称边e1与e2相邻。圈（Circuit）封闭的链称为圈如：μ={(1,2),(2,4),(3,4),(1,3}链:由图G中的某些点与边相间构成的序列{V1,e1,V2,e2,……,Vk,ek},若满足ei=[Vi,Vi],则称此点边序列为G中的一条链。如：μ={(1,2),(3,2),(3,4)}4.链、圈与连通图42314231连通图任意两个节点之间至少有一条链的图称为连通图42315.网络给图中的点和边赋以具体的含义和权数（如距离、费用、容量等），则称这样的图为网络图。4231507020454.2最小支撑树问题树：无圈的连通图，记为T。树的性质24
3、3512435124351如果树T有m个结点，则边的个数为m-1。树中任意两个节点间有且只有一条链。在树中任意去掉一条边，则不连通。图的支撑树若图G=(V,E)的子图T=(V,E’)是树，则称T为G的支撑树。42314231423142314231423142314.2.1求解最小支撑树问题的破圈法方法：去边破圈的过程。步骤：1）在给定的赋权的连通图上任找一个圈。2）在所找的圈中去掉一条权数最大的边。3）若所余下的图已不含圈，则计算结束，余下的图即为最小支撑树，否则返回1）。423142314231生成树2生成树3生成树1////例：用破圈法求右图的最小支撑树。42317458
4、1总权数=3+4+1=84.2.2求解最小支撑树的避圈法方法：选边的过程。步骤：1）从网络中任意选一点vi，找出与vi相关联的权最小的边[vi,vj]，得第二个顶点vj。2）把顶点集V分为互补得两部分A,Ā，其中：A：与已选边相关联得点集Ā：不与已选边相关联得点集3)考虑所有这样的边[vi,vj]，其中vi∈A,vj∈Ā,挑选其中权最小的。4）重复3），直至全部顶点均属于A即可。V4V2V3V174581例：用避圈法求由图的最小支撑树。①任选点v1，挑与之相关联的权最小的边（v1,v2）.②A={v1,v2},Ā={v3,v4}从边（v1,v3）,（v4,v1）,（v2,v3）
5、,（v2,v7）中选权最小的边（v4,v1）。V4V2V3V174581③A={v1,v2,v4},Ā={v3}从边（v1,v3）,（v2,v3）,（v3,v8）中选权最小的边（v2,v3）。④A={v1,v2,v3，v4}网络的生成树和线性规划的关系网络的一个生成树对应于线性规划的一个基生成树上的边对应于线性规划的基变量生成树的弦对应于线性规划的非基变量生成树的变换对应于线性规划单纯形法的进基和离基变换4.3最短路问题问题：求网络中一定点到其它点的最短路。4.3.1最短路问题的Dijstra解法方法：给vi点标号[wi,vk]其中：wi：vi点到起点vs的最短距离vk:vi的
6、前接点方法：(1)给起点vs标号[0，vs]。（2）把顶点集v分为互补的两部分A和Ā其中：A：已标号点集Ā：未标号点集（3）考虑所有这样的边[vi,vj],其中vi∈A,vj∈Ā挑选其中与vs距离最短的点vj标号[min{wi+cij},vi](4)重复（3），直至终点vt标上号[wt,vk]，则wt即为vs至vt的最短距。反向追踪可求得最短路。例：求v1至v8的最短路。v2v3v7v1v8v4v5v66134105275934682v2v3v7v1v8v4v5v66134105275934682(1)v1:[0,v1]计算min{0+2,0+1,0+3}=min{2,1,3}
7、=1v4:[1.v1][1,v1][0,v1](2)A={v1}检查边（v1,v2),(v1,v4),(v1,v3)v2v3v7v1v8v4v5v66134105275934682(3)A={v1,v4}计算min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2v2:[2,v1][0,v1][1,v1][2,v1]考虑边（v1,v2),(v1,v6),(v4,v2),(v4,v7)v2v3v7v1v8v4v5v66134105275934682（4）A={v1,v2,v4
