图论与网络规划ppt课件.ppt

《图论与网络规划ppt课件.ppt》由会员分享，可在线阅读，更多相关《图论与网络规划ppt课件.ppt（141页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十章第十章 图论与网络优化图论与网络优化1 图的基本概念图的基本概念2 最小树问题最小树问题3 最短路问题最短路问题4 网络最大流问题网络最大流问题5 最小费用最大流问题最小费用最大流问题一一 些些 问问 题题图论中著名问题图论中著名问题. 1736. 1736年，图论的创始人年，图论的创始人EulerEuler巧巧妙地将此问题化为图的不重复妙地将此问题化为图的不重复一笔画问题一笔画问题，并证明，并证明了该问题不存在肯定回答，发表了第一篇论文了该问题不存在肯定回答，发表了第一篇论文. .例：七例：七桥桥问题问题AB CD问题：一个散步者能否走过七座桥，且每座桥只走问题：一个散步者能否走过七座

2、桥，且每座桥只走 过一次，最后回到出发点。过一次，最后回到出发点。例：四色猜想例：四色猜想 能否用四种颜色给地图染色，使相邻的国家有能否用四种颜色给地图染色，使相邻的国家有不同的颜色。不同的颜色。点：国家；点：国家；边：两个国家有公共边界。边：两个国家有公共边界。问题：问题：能否用四种颜色给能否用四种颜色给平面图的点染色，使有公平面图的点染色，使有公共边的点有不同的颜色。共边的点有不同的颜色。公元公元1852年，格里斯发现无论多么复杂的地图，只要用四种年，格里斯发现无论多么复杂的地图，只要用四种颜色就能将相邻的区域区分开来，这就是所谓颜色就能将相邻的区域区分开来，这就是所谓“四色猜想四色猜想”

3、。直到公元直到公元1976年，才由美国数学家同时操作三台超大型汁算年，才由美国数学家同时操作三台超大型汁算机作了近机作了近200亿个逻辑判断，花费亿个逻辑判断，花费1200个机时，才取得了个机时，才取得了“四四色猜想色猜想”的证明。的证明。例：例：Hamilton图图 游戏：用正十二面体上游戏：用正十二面体上20个顶点表示个顶点表示20个城市，个城市，要求参加游戏者沿着各边行走，走遍每一个城市且要求参加游戏者沿着各边行走，走遍每一个城市且仅走一次，最后回到出发城市。仅走一次，最后回到出发城市。公元公元1859年，哈密尔顿年，哈密尔顿(Hamilton)在给朋友格拉在给朋友格拉伍斯（伍斯（Gra

4、res）的信中提）的信中提出了这个游戏。出了这个游戏。问题问题：如何判断一个图是：如何判断一个图是否具有这样的性质。如果否具有这样的性质。如果有，这样的行走路线如何有，这样的行走路线如何确定。确定。例：中国邮路问题例：中国邮路问题 一个邮递员送信，要走完他所负责的全部街道一个邮递员送信，要走完他所负责的全部街道分送信件，最后返回邮局。邮递员都会本能地以尽分送信件，最后返回邮局。邮递员都会本能地以尽可能少的行程完成送信任务。如何走路线最短。可能少的行程完成送信任务。如何走路线最短。点：路口；点：路口；边：两路口之间道路，第边：两路口之间道路，第i条道路长条道路长ei。1962年，由我国数学家管梅

5、谷提出，国际上称为年，由我国数学家管梅谷提出，国际上称为中中国邮递员问题国邮递员问题。问题问题：求一个圈，过每边至少一次，并使圈的长度：求一个圈，过每边至少一次，并使圈的长度最最 短。短。例：例：有甲、乙、丙、丁、戊五个球队，各队之间比赛有甲、乙、丙、丁、戊五个球队，各队之间比赛 情况如表：情况如表： 甲甲 乙乙 丙丙 丁丁 戊戊 甲甲 胜胜 负负 胜胜 胜胜 乙乙 负负 胜胜 丙丙 胜胜 负负 胜胜 丁丁 负负 负负 负负 戊戊 负负 胜胜 点：球队；点：球队；连线：两个球队之间比赛过，如甲胜乙，用连线：两个球队之间比赛过，如甲胜乙，用 v1 v2表示。表示。v1v2v3v4v5点点：研究对

6、象（陆地、路口、国家、球队）；：研究对象（陆地、路口、国家、球队）；点间连线：对象之间的特定关系（陆地间有桥、路点间连线：对象之间的特定关系（陆地间有桥、路 口之间道路、两国边界、两球队比赛及口之间道路、两国边界、两球队比赛及 结果结果)。对称关系：桥、道路、边界；对称关系：桥、道路、边界；用不带箭头的连线表示，称为用不带箭头的连线表示，称为边边。非对称关系：甲队胜乙队，用带箭头的连线表示，非对称关系：甲队胜乙队，用带箭头的连线表示， 称为称为弧弧。图图：点及边（或弧）组成。：点及边（或弧）组成。实际生活中，人们经常用实际生活中，人们经常用“图图”来表示一些对象以来表示一些对象以及这些对象之间

