数学建模——图论

1、数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 沈阳工业大学理学院杜洪波杜洪波hb_2015年8月数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 一、涉及图论的历年数学建模题目一、涉及图论的历年数学建模题目 二、图论简介二、图论简介 三、图论的基本概念三、图论的基本概念 四、最短路问题及其算法四、最短路问题及其算法 五、最小生成树及其算法五、最小生成树及其算法

2、六、几个可以用图论解决的范例六、几个可以用图论解决的范例数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling1、93B 足球队排名次2、94A 逢山开路3、94B 锁具装箱问题4、95B 天车与冶炼炉的作业调度5、97B 截断切割：最短路最短路6、98B 灾情巡视：最小生成树、最小生成树、Hamilton圈、旅行商问题圈、旅行商问题数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Mod

3、eling7、99B 钻井布局：最大完全子图最大完全子图8、00B 管道订购：最短路最短路9、01B公交车调度10、02D赛程安排11、04A奥运会临时超市网点设计 12、07乘公交，看奥运 数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling13、08C地面搜索14、08DNBA赛程的分析与评价数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 现实生活中许多问题都可归

4、结为由点和线组成的现实生活中许多问题都可归结为由点和线组成的图形的问题，例如，铁路交通图，公路交通图，市区图形的问题，例如，铁路交通图，公路交通图，市区交通图，自来水管网系统，甚至电路图在研究某些问交通图，自来水管网系统，甚至电路图在研究某些问题时也可简化为由点和线组成的图形。题时也可简化为由点和线组成的图形。 如果我们用点表示这些具体事物，用连接两点如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个就得到了描述这个“图图”的几何形象。的几何形象。 图论就是研究这些由点和线组成的图形的问题。图论就

5、是研究这些由点和线组成的图形的问题。数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 图论是运筹学的一个经典和重要的分支，它起源于18世纪欧拉（Euler）对七桥问题的抽象和论证。 1936年，匈牙利数学家柯尼希（Knig）出版了图论的第一部专著有限图与无限图理论，竖立了图论发展的第一座里程碑。数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling2.1 七桥问题（Eul

6、er） 18世纪东普鲁士有一个城市称为哥尼斯堡，它位于普雷格尔河畔，河中有两个小岛，通过七座桥彼此相联（如图2.1）。当时有人提出： 能否从某个地点出发经过每个桥一次且仅一次然后返能否从某个地点出发经过每个桥一次且仅一次然后返回出发点？回出发点？数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical ModelingD DA AB BC CA AB BC CD Dv建模：点陆地 岛屿 边桥Euler的做法：图 2.1图 2.2数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECH

7、NOLOGYGraph Theory in Mathematical Modeling2.2 Hamilton 周游世界问题 1859年 Hamilton 提出这样一个问题：一个正十二面体有20个顶点，它们代表世界上20个重要城市。正十二面体的每个面均为五边形，若两个顶点之间有边相连，则表示相应的城市之间有航线相通。 Hamilton 提出 “能否从某城市出发经过每个城能否从某城市出发经过每个城市一次且仅一次然后返回出发点？市一次且仅一次然后返回出发点？”数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathemati

8、cal Modeling2.3 四色问题（猜想） 四色问题又称四色猜想、四色定理，是世界近代三大数学难题之一。 地图四色定理(Four color theorem)最先是由一位叫古德里（Francis Guthrie）的英国大学生提出来的。 德摩根（Augustus De Morgan）1852年10月23日致哈密顿的一封信提供了有关四色定理来源的最原始的记载。 数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling四色问题的内容是：“任何一张地图只用四种颜色就任何一张地图只用四种颜色

9、就能使具有共同边界的国家着上不同的颜色能使具有共同边界的国家着上不同的颜色。”用数学语言表示，即“将平面任意地细分为不相重叠的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。” 1890年希五德（Heawood）指出“4换为5”猜想成立。1976年美国数学家阿佩尔（K.Appel）与哈肯（W.Haken）在三台百万次的电子计算机上花了1200小时证明了猜想成立。猜想成为定理。数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling2.4

10、中国邮路问题或中国邮递员问题（CPPChinese Postman Problem） 1962年中国数学家管梅谷提出：一个邮递员从邮局出发递送邮件，要求对他所负责的辖区的每条街至少走一次，问如何选取路程最短的路线？国际上称之为中国邮递员问题中国邮递员问题。 该问题可用专门的算法来求解。数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling2.5 最短路问题（SPPshortest path problem） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网

