《图论初步》PPT课件.ppt

《《图论初步》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图论初步》PPT课件.ppt（92页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、图论初步图论初步第六讲第六讲图论初步图论初步6.1 引言引言 图论是运筹学的一个经典和重要的分支，它起源于欧拉（Euler）对七桥问题的抽象和论证。1936年，匈牙利数学家柯尼希（Knig）出版了图论的第一部专著有限图与无限图理论，竖立了图论发展的第一座里程碑。此后，图论进入发展与突破的快车道，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。图论中所谓的“图”是指某类具体事物和这

2、些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。引例6.1.1 最短路问题（SPPshortest path problem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。引例6.1.2 中国邮递员问题（CPPchinese po

3、stman problem）一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。引例6.1.3 旅行商问题（TSPtraveling salesman problem）一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。引例6.1.4 指派问题（assignment problem）一家公司经理准备安排名员工去完成项

4、任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？引 例 6.1.5 运 输 问 题（transportation problem）某种原材料有个产地，现在需要将原材料从产地运往个使用这些原材料的工厂。假定个产地的产量和家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？6.2 图的基本概念图的基本概念 6.2.1 图的定义 定义6.2.1 称数学结构G=V(G),E(G),G 为一个图，其中V(G)=v1,v2,vn 称为图 G的顶顶点点集集（vertex set）或节点

5、集（node set），V(G)中的每一个元素 vi（i=1,2,n）称为该图的一个顶点顶点（vertex）或节点（node）；E(G)=e1,e2,em 称为图 G 的边边集集（edge set），E(G)中的每一个元素 ek（即V(G)中某两个元素vi,vj 的无序对）记为 ek=(vi,vj)或 ek=vivj=ek=vjvi（k=1,2,m），被称为该图的一条从 vi 到 vj 的边边（edge）；G是从 E(G)到V(G)V(G)的一个映射，它指定 E(G)中的每条边与 V(G)中的点组成的无序点对相对应。若用小圆点表示点集 V(G)中的点，连线表示边集 E(G)中的边，则可用图形将

6、图表示出来，称之为图的图形。我们常用图的图形代表图本身。例6.2.1 设 V=v1,v2,v3,v4，E=e1,e2,e3,e4,e5，：EVV 定义为(e1)=v1v2，(e2)=v2v3，(e3)=v2v3，(e4)=v3v4，(e5)=v4v4，则G=V,E 是一个图，其图形如图所示。图 6.2.1 例6.2.2 设 V=v1,v2,v3,v4，E=v1v2,v1v2,v2v3，则G=V,E 是一个图，其图形如图所示。图 6.2.2 定义6.2.2 设e=uv 为图 G 的一条边，我们称 u，v 是 e 的端端点点，u 与 v 相相邻邻，边 e 与点 u（或v）相关关联联；称 u 是 e

7、 的起点，v 是 e 的终点。若两条边 e1 与 e2 有共同的端点，则称边 e1与 e2 相邻；称有相同起点和终点的两条边为重重边边；称两端点均相同的边为环环；称不与任何边相关联的点为孤立点孤立点。无环且无重边的图称之为简单图简单图。例 6.2.1 和例 6.2.2 都不是简单图，因为例6.2.1 中既含重边（e2 与 e3）又含环（e5），而例 6.2.2 中含重边（v1v2）。下图中给出的则是简单图。图 6.2.3 任意两点均相邻的简单图称之为完全图完全图。n 个点的完全图记为 Kn，图 6.2.4 中给出的分别是 K2，K3，K4。图 6.2.4 如果图 G 的各条边都被赋予了方向，则

8、称图 G 为有有向向图图。如果图 G 的每条边 e 都附有一个实数 w(e)，则称图 G 为赋权图赋权图，实数 w(e)称为边 e 的权（值）。图 6.2.5 和图 6.2.6 分别给出了有向图和赋权图的例子；而图 6.2.7 则给出了有向赋权图的例子。图 6.2.5 图 6.2.6 图 6.2.7 设 v 为图 G 的点，G 中与 v 相关联的边的条数（环计算两次）称为点 v 的度度，记为dG(v)，简记为 d(v)。例如，在图 6.2.1 中，d(v1)=1，d(v2)=d(v3)=d(v4)=3；在图 6.2.2 中，d(v1)=2，d(v2)=3，d(v3)=1，d(v4)=0。如果简