7、的特定关系。及这些对象之间的特定关系。如公路或铁路交通图、管网图、通讯联络图等。如公路或铁路交通图、管网图、通讯联络图等。对所要研究的问题确定具体对象及这些对象间的对所要研究的问题确定具体对象及这些对象间的性质关系，并用图的形式表示出来，这就是对所性质关系，并用图的形式表示出来，这就是对所研究原问题建立的模型。研究原问题建立的模型。图是反映对象之间关系图是反映对象之间关系的一种工具。的一种工具。这里所研究的图与平面几何中的图不同。这里只这里所研究的图与平面几何中的图不同。这里只关心图中有多少个点，点与点之间有无连线，至关心图中有多少个点，点与点之间有无连线，至于连线的方式是直线还是曲线，点与点

8、的相对位于连线的方式是直线还是曲线，点与点的相对位置如何，都是无关紧要的。置如何，都是无关紧要的。是组合意义下的图。是组合意义下的图。图的理论和方法图的理论和方法，就是从形形色色的具体的图以，就是从形形色色的具体的图以及与它们相关的实际问题中，抽象出共同性的东及与它们相关的实际问题中，抽象出共同性的东西，找出其规律、性质、方法，再应用到解决实西，找出其规律、性质、方法，再应用到解决实际问题中去。际问题中去。n图论图论(Graph Theory)是运筹学中的一个重要分支，是运筹学中的一个重要分支，主要研究具有某种主要研究具有某种二元关系二元关系的的离散系统离散系统的组合结构的组合结构和性质。和性

9、质。n随着电子计算机的蓬勃发展，图论不仅得到了迅随着电子计算机的蓬勃发展，图论不仅得到了迅速发展，而且应用非常广泛。它直观清晰，使用方速发展，而且应用非常广泛。它直观清晰，使用方便，易于掌握。便，易于掌握。n应用领域：物理学、化学、控制论、信息论、管应用领域：物理学、化学、控制论、信息论、管理科学、通信系统、交通运输系统、建筑、计算机理科学、通信系统、交通运输系统、建筑、计算机科学、生产工艺流程以及军事后勤保障系统等的问科学、生产工艺流程以及军事后勤保障系统等的问题常用图论模型来描述。题常用图论模型来描述。n网络规划是图论与线性规划的交叉学科网络规划是图论与线性规划的交叉学科,具有广泛具有广泛

10、的应用背景，比如，最短路问题、最小树问题、最的应用背景，比如，最短路问题、最小树问题、最大流问题、最优匹配问题等大流问题、最优匹配问题等.10.1 图的基本概念图的基本概念一个一个图图(Graph) 定义为三元有序组定义为三元有序组G=(V(G), E(G), G )，V(G)是图的是图的顶点集合顶点集合，E(G)是图的是图的边集合边集合， G称为称为顶点顶点与与边边之间的之间的关联函数关联函数。 V(G)中的元素中的元素 vi 称为称为顶点顶点,E(G)中的元素中的元素 ek 称为称为边边.一个图习惯一个图习惯记作记作 G=(V, E).当当V, E为有限集合时，为有限集合时，G称为称为有限

