第九章图论方法建模

第九章图论的数学模型在现实生活、生产中，经常遇到研究事物之间关系的问题.我们可以用图把各种关系形象而直观地描绘出来.图中的点表示要研究的离散对象，用边表示对象间的关系，并利用图的性质和算法求解模型.这是研究离散问题的重要手段.本章将介绍数学上图论的基本概念与最小树、最短路、中国邮递员问题、网络最大流问题及相关的模型应用.9.1图论的基本概念在实际生活当中，我们常利用点与线的示意图反映对象间的关系.例1图9.1是我国北京、上海等十个城市间的铁路交通图，反映了这十个城市间的铁路分布情况.这里用点代表城市，用点和点之间的连线代表着两个城市之间的铁路线.例2有甲、乙、丙、丁、戊五个球队，它们之间比赛的情况，也可以用图表示出来.已知甲队和其它各队都比赛过一次，乙队和甲、丙队比赛过，丙队和乙、丁队比赛过，丁队和丙、戊队比赛过，戊队和甲、丁队比赛过.为了反映这个情况，可以用点v1,v2,v3,v4,v5分别代表五个队，两队之间比赛过，就在这两个队相应点之间连一条线，这条线不过其它点，如图9.2所示.如果我们要进一步反映比赛中的胜负关系，可以用一条带箭头的连线表示，如甲队胜了乙队，可以从v1引一条带箭头的连线到v2.如图9.3反映了五个球队比赛的胜负情况，可见v1三胜一负，v4三场球全负等等.综上所述，图论中的图是由一些点及一些点间的连线组成的.它不同于通常意义的几何图形，它用点表示事物，用点间有无连线表示事物之间的某种关系，以一种抽象的形式来表达确定的事物.由上例知，点间的连线有的不带箭头，有的带箭头.为了区别起见，前者称为边，后者称为弧.如一个图G是由点及边所构成的，则称之为无向图（也简称图），记为G=(V,E).式中V，E分别是G的点集合和边集合.一条连接点vi,vj∈V的边记为[vi,vj](或[vj,vi]).如图9.4是一个无向图.V={v1,v2,v3,v4}，E={e1,e2,e3,e4,e5,e6,e7},其中e1=[v1,v2](或[v2,v1]).e2=[v1,v2]e3=[v2,v3]e4=[v3,v4]e5=[v1,v4]e6=[v1,v3]e7=[v4,v4].如果一个图D式由点及弧所构成的，则称为有向图，记为D=(V,A).式中V,A分别表示D的点集合和弧集合.一条方向从vi指向vj的弧记为（vi,vj）.如图9.5是一个有向图.V={v1,v2,v3,v4,v5}.A={a1,a2,a3,a4,a5,a6}.其中，a1=(v1,v2),a2=(v2,v1),a3=(v1,v3),a4=(v4,v2),a5=(v3,v4),a6=(v4,v5).下面再介绍一些常见名词和记号.考虑无向图G=(V,E).若边e=[u,v]∈E,则称u,v是e的端点，也称u,v是相邻的.称e是点u（及点v）的关联边.若图G中，某个边的两个端点相同，则称e是环（如图9.7中的e7）.若两个点之间有多于一条的边，称这些边为多重边（如图9.4中的e1,e2）.一个无环、无多重边的图称为简单图.一个无环，但允许有多重边的图称为多重图.以点v为端点的边的个数称为v的次，记为d(v).如图9.4中d(v1)=4,d(v2)=3,d(v4)=4(环e7在计算d(v4)作两次算).次为奇数的点，称为奇点，否则称为偶点.给定一个图G=(V,E).一个点、边交错序列（1iv,1ie,2iv,2ie,…,1kiv,1kiekiv）,如果满足tie=[tiv，1tiv]（t=1,2,3,…k-1）.则称之为一条联结链1iv，kiv的链，记为（1iv,2iv,,…,1kiv,kiv）.链（1iv,2iv,,…,1kiv,kiv）中，若1iv=kiv，则称之为一个圈，记为（1iv,2iv,…1kiv,1iv）.若链中（1iv,2iv,,…kiv）中，1iv,2iv,,…kiv都是不同的，则称之为初等链；若圈中（1iv,2iv,…,1kiv,1iv）中1iv,2iv,…,1kiv都是不同的，则称之为初等圈；若链（圈）中含的边均不相同，则称之为简单链（圈）.以后说到链（圈），除非特别交代，均指初等链（圈）.例如图9.6中，（v1,v2,v3,v4,v5,v3,v6）是简单链，但不是初等链.（v1,v2,v3,v4,v5）是一条初等链.（v1,v2,v3,v4,v1）是初等圈.（v4,v1,v2,v3,v5,v7,v6,v3,v4）是简单圈，但不是初等圈.图中不存在v1到v9的链.图G中，若任何两点之间，至少有一条链，则称G是连通图.否则称不连通的图.给定一个图G=(V,E).若)E,V(G使V=V及EE，称G是G的支撑子图.如图9.7中，（b）是（a）的支撑子图，而（c）不是.设给有向图D=(V,A).从D中去掉弧上的箭头，所得到的无向图称D的基础图.D中一条弧a=(u,v),u称a的始点，v称a的终点.称弧是从u指向v的.设（1iv,1ia,2iv,2ia,…1kiv,1kia,kiv）是D中的点、弧交错序列，在基础图中对应一条链，称为D的链.类似的定义D中圈.如（1iv,1ia,2iv,2ia,…1kiv,1kia,kiv）是D中一条链，且tia=（tiv，1tiv）称从1iv到kiv的一条路.若路中的第一个点和最后一个点相同，称回路.如图9.8（v1,v3,v4,v5）是从v1到的v5路，（v1,v2,v4,v5）是链，不是路.（v1,v3,v4,v2,v1）是回路.注：对无向图、链与路（圈与回路）这两个概念是一致的.9.2最小支撑树与最短路9.2.1最小支撑树（最小生成树）及其算法.例1已知有五个城镇，要再它们之间架电话线，要求任何两个城镇都可以互相通话.（允许通过其它城镇），并且电话线的根数最少.用五个点v1,v2,v3,v4,v5代表五个城镇.如果在某两个城镇之间架设电话线，则在相应两个点之间连一条边，这样一个电话线网就可以用一个图来表示.为了使任何两个城镇都可以通话，这样的图必须是连通的.其次，若图中有圈，从圈上任去一边，余下图任连通，省去一根电话线.因而，满足条件的电话线网对应的图必是连通、不含圈的图.如图9.9定义1.一个无圈的连通图称树.定义2.设图T=(V,E)是G=(V,E)的支撑子图，如果图T=(V,E)是一个树，则称T是G的支撑树.定义3.图G=(V,E)，G中每一条边[vi,vj]，相应地有一个数wij，则称这样的图G为赋权图.wij称为边[vi,vj]的权.这里所说的“权”，是指与边有关的数量指标.根据实际问题的需要，可以赋予它不同的含义，例如表示距离、时间、费用等.赋权图不仅指出各点间的邻接关系，同时也表示出各点间的数量关系.定义4.设有连通图G=(V,E)，对每一e=[vi,vj]有一非负权，w(e)=wij.如果T=(V,E)是G的支撑树，称E中所有边权数之和为支撑树T的权，记为w(T).即w(T)=Tvj][vi,wij.如果支撑树T*的权w(T*)是所有支撑树的权中最小者，则称T*是G的最小支撑树（简称最小树）.既w(T*)=Tminw(T).最小支撑树有其广泛的应用，如例1，支撑树有多种，如给出各城镇间的道路长度，我们则应选用造价最低的电话线网.这个问题就是赋权图上的最小树问题.下边就是介绍求最小树的算法.方法一、（避圈法）该算法是1956年由Kruskal（克鲁斯凯尔）提出.步骤如下：设G为由m个节点构成的连通赋权图.(1)先把G中所有边按权数大小由小到大重新排列，并取权数最小的一条边取为T中的边.(2)从剩下的边中按（1）中排列取下一条边.若该边与前已取进T中的边形成某个回路，则舍去该边；否则把该边取进T中.重复步骤（2），直至有m-1条边取进T中为止，则这m-1条边就组成G的最小支撑树.例2（如图9.10）8个城市v0,v1,…,v7之间有一个公路网，公路为图中的边，边上的权数表示公路的长度，现要沿公路架设电话线，要求如何架设，使电话线总长最小.解：这个问题就是求图9.10上的最小树.先按各边权数由小到大排列.为e1=[v0,v1],e2=[v2,v3],e3=[v1,v2],e4=[v0,v2]，e5=[v5,v6],e6=[v3,v4]，e7=[v1,v3]，e8=[v4,v5]，e9=[v4,v7]，e10=[v0,v5]，…顶点数m=8.由Kruskal法的步骤，顺次试将e1,e2,e3,e4,e5,e6,e7,e8,e9取进T中（舍去e4和e7），于是最小支撑树T={e1,e2,e3,e5,e6,e8,e9}.如图9.11.方法二、（破圈法）任取一圈，从圈中去掉一条权最大的边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条）.在余下的图中，重复这个步骤，一直得到一个不含圈的图为止，这时的图便是最小树.用破圈法解上题，任取一圈，比如（v1,v0,v6,v1），边[v6,v0]最大，于是去掉；取圈（v1,v0,v2,v1），边[v0,v2]与[v1,v2]都为2，任去一边[v0,v2].如此下去，得到一个不含圈的图.即为最小树.9.2.2最短路问题及Dijkstra(迪杰斯特拉)算法.一个典型的最短路问题如下：例3.8个城市之间v0,v1,…,v7之间有一个公路网（如图9.12）.每条公路为图中的边，边上的权数表示通过该公路所需的时间.你在城市v0,从v0到v7应该选择什么路径，所需时间最少？即求d(v0,v7)(表示从v0到v7的最短路径的和)目前公认解决最短路的最佳算法是由Dijkstra提出的.这个算法不仅得到从v0到v7的最短路，还会得到由v0出发到其它各点的最短路.Dijkstra法的基本思想是从v0出发，逐步向外探寻最短路.执行过程中，与每个点对应，记寻下一个数（称为这个点的标号），它或者表示从v0到该点的最短路的权（称为P标号），或者是从v0到该点的最短路权的上界（称为T标号）.方法的每一步是去修改T标号，并且把T标号点改为具有P标号的点，从而使G中具P标号的顶点数多一个.这样，经过p－1步（p是图中点的个数），就可求出从v0到各点的最短路.在叙述Dijkstra算法之前，以例3为例说明一下这个方法的思想.例3中，v0出发，wij≥0.故有d(v0,v0)=0.这时v0是具有P标号的点.考察从v0出发的三条边，[v0,v1],[v0,v2],[v0,v3].从v0出发，沿[v0,v1]到达v1,需时间d(v0,v1)+w01=2；如从v0出发，沿[v0,v2]到达v2,需时间d(v0,v0)+w02=8；类似的，沿[v0,v3]到v3,需时间d(v0,v0)+w03=1.因min{d(v0,v0)+w01,d(v0,v2)+w02,d(v0,v0)+w03}=1.可断言，从v0出发到v3的最短路需时间1.即d(v0,v3)=1.最短路（v0,v3）.这时因为从v0到v3的任一条路，如不是（v0,v3），则必先从v0沿[v0,v1]到达v1，或沿[v0,v2]到达v2.但如此，此时已需时间2或8，不管再如何从v1或v2到达v3,所需时间不会比1少.因而推知d(v0,v3)=1.这样使v3具有P标号.现在考察从v0,v3指向余点的边.由上已知，从v0出发，沿[v0,v1]到达v1,需时间为2；如从v0出发，沿[v0,v2]到达v2,需时间为8；从v3出发，沿[v3,v2]到达v2,需时间d(v0,v3)+w32=8，从v3出发，沿[v3,v6]到达v6,需时间d(v0,v3)+w36=10.因min{d(v0,v0)+w01,d(v0,v2)+w02,d(v0,v3)+w32,d(v0,v3)+w36}=d(v0,v0)+w01=2,基于同样的理由，从v0到v1的最短路是：（v0,v1），即d(v0,v1)=2.又使v1变成具有P标号的点.如此重复，直到求出v0到v7的最短路.下面给出Dijkstra的一般步骤：用P，T表示某点的P标号、T标号，Si表示第i步时，具P标号的点集.1.（i=0）令S0={vs}对于v≠v