9、单图 G 的每个顶点都有相同的度数d，则称 G 为 d 次正则图。完全图 Kn 一定是 n 次正则图，如图6.2.4。定理 6.2.1 设 G 是具有 n 个顶点 m 条边的图，则顶点度数的总和等于边数的 2 倍，即 定理 6.2.2 完全图 Kn 的边数为m=n(n1)/2。6.2.2 图的矩阵表示 一个图除了可以用图形表示之外，还可用矩阵来表示。用矩阵表示图有利于计算机处理。设图 G=V,E，V=v1,v2,vn，E=e1,e2,em。无向图的关关联联矩矩阵阵 M(G)=(mij)是一个nm矩阵，其中有向图的关关联联矩矩阵阵 M(G)=(mij)是一个nm矩阵，其中 无向图的邻邻接接矩矩阵

10、阵 A(G)=(aij)是一个 n 阶方阵，其中 aij 为连接点 vi 与点 vj 之间边的数目；有向图的邻邻接接矩矩阵阵 A(G)=(aij)是一个 n 阶方阵，其中 aij 为从点 vi 与出发到点 vj 终止的边的数目；简简单单赋赋权权有有向向图图的的邻邻接接矩矩阵阵 A(G)=(aij)是一个 n 阶方阵，其中 无向赋权图的边边权权矩矩阵阵 W(G)=(wij)是一个3m 方阵，其中 w1j 为第 j 条边的起点的标号，w2j 为第 j 条边的终点的标号，w3j 为第 j 条边的权值。下面的矩阵是图 6.2.6 的边权矩阵：6.2.3 子图 定义 设 G=V(G),E(G),G 与

11、H=V(H),E(H),H 为两个图。若 V(H)V(G)，E(H)E(G)，且 H 是 G 在 E(H)上的限制，则称 H 是 G 的子子图图。若 H 是 G 的子图，且 V(H)=V(G)，则称 H 是 G 的生成子图生成子图。图 6.2.8 中，H1 与 H2 均为 G 的子图，其中H2 是 G 的生成子图。图 6.2.86.3 最短路问题及其算法最短路问题及其算法 6.3.1 相关的概念 定义 6.3.1 设图 G 不是赋权图。由图 G 中点与边交替组成的序列=v1e1v2e2 vkekvk+1，若满足 ei 的端点为 vi 与 vi1，i=1,2,k，则称 为一条从起点 v1 到终点

12、 vk+1 的长为 k 的通通路路。边不重复的通路称为简简单单通通路路；除起点与终点可以相同外，任意两点都不同的通路，称为基基本本通通路路，基本通路简称为路路。显然，基本通路必为简单通路。称起点与终点相同的通路为回回路路；边不重复的回路称为简简单单回回路路；起点与终点相同的长为正的基本通路称为基本回路基本回路，也称为圈圈。如不引起混淆（如在简单图中），通路与回路均可用点序列来表达。例 6.3.1 在图 6.3.1 中，取1=v1v2v3，2=v1v2v3v4v2，3=v1v2v3v2v3v4，则 1，2，3 分别是长为 2，4，5 的通路。其中 1 与 2 为简单通路，1 为基本通路。又取 C

13、1=v1v2v3v4v2v5v1，C2=v1v2v5v1，则 C1 是长为 6 的简单回路，C2 是长为 3 的圈。图 6.3.1 定义6.3.2 任意两点之间均存在通路的图称为连连通通图图，否则称为非连通图。非连通图中的连通子图，称为连通分支连通分支。图 6.3.1 所示的图为连通图，而图 6.3.2 所示的图为非连通图，它含有两个连通分支。图 6.3.1 图 6.3.2 定义 6.3.3 设图 G 是赋权图，为 G 中的一条路，则称 的各边权之和为路 的长长度度。对于 G 的两个顶点 u 和 v，从 u 到 v 的路一般不只一条，其中最短的一条称为从 u 到 v 的最最短短路路；最短路的长

