图论chap1.

-1-图论及其应用第一章图论发展史图论在现代科学技术中有着重要的理论价值和广泛的应用背景，如：线性代数、密码学、物理化学、网络设计、计算机科学、信息科学、DNA的基因谱的确定和计数、工业生产和企业管理中的优化方法等都广泛的应用了图论及其算法。首先我们通过图的发展过程来了解一下图论所研究的内容。图论起源于18世纪的一个游戏----俄罗斯的哥尼斯堡七桥问题。（1736年瑞士数学家欧拉——图论之父）-2-图论及其应用第一章ABDC转化Euler1736年BDCA图论中讨论的图问题：是否能从A，B，C，D中的任一个开始走，通过每座桥恰好一次再回到起点？是否能从任意一个顶点开始，通过每条边恰好一次再回到起点？转化包含两个要素：对象（陆地）及对象间的二元关系（是否有桥连接）七桥问题-3-图论及其应用第一章中国邮递员问题1962年中国数学家管梅谷提出图论中的“中国邮递员问题”。问题：一个邮递员从街区的某一点出发，经过街区每条街道至少一次又回到原出发点，如何设计投递路线，使总路程最短？-4-图论及其应用第一章Hamilton问题源于1856年，英国数学家Hamilton设计了一个名为周游世界的游戏：他用一个正十二面体的二十个端点表示世界上的二十座大城市（见图），提出的问题是要求游戏者找一条沿着十二面体的棱通过每个端点恰好一次的行走路线。反映到图论上就是判断一个给定的图是否存在一条含所有顶点的回路。Hamilton问题-5-图论及其应用第一章四色问题是世界近代三大数学难题之一。四色问题的内容是：任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。它的提出来自英国。1852年，毕业于伦敦大学的弗南西斯·格思里发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。”这个现象能不能从数学上加以严格证明呢？四色问题-6-图论及其应用第一章1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题。1878～1880年两年间，著名的律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此也就解决了。1890年，在牛津大学就读的年仅29岁的赫伍德以自己的精确计算指出了肯普在证明上的漏洞。不久，泰勒的证明也被人们否定了。后来，人们开始认识到，这个貌似容易的题目，其实是一个可与费马猜想相媲美的难题。-7-图论及其应用第一章进入20世纪以来，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。后来美国数学家富兰克林于1939年证明了22国以下的地图都可以用四色着色。1950年，有人从22国推进到35国。1960年，有人又证明了39国以下的地图可以只用四种颜色着色；随后又推进到了50国。1976年6月，美国伊利诺大学哈肯与阿佩尔在两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明，轰动了世界。然而，真正数学上的严格证明仍然没有得到！数学家仍为此努力，并由此产生了多个不同的图论分支。-8-图论及其应用第一章几个事实：1.任意的6个人中，总有3个人互相认识或有3个人互不认识。2.任意的9个人中，总有3个人互相认识或有4个人互不认识。问题：对任意的自然数k和t，是否存在一个最小的正整数r(k,t)，使得每个至少有r(k,t)个人的团体，总有k个人互相认识或有t个人互不认识。拉姆瑟（F.P.Ramsey）在1930年证明了这个数r(k,t)是存在的，人们称之为Ramsey数。确定其精确值是个公开的难题。Ramsey问题-9-图论及其应用第一章Ramsey数R(p,q)p,q345678936914182328364182535–4149–6156–8469–115543–4958–8780–143101–216121–3166102–165111–298127–495169–7807205–540216–1031232–17138282–1870317–35839565–6588-10-图论及其应用第一章Ramsey数的计算•Ramsey数的计算是对人类智力的挑战！例如R(4,5)=25(1993年计算机11年的计算量)•Erdös用如下比喻说明其困难程度：一伙外星人入侵地球，要求一年内求得R(5,5)，否则将灭绝人类！那么也许人类能集中所有计算机和专家来求出它以自保；但如果外星人问的是R(6,6)，那么人类将别无选择，只能拼死一战了。-11-图论及其应用第一章Ramsey理论的哲理意义•完全的无序是不可能的(Completedisorderisimpossible)。任一足够大的结构中必定包含一个给定大小的规则子结构。无序无意的行为产生了有规律的后果，发人深思耐人寻味。•古人在满天的星斗中发现野兽和众神群集于天空的图形，以为是造物主的杰作。但根据Ramsey定理，只要随机分布的星星数目足够多，就可以描绘出各种图形的轮廓。•1994年StatisticalScience的一篇论文利用统计方法证明：圣经隐藏了许多讯息，而这些讯息是有意安排的，绝非文字排列偶然造成的。1997年MichaelDrosnin的《TheBibleCode》通过计算机扫读圣经中的304805个字母，发现圣经密码当中传达的讯息除了拉宾被刺杀外，还包括美国肯尼迪和林肯两位总统，以及印度总理甘地遇刺的事件，日本神户、美国旧金山的大地震、世界末日与广岛原子弹轰炸等，种种过去与未来发生的大事件。Ramsey理论的哲理意义-12-图论及其应用第一章最精美的组合定理Rota：如果要求在组合学中仅举出一个精美的定理，那么大多数组合学家会提名Ramsey定理。•1984年Wolf奖得主Erdös•1997年Fulkerson奖得主Kim•1998年Fields奖得主Gowers•1999年Wolf奖得主Lovasz•2003年Steele奖得主Graham•2005年Gödel奖得主Alon•2006年Fields奖得主Tao均对Ramsey理论有杰出贡献-13-图论及其应用第一章某村里有n个男士与n个女士，每个男士恰好认识r个女士，每个女士也恰好认识r个男士，问：在这个村中，能否做到：每个男士与其认识的女士结婚，每个女士也恰好与其认识的男士结婚。婚姻匹配-14-图论及其应用第一章图论相关的交叉研究代数图论拓扑图论化学图论算法图论随机图论极值图论超图以往数学家习惯将纯数学应用于其它学科，Gowers将图论和组合数学中的Ramsey理论应用于泛函分析的研究，获得了1998年的Fields奖。-15-图论及其应用第一章内容提要图的基本概念图的基本概念；二部图及其性质；图的同构；关联矩阵与邻接矩阵。路、圈与连通图；最短路问题。树及其基本性质；最小生成树。图的连通性割点、割边和块；边连通与点连通；连通度；Whitney定理；可靠通信网络的设计。匹配问题匹配与最大匹配；完美匹配；二部图的最大匹配。-16-图论及其应用第一章欧拉图与哈密尔顿图欧拉图；中国邮递员问题；哈密尔顿图；旅行商问题。独立集、覆盖集与团点独立集、点覆盖集、边覆盖集与团的概念。图的着色问题点着色；边着色；平面图；四色猜想。网络流理论有向图；网络与网络流的基本概念；最大流最小割定理；求最大流的标号算法；网络流理论的应用。-17-图论及其应用第一章主要参考书[1]J.A.BondyandU.S.Murty,GraphTheorywithApplications,1976（GTM244,2008）。[2]B.Bollobas,ModernGraphTheory(现代图论)，科学出版社，2001。[3]王树禾，图论，科学出版社，2004。[4]蒋长浩，图论与网络流，中国林业出版社，2001。[5]徐俊明，图论及其应用，中国科技大学出版社，1998。-18-图论及其应用第一章第一章图和子图1.1图和简单图1.2子图1.3图的同构1.4定点的度1.5路、圈和连通1.6关联矩阵和邻接矩阵1.7应用：最短路问题-19-图论及其应用第一章1.1图和简单图-20-图论及其应用第一章图graph，顶点vertex，边edge图的定义其中V(G)是非空的顶点集，E(G)是不与V(G)相交的边集，G而Ψ是关联函数，它使G的每条边对应于G的无序顶点对。若e是一条边，而u和v是使得的顶点，则称euveG)(连接u和v；顶点u和v称为e的端点。一个图G是指一个有序三元组，)),(),((GGEGV-21-图论及其应用第一章)),(),({GGEGVG},,,{)(4321vvvvGV},,,,,,{)(7654321eeeeeeeGE322211)(,)(vvevveGG414133)(,)(vvevveGG.)(,)(,)(227436435vvevvevveGGG例1此时，G定义为这便定义出一个图。1e2e3e4e5e6e7e1v2v3v4v-22-图论及其应用第一章图的图形表示通常，图的顶点可用平面上的一个点来表示，边可用平面上的线段来表示（直的或曲的）。而边仅在端点处相交，称为平面图。-23-图论及其应用第一章G=(V,E)，其中},,,,{)(54321vvvvvGV)},(),,(),,(),,(),,(),,(),,{()(55515153433221vvvvvvvvvvvvvvGE这便定义出一个图。例2注：由于表示顶点的平面点的位置的任意性，同一个图可以画出形状迥异的很多图示。例2中图的另一个图示：-24-图论及其应用第一章图的图示直观易懂，因此以后一般说到一个图，我们总是画出它的一个图示来表示。阅读书P.2-3页，理解平面图和非平面图，并且完成课后习题1.1.2。-25-图论及其应用第一章一些概念和术语：（1）点与边的关联(incident)（2）点与点的相邻(adjacent)（3）边与边的相邻（4）（自）环(loop)、连杆(link)（5）重边(paralleledge)（6）简单图(simplegraph)（7）有限图(finitegraph)（8）平凡图(trivialgraph)和非平凡图（9）空图(emptygraph)和零图（nullgraph)（10）图的顶点数（图的阶order）、边数(size)-26-图论及其应用第一章1.2图的同构由前已知，同一个图有不同形状的图示。反过来，两个不同的图也可以有形状相同的图示。比如：2u3u可见G1和G2的顶点及边之间都一一对应，且连接关系完全相同，只是顶点和边的名称不同而已。这样的两个图称为是同构的(isomorphic)。-27-图论及其应用第一章从数学上看，同构的两个图，其顶点间可建立一一对应，边之间也能建立一一对应，且若一图的两点间有边，则在另一图中对应的两点间有对应的边。严格的数学定义如下。定义:两个图G=(V(G),E(G))与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。-28-图论及其应用第一章G1、G2在对应vi←→ui(i=1,2,3,4,5,6)下是同构的。例31v2v3v4v5v6v1u2u3u4u6u5u6u2ux1x2y1x3y2y3v1v2v3v4v5v6-29-图论及其应用第一章Canweshowallgraphs(uptoisomorphism)thathaveorderatmost4andsize3?-30-图论及其应用第一章Canweshowallsimplegraphs(uptoisomorphism)thathaveorder5andsize3?G1G2G3G4-31-图论及其应用第一章无标号的图注：判断两个图是否同构目前没有好算法。-32-图论及其应用第一章一些特殊图类：（1）完全图(completegraph)例4K3K4K5K5-3