图论及其应用教学课件

1、图论及其应用第1页，共101页。图论发展史 图论在现代科学技术中有着重要的理论价值和广泛的应用背景，如：线性代数、密码学、物理化学、网络设计、计算机科学、信息科学、DNA的基因谱的确定和计数、工业生产和企业管理中的优化方法等都广泛的应用了图论及其算法。 首先我们通过图的发展过程来了解一下图论所研究的内容。 图论起源于18世纪的一个游戏-俄罗斯的哥尼斯堡七桥问题。 （1736年 瑞士数学家欧拉图论之父）第2页，共101页。A B D C 转化 Euler1736年 B D CA 图论中讨论的图 问题：是否能从A，B，C，D中的任一个开始走，通过每座桥恰好一次再回到起点？是否能从任意一个顶点开始，

2、通过每条边恰好一次再回到起点？转化包含两个要素：对象（陆地）及对象间的二元关系（是否有桥连接）七 桥 问 题第3页，共101页。中国邮递员问题1962年中国数学家管梅谷提出图论中的“中国邮递员问题”。问题：一个邮递员从街区的某一点出发，经过街区每条街道至少一次又回到原出发点，如何设计投递路线，使总路程最短？第4页，共101页。 Hamilton问题源于1856年，英国数学家Hamilton设计了一个名为周游世界的游戏：他用一个正十二面体的二十个端点表示世界上的二十座大城市（见图），提出的问题是要求游戏者找一条沿着十二面体的棱通过每个端点恰好一次的行走路线。反映到图论上就是判断一个给定的图是否存

3、在一条含所有顶点的回路。Hamilton问题第5页，共101页。 四色问题是世界近代三大数学难题之一。 四色问题的内容是：任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。 它的提出来自英国。1852年，毕业于伦敦大学的弗南西斯格思里发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。”这个现象能不能从数学上加以严格证明呢？四色问题第6页，共101页。 1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题。 18781880年两年间，著名的律师兼数学家肯普和泰勒两人分别提交了证

4、明四色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此也就解决了。 1890年，在牛津大学就读的年仅29岁的赫伍德以自己的精确计算指出了肯普在证明上的漏洞。不久，泰勒的证明也被人们否定了。后来，人们开始认识到，这个貌似容易的题目，其实是一个可与费马猜想相媲美的难题。第7页，共101页。 进入20世纪以来，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。后来美国数学家富兰克林于1939年证明了22国以下的地图都可以用四色着色。1950年，有人从22国推进到35国。1960年，有人又证明了39国以下的地图可以只用四种颜色着色；随后又推进到了50国。 1976年6月，美国伊利诺大学哈肯与

5、阿佩尔在两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明，轰动了世界。 然而，真正数学上的严格证明仍然没有得到！数学家仍为此努力，并由此产生了多个不同的图论分支。第8页，共101页。几个事实：任意的6个人中，总有3个人互相认识或有3个人互不认 识。任意的9个人中，总有3个人互相认识或有4个人互不认 识。问题： 对任意的自然数k和t，是否存在一个最小的正整数r(k,t)，使得每个至少有r(k,t)个人的团体，总有k个人互相认识或有t个人互不认识。 拉姆瑟（F.P. Ramsey）在1930年证明了这个数 r(k,t)是存在的，人们称之为 Ramsey数。确定

6、其精确值是个公开的难题。Ramsey 问题第9页，共101页。Ramsey数R(p,q)第10页，共101页。Ramsey数的计算Ramsey数的计算是对人类智力的挑战！例如R(4,5)=25 (1993年计算机11年的计算量)Erds用如下比喻说明其困难程度：一伙外星人入侵地球，要求一年内求得R(5,5)，否则将灭绝人类！那么也许人类能集中所有计算机和专家来求出它以自保；但如果外星人问的是R(6,6) ，那么人类将别无选择，只能拼死一战了。第11页，共101页。Ramsey理论的哲理意义完全的无序是不可能的(Complete disorder is impossible)。任一足够大的结构中

7、必定包含一个给定大小的规则子结构。无序无意的行为产生了有规律的后果，发人深思耐人寻味。古人在满天的星斗中发现野兽和众神群集于天空的图形，以为是造物主的杰作。但根据Ramsey 定理，只要随机分布的星星数目足够多，就可以描绘出各种图形的轮廓。1994年Statistical Science的一篇论文利用统计方法证明：圣经隐藏了许多讯息，而这些讯息是有意安排的，绝非文字排列偶然造成的。 1997 年Michael Drosnin的The Bible Code 通过计算机扫读圣经中的304805个字母，发现圣经密码当中传达的讯息除了拉宾被刺杀外，还包括美国肯尼迪和林肯两位总统，以及印度总理甘地遇刺的

