9图论初步课件

《9图论初步课件》由会员分享，可在线阅读，更多相关《9图论初步课件（92页珍藏版）》请在金锄头文库上搜索。

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

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

3、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) 中的点组成的无序点对相对应。 若用小圆点表示

6、点集 V(G) 中的点，连线表示边集 E(G) 中的边，则可用图形将图表示出来，称之为图的图形。我们常用图的图形代表图本身。,例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,定义

7、6.2.2 设e = uv 为图 G 的一条边，我们称 u，v 是 e 的端点，u 与 v 相邻，边 e 与点 u（或v）相关联；称 u 是 e 的起点，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

8、个点的完全图记为 Kn，图 6.2.4 中给出的分别是 K2，K3，K4。,图 6.2.4,如果图 G 的各条边都被赋予了方向，则称图 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(

9、v2) = d(v3) = d(v4) = 3；在图 6.2.2 中，d(v1) = 2，d(v2) = 3，d(v3) = 1，d(v4) = 0。 如果简单图 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

10、, , vn，E = e1, e2, , em。 无向图的关联矩阵 M(G) = (mij) 是一个nm矩阵，其中,有向图的关联矩阵 M(G) = (mij) 是一个nm矩阵，其中,无向图的邻接矩阵 A(G) = (aij) 是一个 n 阶方阵，其中 aij 为连接点 vi 与点 vj 之间边的数目；有向图的邻接矩阵 A(G) = (aij) 是一个 n 阶方阵，其中 aij 为从点 vi 与出发到点 vj 终止的边的数目；简单赋权有向图的邻接矩阵 A(G) = (aij) 是一个 n 阶方阵，其中,无向赋权图的边权矩阵 W(G) = (wij) 是一个3m 方阵，其中 w1j 为第 j 条边

11、的起点的标号，w2j 为第 j 条边的终点的标号，w3j 为第 j 条边的权值。 下面的矩阵是图 6.2.6 的边权矩阵：, 6.2.3 子图 定义 设 G = V(G), E(G), G 与 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.8,6.3 最短路问题及其算法, 6.3.1 相关的概念 定义 6.

12、3.1 设图 G 不是赋权图。由图 G 中点与边交替组成的序列 = v1e1v2e2 vkekvk+1， 若满足 ei 的端点为 vi 与 vi1，i = 1, 2, , k，则称 为一条从起点 v1 到终点 vk+1 的长为 k 的通路。,边不重复的通路称为简单通路；除起点与终点可以相同外，任意两点都不同的通路，称为基本通路，基本通路简称为路。显然，基本通路必为简单通路。 称起点与终点相同的通路为回路；边不重复的回路称为简单回路；起点与终点相同的长为正的基本通路称为基本回路，也称为圈。 如不引起混淆（如在简单图中），通路与回路均可用点序列来表达。,例 6.3.1 在图 6.3.1 中，取 1

13、 = v1v2v3，2 = v1v2v3v4v2，3 = v1v2v3v2v3v4， 则 1，2，3 分别是长为 2，4，5 的通路。其中 1 与 2 为简单通路，1 为基本通路。又取 C1 = 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 是

14、赋权图， 为 G 中的一条路，则称 的各边权之和为路 的长度。对于 G 的两个顶点 u 和 v，从 u 到 v 的路一般不只一条，其中最短的一条称为从 u 到 v 的最短路；最短路的长称为从 u 到 v 的距离，记为d(u, v)。, 6.3.2 固定起点到其余各点的最短路算法 寻求从一固定起点 u0 到其余各点的最短路的最有效算法之一是 Dijkstra（迪克斯特拉）算法，1959 年由 Dijkstra 提出。这个算法是一种迭代算法，它依据的是一个重要而明显的性质：最短路是一条路，最短路上的任一子段也是最短路。 Dijkstra 算法的基本思想是：按距 u0 从近到远为顺序，依次求得 u0

15、 到图 G 的各顶点的最短路和距离，直至顶点 v0（或直至图 G 的所有顶点）。,Dijkstra 算法 问题：设简单赋权图 G = V, E 有 n 个顶点，求 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，转第二步。 算法终止后，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