14、称为从 u 到 v 的距距离离，记为d(u,v)。6.3.2 固定起点到其余各点的最短路算法 寻求从一固定起点 u0 到其余各点的最短路的最有效算法之一是 Dijkstra（迪克斯特拉）算法，1959 年由 Dijkstra 提出。这个算法是一种迭代算法，它依据的是一个重要而明显的性质：最最短短路路是是一一条条路路，最短路上的任一子段也是最短路最短路上的任一子段也是最短路。Dijkstra 算法的基本思想是：按距 u0 从近到远为顺序，依次求得 u0 到图 G 的各顶点的最短路和距离，直至顶点 v0（或直至图 G 的所有顶点）。Dijkstra 算法算法问题：设简单赋权图 G=V,E 有 n

15、个顶点，求 G 中 u0 点到其它各点的距离及最短路。为避免重复并保留每一步的计算信息，对vV，定义两个标号：l(v)顶点 v 的标号，表示从顶点 u0 到 v 的一条路的权值；z(v)顶点 v 的父节点标号，用以确定最 短路的路线。第一步 赋初值：令l(u0)=0，对所有vV u0，令 l(v)=，z(v)=u0；S0=u0，i=0。第二步 若 i=n 1，停止；否则令 =V Si，进行下一步。第三步 更新标号：对每个 v ，令如果 l(v)l(ui)+w(uiv)，则 z(v)=ui，否则 z(v)不变。第四步 计算 ，并用 ui1 记达到最小值的顶点，置 Si1=Siui1，i=i1，转

16、第二步。算法终止后，u0 到 v 的距离由 l(v)的终值给出，从 v 的父节点标号 z(v)追溯到 u0，就得到 u0 到 v 的最短路的路线。例 6.3.2 求图 6.3.3 所示的图 G 中 v1 到其余各顶点的最短路及其距离。图 6.3.3解：(1)初始标号。i=0。S0=v1，v1=u0，参见图 6.3.4(a)。图 6.3.4(a)(2)用 u0=v1 对各顶点的标号进行更新。i=1。=v2,v3,v4,v5,v6，v ，由算法有：l(v2)=min,0+7=7，l(v3)=min,0+4=4，l(v4)=min,0+=，l(v5)=min,0+=，l(v6)=min,0+2=2。

17、由于 v2，v3，v6 的标号被 v1 更新，故这三个顶点的父节点为 v1，即 z(v2)=z(v3)=z(v6)=v1，参见图 6.3.4(b)，数字边方框中的符号表示父节点。又由于 =l(v6)=2，故u1=v6，S1=v1,v6。参见图 6.3.4(c)。图 6.3.4(b)图 6.3.4(c)(3)用 u1=v6 对各顶点的标号进行更新。i=2。=v2,v3,v4,v5，v ，由算法有：l(v2)=min7,2+=7，l(v3)=min4,2+1=3，l(v4)=min,2+5=7，l(v5)=min,2+5=7。在此次迭代中，v2 的标号不变，v3，v4，v5 的标号被 v6 更新，

18、故 v2 的父节点不变，v3，v4，v5 的父节点为 v6，即 z(v2)=v1，z(v3)=z(v4)=z(v5)=v6。参见图6.3.4(d)。又由于 =l(v3)=3，故 u2=v3，S2=v1,v6,v3。参见图 6.3.4(e)。图 6.3.4(d)图 6.3.4(e)(4)用 u2=v3 对各顶点的标号进行更新。i=3。=v2,v4,v5，v ，由算法有：l(v2)=min7,3+3=6，l(v4)=min7,3+1=4，l(v5)=min7,3+=7。在此次迭代中，v5 的标号不变，v2 和 v4 的标号被 v3 更新，故 v5 的父节点不变，v2 和 v4 的父节点为 v3，即

19、 z(v5)=v6，z(v2)=z(v4)=v3。参见图6.3.4(f)。又由于 =l(v4)=4，故 u3=v4，S3=v1,v6,v3,v4。参见图 6.3.4(g)。图 6.3.4(f)图 6.3.4(g)(5)用 u3=v4 对各顶点的标号进行更新。i=4。=v2,v5，v ，由算法有：l(v2)=min6,4+=6，l(v5)=min7,4+2=6。在此次迭代中，v2 的标号不变，v5 标号被v4 更新，故 v2 的父节点不变，v5 的父节点为v4，即 z(v2)=v3，z(v5)=v4。参见图 6.3.4(h)。又由于 =l(v5)=6，故 u4=v5，S4=v1,v6,v3,v4