11、纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling2.6旅行商问题（TSPtraveling salesman problem） 一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。 2.7 指派问题（assignment p

12、roblem） 一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling2.8 运输问题（transportation problem） 某种原材料有个产地，现在需要将原材料从产地运往个使用这些原材料的工厂。假定个产地的产量和家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低?数数 学

13、学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 3.1 图的定义 3.2 图的分类 3.3 图的同构 3.4 子图 3.5 图的运算 3.6 图的代数表示及特征 数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 定义定义3.1 称数学结构称数学结构G = V(G), E(G), G 为一个为一个图图，其中其中V(G) = v1, v2, , vn 称为图称为图 G的的顶点

14、集顶点集(vertex set)或或节点集节点集(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 = vjvi（k = 1, 2, , m），被称为该图的），被称为该图的一条从一条从 vi到到

15、 vj的的边边(edge)；上级目录数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical ModelingG是从 E(G) 到V(G)V(G) 的一个映射，它指定 E(G) 中的每条边与 V(G) 中的点组成的无序点对相对应。 若用小圆点表示点集 V(G) 中的点，连线表示边集 E(G) 中的边，则可用图形将图表示出来，称之为图的图形。我们常用图的图形代表图本身。数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathemati

16、cal Modeling 定义定义3.2 设e = uv 为图 G 的一条边，我们称 u、v 是 e 的端点端点，u 与 v 相邻相邻，边 e 与点 u（或v）相关联关联；称 u 是 e 的起点，v 是 e 的终点。若两条边 e1 与 e2 有共同的端点，则称边 e1与 e2 相邻； 称有相同起点和终点的两条边为重边重边； 称两端点均相同的边为环环； 称不与任何边相关联的点为孤立点孤立点。 数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling简单图简单图平凡图平凡图非非简单简单图图

17、点集与边集均为有限集合的图称为有限图有限图，一般我们只讨论有限图。只有一个顶点而无边的图称为平凡图平凡图。边集为空的图称为空图空图。 无环且无重边的图称之为简单图简单图。其他所有的图都称为复合图。复合图。数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling例3.1 设 V = v1, v2, v3, v4，E = e1, e2, e3, e4, e5，：EVV 定义为(e1) = v1v2，(e2) = v2v3，(e3) = v2v3，(e4) = v3v4，(e5) = v4v4

18、，则G = V, E 是一个图，其图形如图3.1所示。图 3.1数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling例3.2 设 V = v1, v2, v3, v4，E = v1v2, v1v2, v2v3，则G = V, E 是一个图，其图形如图3.2所示。图 3.2数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling例 3.1 和例 3.2 都不是简单图，因为例3.1

19、 中既含重边（e2 与 e3）又含环（e5），而例 3.2 中含重边（v1v2）。下图3.3给出了一个简单图。图 3.3数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 任意两点均相邻的简单图称之为任意两点均相邻的简单图称之为完全图完全图。 n 个点的完全图记为个点的完全图记为 Kn，图，图 3.4 中给出的分别是中给出的分别是 K2，K3，K4。图 3.4数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in M

20、athematical Modeling 如果图如果图 G 的各条边都被赋予了方向，则称图的各条边都被赋予了方向，则称图 G 为为有向图有向图。如。如果图果图 G 的每条边的每条边 e 都附有一个实数都附有一个实数 w(e)，则称图，则称图 G 为为赋权图赋权图，实，实数数 w(e) 称为边称为边 e 的权（值）。的权（值）。 图 3.5 和图 3.6 分别给出了有向图和赋权图的例子；而图 3.7 则给出了有向赋权图的例子。图 3.5：有向图数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Mod

21、eling图 3.6：赋权图图 3.7：有向赋权图数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 设设 v 为图为图 G 的点，的点，G 中与中与 v 相关联的边的条数（环计相关联的边的条数（环计算两次）称为点算两次）称为点 v 的的度度，记为，记为dG(v)，简记为，简记为 d(v)。v1v2v3v4v5例例3.3图图3.8中中 d (v1) = 5 d (v2) = 4 d (v3) = 3 d (v4) = 0 d (v5) = 2注：该图中各点的度数注：该图中各点的度数

22、 之和等于之和等于14，恰好，恰好 是边数是边数7的的两两倍。倍。图图3.8数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 定理定理 3.1（图论第一定理：握手定理握手定理） Euler提出 设 G 是具有 n 个顶点 m 条边的图，则顶点度数的总和等于边数的 2 倍，即 证明：因图 G 的任一条边均有两个端点 (可以相同)，在计算度时恰被计算两次 (每个端点各被计算了一次)，所以各点的度数之和恰好为边数的两倍，即定理成立。 推论推论3.1：图图G中度数为奇的点的个数为偶数。中

23、度数为奇的点的个数为偶数。mvdnii2)(1数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 例例3.4 3.4 证明在任意一次集会中和奇数个人握手的人的证明在任意一次集会中和奇数个人握手的人的个数为偶数个。个数为偶数个。 证明证明: :将集会中的人作为点，若两个人握手则对应的将集会中的人作为点，若两个人握手则对应的点联线，则得简单图点联线，则得简单图G。这样。这样G中点中点v的度对应于集会中与的度对应于集会中与v握手的人的个数。于是，问题转化为证明握手的人的个数。于是，问题转

24、化为证明“图图G中度数中度数为奇的点的个数为偶数为奇的点的个数为偶数”，这正是推论，这正是推论3.13.1的结论。的结论。数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 定理定理 3.2 完全图完全图 Kn 的边数为的边数为 m = n(n 1)/2。 如果简单图如果简单图 G 的每个顶点都有相同的度数的每个顶点都有相同的度数k，则称，则称 G 为为 k 次正则图次正则图（或（或k -正则图正则图）。）。 完全图完全图 Kn 一定是一定是 n-1 次正则图，如前图次正则图，如前

25、图3.4。 相关术语和记号：相关术语和记号： ：图：图G的顶点的最小度的顶点的最小度 ：图：图G的顶点的最大度的顶点的最大度 奇奇(偶偶)点点: 奇奇(偶偶)数度的顶点数度的顶点( )G( )G数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical ModelingA 按边的方向分类按边的方向分类有向图有向图与与无向图无向图:边有方向的图边有方向的图,叫有向图；边无方向叫有向图；边无方向的图叫无向图。的图叫无向图。起点和终点：在有向图中，有向边起点和终点：在有向图中，有向边e = vivj中中vi称为起

26、称为起点，点， vj称为终点。称为终点。数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical ModelingB 按边的种类分类按边的种类分类简单图简单图与与多重图多重图:不含环与多重边的图叫简单图；含多重不含环与多重边的图叫简单图；含多重边的图叫多重图。边的图叫多重图。赋（有）权图赋（有）权图与与无权图无权图: 有时在一个图中边的旁边可以有时在一个图中边的旁边可以附加数字以刻划此边的某些数量特征，叫做边的权，此边附加数字以刻划此边的某些数量特征，叫做边的权，此边叫做有权边，具有有权边的图叫有权图或赋

27、权图，无有权叫做有权边，具有有权边的图叫有权图或赋权图，无有权边的图叫无权图。边的图叫无权图。数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical ModelingC 按结点集与边集的按结点集与边集的“阶阶”分类分类1、有限图、有限图与与无限图无限图：V 与与 E 为有限集合的图叫有限图，为有限集合的图叫有限图，否则叫无限图。否则叫无限图。2、(n,m)图图：有：有 n 个结点与个结点与 m 条边的图。条边的图。 零图零图:即即(n,0)图图;平凡图平凡图:即即(1,0)图。图。3、完全图、完全图:任

28、意两个结点都相邻接的图。任意两个结点都相邻接的图。 共共n(n-1)/2 条边，是条边，是(n,n(n-1)/2)图。图。4、K-正则图正则图:每个结点都与每个结点都与K条边相关联。条边相关联。数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling完全图的每个结点都与其它完全图的每个结点都与其它 n-1 个结点相邻接个结点相邻接,即与即与n-1条条边相关联边相关联,所以是所以是n-1正则图正则图,反之正则图不一定是完全图。反之正则图不一定是完全图。1、完全图：、完全图： 2、正则图：、

29、正则图：是是3正则图。正则图。 完全图完全图 不是完全图不是完全图数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 定义定义3.33.3 给定两个图给定两个图G=V,E, ,G =V ,E , ,若存在一一若存在一一映射映射f:VV ，使对任意使对任意a,b V, ,有有 (a,b) E (f(a),f(b) E , , 并且并且(a,b)与与(f(a),f(b)有相同重数有相同重数, ,则称则称G与与G 同构同构, ,记为记为G G . . 说明：说明： (1) (1) 两个同

30、构的图均有相同的结构，没有本质上的差两个同构的图均有相同的结构，没有本质上的差异异, , 差异只是顶点和边的名称不同。差异只是顶点和边的名称不同。 （2 2）图同构的几个）图同构的几个必要必要条件：条件： 顶点数相同；顶点数相同； 边边数相同；数相同； 度数相等的顶点个数相同。度数相等的顶点个数相同。数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling （3）不难证明：）不难证明：图的同构关系是一个等价关系图的同构关系是一个等价关系。该关系将所有。该关系将所有的图的集合，划分为一些等

31、价类，即相互同构的图作成同一个等价的图的集合，划分为一些等价类，即相互同构的图作成同一个等价类。类。 （4）在图的图形表示中我们可以不给图的点和边标上符号，称）在图的图形表示中我们可以不给图的点和边标上符号，称这样的图为这样的图为非标定（号）图非标定（号）图，否则称为，否则称为标定（号）图标定（号）图。非标定图实。非标定图实际上是代表一类相互同构的图。际上是代表一类相互同构的图。 不误解时我们也不严格区分标定图与非标定图。不误解时我们也不严格区分标定图与非标定图。 （5）寻求判断图同构的简单且有效的方法仍然是当前图论待解）寻求判断图同构的简单且有效的方法仍然是当前图论待解决的重要问题。决的重要

32、问题。数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling GG HH 1 1a,2a,2b, b, 1 1a,2a,2b,3b,3c,c, 3 3c,4c,4d 4d 4d,5d,5e,6e,6f f1234abcdabcdefGG HH 123456数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling存在结点数及每个结点对应度都相等的两个图仍然不同构存在结点数及每个结点

33、对应度都相等的两个图仍然不同构的情况的情况. .一个例子如下一个例子如下:(:(注意注意: :两个两个4 4度点或邻接或不相邻度点或邻接或不相邻接接) )GG 数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 定义定义3.4 设图设图G= V, E, ，G1= V1, E1, 1 （1）若）若 且当且当 时，时， ，则称，则称G1是是G的的子图子图，有，有时也称时也称G是是G1的的母图母图，记作，记作 。 特别的，若特别的，若V1=V，则，则G1称为称为G的的生成子图生成子图。

34、当当G1 G但但G1G时，记为时，记为G1 G，且称，且称G1是是G的的真子图真子图。（2）设）设 且且 ，以，以V1为顶点集、两个端点都在为顶点集、两个端点都在V1中的图中的图G的的边为边集的图边为边集的图G的子图，称为图的子图，称为图G的的由由V1导出的子图导出的子图，记作，记作GV1。（3）设）设 且且 ，以，以E1为边集、为边集、 E1的顶点集为顶点集的图的顶点集为顶点集的图G的的子图，称为图子图，称为图G的的由由E1导出的子图导出的子图，记作，记作GE1。11,VV EE1eE1( )( )ee1VV1V 1EE1E 1GG上级目录数数 学学 模模 型型 SHENYANG UNIVE

35、RSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling: :由由(1,2),(1,4),(5,1)(1,2),(1,4),(5,1)导出的子图导出的子图; ; : :由由(1,2),(3,2),(3,4),(1,4)(1,2),(3,2),(3,4),(1,4)导出的子图导出的子图( (也是此也是此4 4点导出的子点导出的子图图); ); : :由由1,2,4,51,2,4,5导出的子图导出的子图. .12534125412341254数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph

36、Theory in Mathematical Modeling 定理定理3.3 简单图简单图G中所有不同的生成子图（包括中所有不同的生成子图（包括G和空和空图）的个数是图）的个数是2m个个, 其中其中m为为G的边数。的边数。 证明：易知证明：易知 其个数其个数 = 含含0条边的条边的+含含1条边的条边的+含含m条边的条边的0122mmmmmmCCCC数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 设G1，G2是G的子图，则 G1和和G2不相交不相交: 指它们无公共顶点；指它们无

37、公共顶点； G1和和G2边不重边不重: 指它们无公共边；指它们无公共边； 并图并图G1G2:是指其顶点集为是指其顶点集为V(G1)V(G2)，边集为，边集为E(G1)E(G2) 的的G的一个子图的一个子图;如果如果G1和和G2是不相交的，是不相交的，有时就记其并图为有时就记其并图为G1+G2； 交图交图G1G2:类似地定义；类似地定义； 对称差对称差G1G2: G1G2 = (G1G2) - (G1G2) = (G1-G2)(G2-G1)数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Model

38、ing2 d 4a c e1 f 3 G1b2 d 4 g e 5 i 3 j G2 h c 2 d 4 g a c e 5 b i h1 f 3 G1G2j 2 d 4 c e 3G1G2例例数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling2 d 4a c e1 f 3 G1b2 d 4 g e 5 i 3 j G2 h c2 4a b1 f 3 G1-G254 g h i3 j G2-G1254 g h i j 2a b1 f 3G2G1例例数数 学学 模模 型型 SHENY

39、ANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modelingv1 v2v4 v3 G2v1 v2v4 v3 G1G2u1u1G1例例数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling定义定义3.6 设设G1=V, E1, 对于对于G2=V, E2,若有若有G=V, E1E2是完全图是完全图, ,且且E1E2 = , 则称则称G2是是G1的补图。的补图。 图图G1 图图G2 图图G数数 学学 模模 型型 SHENY

40、ANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 一个图除了可以用图形表示之外，还可用矩阵来表示。用矩阵表示图有利于计算机处理。 3.6.1 邻接矩阵邻接矩阵 3.6.2 关联矩阵关联矩阵上级目录数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 定义定义3.7：设图：设图G = V,E，V = v1,v2, vn，则，则G的邻的邻接矩阵是一个接矩阵是一个nn矩阵矩阵A(G) = aij (简记为简记

41、为A)，其中若，其中若vi邻接邻接vj，则，则aij=1;否则否则aij=0。 注注: 若若aij取为连接取为连接vi与与vj的边的数目的边的数目, 则称则称A为推广的邻为推广的邻接矩阵。接矩阵。数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling邻接矩阵邻接矩阵 A =0 1 0 01 0 1 00 1 0 10 0 1 10 1 0 01 0 2 00 2 0 10 0 1 1推广的推广的邻接矩阵邻接矩阵 A =数数 学学 模模 型型 SHENYANG UNIVERSITY OF

42、 TECHNOLOGYGraph Theory in Mathematical Modeling1） 对无向图对无向图G，其邻接矩阵为，其邻接矩阵为A=aij,其中其中., 0, 1不相邻与若相邻与若jijiijvvvva54321543210010000100110110010100110vvvvvAvvvvv数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling2） 对有向图对有向图G=V,E，其邻接矩阵为，其邻接矩阵为A=aij,其中其中.),(, 0,),(, 1EvvEvva

43、jijiij若若432143210100001000001110uuuuAuuuu数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling3） 对有向赋权图对有向赋权图G=V,E,其邻接矩阵为其邻接矩阵为A=aij,其中其中,(,),0,(,).ijijijijijwv vEwaijv vE若且为其权，若43214321040608730uuuuAuuuu对于无向赋权图的邻接矩阵可类似定义对于无向赋权图的邻接矩阵可类似定义. 数数 学学 模模 型型 SHENYANG UNIVERSITY

44、 OF TECHNOLOGYGraph Theory in Mathematical Modeling定义定义3.8 无环图无环图G的关联矩阵的关联矩阵B(G) = bij (简记为简记为B)是一个是一个nm矩阵矩阵，当点，当点vi与边与边ej关联时关联时bij=1，否则，否则bij=0。v1 e1 e5v2 v5 e6 e7 e2 e4v3 e3 v4例例B = e1 e2 e3 e4 e5 e6 e7v1v2v3v4v500110001001100010011000000111110001数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph

45、Theory in Mathematical Modeling说明：定义中说明：定义中“无环无环”的条件可去掉，此时的条件可去掉，此时bij=点点vi与边与边ej关联的次关联的次数（数（0, 1, 2(环环)。e1v4v3v2v1e7e5e4e3e2e61 1 0 0 1 0 11 1 1 0 0 0 0( )0 0 1 1 0 0 10 0 0 1 1 2 0M G性质：性质：关联矩阵的每列和为关联矩阵的每列和为2 2；其行和为对应顶点的度数。；其行和为对应顶点的度数。数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in M

46、athematical Modeling1） 对无向图对无向图G=V,E，其关联矩阵为，其关联矩阵为M=mij,其中其中., 0, 1不关联与若相关联与若jijiijevevm54321543211000001000111100010100011vvvvvMeeeee数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling2） 对有向图对有向图G=V,E，其关联矩阵为，其关联矩阵为M=mij,其中其中1,1,0,.ijijijijvemveve若是的起点若是的终点若不是的起点与终点432

47、15432111000101100001101101uuuuMeeeee数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 4.1 相关概念相关概念 4.2 Dijkstra算法算法 4.3 Floyd算法算法数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 定义定义4.1 给定图给定图G =V, E，w= v0e1v1e2ekvk是是G中中点边交替点边交替组成组成的

48、的序列序列，其中，其中viV，ei=(vi-1,vi)E，i= 0,1, k，则称，则称w为一条从起为一条从起点点v0到终点到终点vk的长为的长为k的的通路通路(或或路径路径、通道通道、途径途径、链链), 简称简称(v0, vk)通路。通路。 注：对有向图，要求注：对有向图，要求vi-1和和vi为为ei的始点和终点。的始点和终点。 边不重复的通路称为边不重复的通路称为简单通路简单通路（或（或迹迹）；）； 除起点与终点可以相同外，任意两点都不同的通路，称为除起点与终点可以相同外，任意两点都不同的通路，称为基本基本通路通路，基本通路简称为，基本通路简称为路路。 显然，基本通路必为简单通路。显然，基

49、本通路必为简单通路。数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 称起点与终点相同的通路为称起点与终点相同的通路为回路回路(或或闭途径闭途径) ； 边不重复的回路称为边不重复的回路称为简单回路简单回路； 起点与终点相同的长为的基本通路称为起点与终点相同的长为的基本通路称为基本回路基本回路，也，也称为称为圈圈。 如不引起混淆（如在简单图中），通路与回路均可用如不引起混淆（如在简单图中），通路与回路均可用点序列来表达。点序列来表达。 k(奇奇,偶偶)圈：圈：长为长为k (奇奇,偶

50、偶)的圈。的圈。 3圈常称为三角形。圈常称为三角形。 易知，图中若两个不同点易知，图中若两个不同点u与与v 间存在途径间存在途径(通路通路)，则，则 u 与与 v 间必存在路；若过点间必存在路；若过点u存在回路，则过点存在回路，则过点u 必存在必存在圈圈 。 数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling例例4.1 在下图在下图G 中，取中，取w1=v1v2v3，w2=v1v2v3v4v2 ，w3=v1v2v3v2v3v4 ( 注：简单图可只用点序列表通路）注：简单图可只用点序

51、列表通路）v1v4v5v3v2Gw1, w2, w3 依次为长为依次为长为2,4,5的途径；的途径；w1与与w2为为迹迹 ，w1为路。为路。 另外我们可看出另外我们可看出,G中中v1v2v5v1为长为为长为3的圈，的圈，v1v2v3 v4v2v5v1 为长为为长为 6 的回路。的回路。图图4.1数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 定义定义4.2 任意两点之间均存在通路的图称为任意两点之间均存在通路的图称为连通图连通图，否则称为，否则称为非连通图非连通图。非连通图中的

52、连通子图，称为。非连通图中的连通子图，称为连通分支连通分支。 图图4.3所示的图为连通图，而图所示的图为连通图，而图4.4所示的图为非连通图，它含有所示的图为非连通图，它含有两个连通分支。两个连通分支。图图4.3图图4.4数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 定义定义4.3 设图设图G是赋权图，是赋权图， 为为G中的一条路，则称中的一条路，则称 的的各边权之和为路各边权之和为路 的的长度长度。 对于对于G的两个顶点的两个顶点u和和v，从，从u到到v的路一般不只一条，的

53、路一般不只一条，其中最短的一条称为从其中最短的一条称为从u到到v的的最短路最短路；最短路的长称为从；最短路的长称为从u到到v的的距离距离，记为，记为d(u, v)。 约定约定: d(u, u)=0; d(u,v d(u,v)=)= ，若没有路连接若没有路连接u和和v。 图图G的的直径直径: d(G) = max d(u, v) | u, vV数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 最短路问题是图论应用的基本问题，很多实际问题，最短路问题是图论应用的基本问题，很多实际问题

54、，如线路的布设、运输安排、运输网络最小费用流等问题如线路的布设、运输安排、运输网络最小费用流等问题,都可通过建立最短路问题模型来求解都可通过建立最短路问题模型来求解. 求解最短路问题的两种方法：求解最短路问题的两种方法：Dijkstra和和Floyd算法算法. (1)求赋权图中从给定点到其余顶点的最短路求赋权图中从给定点到其余顶点的最短路; ; (2) (2)求赋权图中任意两点间的最短路求赋权图中任意两点间的最短路. .数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 解决上述问

55、题的一个方法是由解决上述问题的一个方法是由Dijkstra (迪杰斯特拉迪杰斯特拉)于于1959年提出的算法，此算法不仅能求出赋权图指定两点年提出的算法，此算法不仅能求出赋权图指定两点间的最短路，而且能求出从指定点到其余各顶点的最短路间的最短路，而且能求出从指定点到其余各顶点的最短路. 目前它是求无负权图最短路的目前它是求无负权图最短路的最好最好方法方法. Dijkstra算法是一种迭代算法，它依据的是一个重要而算法是一种迭代算法，它依据的是一个重要而明显的性质：明显的性质： 最短路是一条路，最短路上的任一子段也是最短路。最短路是一条路，最短路上的任一子段也是最短路。数数 学学 模模 型型 S

56、HENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 按距按距u从近到远为顺序，依次求得从近到远为顺序，依次求得u0到图到图G的各顶点的各顶点的最短路和距离，直至顶点的最短路和距离，直至顶点v(或直至图或直至图G的所有顶点的所有顶点)。步骤步骤: :把结点集把结点集V V分割为二子集分割为二子集 S,T.S,T.开始时开始时S=a,TS=a,T= =V-V-S S. .步骤步骤: :对每结点对每结点 t t T T, ,求出求出 D(tD(t) )之后再定出之后再定出x x T T 使得使得 D(xD(x)=

57、)= minD(x)|tminD(x)|t T T.步骤步骤: :置置 S S 为为 S Sxx 置置 T T为为T-x.T-x.若若 T=T=则停止则停止, ,否则转否则转步骤步骤作作下一次循环下一次循环. .数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 对每个顶点对每个顶点v，定义两个标号，定义两个标号l(v), z(v), 其中其中l(v)为从为从u0到到v的路长；的路长； z(v)为为v的父节点（前一个点）。的父节点（前一个点）。S：具有永：具有永久标号的顶集。久标号

58、的顶集。 算法的过程就是在每一步改进这两个标号，最终算法的过程就是在每一步改进这两个标号，最终l(v)为为u0到到v的最短路长。的最短路长。 输入带权邻接矩阵（距离矩阵）输入带权邻接矩阵（距离矩阵）w(u, v).数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling000(1): , ()0, ,( ),( ),(2)( ), ( ): ,( )( )( , ),( )( )( , ),( )(3)*( ), *,*(4),(2);,.Sul uvSVSl vz vuul v z v

59、vSVSl vl uw u vl vl uw u vz vuvl vSSSvuvS 赋初值 令令更新若则令设是使取最小值的 中的顶点 则令若转否则 停止数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 寻求赋权图中各对顶点之间最短路，显然可以调用寻求赋权图中各对顶点之间最短路，显然可以调用 Dijkstra 算法。算法。 具体方法是：每次以不同的顶点作为起点，用具体方法是：每次以不同的顶点作为起点，用 Dijkstra 算法求出从该起点到其余顶点的最短路径，反复算法求出从该起点到

60、其余顶点的最短路径，反复执行这样的操作，就可得到每对顶点之间的最短路。执行这样的操作，就可得到每对顶点之间的最短路。 但这样做需要大量重复计算，效率不高。但这样做需要大量重复计算，效率不高。R. W. Floyd（弗洛伊德）另辟蹊径，提出了比这更好的算法，操作方（弗洛伊德）另辟蹊径，提出了比这更好的算法，操作方式与式与 Dijkstra 算法截然不同。算法截然不同。数数 学学 模模 型型 SHENYANG UNIVERSITY OF TECHNOLOGYGraph Theory in Mathematical Modeling 直接在图的带权邻接矩阵中用插入顶点的直接在图的带权邻接矩阵中用插入