《图与网络计划》PPT课件.ppt

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

1、第一节：第一节：引论引论第二节：图的基本概念第二节：图的基本概念第三节：树图第三节：树图第四节：最短路问题第四节：最短路问题第五节：最大流问题第五节：最大流问题第六节：中国邮路问题第六节：中国邮路问题第七节：网络计划第七节：网络计划第九章第九章图与网络计划图与网络计划图图论论引论引论1.Euler回路问题回路问题2.Ramsey问题问题近代图论的历史可追溯到近代图论的历史可追溯到18世纪的七桥问题世纪的七桥问题穿过穿过Knigsberg城的七座桥，要求每座桥通过一次且仅通过一次。城的七座桥，要求每座桥通过一次且仅通过一次。这就是著名的这就是著名的“哥尼斯堡哥尼斯堡 7 桥桥”难题。难题。Eul

2、er1736年证明了不年证明了不可能存在这样的路线。可能存在这样的路线。图的基本概念与模型KnigsbergKnigsberg桥对应的图桥对应的图Euler回路问题回路问题Pregel“哥尼斯堡哥尼斯堡7桥桥”难题最终在难题最终在1736年由数学家年由数学家Euler的一篇论文的一篇论文给予了完满的解决，这是图论的第一篇论文。在后来的两百年间给予了完满的解决，这是图论的第一篇论文。在后来的两百年间图论的发展是缓慢的，直到图论的发展是缓慢的，直到1936年匈牙利数学家年匈牙利数学家O.Knig写出写出了了图论的第一本专著有限图与无限图的理论。图论的第一本专著有限图与无限图的理论。四色猜想四色猜想

3、图论的历史上最具有传奇色彩的问题也许要图论的历史上最具有传奇色彩的问题也许要数著名的数著名的“四色猜想四色猜想”了了历史上许许多历史上许许多多数学猜想之一。多数学猜想之一。世界近代三大数学难题：费马最后猜想、哥世界近代三大数学难题：费马最后猜想、哥德巴赫猜想和德巴赫猜想和“四色四色”猜想。它描述对一张猜想。它描述对一张地图着色的问题，在一维直线上用两种颜色地图着色的问题，在一维直线上用两种颜色可以区分任意多不同线段，在二维平面内至可以区分任意多不同线段，在二维平面内至少需要四种颜色可以区分任意多区域（当然少需要四种颜色可以区分任意多区域（当然最简单的情况是二色，如国际象棋棋盘）；最简单的情况是

4、二色，如国际象棋棋盘）；在三维空间内至少需要八种颜色可以区分任在三维空间内至少需要八种颜色可以区分任意多的立体，（最简单的情况还是二色，如意多的立体，（最简单的情况还是二色，如NaCl）Euler回路问题回路问题 A C D BRamsey问题问题 vjvtvkvi vjvtvkRamsey问题问题vi vjvtvkRamsey问题问题vi vjvtvkRamsey问题vi第一节：图的基本概念第一节：图的基本概念1.图的概念图的概念2.关联的概念关联的概念3.简单图、完全图和二分图简单图、完全图和二分图4.连通与回路连通与回路5.部分图与子图部分图与子图1.1.图的概念图的概念（1 1）图：图

5、：图是点和边的集合，记作图是点和边的集合，记作 G=G=（V V，E E）；其中）；其中V V是点的集合，是点的集合，E E是边的是边的集合。集合。（2 2）有向图：有向图：有向图是点和弧的集合，记作有向图是点和弧的集合，记作G=G=（V V，U U）；）；U U是弧的集合，弧是两点的有序是弧的集合，弧是两点的有序偶对。偶对。（3 3）赋权图：赋权图：图中的每一条边均有一个权数图中的每一条边均有一个权数w wijij相对应的图称为赋权图。相对应的图称为赋权图。图的基本概念(v1)赵赵(v2)钱钱孙孙(v3)李李(v4)周周(v5)吴吴(v6)陈陈(v7)e2e1e3e4e5(v1)赵赵(v2)