20、,v5。参见图 6.3.4(i)。图 6.3.4(h)图 6.3.4(i)(6)用 u4=v5 对各顶点的标号进行更新。i=5。=v2，v =v2，由算法有：l(v2)=min6,6+=6。在此次迭代中，v2 的标号不变，故 v2 的父节点不变，即 z(v2)=v3。参见图 6.3.4(i)。又由于 =l(v2)=6，故 u5=v2，S5=v1,v6,v3,v4,v5,v2。参见图 6.3.4(j)。图 6.3.4(h)图 6.3.4(i)(7)由于 i=5=n 1，停止。注注：迭代的终止条件也可使用 Sn1=v1,vn，或者 =。若寻找 v1 到某点 v 的最短路的路由，则由 v 开始追溯父

21、节点直至 v1。例如，寻找 v1 到 v5 的最短路的路由，根据图6.3.4(j)，从 v5 开始追溯父节点：v5 的父节点为 v4，v4的父节点为 v3，v3 的父节点为 v6，v6 的父节点为 v1。于是 v1 到 v5 的最短路为：v1v6v3v4v5。再如，v1 到 v2 的最短路为：v1v6v3v2。若求 v1 到某点 v 的距离，则直接由 l(v)的终值确定。例如，根据图 6.3.4(j)，由于 l(v5)=6，故 v1 到 v5的距离为 6。再如，由于 l(v2)=6，故 v1 到 v2 的距离也为 6。6.3.3 每对顶点间的最短路算法 寻求赋权图中各对顶点之间最短路，显然可以

22、调用 Dijkstra 算法。具体方法是：每次以不同的顶点作为起点，用 Dijkstra 算法求出从该起点到其余顶点的最短路径，反复执行次这样的操作，就可得到每对顶点之间的最短路。但这样做需要大量重复计算，效率不高。R.W.Floyd（弗洛伊德）另辟蹊径，提出了比这更好的算法，操作方式与 Dijkstra 算法截然不同。Floyd 算法的基本思想是：从图的带权邻接矩阵 A=a(i,j)nn 开始，在 A 中用插入顶点的方法依次构造出 n 个矩阵 D(1)、D(2)、D(n)，使最后得到的矩阵 D(n)成为图图的的距距离离矩矩阵阵，即矩矩阵阵 D(n)的的 i 行行 j 列列元元素素便便是是 i

23、 号号顶顶点点到到 j 号号顶顶点点的的距距离离。构造 D(i)的同时，也引入一个路路由矩阵由矩阵 P(i)来记录两点间的最短路径。构造矩阵 D(k)，k=1,2,n，采用如下的递推公式：D(0)=dij(0)nn=A：是带权邻接矩阵，dij(0)表示从 vi 到 vj 的、中间不插入任何点的路径，即边 vivj 的权值；D(1)=dij(1)nn，其中 dij(1)=mindij(0)，di1(0)d1j(0)：dij(1)表示从 vi 到 vj 的、中间最多只允许 v1 作为插入点的路径中最短路的长度；D(2)=dij(2)nn，其中 dij(2)=mindij(1)，di2(1)d2j(

24、1)：dij(2)表示从 vi 到 vj 的、中间最多只允许 v1 和 v2 作为插入点的路径中最短路的长度；D(n)=dij(n)nn，其中 dij(n)=mindij(n1)，di,n1(n1)dn1,j(n1)：dij(n)表示从 vi 到 vj 的、中间最多只允许 v1,v2,vn1 作为插入点的路径中最短路的长度，即 vi 和 vj 之间的距离。建立路由矩阵 P(k)，k=1,2,n，采用如下的递推公式：P(0)=pij(0)nn：pij(0)表示从 vi 到 vj 的最短路要经过点 vj，即 pij(0)=j；每求得一个 D(k)时，按下列方式产生相应的新的 P(k)=pij(k)