8、事件，日本神户、美国旧金山的大地震、世界末日与广岛原子弹轰炸等，种种过去与未来发生的大事件。Ramsey理论的哲理意义第12页，共101页。最精美的组合定理Rota：如果要求在组合学中仅举出一个精美的定理，那么大多数组合学家会提名Ramsey定理。1984年Wolf奖得主Erds1997年Fulkerson奖得主Kim1998年Fields奖得主Gowers1999年Wolf奖得主Lovasz2003年Steele奖得主Graham2005年Gdel奖得主Alon2006年Fields奖得主Tao 均对Ramsey理论有杰出贡献第13页，共101页。第14页，共101页。Ramsey理论的哲理

9、意义第15页，共101页。某村里有n 个男士与n 个女士，每个男士恰好认识 r 个女士，每个女士也恰好认识 r 个男士，问：在这个村中，能否做到：每个男士与其认识的女士结婚，每个女士也恰好与其认识的男士结婚。婚姻匹配第16页，共101页。图论相关的交叉研究 代数图论 拓扑图论 化学图论 算法图论 随机图论 极值图论 超图以往数学家习惯将纯数学应用于其它学科，Gowers将图论和组合数学中的Ramsey理论应用于泛函分析的研究，获得了1998年的Fields奖。第17页，共101页。内容提要图的基本概念图的基本概念；二部图及其性质；图的同构；关联矩阵与邻接矩阵。路、圈与连通图；最短路问题。树及其

10、基本性质；最小生成树。图的连通性割点、割边和块；边连通与点连通；连通度；Whitney 定理；可靠通信网络的设计。匹配问题匹配与最大匹配；完美匹配；二部图的最大匹配。第18页，共101页。欧拉图与哈密尔顿图欧拉图；中国邮递员问题；哈密尔顿图；旅行商问题。独立集、覆盖集与团点独立集、点覆盖集、边覆盖集与团的概念。图的着色问题点着色；边着色；平面图；四色猜想。网络流理论有向图；网络与网络流的基本概念；最大流最小割定理；求最大流的标号算法；网络流理论的应用。第19页，共101页。主要参考书1 J.A. Bondy and U.S. Murty, Graph Theory with Applicati

11、ons, 1976 （GTM244, 2008）。2 B. Bollobas, Modern Graph Theory (现代图论)，科学出版社，2001。3 王树禾，图论，科学出版社，2004。4 蒋长浩，图论与网络流，中国林业出版社，2001。5 徐俊明，图论及其应用，中国科技大学出版社，1998。第20页，共101页。第一章 图和子图1.1 图和简单图1.2 子图1.3 图的同构1.4 顶点的度1.5 路、圈和连通1.6 关联矩阵和邻接矩阵1.7 应用： 最短路问题第21页，共101页。1.1 图和简单图第22页，共101页。图graph， 顶点vertex，边edge图的定义其中V(G

12、) 是非空的顶点集， E(G)是不与V(G)相交的边集，而 是关联函数，它使G的每条边对应于G 的无序顶点对。若e是一条边，而u和v是使得 的顶点，则称 e连接 u 和 v ；顶点 u 和 v 称为 e 的端点。 一个图 G 是指一个有序三元组 ，第23页，共101页。例 1此时， 定义为这便定义出一个图。第24页，共101页。图的图形表示 通常，图的顶点可用平面上的一个点来表示，边可用平面上的线段来表示（直的或曲的），而边仅在端点处相交， 这样画出的平面图形称为图的图形表示。第25页，共101页。G = (V, E) ，其中这便定义出一个图。例2注：由于表示顶点的平面点的位置的任意性，同一个

