运筹学第十章.pptx

《运筹学第十章.pptx》由会员分享，可在线阅读，更多相关《运筹学第十章.pptx（141页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一一些些问问题题图论中著名问题图论中著名问题.1736.1736年，图论的创始人年，图论的创始人EulerEuler巧巧妙地将此问题化为图的不重复妙地将此问题化为图的不重复一笔画问题一笔画问题，并证明，并证明了该问题不存在肯定回答，发表了第一篇论文了该问题不存在肯定回答，发表了第一篇论文.例：七桥问题例：七桥问题ABCD问题：一个散步者能否走过七座桥，且每座桥只走问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。过一次，最后回到出发点。第1页/共141页例：四色猜想例：四色猜想 能否用四种颜色给地图染色，使相邻的国家有不能否用四种颜色给地图染色，使相邻的国家有不同的颜色。同的

2、颜色。点：国家；点：国家；边：两个国家有公共边界。边：两个国家有公共边界。问题：问题：能否用四种颜色给能否用四种颜色给平面图的点染色，使有公平面图的点染色，使有公共边的点有不同的颜色。共边的点有不同的颜色。公元公元1852年，格里斯发现无论多么复杂的地图，只要用四种颜年，格里斯发现无论多么复杂的地图，只要用四种颜色就能将相邻的区域区分开来，这就是所谓色就能将相邻的区域区分开来，这就是所谓“四色猜想四色猜想”。直到公元直到公元1976年，才由美国数学家同时操作三台超大型汁算机年，才由美国数学家同时操作三台超大型汁算机作了近作了近200亿个逻辑判断，花费亿个逻辑判断，花费1200个机时，才取得了个

3、机时，才取得了“四色四色猜想猜想”的证明。的证明。第2页/共141页例：例：Hamilton图图 游戏：用正十二面体上游戏：用正十二面体上20个顶点表示个顶点表示20个城市，个城市，要求参加游戏者沿着各边行走，走遍每一个城市且仅要求参加游戏者沿着各边行走，走遍每一个城市且仅走一次，最后回到出发城市。走一次，最后回到出发城市。公元公元1859年，哈密尔顿年，哈密尔顿(Hamilton)在给朋友格拉在给朋友格拉伍斯（伍斯（Grares）的信中提）的信中提出了这个游戏。出了这个游戏。问题问题：如何判断一个图是：如何判断一个图是否具有这样的性质。如果否具有这样的性质。如果有，这样的行走路线如何有，这样

4、的行走路线如何确定。确定。第3页/共141页例：中国邮路问题例：中国邮路问题 一个邮递员送信，要走完他所负责的全部街道一个邮递员送信，要走完他所负责的全部街道分送信件，最后返回邮局。邮递员都会本能地以尽分送信件，最后返回邮局。邮递员都会本能地以尽可能少的行程完成送信任务。如何走路线最短。可能少的行程完成送信任务。如何走路线最短。点：路口；点：路口；边：两路口之间道路，第边：两路口之间道路，第i条道路长条道路长ei。1962年，由我国数学家管梅谷提出，国际上称为年，由我国数学家管梅谷提出，国际上称为中中国邮递员问题国邮递员问题。问题问题：求一个圈，过每边至少一次，并使圈的长度：求一个圈，过每边至

5、少一次，并使圈的长度最最短。短。第4页/共141页例：例：有甲、乙、丙、丁、戊五个球队，各队之间比赛有甲、乙、丙、丁、戊五个球队，各队之间比赛情况如表：情况如表：点：球队；点：球队；连线：两个球队之间比赛过，如甲胜乙，用连线：两个球队之间比赛过，如甲胜乙，用v1v2表示。表示。v1v2v3v4v5第5页/共141页点点：研究对象（陆地、路口、国家、球队）；：研究对象（陆地、路口、国家、球队）；点间连线：对象之间的特定关系（陆地间有桥、路点间连线：对象之间的特定关系（陆地间有桥、路口之间道路、两国边界、两球队比赛及口之间道路、两国边界、两球队比赛及结果结果)。对称关系：桥、道路、边界；对称关系：

