运筹学课件第六章 图与网络分析

《运筹学课件第六章 图与网络分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Ch6图与网络分析(GraphandNetworkAnalysis)主要内容：基本概念最小支撑树问题最短链问题中国邮递员问题最大流问题网络图的绘制时间参数的计算网络计划的调整和优化重点：最小支撑树问题最短链问题中国邮递员问题最大流问题难点：最大流问题时间参数的计算§1.图论导引（IntroductionofGraph）图论的开创者L.Euler(1707-1783，瑞士)1.图òv1例1：现有五个城镇v1，v2，v3，v4，v5，其中v1与v3，v4有公路相联，v2与v4，v2òòv5v5有公路相联，v3与v5有公路相联，试用图形表示上述关系。%注：1.图上点表示城镇，线

2、表示镇与镇之间有公路相连。v3òòv42.图上点只表示点、线的关系,点、线的位置可以变动。图(graph)：由点和连接点的线组成的图形。点集记为V，线集记为E，图记为G=[V，E]。点(vertex)：图G上的点v，点集为V阶(order)：点集V包含元素的个数边(edge)：图G上的线e，边集为E端点(end)：边e的一个点相邻(adjacent)：一条边e的两个端点v1、v2称为相邻,记边e=v1v2关联(incident)：称e是v1(或v2)的关联边邻域(neighbour)：与v相邻的所有点的集合，记为NG(v)二重边v1òòv2环(loop)：两个端点重合的边

3、多重边(multiple)：与v1和v2相关联有两个孤立点及两个以上的边òv5孤立点(isolated)：不与任一条边关联的点环v3òòv4权(weight)：每个边上赋予值ω(e)赋权图(weightgraph)：具有权的图，记为G=[V，E，W]。简单图(simplegraph)：无多重边无环的图有限图(finitegraph)：点集，边集为有限集的图%注：以下所讨论的图为有限图链(walk)：点边交错序列p={v1,e1,v2,e2,…,vn,en,vn+1}组成的，其中边ei=vivi+1(i=1,2,…,n)，此链p也可记为p=v1v2…vnvn+1或p=e1e

4、2…enòò简单链：链中的边都互不相同òò初等链：链子中的点都不相同ò圈(cycle)：链的起点和终点相同òò简单圈：无相同边的圈初等圈：无相同点的圈%注：初等链⇒简单链，初等圈⇒简单圈2.图与矩阵e1v1òe2òv2e3e4e5v3òòv4e6相邻矩阵(adjacentmatrix)：相关矩阵(incidentmatrix)：vvvv1234v0200eeeeee1234561A=v2010v11110002v0111M=v21111003v1010v30001124v4001010权矩阵（weightmatrix）对于简单赋权图，定义vvvv1234⎧wvv(,),i

5、j若vvij∈Ev1033∞⎪w0=⎨，若i=j，W==()wv3051ijij244×⎪∞∉,,若且vvEi≠jv3503⎩ij3v∞1304v1v2ò3ò351ò3òv3v43.图与树òòòò/子图(subgraph)：图G=[V，E]，V⊆V，////E⊆E，G=[V，E]称为G的子图支掌子图(spanningsubgraph)：子图////G=[V，E]中，V=Vòòòò%注：支掌子图不唯一连通图(connectedgraph)：图中任意两点之间有一条链相连òòòòòòòòòòòò树(tree)：无圈的连通图/支掌树(spanningtree)：图G的支掌子图G是

6、一棵树òòò定理1：图G是一棵树⇔G连通,

7、V

8、−

9、E

10、=1òòò定理2：任何连通图存在支掌树ò根4.有向图òv1例2．设在v1,v2,v3,v4,v5五城之间铺设水管，其中v1向v3，v4送水，v2òòv5v2向v4，v5送水，v3向v5送水，试用图形表示上述关系。v3òòv4%注：1.为表示送水的方向，在右图中的线上标上箭头2.与例1相比，每条线上增加一个方向有向图(digraph)：对于图G=[V,E]中的每条边，òò规定一个方向，用D=(V,E)表示此图弧(arc)：D中的边称为弧路(path)：与箭头方向一致的链回路(circuit)：与箭头方向一致的圈òò