13、图可以画出形状迥异的很多图示。例2中图的另一个图示：第26页，共101页。 图的图示直观易懂，因此以后一般说到一个图，我们总是画出它的一个图示来表示。 阅读书P.2-3页，理解平面图和非平面图，并且完成课后习题1.1.2。第27页，共101页。一些概念和术语：（1） 点与边的关联(incident)（2） 点与点的相邻(adjacent)（3） 边与边的相邻（4）（自）环(loop)、连杆(link)（5）重边(parallel edge)（6）简单图(simple graph)（7）有限图(finite graph)（8）平凡图(trivial graph)和非平凡图（9）空图(empty

14、graph)和零图（null graph)（10）图的顶点数（图的阶order） 、边数(size)第28页，共101页。1.2 图的同构 由前已知，同一个图有不同形状的图示。反过来，两个不同的图也可以有形状相同的图示。比如： 可见 G1 和 G2 的顶点及边之间都一一对应，且连接关系完全相同，只是顶点和边的名称不同而已。这样的两个图称为是同构的(isomorphic)。第29页，共101页。 从数学上看，同构的两个图，其顶点间可建立一一对应，边之间也能建立一一对应，且若一图的两点间有边，则在另一图中对应的两点间有对应的边。严格的数学定义如下。定义: 两个图G = (V (G), E(G) 与

15、H = (V (H), E(H) ，如果存在两个一一映射： :V (G) V (H) ， : E(G) E(H) ，使得对任意e = (u,v) E(G) ，都有( (u), (v) E(H) 且 (e) = ( (u), (v) ，则称图G 与H 同构。记为G H 。第30页，共101页。 G1、G2 在对应viui (i=1,2,3,4,5,6)下是同构的。例3x1x2y1x3y2y3v1v2v3v4v5v6第31页，共101页。画出所有的阶数不大于4，大小为3的所有非同构简单图：第32页，共101页。画出阶数为5大小为3的所有非同构简单图G1G2G3G4第33页，共101页。无标号的图注

16、：判断两个图是否同构目前没有好算法。第34页，共101页。一些特殊图类：（1） 完全图(complete graph)例 4K3K4K5K5第35页，共101页。（2） 二部图 (bipartite graph)：若图G 的顶点集可划分为两个非空子集X 和Y，使得任一条边有一个端点在X 中，另一个端点在Y 中，则称G 为二部图（或偶图），记为G (X U Y , E) ，(X ,Y ) 称为G 的一个划分（二分类）。第36页，共101页。K3,3 K2,4 （3）完全二部图(complete bipartite graph)：在简单二部图G = (X U Y , E) 中，若X 的每个顶点与Y

17、的每个顶点有边连接，则称G 为完全二部图；若| X |= m，|Y |= n ，则记此完全二部图为K m , n。特别地， K 1 , n 称为星。第37页，共101页。（4） r部图、完全r部图任意一个Vi 内部都没有边。完全 r-部图K(n1,n2,nr)：如果任意Vi中的所有点与Vj中的所有点都相连。一个简单图叫作r-部图, 如果第38页，共101页。（6） G的补图(complement)： 设G 是一个图，以V (G) 为顶点集，以(x, y) | (x, y) E(G)为边集的图称为G 的补图，记为GC。第39页，共101页。1.3 子图(1) 子图(subgraph)： 如果V

18、(H) V (G) 且 E(H) E(G) ，则称图 H 是G 的子图，记为 H G 。(2) 生成子图(spanning subgraph): 若H 是G 的子图且V(H)=V(G)，则称H 是G 的生成子图。(3) 点导出子图(induced subgraph)： 设V V (G) ，以V 为顶点集，以两端点均在 V 中的边的全体为边集所组成的子图，称为 G 的由顶点集 V 导出的子图，简称为 G 的点导出子图，记为GV 。第40页，共101页。(4) 边导出子图(edge-induced subgraph)：设E E(G) ，以 E 为边集，以 E 中边的端点全体为顶点集所组成的子图，称

19、为G 的由边集 E 导出的子图，简称为 G 的边导出子图，记为 GE。(5) 定义G - V (6) 定义G - E (7) 基础简单图：压缩平行边，去掉环基础简单图第41页，共101页。例6第42页，共101页。v2v5v3v4v1Ge1e8e7e6e5e4e3e2v2v3v4v1e1e8e6e5e4v2v5v4v1e1e7e3e2v2v5v4e7e6e5e3v2v5v3v4v1e1e7e6e4e3例7第43页，共101页。子图的运算：第44页，共101页。G2G1G2G1图的运算：第45页，共101页。G2G1第46页，共101页。1.4 顶点的度顶点v 的度(degree)：d(v) =

20、 顶点v 所关联的边的数目（环边计两次）。图G 的最大度： (G) = maxd G (v) | v V (G)图G 的最小度： (G) = mind G (v) | v V (G)正则图(regular graph)：每个顶点的度都相等的图。度序列：见习题1.5.5孤立点： d(v) =0 第47页，共101页。定理 1.1证明：按每个顶点的度来计数边，每条边恰数了两次。推论1.1 任何图中，奇度顶点的个数总是偶数（包括0）。设V1 和 V2 分别是G中奇点集和偶点集，由证明：而 是偶数，所以 是偶数，故 是偶数。定理1.1知，是偶数，第48页，共101页。例 晚会上大家握手言欢，试证握过奇

21、次手的人数是偶数。证明：以参加晚会的人为顶点集构造一个图G，当且仅当二人握手时，在相应的两顶点之间连一条边。于是每人握手的次数即为G的相应顶点的度数。由推论1.1，得证。第49页，共101页。例 空间中不可能有这样的多面体存在，它的面数是奇数，而且每个面由奇数条线段围成证明：如果有这样的多面体，以此多面体的面集合为顶点集构造一个图G，当且仅当两个面有公共边界时，在相应的两顶点之间连一条边。于是G有奇数个顶点，且每个顶点都为奇点，与定理1.1矛盾。故这种多面体不存在。第50页，共101页。1.5 路、圈和连通(1) 途径(walk)：图G 中一个顶点和边交替出现的有限非 空序列注1：起点(v0)

22、；终点(vk) ；内部顶点（内点）；长(k)注2：简单图中的途径可以用顶点来表示若在非简单图中，则表示通过这些顶点的任意途径。注3： W-1； W1W2; 注4： W的(vi,vj)节路和圈有关概念第51页，共101页。(2) 迹(trail)：各边相异的途径。(3) 路(path): 各顶点相异的迹（P_k)。第52页，共101页。(4) 闭途径(closed walk)：具有正的长且起点和终点相同的途径。 闭迹(closed trail) 也称为回路（circuit）。(5) 圈(cycle): 各顶点相异的闭迹。 k圈（C_k)；3圈常称为三角形 图G 中长为奇数和偶数的圈分别称为奇圈(

23、odd cycle)和偶圈(even cycle)。 图G 的围长(girth) 是指G 中最短圈的长；若G没有圈，则定义为无穷大。 最长圈的长称为图G 的周长(circumference)。第53页，共101页。v2v5v3v4v1Ge1e8e7e6e5e4e3e2途径长为 5。长为 5。迹 长为 3。试着寻找其它的 (v1, v3)-路?路例8第54页，共101页。图 K4, E3, P4, C4 and C5 第55页，共101页。图的分支（component）：若图G 的顶点集V(G)可划分为若干非空子集V 1,V 2, ,V ，使得两顶点属于同一子集当且仅当它们在G 中连通，则称每个

24、子图GV i 为图G 的一个分支（ i = 1,2, ）。连通性的概念图中两点的连通：如果在图G 中存在(u，v) 路，则称顶点u，v 在图G 中连通。连通图（connected graph）：图G 中任二顶点都连通。第56页，共101页。 非连通图，三个分支v1v2v3v4e2e3e4e5e6e7 连通图注：（1）图G 的分支是G 的一个极大连通子图。 （2）图G 连通当且仅当1。第57页，共101页。有四个分支的不连通图例第58页，共101页。注：（1）若在G中顶点 x 和 y 是连通的 ，则 x 和 y 之间 的距离(distance) d G(x, y) 是G 中最短 (x, y) 路

25、的长；若没有路连接 x 和 y，则定义d G(x, y)为无穷大。（2）图G 的直径(diameter): D = maxd G (x, y) | x, y V (G) 。第59页，共101页。定理1.2 一个图是二部图当且仅当它不含奇圈。证明： 必要性：设 C = v 0 v 1 v k v 0 是二部图G = (X U Y , E) 的一个圈。不妨设v 0 X ，由二部图的定义知v 1 Y ，v 2 X ， ，一般地，v 2 i X ，v 2 i +1 Y ，（ i = 0,1,）。又因v 0 X ，故v k Y ，因而k 是奇数。注意到圈C 上共有k + 1条边，因此是偶圈。偶图的判定条

26、件第60页，共101页。充分性：显然对连通图证明即可。设G 不含奇圈。任取 u V (G) ，令X = v V (G) | d(u, v)是奇数，Y = v V (G) | d(u, v)是偶数。现证（X,Y）是G的一个二分类。任取一条边 e = v1v2，欲证, v1 ，v2分属于X 和Y。 设P，Q 分别是u 到 v1 ，v2 的最短路。Puv1v2（1）如果 P = Q + v 2 v 1或 Q = P + v 1 v 2 ，则 v 1, v 2到u 的距离奇偶性相反， v 1 , v 2分属于X和Y。第61页，共101页。 假如P，Q 的奇偶性相同，则P 的(u , v 1 ) 节和Q

27、 的(u , v 2 ) 节奇偶性相同，它们与边e 构成一个奇圈，与定理条件矛盾。可见P，Q 的奇偶性不同，从而 v 1, v 2分属于X 和Y。证毕。（2）否则，设u是P 与Q 的最后一个公共顶点，因P 的(u, u) 节和Q 的(u, u) 节都是最短的(u,u) 路，故长相等。Puuv1Qv2Puv1Puv1Puv1Puv1Puv1v1第62页，共101页。由定理 1.2可知图 (a) 所示的图不是二部图，因为它包含一个三角形；图 (b) 所示的图是一个二部图，它不含长为奇数的圈。第63页，共101页。证明：设P = v0v1 v k 为G 中的一条最长路 。因 d (v 0) 2 ，故

28、除 v 1外，存在顶点 v 与 v 0相邻。若v V(P) ，则得到比 P 更长的路，这与 P 的取法矛盾。因此必有 v V(P) ，从而 G 包含圈。证毕。例9 设G 是一个简单图，若 (G) 2 ，则G 包含圈。v0v1v2vk第64页，共101页。例10 设 G 是简单图，若 (G) 3 ，则 G 包含偶圈。v0v1v2vkvivj第65页，共101页。证明：设 P =v0v1 v k 是G 的最长路。因为 d (v 0) 3 ， 所以存在两个与 v 1 相异的顶点 v, v 与 v 0 相邻。v, v 必都在路 P 上，否则会得到比 P 更长的路。不妨设 v = v i , v = v

29、 j , (i 0。（w = 0时，可令两端点重合；第81页，共101页。 若路 P = u 0 u 1 u k 1 u k 是从 u 0到 u k的最短路，则 P = u 0 u 1 u k 1必 u 0到u k 1的最短路。基于这一原理，算法由近及远地逐次求出u 0到其它各点的最短路。二、Dijkstra 算法1. 算法思想下面通过例子说明具体做法。第82页，共101页。（1）令 ， ，求 到 中最近点的最短路，结果找到 。（2）令: ，求 到 中最近点的最短路。此时除了考虑 到 的直接连边外，还要考虑 通过 向 的连边，即选取 中第83页，共101页。一点 ，使得结果找到u 2 。一般地

30、，若 以及相应的最短路已找到。则可应用(*)式来选取新的 ，获得 到 的最短路。第84页，共101页。例1472122484646337u019572122484646337u019572122484646337u019572122484646337u019572122484646337u019572122484646337u019572122484646337u019572122484646337u0195第85页，共101页。 1) 置 ，对 ， ， 且 . 2) 对每个 ，用代替 ，计算 ，并把达到这个最小值的一个顶点记为 ，置 3) 若 ，则停止；若 ，则用 i+1 代替i，并转2).