11、图有限图，否则，称为，否则，称为无限图无限图. 我们只讨论有限图我们只讨论有限图.一、基本概念一、基本概念.图图设设G是一个图，是一个图，G=(V(G),E(G)，( ), ,( ),eE G u vV G则称则称e 连接连接u和和v，称，称u和和v是是e的的端点端点.若若称端点称端点u，v与边与边e是是关联关联的，的，称两个顶点称两个顶点u，v是是邻接（相邻）邻接（相邻）的的.两条边两条边e, e1有公共端点有公共端点v，则称，则称e, e1相邻相邻.一个图可用一个几何图形表示一个图可用一个几何图形表示,称为图的称为图的几何几何实现实现，其中每个顶点用点表示，每条边用连接，其中每个顶点用点表

12、示，每条边用连接端点的线表示。图的几何实现有助与我们直观端点的线表示。图的几何实现有助与我们直观的了解图的许多性质的了解图的许多性质.( , )eu v uvewe1euv 或或设设G是一个图，是一个图， (,)GV E 123( ),V Gv v v 12345( ) ,E Ge e e e e 112ev v 212ev v 313ev v 423ev v 53 3ev v G的几何实现的几何实现其中：其中：1e2e3e4e5e1v2v3v例例说明说明一个图的几何实现并不是唯一的；表示顶点的点一个图的几何实现并不是唯一的；表示顶点的点和表示边的线的相对位置并不重要，重要的是图和表示边的线的

13、相对位置并不重要，重要的是图形描绘出形描绘出边与顶点之间保持的相互关系边与顶点之间保持的相互关系。我们常常把一个图的图形当作这个抽象图自身我们常常把一个图的图形当作这个抽象图自身. 并称图形的点为并称图形的点为顶点顶点,图形的线为图形的线为边边.图论中大多数概念是根据图的表示形式提出的，图论中大多数概念是根据图的表示形式提出的，例如：顶点、边、多重边、环、路、圈、树等。例如：顶点、边、多重边、环、路、圈、树等。在一个图的几何实现中，两条边的交点可能不是在一个图的几何实现中，两条边的交点可能不是图的顶点。例如图的顶点。例如4e1e2e3e5e6e1v2v3v4v4e1e2e3e5e6e1v2v3

14、v4v有时也用有时也用 m(G)=|E| 表示图表示图 G 中的中的边数边数，用用 n(G)=|V| 表示图表示图 G 中的中的顶点个数顶点个数，简记为，简记为m, n.图图 G 中的点数记为中的点数记为 p(G)，边数记为，边数记为q(G) .在不引起混淆的情况下，简记为在不引起混淆的情况下，简记为 p, q.此时，图此时，图 G 可以表示为可以表示为G = ( p, q ).平面图平面图一个图称为一个图称为平面图平面图，如它有一个平面图形，使得，如它有一个平面图形，使得边与边仅在顶点相交。下图就是一个平面图：边与边仅在顶点相交。下图就是一个平面图：4e1e2e3e5e6e1v2v3v4v非

15、平面图非平面图环、多重边环、多重边端点重合为一点的边称为端点重合为一点的边称为环环。连接同一对顶点的多条边称为连接同一对顶点的多条边称为多重边多重边。1e2e3e4e5e1v2v3v简单图简单图一个图称为一个图称为简单图简单图,如果它既没有环也没有多重边如果它既没有环也没有多重边.含有多重边的图称为含有多重边的图称为多重图多重图.我们只讨论有限简单图，我们只讨论有限简单图，即顶点集与边集都是有限的图。即顶点集与边集都是有限的图。只有一个顶点的图称为只有一个顶点的图称为平凡图平凡图；边集是空集的图称为边集是空集的图称为空图空图。2e3e4e5e7e1v2v3v4v完全图完全图K n完全图是每一对

16、不同顶点都恰有一边的简单图；完全图是每一对不同顶点都恰有一边的简单图；具有具有 n 个顶点的完全图记为个顶点的完全图记为K n.K52(1)|()|22nnnn nE KC 二分图（二分图（X, Y; E）二分图是一个简单图，其顶点集合可分划成两二分图是一个简单图，其顶点集合可分划成两个子集个子集X与与Y，使得每条边的一个端点在使得每条边的一个端点在X，另另一个端点在一个端点在Y; (X,Y)也称为图的也称为图的二分划二分划。戊戊甲甲乙乙丙丙丁丁工人工人工作工作DCBA完全二完全二分图分图K3,3完全二分图是具有二分划完全二分图是具有二分划(X,Y)的二分图，并且的二分图，并且X的每个顶点与的

17、每个顶点与Y的每个顶点都相连。完全二分图的每个顶点都相连。完全二分图记为记为Km,nX:Y:特殊图例特殊图例都是都是极小极小的的非平面图非平面图.K5K3,32.顶点的度（次）顶点的度（次）3)(2vd4)(1vd3)(3vd4)(4vd称度为称度为奇数的顶点为奇数的顶点为奇点奇点；称度为偶数的顶点为称度为偶数的顶点为偶点偶点.设设G是一个图，是一个图，G=(V(G), E(G), G)，定义图定义图G的的顶点顶点 v 的度的度为与顶点为与顶点v相关联的边数，记作相关联的边数，记作d(v).2e3e4e5e6e7e1v2v3v4v1e定理定理设设G是一个图，则是一个图，则( )( )2v V

18、Gd vq 推论推论：图中奇点的数目为偶数。：图中奇点的数目为偶数。度为度为1的点称为的点称为悬挂点悬挂点,连结悬挂点的边称为连结悬挂点的边称为悬挂边悬挂边.度为度为0的点称为的点称为孤立点孤立点。2e3e4e5e6e7e1v2v3v4v1e5v8e6v3.子图子图有两个图有两个图G和和H，如果如果)()(GVHV)()(GEHE称图称图H是图是图G的的子图子图，记为，记为GH GH GH 若若且且称称H是是G的的真子图真子图。GH )()(GVHV称称H是是G的的支撑子图支撑子图（或（或生成子图生成子图）.如果如果 ，e1e3e2Gv3v4v5v2v1H1: 真子图真子图v3v5v2v1H2

19、:支撑子图支撑子图e1e3e2v3v4v5v2v1顶点导出子图顶点导出子图设设W是图是图G的一个非空顶点子集的一个非空顶点子集,以以W为顶点集，以为顶点集，以二端点均在二端点均在W中的中的边的全体边的全体为边集的子图称为由为边集的子图称为由W导出的导出的G的子图，简称的子图，简称导出子图导出子图，记为，记为GW。导出子图导出子图GV- W记为记为G-W，即即 )(WGVGWG它是从它是从G中删除中删除W中顶点以及与这些顶点相关联的中顶点以及与这些顶点相关联的边所得到的子图。边所得到的子图。如果如果W仅含一个顶点仅含一个顶点v，则把则把vG 简记为简记为vG e1e3e2Gv3v4v5v2v1e

20、3e2v3v4v2Gv2 ,v3 ,v4 G-v1 ,v5 e1e3e2v3v4v5v2v1边导出子图边导出子图设设F是图是图G的非空边子集，以的非空边子集，以F为边集，以为边集，以F中边的中边的端点全体为顶点集所构成的子图称为由端点全体为顶点集所构成的子图称为由F导出的导出的G的子图，简称的子图，简称G的的边导出子图边导出子图。记为。记为GF。记记 G-F 表示以表示以 E(G)F 为边集的为边集的G的的支撑子图支撑子图，它，它是从是从G中删除中删除F 中的边所得到的子图。中的边所得到的子图。eGeG如如F= e ，则记则记e1e3e2Gv3v4v5v2v1Ge1 ,e2 ,e3 G - e

21、1e1e3e2v3v4v5v2v1e1e3e2v3v4v2v14.图的并与图的并与交交设设G1与与G2都是图都是图G的子图；的子图；若若 ，则，则称称G1与与G2不相交不相交；若若 ，则称，则称G1与与G2边不重边不重的。的。定义定义图图G1与与G2的的和和，记为，是，记为，是G的一个子的一个子图，其顶点集为图，其顶点集为 ,边集为边集为 若若G1与与G2是不相交的，则记。是不相交的，则记。类似的可以定义类似的可以定义G1与与G2的的交交 ，此时要求，此时要求12()()V GV G 12()()E GE G 12GG 12()()V GV G 12()()E GE G 1212GGGG 12

22、GG 12()()V GV G 同构同构给定两个图给定两个图),(),(GGEGVG),(),(HHEHVH如果存在两个一一对应的关系如果存在两个一一对应的关系)()(:HVGV)()(:HEGE使的使的)()()(vueHuveG)(称称G和和H是是同构同构的，记为的，记为HG 同构图例同构图例GHe6e4e2e1e3e5f1f2f6f3f5f4v1v2v3v4u1u2u3u4径径n 顶点顶点vk叫叫W的的终点终点，顶点，顶点v0 称为称为W的的起点起点，n 顶点顶点vi 叫叫W的的内部顶点内部顶点(内点内点)，n 整数整数k称为称为W的的长度长度。n 在简单图中，径可由顶点序列表示。在简单

23、图中，径可由顶点序列表示。01122 kkWv e v e ve v ki 1图图G的一个有限的点边交错序列称为从的一个有限的点边交错序列称为从v0到到vk的的径径；其中其中vi 与与vi+1是边是边ei的顶点的顶点;012 kWvvvv 5. 连通性连通性链、路链、路如果径如果径W 的边各不相同，的边各不相同，则则称称W为一条为一条链链，kvvdk),(0如果如果W 顶点互不相同，顶点互不相同，则称则称W 是一条是一条路路。链长链长是是W 中边的个数中边的个数 k.记记路长路长链：链：w c x d y h w b v g y路：路：x c w h y e u a v01122 kkWv e

24、 v e ve v abdefghcuvyxw圈圈(回路回路)n如果径如果径 W 的起点和终点相的起点和终点相同且有正长度，则称它是同且有正长度，则称它是一个一个闭径闭径；n如果一条闭链的顶点互不如果一条闭链的顶点互不相同，则称它是一个相同，则称它是一个圈圈（或（或回路回路）。）。n称一个圈是称一个圈是偶圈偶圈（奇圈奇圈），），如果它的圈长是偶数（奇如果它的圈长是偶数（奇数）。数）。圈：圈：u a v b w h y e uabdefghcuvyxw定理定理：一个图是二分图当且仅当图中不存在奇圈：一个图是二分图当且仅当图中不存在奇圈.连通连通性性图图G称为称为连通连通的，如果的，如果G的任意两

25、个顶点的任意两个顶点u 和和 v 中存在一中存在一条条(u,v)路。路。不不连通图连通图（分离图分离图）至少有两个连通分支。）至少有两个连通分支。用用w 表示表示G的的连通分支数连通分支数。一个连通图称为一个一个连通图称为一个连通分支连通分支。割集：割集：删除掉连通图中的若干条必要的边后，使删除掉连通图中的若干条必要的边后，使得图不连通，则这些边的集合称为图的一个得图不连通，则这些边的集合称为图的一个割集割集.割边割边：删除掉这条边后图：删除掉这条边后图G不连通。不连通。割点割点：删除掉这个点后图：删除掉这个点后图G不连通。不连通。Euler圈圈nEuler圈圈是指过所有边一是指过所有边一次且

26、恰好一次的闭链。次且恰好一次的闭链。nEuler链链是指过所有边一是指过所有边一次且恰好一次的链。次且恰好一次的链。Euler链：链：y d x c w h y e u a v f y g v b wabdefghcuvyxwEuler圈：所有的顶点度数为偶数。圈：所有的顶点度数为偶数。Euler链：除了两个顶点度数为奇数链：除了两个顶点度数为奇数,其余为偶数其余为偶数.Euler 型（型（Euler 图）图）n定理设定理设G是连通图，则是连通图，则G是是Euler 型的充要条型的充要条件是件是G没有奇次数的顶点。没有奇次数的顶点。n推论推论设设G是一个连通图，是一个连通图，则则G有有Eule

27、r 链当且链当且仅仅当当G最多有两个奇数次数的顶点。最多有两个奇数次数的顶点。n如果图如果图G包含一条包含一条Euler圈，则称圈，则称G是是Euler型型的的.Hamilton 型（型（Hamilton 图）图）nHamilton路路是指包含是指包含G的每个顶点的一条路。的每个顶点的一条路。nHamilton圈圈是指包含是指包含G的每个顶点的一个圈。的每个顶点的一个圈。n如果图如果图G包含一条包含一条Hamilton圈，则称圈，则称G是是Hamilton型型的的.对图对图G的每条边的每条边e，赋予一赋予一实数实数w(e),称为边称为边e的的权权，可得一可得一赋权图（网络）赋权图（网络）。定义

28、定义赋权图赋权图 G 的权的权为为 G 的所有边权的总和。的所有边权的总和。赋权图中一条赋权图中一条路的权路的权称为称为路长路长。76528936uvyxw图图G的每条边如果有方向，称为的每条边如果有方向，称为有向图有向图。有向图的边称为有向图的边称为有向弧有向弧（简称（简称弧弧）,用用ai 表示表示.有向图的各弧用边对应替换后所得的无向图称有向图的各弧用边对应替换后所得的无向图称为该有向图的为该有向图的基础图基础图。度：度：出度出度、入度入度相应的可以定义有向图相应的可以定义有向图的路、圈、连通性、的路、圈、连通性、有向网络等。有向网络等。戊戊甲甲乙乙丙丙丁丁工人工人工作工作DCBA1. 邻

29、接矩阵邻接矩阵1101101101021120)(GA设设G是一个图，是一个图，G=(V(G),E(G), G)，定义图定义图G的的邻接矩阵邻接矩阵A(G) =(aij)为为 nn 矩阵矩阵, 其中其中aij为为连接连接vi与与vj的边数。的边数。2e3e4e5e6e7e1v2v3v4v1e1v2v3v4v1v2v3v4v二、图的矩阵表示二、图的矩阵表示2. 关联矩阵关联矩阵0211000100110000001111010011)(GM取值可能为取值可能为0、1、2。设设G是一个图，是一个图，G=(V(G),E(G), G)，定义图定义图G 的的关联矩阵关联矩阵M(G) =(mij)为为nm

30、矩阵矩阵, 其中其中mij为为vi与与ej的的关联次数。关联次数。2e3e4e5e6e7e1v2v3v4v1e1v2v3v4v1234567 e e e e e e e注注关联矩阵和邻接矩阵统称图的关联矩阵和邻接矩阵统称图的矩阵表示矩阵表示。图的邻接矩阵比它的关联矩阵小的多，因而图图的邻接矩阵比它的关联矩阵小的多，因而图常常以其邻接矩阵的形式存贮于计算机中。常常以其邻接矩阵的形式存贮于计算机中。例例4)(1vd3)(2vd3)(3vd4)(4vd2222 2224+3+3+4=14=272e3e4e5e6e7e1v2v3v4v1e0211000100110000001111010011)(GM

31、1v2v3v4v1234567 e e e e e e e关联矩阵性质关联矩阵性质图图G的关联矩阵的关联矩阵M=(mij)为为mn矩阵；则每行元素矩阵；则每行元素之和等于相应顶点的度；每列元素之和等于之和等于相应顶点的度；每列元素之和等于2.因此，图因此，图G的关联矩阵的关联矩阵M所有元素之和既等于所有所有元素之和既等于所有顶点的度之和，又等于边数的顶点的度之和，又等于边数的2倍。倍。1 1 0 0 1 0 11 1 1 0 0 0 0( )0 0 1 1 0 0 10 0 0 1 1 2 0MG 10.2 树树一、树的概念和性质一、树的概念和性质二、图的支撑树二、图的支撑树三、最小支撑树三、

32、最小支撑树一、树的概念和性质一、树的概念和性质树是图论中结构最简单但又十分重要的图。树是图论中结构最简单但又十分重要的图。例例 某企业的组织结构可用下图表示某企业的组织结构可用下图表示.厂长厂长人事科人事科财务科财务科总总工程师工程师生产生产副厂长副厂长经营经营副厂长副厂长技术科技术科新产品新产品开发科开发科生产科生产科设备科设备科供应科供应科动力科动力科检验科检验科销售科销售科树树（tree）是一个不包含圈的简单连通图。）是一个不包含圈的简单连通图。树中度为树中度为1的点称为的点称为树叶树叶，度大于，度大于1的点称为的点称为分枝点分枝点.具有具有k个连通分支的不包含圈的图称为个连通分支的不包

33、含圈的图称为k-树，或树，或森林森林.下图列出了具有六个顶点的不同构的树。下图列出了具有六个顶点的不同构的树。从中可以看出，图中的每棵树都只有从中可以看出，图中的每棵树都只有5条边，并且至条边，并且至少有少有2个顶点的次数是个顶点的次数是1。树的性质树的性质设设G是一个简单图，是一个简单图， ,则下列六个命题是等价的则下列六个命题是等价的.nG是一棵树。是一棵树。nG无圈且无圈且 m = n-1。nG连通且连通且 m = n-1。nG连通并且每条边都是割边。连通并且每条边都是割边。nG中任意两点都有唯一的路相连。中任意两点都有唯一的路相连。nG无圈，但在任意一对不相邻的顶点之间加连一无圈，但在

34、任意一对不相邻的顶点之间加连一条边，则构成唯一的一个圈。条边，则构成唯一的一个圈。3n二、图的支撑树（生成树）二、图的支撑树（生成树）n若图若图G的支撑子图是一棵树，则称该树为图的支撑子图是一棵树，则称该树为图G的的支撑树支撑树（生成树生成树）。或简称为）。或简称为图图G的树的树.n支撑树也称为连通图的支撑树也称为连通图的极小连通支撑子图极小连通支撑子图。n图图G有支撑树的有支撑树的充要条件充要条件为为G是连通图是连通图.n很显然，一个连通图只要本身不是一棵树，它很显然，一个连通图只要本身不是一棵树，它的支撑树就不止一个的支撑树就不止一个。图的支撑树的求法图的支撑树的求法寻找图的支撑树的方法有

35、两种：寻找图的支撑树的方法有两种：破圈法、避圈法破圈法、避圈法.破圈法破圈法：在图：在图G中任意取一个圈，从圈上任意去中任意取一个圈，从圈上任意去掉一条边，将这个圈破掉。重复这个步骤直到不掉一条边，将这个圈破掉。重复这个步骤直到不含圈为止，所得图即为支撑树。含圈为止，所得图即为支撑树。v1v2v4v5v32444避圈法避圈法：在给定的图：在给定的图G中，每步选出一条边，使中，每步选出一条边，使它与已选边不构成圈，直到选够它与已选边不构成圈，直到选够n-1条边为止。条边为止。按照边的选法不同按照边的选法不同,可分为两种：可分为两种：深探法深探法,广探法广探法.深探法深探法: v1v2v4v5v3

36、避圈法避圈法：在给定的图：在给定的图G中，每步选出一条边，使中，每步选出一条边，使它与已选边不构成圈，直到选够它与已选边不构成圈，直到选够n-1条边为止。条边为止。按照边的选法不同按照边的选法不同,可分为两种：可分为两种：深探法深探法,广探法广探法.广探法广探法: v1v2v4v5v3v1v2v4v5v3设设G是一个赋权图，是一个赋权图，T为为G的一个支撑树。定义的一个支撑树。定义T的的权权为：为：G中权最小的支撑树称为中权最小的支撑树称为G的的最小支撑树最小支撑树(最小树最小树).三、最小支撑树问题三、最小支撑树问题()( )( )e E Tw Tw e 许多网络问题都可以归结为最小树问题。

37、例如许多网络问题都可以归结为最小树问题。例如:设计长度最小的公路网把若干城市联系起来设计长度最小的公路网把若干城市联系起来;设计用料最省的电话线网把有关单位联系起来等设计用料最省的电话线网把有关单位联系起来等.下面介绍求最小树的两种算法下面介绍求最小树的两种算法.Step0 把边按权的大小从小到大排列得：把边按权的大小从小到大排列得： 置置 Step1 若若 ，则停，此时，则停，此时GS即为所即为所 求的最小树；否则，转向求的最小树；否则，转向Step2。Step2 如果如果 GS+e j不构成回路，则令不构成回路，则令 转向转向Step1；否则，否则，令令j=j+1转向转向Step2。1vi

38、S01,meee,0,1Sij 11,1,1ijieeSSeiijj 算法算法1：Kruskal算法算法（类似于广探法）（类似于广探法）（1965）思想思想:开始选一条权最小的边开始选一条权最小的边,以后每一步以后每一步,总从未选总从未选的边中选一条权最小的边的边中选一条权最小的边,使它与已选边不构成圈使它与已选边不构成圈.算例算例1： 利用利用Kruskal算法求最小树。算法求最小树。12244342v1v2v4v5v31232v1v2v4v5v3评注评注Kruskal算法的总计算量为算法的总计算量为 ，有效，有效性不太好。性不太好。求最小树的一个好的算法求最小树的一个好的算法是是Dijks

39、tra于于1959年年提出的，算法的实质是在图的提出的，算法的实质是在图的 个独立割个独立割集中，取每个割集的一条极小边来构成最小集中，取每个割集的一条极小边来构成最小树。树。)log(2nn1n算法算法2：Dijkstra算法算法（类似于深探法）（类似于深探法）Step0 置置Step1 取取 置置 Step2 若若 ，则停止；，则停止；否则，置否则，置 ，返回，返回Step1.1,1,2,3, ,jjTRSnuwjS minkjikj Suuw , , ikTTeRRkSSkSmin,jjkjj Suu w 算例算例2： 利用利用Dijkstra算法求最小树。算法求最小树。12244342

40、v1v2v4v5v3算法算法3：破圈破圈法法破圈法是破圈法是Dijkstra算法的对偶算法。最适合于图算法的对偶算法。最适合于图上作业。尤其是当图的顶点数和边数比较大时，上作业。尤其是当图的顶点数和边数比较大时，可以在各个局部进行。可以在各个局部进行。Step1 若若G不含圈，则停止；否则不含圈，则停止；否则在在G中找一个中找一个 圈圈C，取圈取圈C中权值最大的一条中权值最大的一条边边e .Step2 置置 G = G - e ，返回返回Step1。算例算例3： 利用破圈法求最小树。利用破圈法求最小树。12244342v1v2v4v5v312244342v1v2v4v5v32444最小连接问题

41、最小连接问题n作为最小树的应用问题之一是所谓的连接问题：作为最小树的应用问题之一是所谓的连接问题：欲建造一个连接若干城镇（矿区或工业区）的铁欲建造一个连接若干城镇（矿区或工业区）的铁路网，给定城镇路网，给定城镇i和和j之间直通线路的造价为之间直通线路的造价为 cij ，试设计一个总造价最小的铁路运输图。试设计一个总造价最小的铁路运输图。n把每个城镇看作是具有权把每个城镇看作是具有权cij的赋权图的赋权图G的一个顶的一个顶点。显然连接问题可以表述成：在赋权图点。显然连接问题可以表述成：在赋权图G中，中，求出具有最小权的支撑树求出具有最小权的支撑树。10.3 最短路问题最短路问题最短路问题是网络理

42、论中应用最广泛的问题之一最短路问题是网络理论中应用最广泛的问题之一.许多优化问题可以使用这个模型如设备更新、许多优化问题可以使用这个模型如设备更新、管道铺设、线路安排、厂区布局等管道铺设、线路安排、厂区布局等.我们曾介绍了最短路问题的动态规划解法，但某我们曾介绍了最短路问题的动态规划解法，但某些最短路问题些最短路问题(如道路不能整齐分段者如道路不能整齐分段者)构造动态规构造动态规划方程比较困准、而图论方法则比较有效。划方程比较困准、而图论方法则比较有效。n最短路问题：在一个赋权图最短路问题：在一个赋权图G上，给定两个顶上，给定两个顶点点u和和 v，在所有连接顶点，在所有连接顶点u和和 v 的路

43、中，寻找的路中，寻找路长最短的路（称为路长最短的路（称为u和和 v最短路最短路.）n u和和 v最短路的路长也称为最短路的路长也称为u和和 v的的距离距离-d(u,v).有些最短路问题也可以求网络中某指定点到其余所有些最短路问题也可以求网络中某指定点到其余所有结点的最短路、或求网络中任意两点间的最短路有结点的最短路、或求网络中任意两点间的最短路.一、网络无负权的最短路一、网络无负权的最短路本算法由本算法由Dijkstra于于1959年提出，可用于求解指定年提出，可用于求解指定两点间的最短路，或从指定点到其余各点的最短两点间的最短路，或从指定点到其余各点的最短路，目前被认为是求无负权网络最短路问

44、题的最路，目前被认为是求无负权网络最短路问题的最好方法。好方法。算法的基本思路基于以下算法的基本思路基于以下原理原理：若序列若序列vs ,v1 , ,vn是从是从vs到到vn的最短路，的最短路，则序列则序列vs ,v1 , ,vn-1必为从必为从vs到到vn-1的最短路。的最短路。Dijkstra算法算法Dijkstra算法算法基本思想基本思想Dijkstra算法的基本思想是从算法的基本思想是从vs出发，逐步地向外出发，逐步地向外探寻最短路，采用探寻最短路，采用标号法标号法。执行过程中，与每个点对应，记录下一个数（称执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从为这个

45、点的标号），它或者表示从vs到该点的最短到该点的最短路长（称为路长（称为P标号标号），或者是从），或者是从vs到该点的最短路到该点的最短路长的上界（称为长的上界（称为T标号标号）。）。算法每一步都把某个顶点的算法每一步都把某个顶点的T 标号改为标号改为P 标号，标号， 当终点当终点vt 得到得到 P 标号时，计算结束。最多标号时，计算结束。最多n-1步。步。计算实例：计算实例： 求连接求连接 vs、vt 的最短路的最短路.0 - - P T- - - - 开始，给开始，给vs以以 P 标号，标号，P(vs)=0,其余各点给其余各点给 T 标号标号 T(vi)=+.227414731555vsv

46、2v1vtv4v5v3Step 1: 迭迭代代 1 Dijkstra算法算法基本步骤：基本步骤：0 - - - - - - 若若 vi 为刚得到为刚得到 P 标号的点标号的点,考虑这样的点考虑这样的点 vj : (vi ,vj)E 且且vj 为为 T 标号。标号。227414731555vsv2v1vtv4v5v3Step 2: 对对vj的的T 标号进行如下更改标号进行如下更改T(vj)=minT(vj),P(vi)+wij245迭迭代代 1 考察考察vs , T(v2)=minT(v2),P(vs)+ws2= min+,0+5=5T(v1)=minT(v1),P(vs)+ws1= min+,

47、0+2=20 - - - - - - 比较所有具有比较所有具有 T 标号的点，把最小者改为标号的点，把最小者改为P 标号，标号，227414731555vsv2v1vtv4v5v3Step 3: 245即即 P(vi)=minT(vi).当存在两个以上最小者时当存在两个以上最小者时,可同时改为可同时改为P 标号。若标号。若全部点为全部点为P标号标号,则停止。否则用则停止。否则用vi代替代替vi转转step 2.-2迭迭代代 1 全部全部T标号中标号中,T(v1)最小最小,令令P(v1)=2,记录路径记录路径(vs ,v1).0 -2-5- - - -4227414731555vsv2v1vtv

48、4v5v394 若若 vi 为刚得到为刚得到 P 标号的点标号的点,考虑这样的点考虑这样的点 vj : (vi ,vj)E 且且vj 为为 T 标号。标号。Step 2: 对对vj的的T 标号进行如下更改标号进行如下更改T(vj)=minT(vj),P(vi)+wij迭迭代代 2 考察考察v1 , T(v4)=minT(v4),P(v1)+w14= min+,2+7=9T(v2)=minT(v2),P(v1)+w12= min5,2+2=40 -2-4-9- - -4227414731555vsv2v1vtv4v5v344迭迭代代 2 比较所有具有比较所有具有 T 标号的点，把最小者改为标号的

49、点，把最小者改为P 标号，标号，Step 3: 即即 P(vi)=minT(vi).-全部全部 T 标号中标号中,T(v2),T(v3)最小最小,令令P(v2)=4, P(v3)=4,记录路径记录路径(v1 ,v2), (v1 ,v4),.0 -2-4-9- - 4-227414731555vsv2v1vtv4v5v37迭迭代代 3 若若 vi 为刚得到为刚得到 P 标号的点标号的点,考虑这样的点考虑这样的点 vj : (vi ,vj)E 且且vj 为为 T 标号。标号。Step 2: 对对vj的的T 标号进行如下更改标号进行如下更改T(vj)=minT(vj),P(vi)+wij0 -2-4

50、-9- -74-227414731555vsv2v1vtv4v5v37迭迭代代 3 比较所有具有比较所有具有 T 标号的点，把最小者改为标号的点，把最小者改为P 标号，标号，Step 3: 即即 P(vi)=minT(vi).-0 -2-4-9- 7-4-227414731555vsv2v1vtv4v5v3迭迭代代 4 若若 vi 为刚得到为刚得到 P 标号的点标号的点,考虑这样的点考虑这样的点 vj : (vi ,vj)E 且且vj 为为 T 标号。标号。Step 2: 对对vj的的T 标号进行如下更改标号进行如下更改T(vj)=minT(vj),P(vi)+wij8140 -2-4-8-