图论课件---01-2015

1、图论任课教师：王磊基础教学部数学教研室图论发展史图论在现代科学技术中有着广泛的应用,如： 网络设计、计算机科学、信息科学、密码学、DNA 的基因谱的确定和计数、工业生产和企业管理中 的优化方法等都广泛的应用了图论及其算法。首先我们通过图的发展过程来了解一下图论所 研究的内容。图论起源于1736年的一个游戏-哥尼斯城堡 七桥问题。七桥问题C包含两个要素：对象（陆 地）及对象间的二元关系（是否有桥连接）C转化ADEuler 1736年BADB图论中讨论的图问题：是否能从四块 陆地中的任一块开 始，通过每座桥恰好 一次再回到起点？转化 是否能从任意一个 顶点开始，通过每 条边恰好一次再回到起点？问题

2、一：四色问题四色问题是世界近代三大 数学难题之一。四色问题的内容是：任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。它 的 提 出 来 自 英 国 。1852年，毕业于伦敦大学的弗南西斯 ·格思里发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家 都被着上不同的颜色。”进入20世纪以来，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。后来美国数 学家富兰克林于1939年证明了22国以下的地图都 可以用四色着色。1950年，有人从22国推进到35 国。1960年，有人又证明了39国以下的地图可以 只用四种颜色着色；随后又推进到了50国

3、。1976年6月，美国伊利诺大学哈肯与阿佩尔在 两台不同的电子计算机上，用了1200个小时，作 了100亿判断，终于完成了四色定理的证明，轰动 了世界。然而，真正数学上的严格证明仍然没有得到！数学家仍为此努力，并由此产生了多个不同的图论分支。问题二：Hamilton问题Hamilton问 题 源 于 1856年 ，英 国 数 学 家 Hamilton 设 计 了一 个 名 为 周游世界 的游戏：他 用 一 个 正十二面 体的二十个 端 点 表 示世界上 的二十座大 城 市 （ 见图）， 要求游戏者 找 一 条 沿着十二 面体的棱通 过 每 个 端点恰好 一次的行走 路 线 。 反映到图 论上就

4、是判 断 一 个 给定的图 是否存在一条含所有顶点的回路。图论是组合数学的一个分支，与其它数学分支如群论、矩阵论、集合论、概率论、拓 扑学、数值分析等有着密切的联系。又由于图论给含有二元关系的系统提供了 数学模型，因而在许多领域里都具有越来越 重要的地位，并且在物理、化学、信息学、 运筹学等各方面都取得了丰硕的成果。从二十世际50年代以来，由于计算机的 迅速发展，有力地推动了图论的发展，使得 图论成为数学领域里发展最快的分支之一。 因此,学好图论十分重要。第八章图论原理第1节图的基本概念第2节通路、回路与连通性 第3节欧拉图第4节哈密顿图第5节图的矩阵表示第8章图论原理§8.1图的基

5、本概念 一 、基本概念图论中的“图”并不是通常意义下的几何图形或物体的形状图,而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统.定义8.1.1 一个有序二元组(V, E ) 称为一个图,记为G = <V, E >, 其中 V称为G的顶点集, Vf, 其元素称为顶点或结点, 简称点; E称为G的边集, 其元素称为边, 它联结V 中的两个点, 如果这两个点是无序的, 则称该边为无向边, 否则, 称为有向边.例子8.1.1四个城市：v1、v2、v3、v4, 其中v1与v2间，v1与 v3间，v2与v4间有直达高速公路相连，写出其集 合并画出此图。解：G =V，E，V =

6、(v1，v2，v3，v4) ，E = (l1，l2，l3)，其中：l1= (v1, v2)l2= (v1, v3)l3 = (v2, v4)l1v1v2ll2 3v4v3(一)结点与边的关系: 结点与边(不)相 关联：若一条边 lk = (v ,v )，则称结点vi、vj与边lk相ij与边l1、l2关联。例如：前边例题中结点 v1相关联，而与边l3不相关联。l1v1v2l结点与结点,边与边(不)相邻接A结点与结点：如果两个结点与 同一条边相关联, 则称这两个结点v4 相邻接,否则不相邻接如：例题中 v1 与 v2、v3 相邻接，而与v4 不相 邻接。2l3v3B边与边：如果若干条边与同一个结点

7、相关联，则称这些边是相邻接的，否则不相 邻接。如: 例题中 l2 与 l1 相邻接，而与 l3 不相邻接。l1v1v2l3l2v4v3(二)特殊点:孤立点:不与任何结点相邻接的结点悬挂点:只与一条边相邻接的结点v1v1是孤立点v3 、v4是悬挂点v2v3v4(三)特殊的边:环:一条与两个相同的结点相关联的边多重边:与两个结点相关联的边若多于一条，这些边为多重边。如图：(四) 图的分类: a 按边的方向分类有向图：边有方向的图无向图：边无方向的图图1 图2称点vi , vj为无向边（vi ,vj )的端点. 在有向图中, 称 点vivj分别为边（vi ,vj )的起点和终点。b.按边的种类分类：