25、nn，其中即当 vk 被插入到 vi 与 vj 之间的最短路时，被记录在 P(k)中。依次求 D(n)时求得 P(n)，可由 P(k)来查找任何两点之间最短路的路由。Floyd 算法算法 问题：设简单赋权图 G=V,E 有 n 个顶点，求 G 中任意两点 vi 和 vj 之间的距离及最短路。输入带权邻接矩阵 A=a(i,j)nn。第一步 赋初值：对所有 I 和 j，d(i,j)=a(i,j)；当 a(i,j)=时，path(i,j)=0，否则 path(i,j)=j，k=1。第二步 更新 d(i,j)，path(i,j)：对所有 i 和j，若 d(i,k)d(k,j)d(i,j)，则转第三步；

26、否则d(i,j)=d(i,k)d(k,j)，path(i,j)=path(i,k)，k=k 1，继续执行第三步。第三步 重复第二步直到 k=n 1。在此：d(i,j)：dij(k)。path(i,j)：pij(k)；对应于 dij(k)的路径上 I 的后继点，最终的取值为 i 到 j 的最短路径上 i 的后继点。例如，若则顶点 1 到顶点 3 的最短路径为 1253。这是因为：path(1,3)=2，意味着顶点 1 的后继点为 2；又 path(2,3)=5，意味着顶点 2 的后继点为 5；同理，因 path(5,3)=3，从而顶点 5 的后继点为 3。故 1253 便是顶点 1 到顶点 3

27、的最短路径。6.3.4 最短路算法的 Matlab 实现 根据 Dijkstra 算法和 Floyd 算法的步骤，可以编写相应的 Matlab 程序。6.4 树及其算法树及其算法 6.4.1 相关的概念 树（tree）在图论中是相当重要的一类图，它非常类似于自然界中的树。树的性质非常好，应用相当广泛。定义 6.4.1 无圈的连通图称为树树。例如，图 6.4.1 给出的 G1 和 G2 是树，但G3 和 G4 则不是树。G1 G2 G3（有圈）G4（不连通）图 6.4.1 定理 6.4.1 设 G 是具有 n 个点 m 条边的图，则以下关于树的命题等价。(1)G 是树；(2)G 中任两个不同点之

28、间存在唯一的路；(3)G 连通，删去任一条边均不连通；(4)G 连通，且 n=m+1；(5)G 无圈，且 n=m+1；(6)G 无圈，添加任一条边可得唯一的圈。定义 6.4.2 若图 G 的生成子图 H 是树，则称 H 为 G 的生成树生成树或支撑树支撑树。一般来讲，一个图的生成树不唯一。例如，在图6.4.2 中，(a)、(b)、(c)均是(d)的生成树。(c)(d)图 6.4.2(a)(b)定理 6.4.2 连通图的生成树一定存在。证明 给定连通图 G，若 G 无圈，则 G 本身就是自己的生成树。若 G 有圈，则任取 G 中一个圈C，记删去 C 中一条边后所得之图为 G。显然 G 中圈 C

29、已经不存在，但 G 仍然连通。若 G 中还有圈，再重复以上过程，直到得到一个无圈的连通图 H。易知 H 是 G 的生成树。证毕。定理 6.4.2 的证明方法也是求生成树的一种方法，称为“破圈法”。定义 6.4.3 在赋权图 G 中，边权之和最小（大）的生成树称为 G 的最小（大）生成树最小（大）生成树。6.4.2 最小生成树算法 一个简单连通图只要不是树，其生成树就不唯一，而且非常多。一般地，n 个顶点地完全图，其不同地生成树个数为 nn2。因而，寻求一个给定赋权图的最小生成树，一般是不能用穷举法的。例如，30 个顶点的完全图有 3028个生成树，3028 有 42 位，即使用最现代的计算机，

30、在我们的有生之年也是无法穷举的。所以，穷举法求最小生成树是无效的算法，必须寻求有效的算法。在求最小生成树的有效算法中，最著名的两个是 Kruskal（克罗斯克尔）算法和 Prim（普瑞姆）算法，其迭代过程都是基于贪婪法来设计的。1求最小生成树的 Kruskal 算法 Kruskal 算法的直观描述算法的直观描述 假设 T0 是赋权图 G 的最小生成树，T0 中的边和顶点均涂成红色，初始时 G 中的边均为白色。将所有顶点涂成红色；在白色边中挑选一条权值最小的边，使其与红色边不形成圈不形成圈，将该白色边涂红；重复直到有 n1 条红色边，这 n1 条红色边便构成最小生成树 T0 的边集合。例如，对于