6、桥、道路、边界；用不带箭头的连线表示，称为用不带箭头的连线表示，称为边边。非对称关系：甲队胜乙队，用带箭头的连线表示，非对称关系：甲队胜乙队，用带箭头的连线表示，称为称为弧弧。图图：点及边（或弧）组成。：点及边（或弧）组成。实际生活中，人们经常用实际生活中，人们经常用“图图”来表示一些对象以来表示一些对象以及这些对象之间的特定关系。及这些对象之间的特定关系。如公路或铁路交通图、管网图、通讯联络图等。如公路或铁路交通图、管网图、通讯联络图等。第6页/共141页对所要研究的问题确定具体对象及这些对象间的对所要研究的问题确定具体对象及这些对象间的性质关系，并用图的形式表示出来，这就是对所性质关系，并

7、用图的形式表示出来，这就是对所研究原问题建立的模型。研究原问题建立的模型。图是反映对象之间关系图是反映对象之间关系的一种工具。的一种工具。这里所研究的图与平面几何中的图不同。这里只这里所研究的图与平面几何中的图不同。这里只关心图中有多少个点，点与点之间有无连线，至关心图中有多少个点，点与点之间有无连线，至于连线的方式是直线还是曲线，点与点的相对位于连线的方式是直线还是曲线，点与点的相对位置如何，都是无关紧要的。置如何，都是无关紧要的。是组合意义下的图。是组合意义下的图。图的理论和方法图的理论和方法，就是从形形色色的具体的图以，就是从形形色色的具体的图以及与它们相关的实际问题中，抽象出共同性的东

8、及与它们相关的实际问题中，抽象出共同性的东西，找出其规律、性质、方法，再应用到解决实西，找出其规律、性质、方法，再应用到解决实际问题中去。际问题中去。第7页/共141页图论图论(GraphTheory)是运筹学中的一个重要分是运筹学中的一个重要分支，主要研究具有某种支，主要研究具有某种二元关系二元关系的的离散系统离散系统的组的组合结构和性质。合结构和性质。随着电子计算机的蓬勃发展，图论不仅得到了迅随着电子计算机的蓬勃发展，图论不仅得到了迅速发展，而且应用非常广泛。它直观清晰，使用速发展，而且应用非常广泛。它直观清晰，使用方便，易于掌握。方便，易于掌握。应用领域：物理学、化学、控制论、信息论、管