6、钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来例如：在一个人群中，对相互认识这个关系我们可以用图来表示。表示。1.1.图的概念图的概念298653图图有向图有向图赋权图赋权图2.关联的概念关联的概念(1)(1)端点和关联边：端点和关联边：若有边若有边e e可表示为可表示为e=(ve=(vi i,v,vj j),则则 称称v vi i和和v vj j为边为边e e的两个端点的两个端点；边；边e e为为v vi i和和v vj

7、 j的关联边的关联边。(2)(2)相邻：相邻：若点若点v vi i和和v vj j与同一条边相关联，则称与同一条边相关联，则称v vi i和和v vj j相邻；相邻；若边若边e ei i和和e ej j具有一个公共的端具有一个公共的端点，则称点，则称e ei i和和 e ej j相邻相邻。(1)(1)(3)(3)环：环：若边若边e ei i的两个端点相互重合，则称的两个端点相互重合，则称e ei i为环为环。如图如图9-59-5中，中，v v2 2和和v v5 5是边是边e e4 4的两个端点，的两个端点，e e4 4为为v v2 2和和v v5 5的关联边；的关联边；v v2 2和和v v5

8、 5是边是边e e4 4的两的两个端点，边个端点，边e e8 8是是v v4 4和和v v5 5的关联边。的关联边。图9-5v v1 1e e2 2e e4 4v v2 2e e6 6e e5 5v v3 3e e7 7v v4 4v v5 5e e3 3e e1 1e e8 8v v4 4和和v v5 5均与均与e e8 8相关联，所以相关联，所以v v4 4和和v v5 5相邻。相邻。e e6 6和和e e7 7有一个公共的端点有一个公共的端点v v3 3，e e6 6和和e e7 7相邻。相邻。e e1 1即为一个环即为一个环 图9-5v v1 1e e2 2e e4 4v v2 2e

9、e6 6e e5 5v v3 3e e7 7v v4 4v v5 5e e3 3e e1 1e e8 82.2.关联的概念关联的概念(4)多重边：多重边：若若vi,和和vj两点之间有两条或两条以两点之间有两条或两条以上的边存在上的边存在,则则 称称vi i,和和vj j两点之间有多重边。两点之间有多重边。(5)(5)点的度（或次）：点的度（或次）：与点与点vi i相关联的边的数相关联的边的数量称为点量称为点vi i的度（或次）；度（或次）为偶数的度（或次）；度（或次）为偶数的点称为的点称为偶点偶点，度（或次）为奇数的点称为，度（或次）为奇数的点称为奇奇点点；度（或次）为；度（或次）为1 1的点

10、称为的点称为悬挂点悬挂点；度（或；度（或次）为次）为0 0的点称为的点称为孤立点孤立点。图的度图的度:一个图的度等于各点的度之和。一个图的度等于各点的度之和。v3e7e4e8e5e6e1e2e3v1v2v4v5v v2 2和和v v5 5之间存在之间存在e e4 4和和e e5 5二条边，所以称二条边，所以称v v2 2和和v v5 5之之间具有二重边间具有二重边 d(vd(v1 1)=4)=4、d(vd(v2 2)=4)=4、d(vd(v5 5)=5)=5、d(vd(v4 4)=1)=1。v v5 5和和v v4 4为奇点为奇点 ,v,v4 4为悬挂点为悬挂点,v,v1 1、v v2 2、v

11、 v3 3为偶为偶点点 图9-5v v1 1e e2 2e e4 4v v2 2e e6 6e e5 5v v3 3e e7 7v v4 4v v5 5e e3 3e e1 1e e8 82.关联的概念关联的概念图9-5v v1 1e e2 2e e4 4v v2 2e e6 6e e5 5v v3 3e e7 7v v4 4v v5 5e e3 3e e1 1e e8 8定理定理1 任何图中，顶点度数之和等于所有边数的任何图中，顶点度数之和等于所有边数的2倍。倍。定理定理2 任何图中，度为奇数的顶点必为偶数个。任何图中，度为奇数的顶点必为偶数个。3.简单图、完全图和二分图简单图、完全图和二分

12、图(1)简单图：无环无多重边的图称为简单图。简单图：无环无多重边的图称为简单图。(2)完全图：任意一对顶点均相邻的简单图称为完全图：任意一对顶点均相邻的简单图称为完全图。完全图。(3)二分图：若图的点集二分图：若图的点集V能被分成二个不相交能被分成二个不相交的子集的子集V1和和V2，使得同一个集合中的任何两点，使得同一个集合中的任何两点均不相邻，则称此图为二分图。均不相邻，则称此图为二分图。简单图、完全图和二分图简单图、完全图和二分图简单图简单图二分图二分图完全图完全图图的基本概念图的基本概念 二分图（偶图）二分图（偶图）图图G=(V,E)的点集的点集V可以分为两各非空子集可以分为两各非空子集

13、X，Y，集，集XY=V,XY=,使得同一集合中任意两个顶点均不使得同一集合中任意两个顶点均不相邻，称这样的图为偶图。相邻，称这样的图为偶图。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为二分图，明显为二分图，(b)也是二分图，但不明显，改画为也是二分图，但不明显，改画为(c)时可以清楚看出。时可以清楚看出。4.连通与回路连通与回路(1)链：链是相关联的点和边的交替序列；边不重链：链是相关联的点和边的交替序列；边不重复的链称为简单链；边和点均不重复的链称为复的链称为简单链；边和点均不重复的链称为初等链。初等链。(2)连通：任意一对顶点之间均有链相连的图称为

14、连通：任意一对顶点之间均有链相连的图称为连通图。连通图。(3)回路：链的首尾重合便构成了回路；简单链的回路：链的首尾重合便构成了回路；简单链的首尾重合便构成了简单回路；初等链的首尾重首尾重合便构成了简单回路；初等链的首尾重合便构成了初等回路。合便构成了初等回路。4.连通与回路连通与回路e5v1v5v4v3v2e1e4e3e2e6e8v4到到v5的一条链的一条链：v4 e6-v2-e2-v1-e3-v3-e5-v2-e2-v1-e1-v1-e3-v3-e8-v5v4到到v5的一条简单链的一条简单链：v4 e6-v2-e2-v1-e3-v3-e5-v2 e4-v3-e8-v5v4到到v5的一条初等

15、链的一条初等链：v4 e6-v2-e2-v1-e3-v3-e8-v55.部分图与子图部分图与子图(1)部分图：部分图：图图G1=（V1，E1）和图和图G2=（V2，E2），若存在），若存在V1=V2、E1 E2，则称，则称G1为为G2的部分图。的部分图。(2)子图：子图：图图G1=（V1，E1）和图）和图G2=（V2，E2），若存在），若存在V1 V2、E1 E2，则称，则称G1为为G2的子图。的子图。5.5.部分图与子图部分图与子图图图子图子图部分图部分图图的基本概念与模型图的模型应用例例9.1 有甲有甲,乙乙,丙丙,丁丁,戊戊,己己6名运动员报名参加名运动员报名参加A,B,C,D,E,F

16、6个项目的比赛。下表中打个项目的比赛。下表中打的是各运动员报告参加的比赛项的是各运动员报告参加的比赛项目。问目。问6个项目的比赛顺序应如何安排，做到每名运动员都个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。不连续地参加两项比赛。ABCDEF甲乙丙丁戊己图的基本概念与模型解：用图来建模。把比赛项目作为研究对象，用解：用图来建模。把比赛项目作为研究对象，用点表示。如果点表示。如果2个项目有同一名运动员参加，在个项目有同一名运动员参加，在代表这两个项目的点之间连一条线，可得下图。代表这两个项目的点之间连一条线，可得下图。ABCDEF在图中找到一个点在图中找到一个点序列，使得依次排

17、序列，使得依次排列的两点不相邻，列的两点不相邻，即能满足要求。如：即能满足要求。如：1)A,C,B,F,E,D2)D,E,F,B,C,A图的基本概念与模型一一个个班班级级的的学学生生共共计计选选修修A A、B B、C C、D D、E E、F F六六门门课课程程，其其中中一一部部分分人人同同时时选选修修D D、C C、A A，一一部部分分人人同同时时选选修修B B、C C、F F，一一部部分分人人同同时时选选修修B B、E E，还还有有一一部部分分人人同同时时选选修修A A、B B，期期终终考考试试要要求求每每天天考考一一门门课课，六六天天内内考考完完，为为了了减减轻轻学学生生负负担担，要要求求