31、图 6.4.3(a)给出的赋权图，按照上述的步骤，容易求出其最小生成树。其中(b)、(c)分别是第一步和第二步，(d)是最后结果。(a)(b)(c)(d)(d)图6.4.3 Kruskal 算法的基本思想算法的基本思想 设 T0 和 C(T0)分别为图 G 的最小生成树的边集及其权值，初始状态均为空，算法结束时 T0 包含最小生成树的所有边，C(T0)表示最小生成树的权值。令 VS是一个不相交的节点的集合，初始状态时 VS=v1,v2,vn。算法的主要步骤是每次从边集 E 中选出一条未处理的有最小权值的边(u,v)进行分析，如果 u 和 v 同属于 VS 的一个元素集，则将边(u,v)删除，如

32、果 u 和 v 分属于 VS 的两个元素集，则将边(u,v)加入到 T0 中，并将这两个元素集合并为一个元素集，然后再从 E 中另选权值最小的边进行处理，直至找到一棵最小生成树为止。Kruskal 算法的步骤算法的步骤 第一步 T0，C(T0)0，VS，将 E 中的边按权值从小到大排成序列 Q。第二步 对所有 vV，VSv，即 VS=v1,v2,vn。第三步 如果|VS|=1，输出 T0 和 C(T0)，停止。否则进行下一步。第四步 从 Q 中取出权值最小的边(u,v)，并从 Q中删除(u,v)。第五步 如果 u，v 在 VS 的元素集 V1、V2 中且 V1=V2，则转第四步。否则进行下一步

33、。第六步 T0T0(u,v)，VV1V2，C(T0)C(T0)+w(u,v)，转第三步。例 6.4.1 用 Kruskal 算法求图 6.4.3(a)给出的赋权图的最小生成树。解：将图的边按照权值从小到大进行排列：边(a,b)(c,e)(a,e)(b,c)(d,g)(a,c)权45791215边(d,f)(f,g)(c,d)(a,g)(e,g)(d,e)权162025283032 操作 Kruskal 算法，迭代 9 步完成最小生成树的寻找。操作过程的各个步骤列于下表。步骤选出边ew(e)操作VST0C(T0)1(a,b)4加到T0中a,b,c,d,e,f,g(a,b)42(c,e)5加到T0

34、中a,b,c,e,d,f,g(a,b),(c,e)93(a,e)7加到T0中a,b,c,e,d,f,g(a,b),(c,e),(a,e)164(b,c)9删除a,b,c,e,d,f,g(a,b),(c,e),(a,e)165(d,g)12加到T0中a,b,c,e,d,g,f(a,b),(c,e),(a,e),(d,g)286(a,c)15删除a,b,c,e,d,g,f(a,b),(c,e),(a,e),(d,g)287(d,f)16加到T0中a,b,c,e,d,g,f(a,b),(c,e),(a,e),(d,g),(d,f)448(f,g)20删除a,b,c,e,d,g,f(a,b),(c,e

35、),(a,e),(d,g),(d,f),(c,d)449(c,d)25加到T0中a,b,c,e,d,g,f(a,b),(c,e),(a,e),(d,g),(d,f),(c,d)69结果显示于图 6.4.4 图 6.4.4 2求最小生成树的 Prim 算法 Prim 算法的直观描述算法的直观描述 假设 T0 是赋权图 G 的最小生成树。任选一个顶点将其涂红，其余顶点为白点；在一个端点为红色，另一个端点为白色的边中，找一条权最小的边涂红，把该边的白端点也涂成红色；如此，每次将一条边和一个顶点涂成红色，直到所有顶点都成红色为止。最终的红色边便构成最小生成树 T0 的边集合。例如，对于图 6.4.3(

36、a)给出的赋权图，按照上面的描述，容易求出其最小生成树。其中图6.4.5(a)、(b)分别是第一步和第二步，(c)是最后结果。(a)(b)(c)图 6.4.5 Prim 算法的基本思想 设 T0 和 C(T0)分别为图 G 的最小生成树的边集及其权值，初始状态均为空，算法结束时T0 包含最小生成树的所有边，C(T0)表示最小生成树的权值。先指定一个顶点为初始访问点，记做 v0，将 v0 加到“通过点”的集合 V 中，然后找出跨接在“通过点”集合V 与“未通过点”集合 VV 之间权最小的边 e 作为“通过边”加入 T0 中，并将 e 在 VV 中的端点转到 V 中。重复上述过程直至 V =V 为