31、2算法实现标号法第86页，共101页。计算实例：求连接 vs、vt 的最短路.开始，给vs以 P 标号，P(vs)=0,其余各点给 T 标号 T(vi)=+.227414731555vsv2v1vtv4v5v3Step 1: 迭代 1 Dijkstra算法基本步骤：例15第87页，共101页。 若 vi 为刚得到 P 标号的点,考虑这样的点 vj : (vi ,vj)E 且vj 为 T 标号。227414731555vsv2v1vtv4v5v3Step 2: 对vj的T 标号进行如下更改T(vj)=minT(vj),P(vi)+wij245迭代 1 考察vs , T(v2)=minT(v2),

32、P(vs)+ws2= min+,0+5=5T(v1)=minT(v1),P(vs)+ws1= min+,0+2=2第88页，共101页。 比较所有具有 T 标号的点，把最小者改为P 标号，227414731555vsv2v1vtv4v5v3Step 3: 245即 P(vi)=minT(vi).当存在两个以上最小者时,可同时改为P 标号。若全部点为P标号,则停止。否则用vi代替vi转step 2.-2迭代 1 全部T标号中,T(v1)最小,令P(v1)=2,记录路径(vs ,v1).第89页，共101页。227414731555vsv2v1vtv4v5v394 若 vi 为刚得到 P 标号的点

33、,考虑这样的点 vj : (vi ,vj)E 且vj 为 T 标号。Step 2: 对vj的T 标号进行如下更改T(vj)=minT(vj),P(vi)+wij迭代 2 考察v1 , T(v4)=minT(v4),P(v1)+w14= min+,2+7=9T(v2)=minT(v2),P(v1)+w12= min5,2+2=4第90页，共101页。227414731555vsv2v1vtv4v5v344迭代 2 比较所有具有 T 标号的点，把最小者改为P 标号，Step 3: 即 P(vi)=minT(vi).-全部 T 标号中,T(v2),T(v3)最小,令P(v2)=4, P(v3)=4,记录路径(v1 ,v2