18、每每人人都都不不会会连连续续参参加加考考试试，试试设设计计一一个个考考试试日程表。日程表。思考题思考题思考题思考题图的基本概念与模型思考题解答：以每门课程为一个顶点，共同被选修的以每门课程为一个顶点，共同被选修的课程之间用边相连，得图，按题意，相邻顶课程之间用边相连，得图，按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应点对应课程不能连续考试，不相邻顶点对应课程允许连续考试，因此，作图的补图，问课程允许连续考试，因此，作图的补图，问题是在图中寻找一条哈密顿道路，如题是在图中寻找一条哈密顿道路，如C C C CE E E EA A A AF F F FD D D DB B B B，就是一个符

19、合要求的考试课程，就是一个符合要求的考试课程表。表。图的基本概念与模型A AF FE ED DC CB B图的基本概念与模型A AF FE ED DC CB B图的基本概念与模型图的矩阵描述：图的矩阵描述：如何在计算机中存储一个图呢？现在已有很多存如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同一个图，图的矩阵表示也根据所关心的问题不同而有：而有：邻接矩阵、关联矩阵、权矩阵等。邻接矩阵、关联矩阵、权矩阵等。1.邻接矩阵邻接矩阵对于图对于图G=（V，E），），|V|=n，|E|

20、=m，有，有n n阶方阶方矩阵矩阵A=(aij)n n，其中其中图的基本概念与模型v5v1v2v3v4v64332256437例例9.2 下图所表示的图可以构造邻接矩阵下图所表示的图可以构造邻接矩阵A如下如下对于赋权图对于赋权图G=(V,E),其中边其中边 有权有权 ,构造矩阵构造矩阵B=(bij)n n 其中：其中：图的基本概念与模型2.2.2.2.关联矩阵关联矩阵关联矩阵关联矩阵对于图对于图G=(V,E),|V|=n,|E|=m,G=(V,E),|V|=n,|E|=m,有有m m n n阶阶矩阵矩阵M=M=(m(mijij)m m n n，其中其中:3.3.权矩阵权矩阵权矩阵权矩阵图的基本

21、概念与模型1 0 1 0 0 0 0 0 0 0 0 01 1 0 0 1 0 0 0 0 0 0 00 1 0 0 0 1 1 1 0 0 0 00 0 0 0 0 0 0 0 1 0 0 10 0 1 1 1 1 0 0 0 0 0 00 0 0 0 0 0 0 0 1 1 0 00 0 0 0 0 0 0 0 0 1 1 10 0 0 1 0 0 1 1 0 0 0 0v1v2v3v4v5v6v7v8e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4例例9.3 下图所表示的图

22、可以构造邻接矩阵下图所表示的图可以构造邻接矩阵M如下如下:M=（mij）=图的基本概念与模型v5v1v2v3v4v64332256437例例9.4 下图所表示的图可以构造权矩阵下图所表示的图可以构造权矩阵B如下如下:第二节：树图第二节：树图1.树的概念树的概念2.树的性质树的性质3.部分树部分树4.最小部分树最小部分树5.最小部分树的求解最小部分树的求解树与图的最小树树与图的最小树树是图论中结构最简单但又十分重要的图。在自然和社会领树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。域应用极为广泛。例例9.4 乒乓求单打比赛抽签后，可用图来表示相遇情况，如乒乓求单打比赛抽签后，

23、可用图来表示相遇情况，如下图所示。下图所示。AB CDEF GH运动员运动员树与图的最小树例例9.5某企业的组织机构图也可用树图表示。某企业的组织机构图也可用树图表示。厂长厂长人事科人事科财务科财务科总工总工程师程师生产副生产副厂长厂长经营副经营副厂长厂长开发科开发科技术科技术科生产科生产科设备科设备科供应科供应科销售科销售科检验科检验科动力科动力科1.树的概念树的概念树：树是不含回路的连通图。树：树是不含回路的连通图。树枝：树图的各条边称为树枝树枝：树图的各条边称为树枝2.树的性质树的性质 树：无圈的连通图即为树树：无圈的连通图即为树性质性质1：树中任意两个顶点之间，恰有且仅有一条链：树中任

24、意两个顶点之间，恰有且仅有一条链。性质性质2：树连通，但去掉任一条边，必变为不连通。：树连通，但去掉任一条边，必变为不连通。性质性质3：树无回圈，但不相邻的两个点之间加一条边，恰：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。得到一个圈。性质性质4：n 个顶点的树必有个顶点的树必有n-1 条边。条边。性质性质5：任何树中必存在度为：任何树中必存在度为1的点。的点。树中至少存在两个悬挂点。树中至少存在两个悬挂点。v1v2v3v4v5v63.部分树部分树部分树：部分树：如果图如果图G G的部分图的部分图T T是一棵树，则称是一棵树，则称T T是是G G的部分树的部分树。一般图。一般图G含有

25、多个部分树。含有多个部分树。图G图G的部分树T1图G的部分树T24.最小部分树最小部分树最小部分树：最小部分树：在赋权图在赋权图G的所有部分树中，树枝权的所有部分树中，树枝权数和最小的部分树称为最小部分树（或最小支撑数和最小的部分树称为最小部分树（或最小支撑树）。树）。图G图图G的部分树的部分树（15）图图G的最小部分树的最小部分树（8）23169223192312树与图的最小树a ab bc cf fe ed dh hg gb bf fe ed d树与图的最小树a ab bc cf fe ed dh hg gb bf fd dg g树与图的最小树b bc ce ed da ab bc cf

26、fe ed dh hg g树与图的最小树a ab bc ch ha ab bc cf fe ed dh hg g树与图的最小树a af fd dg ga ab bc cf fe ed dh hg g5.最小部分树的求解最小部分树的求解（1）破圈破圈（回路）法（回路）法（2）避圈避圈（回路）法（回路）法（3）顺序生枝法顺序生枝法n破圈法破圈法:在连通图中任意选取一个回路，从在连通图中任意选取一个回路，从该回路中去掉一条权数最大的边（如果权该回路中去掉一条权数最大的边（如果权数最大的边不唯一，则任意选取其中一条）数最大的边不唯一，则任意选取其中一条）。在余下的图中，重复这一步骤，直至得。在余下的图

27、中，重复这一步骤，直至得到一个不含回路的连通图（有个顶点条边）到一个不含回路的连通图（有个顶点条边），该连通图便是最小部分树。，该连通图便是最小部分树。求树的方法：破圈法和避圈法求树的方法：破圈法和避圈法树与图的最小树破圈法破圈法树与图的最小树部分树部分树树与图的最小树避圈法避圈法避圈法避圈法v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5树与图的最小树破圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数边数n-1=5赋权

28、图中求最小树的方法：破圈法和避圈法树与图的最小树v1v2v3v4v5v643521得到最小树：得到最小树：Min C(T)=15（1）破圈（回路）法）破圈（回路）法227541435715ASBDCET（1）破圈（回路）法）破圈（回路）法227541435715ASBDCET（1）破圈（回路）法）破圈（回路）法22741435715ASBDCET（1）破圈（回路）法）破圈（回路）法22741435715ASBDCET（1）破圈（回路）法）破圈（回路）法2271435715ASBDCET（1）破圈（回路）法）破圈（回路）法2271435715ASBDCET（1）破圈（回路）法）破圈（回路）法22

29、1435715ASBDCET（1）破圈（回路）法）破圈（回路）法221435715ASBDCET（1）破圈（回路）法）破圈（回路）法22135715ASBDCET（1）破圈（回路）法）破圈（回路）法22135715ASBDCET（1）破圈（回路）法）破圈（回路）法2213715ASBDCET（1）破圈（回路）法）破圈（回路）法2213715ASBDCET（1）破圈（回路）法）破圈（回路）法221315总权数和为总权数和为14ASBDCETn避圈法避圈法:从图中任选一点从图中任选一点vi，让其他各点均，让其他各点均属于属于；从沟通集合；从沟通集合V和和的连线中找出的连线中找出最小边，使之包含在最

30、小部分树内。不妨假最小边，使之包含在最小部分树内。不妨假设最小边为（设最小边为（vi,vj）令）令，其他各，其他各点均属于点均属于；重复寻找从集合；重复寻找从集合V到到的的最小边并使之包含在最小部分树内，直到图最小边并使之包含在最小部分树内，直到图中的所有点都包含在集合中的所有点都包含在集合V中为止。中为止。树与图的最小树避圈法:去掉去掉G中所有边，得到中所有边，得到n个孤立点；然后个孤立点；然后加边。加边。加边的原则为：从最短边开始添加，加边的加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通过程中不能形成圈，直到点点连通(即即:n-1条条边边)。5v1v2v3v4v5v6

31、843752618树与图的最小树v1v2v3v4v5v6435215v1v2v3v4v5v6843752618Min C(T)=15（2）避圈（回路）法）避圈（回路）法2275414357150ASBDCET（2）避圈（回路）法）避圈（回路）法227541435715ASBDCET（2）避圈（回路）法）避圈（回路）法2275414357150ASBDCET（2）避圈（回路）法）避圈（回路）法227541435715ASBDCET（2）避圈（回路）法）避圈（回路）法227541435715ASBDCET（2）避圈（回路）法）避圈（回路）法227541435715ASBDCET（2）避圈（回路）法

32、）避圈（回路）法227541435715ASBDCET（2）避圈（回路）法）避圈（回路）法227541435715ASBDCET（2）避圈（回路）法）避圈（回路）法227541435715ASBDCET（2）避圈（回路）法）避圈（回路）法227541435715ASBDCET（2）避圈（回路）法）避圈（回路）法227541435715ASBDCET（2）避圈（回路）法）避圈（回路）法227541435715ASBDCET树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636练习：练习：练习：

33、练习：应用破圈法求最小树应用破圈法求最小树应用破圈法求最小树应用破圈法求最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v

34、6v615159 9161625253 3282817174 41 12323树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 9161625253 3282817174 41 12323树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 9161625253 3282817174 41 12323树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 4

35、1 12323树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 317174 41 12323min=1+4+9+3+17+23=57树与图的最小树练习：练习：练习：练习：应用避圈法求最小树应用避圈法求最小树

36、应用避圈法求最小树应用避圈法求最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625

37、253 3282817174 41 123233636树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636min=1+4+9+3+17+23=57min=1+4+9+3+17+2

38、3=57nKruskal顺序生枝法顺序生枝法:首先将图中的所有边按首先将图中的所有边按权的大小从小到大的进行排列，在确保不权的大小从小到大的进行排列，在确保不出现回路的前提下，将依次排列的边逐一出现回路的前提下，将依次排列的边逐一绘出；若在增加某条边时出现了回路，则绘出；若在增加某条边时出现了回路，则排除该边并继续寻找下一条边。排除该边并继续寻找下一条边。（3）顺序生枝法）顺序生枝法 现有五口油井，相互之间的距离（千米）如下现有五口油井，相互之间的距离（千米）如下表所示，问应如何铺设输油管线使输油管长度最短。表所示，问应如何铺设输油管线使输油管长度最短。为便于检修和计量，输油管只允许在井口处分

39、路。为便于检修和计量，输油管只允许在井口处分路。到到从从w2w3w4w5w11.32.10.90.7w20.91.81.2w32.61.7w40.7（3）顺序生枝法）顺序生枝法（1）排序：按井距从小到大排列）排序：按井距从小到大排列d15=d45=0.7d14=d23=0.9d25=1.2d12=1.3d35=1.7d24=1.8d13=2.1d34=2.6（2）生枝：按排序顺序生枝，如果某生枝形成）生枝：按排序顺序生枝，如果某生枝形成回路，略去该枝并继续直到生成回路，略去该枝并继续直到生成P-1条边。条边。（3）顺序生枝法）顺序生枝法w5w4w10.70.7（3）顺序生枝法）顺序生枝法w5w

40、4w10.70.7（3）顺序生枝法）顺序生枝法w5w4w10.70.7w3w20.9（3）顺序生枝法）顺序生枝法w5w4w10.70.7w3w20.91.2最短路问题如何用最短的线路将三部电话连起来？如何用最短的线路将三部电话连起来？此问题可抽象为设此问题可抽象为设ABC为等边三角形，连接为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如其中最短路线者显然是二边之和（如AB AC）。）。ABC最短路问题ABCP但若增加一个周转站（新点但若增加一个周转站（新点P P），连接），连接4 4点的新网络的最短路点的

41、新网络的最短路线为线为PAPAPBPBPCPC。最短新路径之长。最短新路径之长N N比原来只连三点的最短路比原来只连三点的最短路径径O O要短。这样得到的网络不仅比原来节省材料，而且稳定性要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。也更好。最短路问题问题描述：问题描述：就是从给定的网络图中找出一点到各点就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路或任意两点之间距离最短的一条路.有些问题，如选址、管道铺设时的选线、有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因

42、的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。此这类问题在生产实际中得到广泛应用。最短路问题最短路问题例例渡河游戏渡河游戏一老汉带了一只狼、一只羊、一老汉带了一只狼、一只羊、干草干草想要从南岸想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃吃羊，羊就要吃干草干草，问应该怎样安排渡河，才能，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就

43、可以用求最短路方法解决。数最少？这个问题就可以用求最短路方法解决。最短路问题最短路问题定义：定义：1）人）人M（Man），狼），狼W（Wolf），），羊羊G（Goat），），草草H（Hay）2）点点vi表示河岸的状态表示河岸的状态3）边边ek表示由状态表示由状态vi经一次渡河到经一次渡河到状态状态vj4）权权边边ek上的权定为上的权定为1我们可以得到下面的加权有向图我们可以得到下面的加权有向图最短路问题状态说明：状态说明：v1,u1=(M,W,G,H);v2,u2=(M,W,G);v3,u3=(M,W,H);v4,u4=(M,G,H);v5,u5=(M,G)此游戏转化为在下面的二分图中求从此游

44、戏转化为在下面的二分图中求从 v1 到到 u1 的最短路问题。的最短路问题。v1v2v3v4v5u5u4u3u2u1第三节：最短路问题第三节：最短路问题1.求图中某一点到其他各点最短路的求图中某一点到其他各点最短路的Dijkstra标号算法标号算法2.求图中所有点之间最短路的求图中所有点之间最短路的Floyd矩阵算法矩阵算法令nDijkstra算法算法vi与与vj不相邻不相邻vi与与vj相邻相邻vi与与vj相等相等n若用若用L Lijij代表从点到点的最短路，那么求代表从点到点的最短路，那么求从点从点i i到点到点j j的最短路的的最短路的DijkstraDijkstra算法的算法的具体步骤可

45、概括如下：具体步骤可概括如下：从点从点s s出发，因出发，因Lss=0 ，将，将“0 0”标注在旁的小标注在旁的小方框内，表示点方框内，表示点s s已标号；已标号；从点从点s s出发，找出与点出发，找出与点s s相邻且距离最小的点相邻且距离最小的点r r，将，将Lsr=Lss+Lsr的值标注在点的值标注在点r r旁的小方框内，旁的小方框内，表明点表明点r r也已标号；也已标号；Dijkstra算法算法找出所有与已标号点相邻的末标号点，若找出所有与已标号点相邻的末标号点，若Lsp=minLss+Lsp,Lsr+Lrp，则给点，则给点p标号，标号，即将即将Lsp的值标注在的值标注在p旁的小方框内；

46、旁的小方框内；重复第三步，一直到重复第三步，一直到t t点得到标号为止；此点得到标号为止；此时各点小方框内的标注值就是时各点小方框内的标注值就是s s点到该点的点到该点的最短路。最短路。Dijkstra算法算法227541435715SABCDEF0|第一步：从点第一步：从点s出发，对其标出发，对其标“0”，令令，其他各点均属于，其他各点均属于；227541435715SABCDEF0故故A点得到标号点得到标号“2”，令令其余各点均属于其余各点均属于2|第二步：与第二步：与s点相邻的未标号点有点相邻的未标号点有A、B、C三个点，又因：三个点，又因：，227541435715SABCDEF02|

47、第三步：与标号点第三步：与标号点s和和A相邻的未相邻的未标号点有标号点有B、C、E三个点，又因：三个点，又因：故故B、C两点同时得到标号两点同时得到标号“4”，其余各点均属于其余各点均属于44227541435715SABCDEF024依此类推，直到所有的点均得到标号依此类推，直到所有的点均得到标号 478132.求图中所有点之间求图中所有点之间最短路最短路的的Floyd矩阵算法矩阵算法dij(0)=wij (if i与与 j相邻相邻)dij(0)=0 (if i=j )dij(0)=(if i与与 j不相邻不相邻)dij=D(0)=dij(0)代表从代表从i直接到达直接到达j的距离矩阵的距离

48、矩阵2.求图中所有点之间求图中所有点之间最短路最短路的的Floyd矩阵算法矩阵算法D(0)=dij代表从代表从i i直接到达直接到达 j j的距离矩阵的距离矩阵从从i i到达到达 j j的最短路并不局限在直接到达，的最短路并不局限在直接到达，两点之间可以有两点之间可以有1 1、2 2、个中间点。个中间点。先考虑先考虑i i和和 j j两点之间可以有两点之间可以有1 1个中间点个中间点的情况：的情况：dij(1)=mindik(0)+dkj(0)k=1,2,Pikjk2.求图中所有点之间最短路的求图中所有点之间最短路的Floyd矩阵算法矩阵算法再考虑再考虑i和和j两点之间可以有两点之间可以有3个

49、中间点的情个中间点的情况：况：dij(2)=mindik(1)+dkj(1)k=1,2,Pikjnm2.求图中所有点之间最短路的求图中所有点之间最短路的Floyd矩阵算法矩阵算法i和和j两点之间可以有两点之间可以有2n-1个中间点的情况：个中间点的情况：dij(n)=mindik(n-1)+dkj(n-1)k=1,2,P结束条件：结束条件：或或即即2.求图中所有点之间最短路的求图中所有点之间最短路的Floyd矩阵算法矩阵算法SACBEDT227541435715SACBDETSACB EDTSACBEDT227541435715SACBDETSACB EDT227541435715SACBDE

50、T227541435715SACBDET最短路问题例例设备更新问题。某公司使用一台设备，在每年年初，设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：使