37、止。Kruskal 算法的步骤算法的步骤 第一步 T0，C(T0)0，V v0。第二步 对每一个点 vV V，L(v)c(v,v0)（如果 (v,v0)E，则 c(v,v0)=）。第三步 如果 V =V，输出 T0，C(T0)，停止。否则进行下一步。第四步 在 V V 中找一点 u，使L(u)=minL(v)|vV V，并将 V 中与 u 邻接的点记为 w，e=(w,u)。第五步 T0T0e，C(T0)C(T0)+C(e)，V V u。第六步 对所有 vVV，如 c(v,u)L(v)，则 L(v)c(v,u)，否则 L(v)不变。第七步 转第三步。例 6.4.2 用 Prim 算法求图 6.4

38、.3(a)给出的赋权图的最小生成树。解：为简便起见，将操作 Prim 算法的步骤列于下表，结果参加图 6.4.4。步骤uL(b)L(c)L(d)L(e)L(f)L(g)eV T0C(T0)1a415728a02b9728(a,b)a,b(a,b)43e53228(a,e)a,b,e(a,b),(a,e)114c2528(c,e)a,b,e,c(a,b),(a,e),(c,e)165d1612(c,d)a,b,e,c,d(a,b),(a,e),(c,e),(c,d)416g16(d,g)a,b,e,c,d,g(a,b),(a,e),(c,e),(c,d),(d,g)537f(d,f)a,b,e,

39、c,d,g,f(a,b),(a,e),(c,e),(c,d),(d,g),(d,f)69 6.4.3 最小生成树算法的 Matlab 实现 根据 Kruskal 算法和 Prim 算法的步骤，许多人都编写了相应的 Matlab 程序。在此选用5中给出的 Matlab 程序。6.4.4 关于最小生成树算法的注释 最小生成树的 Kruskal 算法是 1956 年由Kruskal 提出的。随后在 1957 年，领导贝尔实验室数学研究室的 Prim 得到了他的算法。Kruskal 算法的时间复杂性以 O(mlog2m)为界，当边数较多或是一个完全图时，m (n 1)2，则时间复杂性近似于 O(n2l

40、og2n)。而 Prim 算法的时间复杂性为O(n2)，所以，如果图的连通度较高（最高为完全图），以 Prim 算法较好，如果图的连通度较低，特别当 m O(n)时，则 Kruskal 算法更合适。在实际应用中，还会遇到求一个赋权图的最大生成树的问题。比如，某图的边权代表的是利润或效益，则最终的问题很可能就是求其最大生成树。事实上，从上面两个算法可以看出，只要边权的选择改为从大到小，求最小生成树的算就可以用来求最大生成树了。6.5 范例范例 图论是离散数学的重要分支，它能够为自然科学、工程技术、经济管理、社会现象等诸多问题提供得力的数学模型。因而，许多实际问题都可以转化为图论的问题加以解决。在

41、此，仅举几个可以利用图论方法解决的问题，予以示范。设设备备更更新新问问题题。某工厂的某台机器可连续工作4年，决策者每年年初都要决定机器是否需要更新。若购置新的，就要支付一定的购置费用；若继续使用，则要支付一定的维修与运行费用，而且随着机器使用年限的增加费用逐年增多。计划期（4 年）中每年年初的购置价格及各个年限内维修与运行费用由下表给出，试制订今后 4 年的机器更新计划，使总的支付费用最少。第i年初1234购置费（万元）2.52.62.83.1使用年限1234每年的维修与运行费（万元）11.524 又如果已知不同役龄机器年末的处理价格如下表所示，那末在这计划期内机器的最优更新计划又会怎样？年度

42、第1年末第2年末第3年末第4年末机器处理价（万元）2.01.61.31.1 解：关于第一问，把该问题看成一个最短路问题。设 v1 和 v5 分别表示计划期的始点和终点（x5 可理解为第4年年末）。图中各边(vi,vj)表示在第 i 年初购进的机器使用到第 j 年初（即第 j 1 年底），边旁的数字由表中的数据得到。关于第二问，类似于第一问，可转化为求下图中从 v1 到 v5 的最短路问题。按照最短路算法可得最短路 v1,v2,v3,v5，即计划期内机器更新最优计划为第 1 年、第 3 年初各购进一台新机器，4 年总的支付费用为 6.8万元。选选址址问问题题。选址问题是指为一个或几个服务设施在一