8、多重图:含多重边的图叫多重图。简单图:不含环与多重边的图叫简单图。有权图:有时在一个图中边的旁边可以附 加数字以刻划此边的某些数量特征，叫做 边的权，此边叫做有权边，具有有权边的 图叫有权图或带权图。无权图:没有权边的图叫无权图。G1、G2是多重图G4是简单图G3是多重图A1有权图BBBAA BA BBA A2B无权图c.按结点集与边集的“阶”分类有限图与无限图：V 与 E 为有限集合的图叫有限图，否则叫 无限图。(n,m)图：有 n 个结点与 m 条边的图。零图:即(n,0)图;平凡图:即(1,0)图。一些特殊的图定义8.1.2设G为n阶无向简单图，若G中每个顶点 均与其余的n-1个顶点相邻

9、，则称G为n阶无向完 全图，简称n阶完全图，记做Kn(n1)。设D为n阶有向简单图，若D中每个顶点都邻接到其余的n-1个顶点，又邻接于其余的n-1个顶点，则称D是n阶有向完全(完备)图。设D为n阶有向简单图，若D的基图为n阶无向完全图Kn，则称D是n阶竞赛图。(1)为K5，(2)为3阶有向完全图，(3)为4阶竞 赛图这几种图形的边数： n阶无向完全图的边数为n(n-1)/2 n阶有向完全图的边数为n(n-1) n阶竞赛图的边数为n(n-1)/2二、子图定义8.1.3 设G=<V，E>，G =<V，E>为两个图(同为无向图或同为有向图)，若VÍV且E Í

10、;E，则称G是G的子图，G为G的母图，记作GÍG. 又 若VÍV 且EÌE，则称G为G的真子图。若V=V， EÍE 则称G为G的生成子图。ababba1a1b11母图真子图d1c1dcdcaba1生成子图b1G'ÍG且d1c1dcV'=V定义8.1.4设G=<V，E>为n阶无向简单图，以V为结点集，以使G成为完全图Kn所添加边构成的集合为边集的图，称为G的补图，记做GG相对于Kn的补图是下图中的G时于补图，显然再以下结论:1、G 与 百 互为补图 ， n G =G c2 、E(G )U E( G )=E(完全国 )且

11、E(G )nE( E ) =申 。3、完全国与 n阶零固互为补图 c4、G 与 G 均是完全国的生成子固 。互为补图互为补图不是补图三、结点的次数定义8.1.5：在有向图中,对于任何结点v.引出次数(或出度):以v为始点的边的条数,记为deg+(v);引入次数(或入度):以v为终点的边的条数,记为deg-(v);次数(或度数):结点v的引出次数和引入次数 之和,记作deg(v)。deg+(v1)=2 deg+(v2)=1 deg+(v3)=2 deg+(v4)=2deg-(v1)=2 deg-(v2)=1 deg-(v3)=2 deg-(v4)=2deg(v1)=4 deg(v2)=2 deg

12、(v3)=4 deg(v4)=4在无向图中,结点v的次数是与结点v相关联的边的条数,也记为deg(v)。孤立结点的次数为零。l1deg(v1)=2v1v2deg(v2)=2l2l3deg(v3)=1v4v3deg(v4)=1握手定理定理8.1.1(握手定理) 设图G=<V,E>为任意无向图V=v1,v2,vn，|E|=m，则nåi =1d (vi ) = 2m有n个人握手，每人握手x次，握手总次数为S，必有S= nx/2证 G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，当然，m条边，共提供2m度。定理8.1.2(握手定理) 设D=&l

13、t;V,E>为任意有向 图，V=v1,v2,vn，|E|=m，则nnnåd (vi ) = 2m且 åd(vi ) = åd(vi ) = m+-i=1i=1i=1练习1:2+2+1+6=11已知无向图G中有10条边，2个2度结点,2个3度结点,1 个4度结点,其余结点的度数都是1,问G中 有多少个结点?练习2:2+2+3=72+2+6=10已知无向图G中有10条边，3度与4度结点各2个,其余结点的度数均小于3,问G中至少有多少个 结点?最多有多少个结点?K5图3彼得松图定义8.1.6:各结点的次数均相同的图称为正则图,各结点的次数均为k时称为k正则图。图3

