第11章图与网络模型

运筹学OperationsResearchChapter11网络模型NetworkModeling11.1基本概念11.2最小(支撑)树问题11.3最短路问题11.4最大流问题11.5最小费用最大流11.6中国邮路问题18.05.2020欧拉早年解决著名的哥尼斯堡七桥问题，哥尼斯堡城市中有一条河，河中有两个岛，河的两岸和河中的两个小岛有7座桥。当地居民提出：一个步行者能否通过每座桥一次且仅一次就能返回原出发地。DCA岸B岸18.05.2020欧拉将此问题归为一笔画问题，即能否从某点开始一笔画出这个图形，最后回到出发点，而不重复。CDAB欧拉证明了这是不可能的。18.05.2020在这一时期，还有许多游戏问题，诸如环球旅行、迷宫问题、博奕问题等难题，吸引了许多学者，这些问题看起来似乎是一些无足轻重的游戏，但常常是由于这些游戏引出了许多实用意义的新问题，开辟了新学科。图论在现实生活中很多，如各种通信网络的合理架设，交通网络的合理分布，邮递员送信，怎么走完他负责投递的全部街道，完成任务回到邮局，使走的路线最短，电子商务物流配送中的最佳运送路线的选择等，都属于图论问题。18.05.20205v1v2v3v4v5v6843752618图11－1运筹学中研究的图具有下列特征：（1）用点表示研究对象，用边（有方向或无方向）表示对象之间某种关系。（2）强调点与点之间的关联关系，不讲究图的比例大小与形状。（3）每条边上都赋有一个权，其图称为赋权图。实际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的含义。（4）建立一个网络模型，求最大值或最小值。18.05.202011.1图的基本概念18.05.2020例1：五个队比赛的图v1v3v4v1v3v4v2v1v1v518.05.2020图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，图论中的图与几何图、工程图是不一样的。18.05.2020从以上图可看出图：（1）图是由一些点和一些点之间的连线（带箭头或不带箭头）所组成的。（2）具有“对称性”和“不对称性”概念：边：两点之间的不带箭头的连线。弧：两点之间的带箭头的连线。无向图：由点和边组成。记为Ｇ＝（Ｖ，Ｅ）点的集合边的集合18.05.2020e3一条连结vi,vj∈V的边,记为［vi,vj]或[vj,vi]上图中：Ｖ＝{v1,v2,v3,v4}E＝{e1,e2,…..e7}e1=[v1,v2],e2=[v2,v1]………e7=[v4,v4]v4v1v2v3e6e5e4e2e1e7e318.05.2020v9a2有向图：由点和弧组成。记为D=(V,A)一条方向从vi→vj的弧,记为：（vi,vj)V={v1,…..,v7}A={a1,…….,a11}a1=(v1,v2)a2=(v1,v3)…….弧的集合v1a4a5a6a7a10a11v3v2v5v4v6v7a8a1a318.05.2020点数记为：p(G),p(D)边数记为：q(G)弧数记为：q(D)下面介绍一些名词，先考虑无向图：e=[u,v],称u、v是e的端点，也称u、v是相邻的。称e是u(v)的关联边。多重边：两点之间有多于一条的边。简单图：无环，无多重边的图。多重图：无环，但允许有多重边的图。18.05.2020次：以点v为端点的边的个数，记为d(v).悬挂点：次为1的点。悬挂边：悬挂点的关联边孤立点：次为0的点。定理1：在G=(V,E)中，所有点的次之和是边数的两倍。Vvqvd2)(18.05.2020奇点：次为奇数的点。偶点：次为偶数的点。定理2：任一个图中，奇点的个数为偶数。（因为奇点的边数为奇数，所以个数为偶数）qvdvdVvVv2d(v))()(Vv偶偶奇奇为偶数18.05.2020链：G=(V,E)，一个点、边交错序列（vi1,ei1,vi2,ei2,…..,v(ik-1),e(ik-1),vik)。如满足eit=[vit,v(it+1)],称为一条连结vi1,vi2,…..,v(ik-1),vik的链。记为（vi1,vi2,…..,v(ik-1),vik）圈：链（vi1,vi2,…..,v(ik-1),vik）中，若vi1=vik,称为圈。记为（vi1,vi2,…..,v(ik-1),vi1）。初等链：链中各点都不同。初等圈：圈中除头尾外，中间点都不同。18.05.2020e7e4简单链（圈）：链（圈）中含的边都不相同。（点可以相同）以后提到的链（圈），除非特别交代，都指初等链（圈）。v1e1e2e3e6e8e9v2v4v3v6v5v7e10v9v8e518.05.2020(v1,v2,v3,v4,v5,v3,v6,v7)是简单链。(v1,v2,v3,v6,v7)是初等链。连通图：G中，若任何两点之间，至少有一条链，否则，称为不连通图。连通分图：若Ｇ不连通，它的每个连通，部分称为连通分图。支撑子图：G=(V,E)，如果G’=(V’,E’),使V=V’及E’E,则G’为G的一个支撑子图.18.05.2020有向图中:路:如有（vi1,ai1,vi2,ai2,…..,v(ik-1),a(ik-1),vik)是D中一条链，且有ait=(vit,v(it+1)),称从vi1→vik的一条路。回路：若路中第一点和最后一点相同，则称为回路。支撑子图11.2最小(支撑)树问题Minimal(Spanning)TreeProblem18.05.202011.2.1树的概念一个无圈并且连通的无向图称为树图或简称树(Tree)。组织机构、家谱、学科分支、因特网络、通讯网络及高压线路网络等都能表达成一个树图。可以证明：（1）一棵树的边数等于点数减1；（2）在树中任意两个点之间添加一条边就形成圈；（3）在树中去掉任意一条边图就变为不连通。在一个连通图G中，取部分边连接G的所有点组成的树称为G的部分树或支撑树(SpanningTree)。图11－2是图11－1的部分树。v1v2v3v4v5v64321图11－2711.2最小树问题Minimaltreeproblem18.05.202011.2.2最小部分树将网络图G边上的权看作两点间的长度（距离、费用、时间），定义G的部分树T的长度等于T中每条边的长度之和，记为C(T)。G的所有部分树中长度最小的部分树称为最小部分树，或简称为最小树。最小部分树可以直接用作图的方法求解，常用的有破圈法和加边法。破圈法：任取一圈，去掉圈中最长边，直到无圈。11.2最小树问题Minimaltreeproblem18.05.20205v1v2v3v4v5v6843752618图11－1【例11.1】用破圈法求图11－1的最小树。图11－4图11－4就是图11－1的最小部分树，最小树长为C(T)=4+3+5+2+1=15。当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同11.2最小树问题Minimaltreeproblem18.05.2020加边法：取图G的n个孤立点｛v1，v2，…，vn}作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有n－1条边）v1v2v3v4v5v643521图11－5在图11－5中，如果添加边[v1,v2]就形成圈｛v1,v2,v4｝，这时就应避开添加边[v1,v2]，添加下一条最短边[v3,v6]。破圈法和加边法得到树的形状可能不一样，但最小树的长度相等5v1v3v515v2v4v684375268×MinC(T)=1511.2最小树问题Minimaltreeproblem18.05.2020下一节：最短路问题1.树、支撑树、最小支撑树的概念2.掌握求最小树的方法：（1）破圈法（2）加边法11.2最小树问题Minimaltreeproblem11.3最短路问题ShortestPathProblem18.05.2020最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也可以归结为求最短路问题求最短路有两种算法：一是求从某一点至其它各点之间最短离的狄克斯屈拉(Dijkstra)算法另一种是求网络图上任意两点之间最短路的Floyd(弗洛伊德)矩阵算法。最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路11.3.1最短路问题的网络模型11.3最短路问题ShortestPathProblem18.05.2020①②③④⑤⑥⑦610123214675811165图11－69【例11.2】图11－6中的权cij表示vi到vj的距离（费用、时间），从v1修一条公路或架设一条高压线到v7，如何选择一条路线使距离最短，建立该问题的网络数学模型。11.3最短路问题ShortestPathProblem18.05.202011.3.2有向图的狄克斯屈拉(Dijkstra)标号算法点标号：b(j)—起点vs到点vj的最短路长；边标号：k(i，j)=b(i)+cij，步骤：(1)令起点的标号；b(s)＝0。先求有向图的最短路，设网络图的起点是vs,终点是vt,以vi为起点vj为终点的弧记为（i，j）,距离为cij(2)找出所有vi已标号vj未标号的弧集合B={(i，j)}，如果这样的弧不存在或vt已标号则计算结束；(3)计算集合B中弧k(i，j)=b(i)+cij的标号(4)选一个点标号返回到第(2)步。)(,),(|),(min)(lbvBjijiklblj处标号在终点11.3最短路问题ShortestPathProblem18.05.2020②③④⑤⑥⑦610123214675811165图11－690610129209186①161217162432182929【例11.3】用Dijkstra算法求图11－6所示v1到v7的最短路及最短路长v1到v7的最短路为：p17=｛v1,v2,v3,v5,v7｝，最短路长为L17=2911.3最短路问题ShortestPathProblem14S={①}T={②③④⑤⑥⑦}min{0+c12,0+c13,0+c14}S={①②}①②↓↓T={③④⑤⑥⑦}min{0+c13,0+c14,6+c23,6+c25}S={①②③}①②③↓↓↓T={④⑤⑥⑦}min{0+c14,6+c25,9+c35,9+c36,9+c34}18.05.2020从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj。11.3.3无向图最短路的求法无向图最短路的求法只将上述步骤（2）改动一下即可。点标号：b(i)—起点vs到点vj的最短路长；边标号：k(i，j)=b(i)+cij，步骤：(1)令起点的标号；b(s)＝0。(3)计算集合B中边标号：k[i，j]=b(i)+cij)(,],[|],[min)(lbvBjijiklblj处标号在端点(4)选一个点标号:返回到第(2)步。(2)找出所有一端vi已标号另一端vj未标号的边集合B={[i，j]}如果这样的边不存在或vt已标号则计算结束；11.3最短路问题ShortestPathProblem18.05.2020【例11.4】求图11-10所示v1到各点的最短路及最短距离①②③④⑤⑥⑦⑧4526178393261216180452231039612641166188122482418所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。图11-1011.3最短路问题ShortestPathProblem18.05.2020下一节：最大流问题11.3最短路问题ShortestPathProblem1.最短路的概念及应用。2.有向图、无向图一点到各点最短路的Dijkstra算法11.4最大流问题MaximalFlowProblem18.05.202011.4