9、应用领域：物理学、化学、控制论、信息论、管理科学、通信系统、交通运输系统、建筑、计算理科学、通信系统、交通运输系统、建筑、计算机科学、生产工艺流程以及军事后勤保障系统等机科学、生产工艺流程以及军事后勤保障系统等的问题常用图论模型来描述。的问题常用图论模型来描述。网络规划是图论与线性规划的交叉学科网络规划是图论与线性规划的交叉学科,具有广具有广泛的应用背景，比如，最短路问题、最小树问题、泛的应用背景，比如，最短路问题、最小树问题、最大流问题、最优匹配问题等最大流问题、最优匹配问题等.第8页/共141页10.1图的基本概念图的基本概念一个一个图图(Graph)定义为三元有序组定义为三元有序组G=(

10、V(G),E(G),G)，V(G)是图的是图的顶点集合顶点集合，E(G)是图的是图的边集合边集合，G称为称为顶点顶点与与边边之间的之间的关联函数关联函数。V(G)中的元素中的元素vi 称为称为顶点顶点,E(G)中的元素中的元素ek 称为称为边边.一个图习惯一个图习惯记作记作G=(V,E).当当V,E为有限集合时，为有限集合时，G称为称为有限图有限图，否则，称为，否则，称为无限图无限图.我们只讨论有限图我们只讨论有限图.一、基本概念一、基本概念.图图第9页/共141页设设G是一个图，是一个图，G=(V(G),E(G)，则称则称e 连接连接u和和v，称，称u和和v是是e的的端点端点.若若称端点称端

11、点u，v与边与边e是是关联关联的，的，称两个顶点称两个顶点u，v是是邻接（相邻）邻接（相邻）的的.两条边两条边e,e1有公共端点有公共端点v，则称，则称e,e1相邻相邻.一个图可用一个几何图形表示一个图可用一个几何图形表示,称为图的称为图的几何实几何实现现，其中每个顶点用点表示，每条边用连接端，其中每个顶点用点表示，每条边用连接端点的线表示。图的几何实现有助与我们直观的点的线表示。图的几何实现有助与我们直观的了解图的许多性质了解图的许多性质.uvewe1第10页/共141页设设G是一个图，是一个图，G的几何实现的几何实现其中：其中：例例第11页/共141页说明说明一个图的几何实现并不是唯一的；

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

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

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

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

16、个顶点与Y的每个顶点都相连。完全二分图的每个顶点都相连。完全二分图记为记为Km,nX:Y:第20页/共141页特殊图例特殊图例都是都是极小极小的的非平面图非平面图.K5K3,3第21页/共141页2.顶点的度（次）顶点的度（次）称度为奇数的顶点为称度为奇数的顶点为奇点奇点；称度为偶数的顶点为称度为偶数的顶点为偶点偶点.设设G是一个图，是一个图，G=(V(G),E(G),G)，定义图，定义图G的的顶点顶点v 的度的度为与顶点为与顶点v相关联的边数，记作相关联的边数，记作d(v).第22页/共141页定理定理设设G是一个图，则是一个图，则推论推论：图中奇点的数目为偶数。：图中奇点的数目为偶数。度为

17、度为1的点称为的点称为悬挂点悬挂点,连结悬挂点的边称为连结悬挂点的边称为悬挂边悬挂边.度为度为0的点称为的点称为孤立点孤立点。第23页/共141页3.子图子图有两个图有两个图G和和H，如果，如果称图称图H是图是图G的的子图子图，记为，记为若若且且称称H是是G的的真子图真子图。称称H是是G的的支撑子图支撑子图（或（或生成子图生成子图）.如果如果，第24页/共141页e1e3e2Gv3v4v5v2v1H1:真子图真子图v3v5v2v1H2:支撑子图支撑子图e1e3e2v3v4v5v2v1第25页/共141页顶点导出子图顶点导出子图设设W是图是图G的一个非空顶点子集的一个非空顶点子集,以以W为顶点集

18、，以为顶点集，以二端点均在二端点均在W中的中的边的全体边的全体为边集的子图称为由为边集的子图称为由W导出的导出的G的子图，简称的子图，简称导出子图导出子图，记为，记为GW。导出子图导出子图GV-W记为记为G-W，即，即它是从它是从G中删除中删除W中顶点以及与这些顶点相关联的中顶点以及与这些顶点相关联的边所得到的子图。边所得到的子图。如果如果W仅含一个顶点仅含一个顶点v，则把，则把简记为简记为第26页/共141页e1e3e2Gv3v4v5v2v1e3e2v3v4v2Gv2,v3,v4G-v1,v5e1e3e2v3v4v5v2v1第27页/共141页边导出子图边导出子图设设F是图是图G的非空边子集

19、，以的非空边子集，以F为边集，以为边集，以F中边的中边的端点全体为顶点集所构成的子图称为由端点全体为顶点集所构成的子图称为由F导出的导出的G的子图，简称的子图，简称G的的边导出子图边导出子图。记为。记为GF。记记G-F 表示以表示以E(G)F 为边集的为边集的G的的支撑子图支撑子图，它，它是从是从G中删除中删除F 中的边所得到的子图。中的边所得到的子图。如如F=e，则记，则记第28页/共141页e1e3e2Gv3v4v5v2v1Ge1,e2,e3G-e1e1e3e2v3v4v5v2v1e1e3e2v3v4v2v1第29页/共141页4.图的并与交图的并与交设设G1与与G2都是图都是图G的子图；

20、的子图；若若，则称，则称G1与与G2不相交不相交；若若，则称，则称G1与与G2边不重边不重的。的。定义图定义图G1与与G2的的和和，记为，是，记为，是G的一的一个子图，其顶点集为个子图，其顶点集为,边集为边集为若若G1与与G2是不相交的，则记。是不相交的，则记。类似的可以定义类似的可以定义G1与与G2的的交交，此时要，此时要求求第30页/共141页同构同构给定两个图给定两个图如果存在两个一一对应的关系如果存在两个一一对应的关系使的使的称称G和和H是是同构同构的，记为的，记为第31页/共141页同构图例同构图例GHe6e4e2e1e3e5f1f2f6f3f5f4v1v2v3v4u1u2u3u4第

21、32页/共141页径径顶点顶点vk叫叫W的的终点终点，顶点，顶点v0称为称为W的的起点起点，顶点顶点vi叫叫W的的内部顶点内部顶点(内点内点)，整数整数k称为称为W的的长度长度。在简单图中，径可由顶点序列表示。在简单图中，径可由顶点序列表示。图图G的一个有限的点边交错序列称为从的一个有限的点边交错序列称为从v0到到vk的的径径；其中其中vi 与与vi+1是边是边ei的顶点的顶点;5.连通性连通性第33页/共141页链、路链、路如果径如果径W 的边各不相同，的边各不相同，则称则称W为一条为一条链链，如果如果W 顶点互不相同，顶点互不相同，则称则称W 是一条是一条路路。链长链长是是W 中边的个数中

22、边的个数k.记记路长路长链：链：w c x d y h w b v g y路：路：x c w h y e u a vabdefghcuvyxw第34页/共141页圈圈(回路回路)如果径如果径W 的起点和终点的起点和终点相同且有正长度，则称它相同且有正长度，则称它是一个是一个闭径闭径；如果一条闭链的顶点互不如果一条闭链的顶点互不相同，则称它是一个相同，则称它是一个圈圈（或（或回路回路）。）。称一个圈是称一个圈是偶圈偶圈（奇圈奇圈），），如果它的圈长是偶数（奇如果它的圈长是偶数（奇数）。数）。圈：圈：u a v b w h y e uabdefghcuvyxw定理定理：一个图是二分图当且仅当图中不

23、存在奇圈：一个图是二分图当且仅当图中不存在奇圈.第35页/共141页连通性连通性图图G称为称为连通连通的，如果的，如果G的任意两个顶点的任意两个顶点u 和和v 中存在一条中存在一条(u,v)路。路。不连通图不连通图（分离图分离图）至少有两个连通分支。）至少有两个连通分支。用用w表示表示G的的连通分支数连通分支数。一个连通图称为一个一个连通图称为一个连通分支连通分支。割集：割集：删除掉连通图中的若干条必要的边后，使删除掉连通图中的若干条必要的边后，使得图不连通，则这些边的集合称为图的一个得图不连通，则这些边的集合称为图的一个割集割集.割边割边：删除掉这条边后图：删除掉这条边后图G不连通。不连通。

24、割点割点：删除掉这个点后图：删除掉这个点后图G不连通。不连通。第36页/共141页Euler圈圈Euler圈圈是指过所有边一是指过所有边一次且恰好一次的闭链。次且恰好一次的闭链。Euler链链是指过所有边一是指过所有边一次且恰好一次的链。次且恰好一次的链。Euler链：链：y d x c w h y e u a v f y g v b wabdefghcuvyxwEuler圈：所有的顶点度数为偶数。圈：所有的顶点度数为偶数。Euler链：除了两个顶点度数为奇数链：除了两个顶点度数为奇数,其余为偶数其余为偶数.第37页/共141页Euler 型（型（Euler 图）图）定理设定理设G是连通图，则

25、是连通图，则G是是Euler 型的充要型的充要条件是条件是G没有奇次数的顶点。没有奇次数的顶点。推论设推论设G是一个连通图，则是一个连通图，则G有有Euler 链当链当且仅当且仅当G最多有两个奇数次数的顶点。最多有两个奇数次数的顶点。n如果图如果图G包含一条包含一条Euler圈，则称圈，则称G是是Euler型型的的.第38页/共141页Hamilton型（型（Hamilton图）图）nHamilton路路是指包含是指包含G的每个顶点的一条路。的每个顶点的一条路。nHamilton圈圈是指包含是指包含G的每个顶点的一个圈。的每个顶点的一个圈。n如果图如果图G包含一条包含一条Hamilton圈，则

26、称圈，则称G是是Hamilton型型的的.第39页/共141页6.6.赋权图赋权图赋权图赋权图对图对图G的每条边的每条边e，赋予一，赋予一实数实数w(e),称为边称为边e的的权权，可得一可得一赋权图（网络）赋权图（网络）。定义定义赋权图赋权图G 的权的权为为G 的的所有边权的总和。所有边权的总和。赋权图中一条赋权图中一条路的权路的权称为称为路长路长。76528936uvyxw第40页/共141页7.7.有向图有向图有向图有向图图图G的每条边如果有方向，称为的每条边如果有方向，称为有向图有向图。有向图的边称为有向图的边称为有向弧有向弧（简称（简称弧弧）,用用ai 表示表示.有向图的各弧用边对应替

27、换后所得的无向图称有向图的各弧用边对应替换后所得的无向图称为该有向图的为该有向图的基础图基础图。度：度：出度出度、入度入度相应的可以定义有向图相应的可以定义有向图的路、圈、连通性、的路、圈、连通性、有向网络等。有向网络等。戊戊甲甲乙乙丙丙丁丁工人工人工作工作DCBA第41页/共141页1.邻接矩阵邻接矩阵设设G是一个图，是一个图，G=(V(G),E(G),G)，定义图，定义图G的的邻接矩阵邻接矩阵A(G)=(aij)为为nn 矩阵矩阵,其中其中aij为连接为连接vi与与vj的边数。的边数。二、图的矩阵表示二、图的矩阵表示第42页/共141页2.关联矩阵关联矩阵取值可能为取值可能为0、1、2。设

28、设G是一个图，是一个图，G=(V(G),E(G),G)，定义图，定义图G 的的关联矩阵关联矩阵M(G)=(mij)为为nm矩阵矩阵,其中其中mij为为vi与与ej的关联次数。的关联次数。第43页/共141页注注关联矩阵和邻接矩阵统称图的关联矩阵和邻接矩阵统称图的矩阵表示矩阵表示。图的邻接矩阵比它的关联矩阵小的多，因而图图的邻接矩阵比它的关联矩阵小的多，因而图常常以其邻接矩阵的形式存贮于计算机中。常常以其邻接矩阵的形式存贮于计算机中。第44页/共141页例例2222 2224+3+3+4=14=27第45页/共141页关联矩阵性质关联矩阵性质图图G的关联矩阵的关联矩阵M=(mij)为为mn矩阵；

29、则每行元素之矩阵；则每行元素之和等于相应顶点的度；每列元素之和等于和等于相应顶点的度；每列元素之和等于2.因此，图因此，图G的关联矩阵的关联矩阵M所有元素之和既等于所有所有元素之和既等于所有顶点的度之和，又等于边数的顶点的度之和，又等于边数的2倍。倍。第46页/共141页10.2树树一、树的概念和性质一、树的概念和性质二、图的支撑树二、图的支撑树三、最小支撑树三、最小支撑树第47页/共141页一、树的概念和性质一、树的概念和性质树是图论中结构最简单但又十分重要的图。树是图论中结构最简单但又十分重要的图。例例某企业的组织结构可用下图表示某企业的组织结构可用下图表示.厂长厂长人人事事科科财财务务科

30、科总总工工程程师师生生产产副副厂厂长长经经营营副副厂厂长长技技术术科科新新产产品品开开发发科科生生产产科科设设备备科科供供应应科科动动力力科科检检验验科科销销售售科科第48页/共141页树树（tree）是一个不包含圈的简单连通图。）是一个不包含圈的简单连通图。树中度为树中度为1的点称为的点称为树叶树叶，度大于，度大于1的点称为的点称为分枝点分枝点.具有具有k个连通分支的不包含圈的图称为个连通分支的不包含圈的图称为k-树，或树，或森林森林.下图列出了具有六个顶点的不同构的树。下图列出了具有六个顶点的不同构的树。从中可以看出，图中的每棵树都只有从中可以看出，图中的每棵树都只有5条边，并且至条边，并

31、且至少有少有2个顶点的次数是个顶点的次数是1。第49页/共141页树的性质树的性质设设G是一个简单图，是一个简单图，,则下列六个命题是等价则下列六个命题是等价的的.G是一棵树。是一棵树。G无圈且无圈且m=n-1。G连通且连通且m=n-1。G连通并且每条边都是割边。连通并且每条边都是割边。G中任意两点都有唯一的路相连。中任意两点都有唯一的路相连。G无圈，但在任意一对不相邻的顶点之间加连无圈，但在任意一对不相邻的顶点之间加连一条边，则构成唯一的一个圈。一条边，则构成唯一的一个圈。第50页/共141页二、图的支撑树（生成树）二、图的支撑树（生成树）若图若图G的支撑子图是一棵树，则称该树为图的支撑子图

32、是一棵树，则称该树为图G的的支撑树支撑树（生成树生成树）。或简称为）。或简称为图图G的树的树.支撑树也称为连通图的支撑树也称为连通图的极小连通支撑子图极小连通支撑子图。图图G有支撑树的有支撑树的充要条件充要条件为为G是连通图是连通图.很显然，一个连通图只要本身不是一棵树，很显然，一个连通图只要本身不是一棵树，它的支撑树就不止一个。它的支撑树就不止一个。第51页/共141页图的支撑树的求法图的支撑树的求法寻找图的支撑树的方法有两种：寻找图的支撑树的方法有两种：破圈法、避圈法破圈法、避圈法.破圈法破圈法：在图：在图G中任意取一个圈，从圈上任意去中任意取一个圈，从圈上任意去掉一条边，将这个圈破掉。重

33、复这个步骤直到不掉一条边，将这个圈破掉。重复这个步骤直到不含圈为止，所得图即为支撑树。含圈为止，所得图即为支撑树。v1v2v4v5v32444第52页/共141页避圈法避圈法：在给定的图：在给定的图G中，每步选出一条边，使中，每步选出一条边，使它与已选边不构成圈，直到选够它与已选边不构成圈，直到选够n-1条边为止。条边为止。按照边的选法不同按照边的选法不同,可分为两种：可分为两种：深探法深探法,广探法广探法.深探法深探法:v1v2v4v5v3第53页/共141页避圈法避圈法：在给定的图：在给定的图G中，每步选出一条边，使中，每步选出一条边，使它与已选边不构成圈，直到选够它与已选边不构成圈，直到

34、选够n-1条边为止。条边为止。按照边的选法不同按照边的选法不同,可分为两种：可分为两种：深探法深探法,广探法广探法.广探法广探法:v1v2v4v5v3v1v2v4v5v3第54页/共141页设设G是一个赋权图，是一个赋权图，T为为G的一个支撑树。定义的一个支撑树。定义T的的权权为：为：G中权最小的支撑树称为中权最小的支撑树称为G的的最小支撑树最小支撑树(最小树最小树).三、最小支撑树问题三、最小支撑树问题许多网络问题都可以归结为最小树问题。例如许多网络问题都可以归结为最小树问题。例如:设计长度最小的公路网把若干城市联系起来设计长度最小的公路网把若干城市联系起来;设计用料最省的电话线网把有关单位

35、联系起来等设计用料最省的电话线网把有关单位联系起来等.第55页/共141页下面介绍求最小树的两种算法下面介绍求最小树的两种算法.Step0把边按权的大小从小到大排列得：把边按权的大小从小到大排列得：置置Step1若若，则停，此时，则停，此时GS即为即为所所求的最小树；否则，转向求的最小树；否则，转向Step2。Step2如果如果GS+ej不构成回路，则令不构成回路，则令转向转向Step1；否则，令；否则，令j=j+1转向转向Step2。算法算法1：Kruskal算法算法（类似于广探法）（类似于广探法）（1965）思想思想:开开始选一条权最小的边始选一条权最小的边,以后每一步以后每一步,总从未选

36、总从未选的边中选一条权最小的边的边中选一条权最小的边,使它与已选边不构成圈使它与已选边不构成圈.第56页/共141页算例算例1：利用利用Kruskal算法求最小树。算法求最小树。12244342v1v2v4v5v31232v1v2v4v5v3第57页/共141页评注评注Kruskal算算法法的的总总计计算算量量为为，有有效效性不太好。性不太好。求求 最最 小小 树树 的的 一一 个个 好好 的的 算算 法法 是是 Dijkstra于于1959年年提提出出的的，算算法法的的实实质质是是在在图图的的个个独独立立割割集集中中，取取每每个个割割集集的的一一条条极极小小边边来来构成最小树。构成最小树。第

37、58页/共141页算法算法2：Dijkstra算法算法（类似于深探法）（类似于深探法）Step0置置Step1取取置置Step2若若，则停止；，则停止；否则，置否则，置，返回，返回Step1.第59页/共141页算例算例2：利用利用Dijkstra算法求最小树。算法求最小树。12244342v1v2v4v5v3第60页/共141页算法算法3：破圈法破圈法破圈法是破圈法是Dijkstra算法的对偶算法。最适合于算法的对偶算法。最适合于图上作业。尤其是当图的顶点数和边数比较大图上作业。尤其是当图的顶点数和边数比较大时，可以在各个局部进行。时，可以在各个局部进行。Step1若若G不含圈，则停止；否则

38、在不含圈，则停止；否则在G中找一中找一个个圈圈C，取圈，取圈C中权值最大的一条边中权值最大的一条边e.Step2置置G=G-e，返回，返回Step1。第61页/共141页算例算例3：利用破圈法求最小树。利用破圈法求最小树。12244342v1v2v4v5v312244342v1v2v4v5v32444第62页/共141页最小连接问题最小连接问题作作为为最最小小树树的的应应用用问问题题之之一一是是所所谓谓的的连连接接问问题题：欲欲建建造造一一个个连连接接若若干干城城镇镇（矿矿区区或或工工业业区区）的的铁铁路路网网，给给定定城城镇镇i和和j之之间间直直通通线线路路的的造造价价为为cij，试设计一个

39、总造价最小的铁路运输图。，试设计一个总造价最小的铁路运输图。把每个城镇看作是具有权把每个城镇看作是具有权cij的赋权图的赋权图G的一个的一个顶点。显然连接问题可以表述成：在赋权图顶点。显然连接问题可以表述成：在赋权图G中，求出具有最小权的支撑树。中，求出具有最小权的支撑树。第63页/共141页10.3最短路问题最短路问题最短路问题是网络理论中应用最广泛的问题之一最短路问题是网络理论中应用最广泛的问题之一.许多优化问题可以使用这个模型如设备更新、许多优化问题可以使用这个模型如设备更新、管道铺设、线路安排、厂区布局等管道铺设、线路安排、厂区布局等.我们曾介绍了最短路问题的动态规划解法，但某我们曾介

40、绍了最短路问题的动态规划解法，但某些最短路问题些最短路问题(如道路不能整齐分段者如道路不能整齐分段者)构造动态规构造动态规划方程比较困准、而图论方法则比较有效。划方程比较困准、而图论方法则比较有效。n最短路问题：在一个赋权图最短路问题：在一个赋权图G上，给定两个顶上，给定两个顶点点u和和v，在所有连接顶点，在所有连接顶点u和和v的路中，寻找路的路中，寻找路长最短的路（称为长最短的路（称为u和和v最短路最短路.）nu和和v最短路的路长也称为最短路的路长也称为u和和v的的距离距离-d(u,v).有些最短路问题也可以求网络中某指定点到其余所有些最短路问题也可以求网络中某指定点到其余所有结点的最短路、

41、或求网络中任意两点间的最短路有结点的最短路、或求网络中任意两点间的最短路.第64页/共141页一、网络无负权的最短路一、网络无负权的最短路本算法由本算法由Dijkstra于于1959年提出，可用于求解指定年提出，可用于求解指定两点间的最短路，或从指定点到其余各点的最短两点间的最短路，或从指定点到其余各点的最短路，目前被认为是求无负权网络最短路问题的最路，目前被认为是求无负权网络最短路问题的最好方法。好方法。算法的基本思路基于以下算法的基本思路基于以下原理原理：若序列若序列vs,v1,vn是从是从vs到到vn的最短路，的最短路，则序列则序列vs,v1,vn-1必为从必为从vs到到vn-1的最短路

42、。的最短路。Dijkstra算法算法第65页/共141页Dijkstra算法算法基本思想基本思想Dijkstra算法的基本思想是从算法的基本思想是从vs出发，逐步地向外出发，逐步地向外探寻最短路，采用探寻最短路，采用标号法标号法。执行过程中，与每个点对应，记录下一个数（称执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从为这个点的标号），它或者表示从vs到该点的最短到该点的最短路长（称为路长（称为P标号标号），或者是从），或者是从vs到该点的最短路到该点的最短路长的上界（称为长的上界（称为T标号标号）。）。算法每一步都把某个顶点的算法每一步都把某个顶点的T 标号改为标号改

43、为P 标号，标号，当当终点终点vt得到得到P 标号时，计算结束。最多标号时，计算结束。最多n-1步。步。第66页/共141页计算实例：计算实例：求连接求连接vs、vt的最短路的最短路.0-P T-开始，给开始，给vs以以P标号，标号，P(vs)=0,其余各点给其余各点给T 标号标号T(vi)=+.227414731555vsv2v1vtv4v5v3Step1:迭迭代代1Dijkstra算法算法基本步骤：基本步骤：第67页/共141页0-若若vi 为刚得到为刚得到P标号的点标号的点,考虑这样的点考虑这样的点vj:(vi,vj)E且且vj为为T 标号。标号。227414731555vsv2v1vt

44、v4v5v3Step2:对对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+,0+2=2第68页/共141页0-比较所有具有比较所有具有T标号的点，把最小者改为标号的点，把最小者改为P 标号，标号，227414731555vsv2v1vtv4v5v3Step3:245即即 P(vi)=minT(vi).当存在两个以上最小者时当存在两个以上最小者时,可同时改为可同时改为P 标号。若全标号。若全部点

45、为部点为P标号标号,则停止。否则用则停止。否则用vi代替代替vi转转step2.-2迭迭代代1全部全部T标号中标号中,T(v1)最小最小,令令P(v1)=2,记录路径记录路径(vs,v1).第69页/共141页0-2-5-4227414731555vsv2v1vtv4v5v394若若vi 为刚得到为刚得到P标号的点标号的点,考虑这样的点考虑这样的点vj:(vi,vj)E且且vj为为T 标号。标号。Step2:对对vj的的T 标号进行如下更改标号进行如下更改T(vj)=minT(vj),P(vi)+wij迭迭代代2考察考察v1,T(v4)=minT(v4),P(v1)+w14=min+,2+7=

46、9T(v2)=minT(v2),P(v1)+w12=min5,2+2=4第70页/共141页0-2-4-9-4227414731555vsv2v1vtv4v5v344迭迭代代2比较所有具有比较所有具有T标号的点，把最小者改为标号的点，把最小者改为P 标号，标号，Step3:即即 P(vi)=minT(vi).-全部全部T 标号中标号中,T(v2),T(v3)最小最小,令令P(v2)=4,P(v3)=4,记录路径记录路径(v1,v2),(v1,v4),.第71页/共141页0-2-4-9-4-227414731555vsv2v1vtv4v5v37迭迭代代3若若vi 为刚得到为刚得到P标号的点标号

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

48、样的点vj:(vi,vj)E且且vj为为T 标号。标号。Step2:对对vj的的T 标号进行如下更改标号进行如下更改T(vj)=minT(vj),P(vi)+wij814第74页/共141页0-2-4-8-147-4-227414731555vsv2v1vtv4v5v3迭迭代代48-比较所有具有比较所有具有T标号的点，把最小者改为标号的点，把最小者改为P 标号，标号，Step3:即即 P(vi)=minT(vi).第75页/共141页0-2-4-8-147-4-227414731555vsv2v1vtv4v5v3迭迭代代513若若vi 为刚得到为刚得到P标号的点标号的点,考虑这样的点考虑这样的

49、点vj:(vi,vj)E且且vj为为T 标号。标号。Step2:对对vj的的T 标号进行如下更改标号进行如下更改T(vj)=minT(vj),P(vi)+wij第76页/共141页0-2-4-8-137-4-227414731555vsv2v1vtv4v5v3迭迭代代513比较所有具有比较所有具有T标号的点，把最小者改为标号的点，把最小者改为P 标号，标号，Step3:即即 P(vi)=minT(vi).当存在两个以上最小者时当存在两个以上最小者时,可同时改为可同时改为P 标号。若全标号。若全部点为部点为P标号标号,则停止。否则用则停止。否则用vi代替代替vi转转step2.-第77页/共14

50、1页0-2-4-8-13-7-4-227414731555vsv2v1vtv4v5v3最短路最短路nDijkstra算法不仅找到了所求最短路，而且找到算法不仅找到了所求最短路，而且找到了从了从vs点到其他所有顶点的最短路；这些最短点到其他所有顶点的最短路；这些最短路构成了图的一个连通无圈的支撑子图，即图路构成了图的一个连通无圈的支撑子图，即图的一个支撑树。的一个支撑树。第78页/共141页开始，给开始，给vs以以P标号，标号，P(vs)=0,其余各点给其余各点给T 标号标号T(vi)=+.Step1:若若vi 为刚得到为刚得到P标号的点标号的点,考虑这样的点考虑这样的点vj:(vi,vj)E且