14、所示的称为彼得松(Petersen)图易见n阶零图是0-正则图n阶无向完全图是(n-1)-正则图彼得松图是3-正则图。四、图的同构试观察下面各图有何异同？定义8.1.7 G1=<V1,E1>和G2=<V2,E2>是两个图，若存在函数f:V1® V2 ,f是双射，且若定义函数 g : E1® E2 ,对于任意的 (v1 ,v1¢) Î E1 , g(v1, v1¢) = (f (v1 ),f (v1¢).g也是一个双射则称图G1和图G2是同构的两个图，并称 f 为图的同构映射，记为G G .12v1u1v4v2v

15、3u 4(a)(b)两个同构的u2图，在我们讨论的范围内认为是一u样的图4图 4所 示 的 两图是 同构的。 因为作 映射g(vi)=vi(i=1,2,6), 可 使 (vi,vj) 一 一 对 应 于(g(vi),g(vj)。图4u3u1u2u4可以看到此两图在结点间存在着一一对应映射g：g(a)u3， g(b)u1，g(c)u4，g(d)u2，且有（a,c），（a,b），（b,d），（c,d）分别与（u3,u4）,（u3,u1），（u1,u2），（u4,u2）一一对应。同构分析本例还可以知道，此两图的结点度数也分别对应相等，如表所示。同构的性质(必要条件)：1结点数目相同；2边数相等；3度

16、数相同的结点数目相等。不是充分条件，下图(a)和(b)满足上述三个条 件，但并不同构。若 G与 G同构，它的充要条件是：两个图的结点和边分别存在着一一对应，且保持关联关系。G1 G2 .G3 G4在 G1 G G5 G6点间的对应关系为：G7与G8不同构2 . 中，结av1, bv2, cv3, dv4, ev5G5称为彼得松图图中(a)(b)均满足前面3个条件，但因为对于图(a)中的任一顶点，与该点关联的3个顶点间彼此不 邻接；而对于图(b)中的任一顶点，与该点关联 的3个顶点中有2个是邻接点，所以它们不同同构样。可以看出图(c)(d)也是不同构的。§8.2通路、回路、图的连通性先

17、讨论有向图的通路、回路，然后推广到无向图 一、通路定义8.2.1 给定有向图 G=<V,E>,设G中顶点与边 的交替序列 =v0e1v1e2 elvl，若满足如下 条件：vi-1 是ei的始点,vi 是ei的终点,i=0,1,l , 则 称为顶点v0到vl的通路。v0和vl分别称为此通 路的起点和终点,中边的数目l 称为的长 度。ü若v0=vi ，则称此通路为回路。ü若中所有边各异，则称为简单通路ü若中所有点各异，则称为基本通路。P4, P6则即非基本下图：起点为1，终点为通3路的亦通非路简有单：通路P1: (1, 2, 3),P2: (1, 4, 3

18、)12P3: (1, 2, 4, 3)P4: (1, 2, 4, 1, 2, 3)P5: (1, 2, 4, 1, 4, 3)P6: (1, 1,1, 2, 3)43简单通路：各边都不相同的通路。基本通路：各点都不相同的通路。一条基本通路一定是简单通路, 反之不然。如P5:是简单 通路但不是基本通路。 P1, P2, P3是基本通路.二、回路回路:起始结点与终止结点相同的通路。可见回路是一种特殊的通路。12简单回路:各边都不同基本回路:各点都不同C1: (1, 1),C2: (1, 2, 1)C3: (1, 2, 3, 1)C4: (1, 4, 3, 1)C5: (1, 2, 3, 2, 1)

19、43C6: (1, 2, 3, 2, 3, 1), C1, C2, C3 , C4是基本回路, (当然也是简单回路), C5是简单回路但非基本回路, 而C6既非基本回路亦非简单回路。例如：v0v1v2v3v41图(1) 为v0 到v4的长为4的 基本通路v0v1v22v7v8v3v4v6v5 v4图(2)为v0 到v8的长为8的 简单通路v0= v5v1v2v3v4图(3) 为v0 到v5(= v0)的3长为5的基本回路vvv0= v815图(4) 为v0 到v8(= v0)的vv27v6v34长为8的简单回路有向图中, 环和两条方向相反边构成的回路分别为长度为1和2的基本回路(圈)。定理8.

20、2.1在有向(n,m)图中，任何基本通路长度小于或等于n-1。定理8.2.2在有向(n,m)图中，任何基本回路长度小 于或等于n。例8.2.1：求下图回路数和C到B的通路A要求各找出4个以上e8(e2),(e3, e4, e2),(e3, e5, e6, e10, e2),e7e9Fe1Be10(e3, e5, e6, e7, e1)是从Ce6e2到B的4个通路。这4条Ee4C通路中第一条、第四条是基本通路；e5e3D(e3, e4),(e3, e5, e6, e10),(e8),(e9)是4条有向回路;上图中,从B到其它任意点都没有回路。定义8.2.2在一个有向图G中，若从顶点vi到vj 存在通路，则称vi与vj是可达的的。短程线:有向图G中，从结点vi到vj长度最短的通 路。距离：短程线的长度称为vi与vj之间的距离,记 作 d<vi ,vj>,当vi不可达vj时,规定 d<vi,vj>=注：相应概念可以推广到无向图，将无向图中 方向相反的两条边转换成一条无向边。例8.2.2在(a)中有：d(v2，v1)1，d(v1，v2)2，d(v3，v1)2，d(v1，v3)4；在(b)中有：d(v1，v3)2，d(v3，v7)3，d(