第八章第八章 图与网络分析图与网络分析 主要内容：主要内容： 8.1 图的基本概念与基本定理 8.2 树和最小支撑树 8.3 最短路问题 8.4最小费用流问题 8.5最大流问题 8.6网络计划 8.7中国邮递员问题 8.7指派问题8.1 8.1 图的基本概念与基本定理图的基本概念与基本定理图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论， 工程技术，交通运输，经济管理，电子计算 机等各项领域。对于科学研究，市场和社会 生活中的许多问题，可以同图论的理论和方 法来加以解决。例如，各种通信线路的架设 ，输油管道的铺设，铁路或者公路交通网络 的合理布局等问题，都可以应用图论的方法 ，简便、快捷地加以解决。随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。关于图的第一篇论文是瑞士数学家欧拉 （E. Euler）在1736年发表的解决“哥尼斯堡” 七桥难题的论文；德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，（见图8.1 a）当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都 没有成功。为了寻找答案，1736年欧拉将这个问题抽象成图8.1b所示图形的一笔画问题。哥尼斯堡七桥问题哥尼斯堡七桥问题图 8.1 aABCD哥尼斯堡七桥问题可简化为以下图形哥尼斯堡七桥问题可简化为以下图形 其中的四个顶点都是奇顶点其中的四个顶点都是奇顶点ABCDCADB图8.1 b即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。例例8.18.1 图8.2是我国北京、上海、重庆等 十四个城市之间的铁路交通图，这里用点 表示城市，用点与点之间的线表示城市之 间的铁路线。诸如此类还有城市中的市政 管道图，民用航空线图等等。石家庄太原北京 天津 塘沽济南 青岛徐州 连云港南京上海郑州武汉重庆图8.2例例8.28.2 有六支球队进行足球比赛，我们分别用点v1 ，v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2 队，v2 队战胜v3 队，v3 队战胜v5队，如此等等。这个胜负情况，可以用图8.3所示的有向图反映出来图8.3v3v5v2v4v6v1从以上的几个例子可以看出，我们用 点和点之间的线所构成的图，反映实际生 产和生活中的某些特定对象之间的特定关 系。一般来说，通常用点表示研究对象， 用点与点之间的线表示研究对象之间的特 定关系。由于在一般情况下，图中的相对 位置如何，点与点之间线的长短曲直，对 于反映研究对象之间的关系，显的并不重 要，因此，图论中的图与几何图，工程图 等本质上是不同的。综上所述，图论中的图是由点和点与点之间的 线所组成的。通常，我们把点与点之间不带箭头的 线叫做边，带箭头的线叫做弧。如果一个图是由点和边所构成的，那么，称为 无向图，记作G=(V，E)，其中V表示图G 的点集合 ，E表示图G的边集合。连接点vi , vjV 的边记作vi , vj，或者vj , vi。如果一个图是由点和弧所构成的，那么称为它 为有向图，记作D=(V, A)，其中V表示有向图D的点 集合，A表示有向图D的弧集合。一条方向从vi 指向vj 的弧，记作(vi , vj)。例如例如. .图8.4是一个无向图G=（V，E），其中V=v1 , v2 , v3 , v4 E=v1 , v2,v2 ,v1,v2 ,v3,v3 ,v4,v1 ,v4,v2 ,v4, v3 ,v3v3v2v1v4图8.4图图8.58.5 是一个有向图D=（V，A）其中V=v1 ,v2 ,v3 ,v4 ,v5 ,v6 ,v7 A=(v1,v2),(v1,v3),(v3 ,v2)(v3 ,v4),(v2 ,v4),(v4 ,v5),(v4 ,v6),(v5 ,v3),(v5 ,v4), (v5 ,v6),(v6 ,v7)图8.5v7v5v3v4v2v6v1下面介绍一些常用的名词：下面介绍一些常用的名词：一个图G或有向图D中的点数,记作P(G)或 P(D),简记作P,边数或者弧数,记作q(G)或者q(D), 简记作q 。如果边vi ,vjE ,那么称vi , vj 是边的端点， 或者vi ,vj是相邻的。如果一个图G中，一条边的两个端点是相同的,那么称为这条边是环，如图8.4 中的边v3 ,v3是环。如果两个端点之间有两条以上的边，那么称为它们为多重边，如图8.4中的边 v1 ,v2 ,v2 ,v1。一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。以点v为端点的边的个数称为点v的度，记作d(v),如图84中d(v1)=3， d(v2 )=4,d(v3 )=4,d(v4 )=3。度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。端点的度 d(v)：点 v 作为端点的边的个数奇点：d(v)=奇数；偶点：d(v) = 偶数；悬挂点：d(v)=1；悬挂边：与悬挂点连接的边；孤立点：d(v)=0；空图：E = ，无边图v1v2v3v4v5 v6v1v7v6v5v4v3v2V=v1 , v2 , v3 , v4 , v5 ,v6 , v7 d(v1)=3 ; d(v2)=5 ;d(v3)=4 ; d(v4)=4 ;d(v5)=1 ; d(v6)=3;d(v7)=0其中 v5 为悬挂点， v7 为孤立点。定理8.1 所有顶点度数之和等于所有边数的2倍。证明：因为在计算各个点的度时，每条边 被它的两个端点个用了一次。v1v5v4v3v2简单图（2）（4）（3）（3）（2）v1v5v4v3v2多重图（4） （6）（3）（3）（2）定理定理8.28.2 在任一图中，奇点的个数必为偶数。证明：证明：设 V1，V2 分别是图G中奇点和偶点的集合，由定理8.1 ，有因为 是偶数， 也是偶数，因此也必是偶数，从而V1 中的点数是偶数 。图的连通性：图的连通性：链：由两两相邻的点及其相关联的边构成的点边序列。 如:v0 ,e1 ,v1 ,e2 ,v2，e3 ,v3 ,vn-1 , en ， vn ; v0 ，vn分别为链的起点和终点 。记作（ v0 ,v1 , v2， ,v3 , , vn-1 , vn ）简单链：链中所含的边均不相同；初等链：链中所含的点均不相同, 也称通路； 圈：若 v0 vn 则称该链为开链，否则称为闭链或回路或圈；简单圈：如果在一个圈中所含的边均不相同初等圈：除起点和终点外链中所含的点 均不相同的圈；连通图：图中任意两点之间均至少有一条通路，否则称为不连通图。v1v2v4v3v5v6 v7v8v9初等链: (v1 , v2 , v3 , v6 , v7 , v5 )初等圈： (v1 , v2 , v3 , v5 , v4 , v1 )简单圈： (v4 , v1 , v2 , v3 , v5 , v7 , v6 ,v3 , v4 )简单链：(v1 , v2 , v3 , v4 ,v5 , v3 ) 以后除特别声明，均指初等链和初等圈。 v1v2v3v4v5连通图v1v5v4v3v2v6子图定义：如果 V2 V1 , E2 E1 称 G2 是G1 的子图； 真子图：如果 V2 V1 , E2 E1 称 G2 是G1 的真子图； 部分图：如果 V2 = V1 , E2 E1 称 G2 是G1 的部分图或支撑子图；导出子图：如果V2 V1, E2=vi,vjvi,vjV2,称 G2 是 G1 中由V2 导出的导出子图。设设 G G1 1= V= V1 1, E , E1 1,G ,G2 2= V= V2 2 ,E,E2 2 G1G2真子图G3子图 部分图G4导出子图G5 生成树G6 G5余树有向图：关联边有方向 弧：有向图的边 a=(u ,v),起点u ,终点v；路：若有从 u 到 v 不考虑方向的链,且 各方向一致,则称之为从u到v 的路；初等路: 各顶点都不相同的路；初等回路:u = v 的初等路; 连通图： 若不考虑方向 是无向连通图;强连通图：任两点有路;v1 v2v3v4v58.2 8.2 树和最小支撑树树和最小支撑树一、树及其性质在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。树。例8.3 已知有六个城市，它们之间 要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。如果用六个点v1v6代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。表示任意两个城市之间均可以通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。图8.8是一个不含圈的连通图，代表了一个电话线网。图8.8v6v3v4v2v5v1定义定义8.18.1 一个无圈的连通图叫做树树。下面介绍树的一些重要性质：下面介绍树的一些重要性质：定理定理8.38.3 设图G=（V，E）是一个树 P(G) 2，那么图G中至少有两个悬挂点。定理8.4 图G=（V，E）是一个树的充要条件是G 不含圈，并且有且仅有P-1条边。定理定理8.58.5 图G=（V，E）是一个树的充要条件是G是连通图，并且有且仅有 p1 条边。定理定理8.68.6 图G是一个树的充分必要条件是任意两个顶点之间有且仅有一条链。从以上定理，不难得出以下结论：（1）从一个树中任意去掉一条边，那么剩下的图不是连通图，亦即，在点集合相同的图中，树是含边数最少的连通图。（2）在树中不相邻的两个点之间加上一条边，那么恰好得到一个圈。二.支撑树定义定义8.28.2 设图K=( V , EI )是图G=(V , E )的一支撑子图，如果图K=(V,EI) 是一个树,那么称K 是G 的一个支撑树。例如,图8.10b 是图8.10a 的一个支撑树图8.10v6v5v2v3v4v1av6v5v2v3v4v1b显然,如果图K=(V,EI)是图G=(V,E)的一个支撑树,那么K 的边数是p(G)-1，G中不属于支撑树K 的边数是q(G)-p(G)+1。定理定理8.78.7 一个图G有支撑树的充要条件是G 是连通图。证明：充分性: 设图G是连通的，若G不含圈，则按照定义，G是一个树，从而G是自身的一个支撑树。若G含圈，则任取G的一个圈，从该圈中任意去掉一条边，得到图 G的一支撑子图G1。若G1不含圈，则G1是G的一个支撑树。若G1仍然含圈，则任取G1的一个圈，再从圈中任意去掉一条边，得到图 G的一支撑子图G2。依此类推，可以得到图G的一个支撑子图GK，且不含圈，从而GK是一个支撑树。定理8.7充分性的证明，提供了一个 寻找连通图支撑树的方法叫做“破圈法” 。就是从图中任取一个圈，去掉一条边。 再对剩下的图重复以上步骤，直到不含圈 时为止，这样就得到一个支撑树。例8.4 用破圈法求出图8-11的一个支 撑树。e4e6e5e3e2e1e7e8v3v2v1v4v5图8-11取一个圈(v1,v2,v3,v1)，在一个圈中去掉边e3 。在剩下的图中，再取一个圈（v1,