43、定区域内选定它的位置，使某一指标达到最优值。选址问题的数学模型依赖于设施可能的区域和评判位置优劣的标准，有许多不同类型的选址问题。比较简单的两类选址问题是中心问题和重心问题。中心问题：有些公共服务设施（例如一些紧急服务型设施如急救中心、消防战等）的选址，要求网络中最远的被服务点距离服务设施的距离尽可能小。例如：某城市要建立一个消防站，为该市所属的七个区服务，如下图所示。问应设在那个区，才能使它至最远区的路径最短。解：(1)用 Floyd 算法求出距离矩阵 D=(dij)vv：(2)计算在各点 vi 设立服务设施的最大服务距离 S(vi)，i=1,2,v有：S(v1)=10，S(v2)=7，S(

44、v3)=6，S(v4)=8.5，S(v5)=7，S(v6)=7，S(v7)=8.5。(3)求出顶点 vk，使 ，则 vk 就是要求的建立消防站的地点。因为 S(v3)=6最小，故应将消防站设在 v3 处。此点称为图的中心点中心点。重心问题：有些设施（例如一些非紧急型的公共服务设施，如邮局、学校等）的选址，要求设施到所有服务对象点的距离总和最小。一般要考虑人口密度问题，要使全体被服务对象来往的平均路程最短。例如，某矿区有七个矿点，如下图所示。已知各矿点每天的产矿量q(vj)（标在图的各顶点上），现要从这七个矿点选一个来建造矿厂，问应选在哪个矿点，才能使各矿点所产的矿运到选矿厂所在地的总运力（千吨

45、公里）最小。解：(1)用 Floyd 算法求出距离矩阵 D=(dij)vv：(2)计算各顶点作为选矿厂的总运力 m(vi)(3)求 vk 使 ，则 vk 就是选矿厂应设之矿点。此点称为图的重心重心或中位点中位点。分分组组技技术术。分组技术是设计制造系统的一种方法，它把生产零件的机器分组，相应地把需生产的零件分类，使零件跨组加工的情形尽量少，最理想的情况是使每个零件的加工都在组内完成。假设有 13 种零件，需在 9 台机器上加工。在各台机器上加工的零件号在下表中给出。将这 9 台机器分为 3 组，使零件跨组加工的情形尽量少。机器123456789加工的零件2，3，7，8，9，12，132，7，8

46、，11，121，63，5，103，7，8，9，12，1354，104，106 解：(1)建建模模 设用 Mi 表示需由机器 i 加工的零件集合。对任意两台机器 i，j，定义 i 与 j的相异度：其中“”表示对称差，分子即为在机器 i 但不在机器 j 上加工，或在机器 j 但不在机器 i 上加工的零件数。分母为在机器 i 或在机器 j 上加工的零件数。显然，0 w 1，w(i,j)=0 表示机器 i 与机器 j 加工的零件完全相同；w(i,j)=1 表示机器 i 与机器 j 加工的零件没有一个相同。w 表达了两台不同机器加工零件的相异程度。以机器为顶点，作一个完全图，每条边 (i,j)被赋予权

47、w(i,j)。这个图的最小生成树是由那些相异度最小的边构成的连通图，或看成是去掉了相异度相对比较大的边后余下的连通图。如果希望把机器分成 k 个组，就继续删去最小生成树上权最大的 k1条边。于是得到 k 个分离的子树，每棵树的顶点就构成各机器组。(2)模模型型求求解解 对前面表中给出的数据，按照上述建模方式构造加权图，边权矩阵如下表所示。边111111112222234567893456边权0.510.890.141111110.621边222333333444789456789567边权111111110.50.870.670.75边445555666778896789789899边权0.7511111111011 用 Kruskal 算法可求出最小生成树，如下图。将最小生成树中最大权的两条边去掉，得到三个分离树，它们的顶点集合分别为：3,9，1,2,5，4,6,7,8，这也就是机器的分组。实验作业实验作业 设备更新策略最大容量路径谢谢！