组合与图论1.1-1.2

1、授课教师：程绩E-mail:Tel25680792022年6月26日参考文献1. JA邦迪等.图论及其应用.吴望民等译.北京:科学出版社.19842. F哈拉里.图论.李慰萱译.上海:上海科学技术出版社.19803. 卢开澄,卢华明.图论及其应用.第二版.北京:清华大学出版社.19954.Bela Bollobas. Moden Graph Theory.影印版.北京:科学出版社.20015. 徐俊明.图论及其应用.安徽：中国科学技术大学出版社.20046. 张先迪 李正良.图论及其应用.北京:高等教育出版社.20052022年6月26日说明本课程做为组合数学的后续

2、课程，继续沿用教材组合数学与图论。 从主要内容上看，本课程主要分为两部分：一是图论初步；二是竞赛数学中的图论问题。2022年6月26日第一章图的基本概念2022年6月26日1.1哥尼斯堡七桥问题一、图论学科概况大家所熟知的一些问题，例如四色猜想，一笔画问题，推销员问题，邮路问题，哈米尔顿问题等都是一些经典的图论问题。图论是一个新的数学分支，起源于18世纪，是一门很有应用价值的学科。它在自然科学和社会科学等各领域有很多应用。近年来随着计算机科学蓬勃发展，图论的发展也极其迅速，应用范围不断拓广，已渗透到语言学、心理学、逻辑学、物理学、2022年6月26日一、图论学科概况化学、电讯工程、计算机科学以

3、及数学的其它分支中。特别在计算机科学的形式语言、数据结构、分布式系统、操作系统等方面均扮演着重要的角色。历史上，图论曾经被很多数学家各自独立地建立过，因为图论本身就是应用数学的一部分，所以这种情况并不是偶然的巧合。事实上，提到这个主题的文字记载最早是出现在欧拉的著作中。2022年6月26日四色猜想（4CC）的表述 问题：问题： 在一个平面上的任何地图，是否可以最多用四种颜色就能使相邻的国家着不同的颜色。这里假设地图上的国家都是单连通的区域。2022年6月26日四色猜想的背景背景：背景： 这个猜想的起源有点模糊。有些报告说Mbius（默比乌斯）在1840年就熟悉这个问题，但是，可以肯定的仅仅是该

4、问题约于1850年由Guthrie转告给De Morgan。该猜想提出之后，许多人都试图解决这个猜想，但都未成功。1879年，Kempe（肯普）给出了这个猜想的许多错误“证明”中的第一个“证明”。1890年，Heawood（希伍德）发现了它的一个错误，并指出若将“四”换成“五”猜想成立。2022年6月26日四色猜想的解决解决：解决： 这个猜想在数学上严格证明，经历了一个多世纪都未能成功。直到1976年才被K.Appel（阿佩尔）, W.Hakan（黑肯）, J.Koch（科赫）等三人借助于电子计算机所证明，证明了该猜想成立。他们的证明需要计算机计算1200小时，100亿个分离的逻辑判定。202

5、2年6月26日推销员（TSP）问题问题：问题： 一个售货员从他所在的城镇出发，想去若干城镇售货，要求每个城镇至少经过一次，然后返回原地，问怎样安排他的路线才会使通过的总路程最短？ 在数学建模中，有一个与抗洪巡视相关的问题，其中用到了TSP模型。2022年6月26日中国邮递员问题问题：问题： 邮递员的工作是：在邮局里选出邮件，递送邮件，然后再返回邮局。自然，他必须走过他投递范围内的每一条街道至少一次。在这个前提下，希望选择一条尽可能短的路线。 这个问题是中国数学家管梅谷（1962）年研究的。 在数学建模中有一个铲雪车的行驶问题用到了这个模型。2022年6月26日哈米尔顿图 1859年，数学家威廉

6、哈米尔顿(Hamilton)爵士发明了一种周游世界的游戏：在一个12面体上的每个角点标以有名的城市的名字，要求游戏者找一条沿着各边通过每个顶点正好一次，最后回到出发地的路线。这个游戏在欧洲曾风靡一时，哈米尔顿以25个金币的高价把该项专利卖给了一个玩具商。然而，这是一笔滑头的生意，因为这个游戏在经济上并不成功。 用图论的语言来说，游戏的目的是在十二面体的图中找一个生成圈。2022年6月26日2022年6月26日思考 推销员问题、邮路问题和哈米尔顿所描述的是不是一类问题。 这是三个不同的问题。从图论角度说，推销员问题和哈米尔顿问题有密切的联系，它们寻找的主要是基于哈米尔尔顿性质的回路，而中国邮递员

7、问题所寻找的主要是Euler圈。2022年6月26日二、哥尼斯堡七桥问题欧拉（Euler,17071782，瑞士）在1736年解决了一个当时还没有解决的著名问题，称为哥尼斯堡七桥问题，从外表上看这是一个颇为无聊的问题，然而正是这个问题的解决，使欧拉成为了图论和拓扑学两大学科的创始人。2022年6月26日哥尼斯堡七桥问题18世纪，东普鲁士（现俄罗斯列宁格勒），哥尼斯堡（Knisberg），普雷格尔河畔（Pregel）。问题：问题：从河的南北两岸或者两个小岛中任何一地出发，能否找到一条路线，做到每座桥恰好通过一次且最后返回出发地？2022年6月26日欧拉怎么做？问题：问题：能否找到一条路线，从图中

8、任一点出发，经过每条边一次且仅一次，最后返回出发点？结论结论：所求线路不存在2022年6月26日问题的解决欧拉在1736年发表了哥尼斯堡七桥问题，给出了上述问题的否定回答，这成为图论史上的第一篇论文。欧拉在此基础上对此类问题进行推广，找到对于一般图存在这样的一条路线的充要条件。简单地说，这就是一笔画问题的一种表达方式。类似的，在习题中的“人、羊、狼、菜过河”问题，“8L、5L、3L容器的均分”问题、“10个人中或者必有3个人互相认识，或者有4个人互相不认识”等都是非常经典的图论问题。2022年6月26日1.2基本概念欧拉将哥尼斯堡七桥问题归结为一些点与连接这些点的线之间的联系，从而它可以用一个

9、由若干个顶点和若干条边所组成的图形来表示，所以我们把一个顶点集合与一个边的集合放在一起，称之为“图”。2022年6月26日图论中图的特点图论中所说的图是描述事物之间关系的一种手段。现实世界中，许多事物之间的关系可抽象成点及它们之间的连线，集合论中二元关系的关系图就是图论中“图”的很好的例子。在集合论中二元关系的关系图中，我们只关心点与点之间是否有边，而不关心点及边的位置，以及边的曲直、长短，这就是图论中的图与一般几何图形的区别。2022年6月26日一、图的定义定义定义1.2.1一个图G定义为一个偶对:（V,E），且记作G=(V,E)，其中，V是一个集合，V中元素称为顶点或端点；E表示边的集合。

10、通常约定：用G(graph)表示图，用v表示顶点(vertex)，e表示边(edge)。2022年6月26日例1.2.1(P107) 北京、上海、杭州、南京、广州、武汉、郑州、重庆、西安等十个城市之间的航线构成一个图。其中：V=北京、上海、杭州、南京、广州、武汉、郑州、重庆、西安为顶点的集合。E=(北京，上海)，(南京，武汉)，(西安，郑州)为边的集合。2022年6月26日例1.2.2(P108)(教材标图有误),4321vvvvV ,654321eeeeeeE 和书上的说法略有不同，现在图论中比较通行的边的表示方法是这样的：设边e的两个端点是u,v，则记e=u,v，表明，u和v之间是无序的。

11、,326412211vvevvevve2022年6月26日图的两大特点1.描述一个图的几何图形不是唯一的描述一个图的几何图形不是唯一的，几何图形仅描绘出该图的顶点与边之间保持的相互关联关系。至于各顶点的相关位置以及各边的长、短、曲、直等都是无关紧要的。2.图的本质内容是各顶点与边之间的关联关系，至于顶点和边是否用平面上的几何点和线段来表示，则不是必要的。换句话说，图的概念可以高度的抽象化图的概念可以高度的抽象化，它完全可以由一个抽象集合G=(V,E)来表示。2022年6月26日一些相关概念1V对于图G=(V,E)中的顶点数，用 表示，一般也用n,表示；边的数目用表示，一般也用m,表示，通常用（

12、n,m）或者(,)表示一个图的大小（规模）。E若n,m均有限，称G为有限图；E=，n=1，称G为平凡图（只有一个孤立顶点的图）；n=或m= ，称G为无限图；若G中任两点之间有边相连，则称G为完全图，记为Kn。2022年6月26日一些相关概念2在G中连接同一对顶点的边数大于，则称这样的边为多重边，有时也称其为平行边，而连接同一对顶点的边数称为连接该对顶点的边的重数。又若图G=(V,E)中形如v,v的边，即一条边中的两个端点重合为一点时，称这样的边为环。称没有重边，没有环的图为简单图。如无特别声明，今后所讨论的图指简单图。2022年6月26日一个有趣的图Graph Buster (小鬼图)n=13

13、m=212022年6月26日关于有向图有向图的概念教材上有所提及，这里不做为教学内容。 简单地说，有向边就是它的两个端点有先后顺序，有所指向的边。有向边构成的图称为有向图(图1.2.2)，无向边构成的图称为无向图。若一个图既有有向边，又有无向边，则称其为混合图。如大城市的交通系统就是一个混合图结构。2022年6月26日邻接与关联Vvu,定义定义1.2.2在图G=(V,E)中，若v是e的一个端点，则称边e和顶点v是相关联的；若，且有，则称顶点u和v邻接；若两条边有共同的顶点，则称这两条边是邻接的。Evue,2022年6月26日子图与导出子图),(111EVG EEVV11且1G定义定义1.2.3

14、设G=(V,E)和，若满足，则称图是图G的一个子图；若，则称是G的一个真子图。特别地，当时，称是G的一个生成子图（支撑子图）。EEVV11或1GVV 12022年6月26日子图与导出子图11VVV且1V1VG设，以为顶点集，两个端点都在中的边为边集的G的子图，称为G的由顶点集导出的子图，记为。1V1V设，以为边集，的端点集为顶点集的图G的子图，称为G的由边集导出的子图，记为。11EEE且1E1EG1E1E举例说明2022年6月26日图的运算),(),(222111EVGEVG),(212121EEVVGG图的并121212,G GGGGG特别地 当的点不交时 则有121212,G GGGGG特

15、别地,当的边不交时 则有2022年6月26日图的运算121212(,)GGVV EE图的交),(),(222111EVGEVG定义交图时，两图至少要有一个公共顶点。2022年6月26日图的运算),(),(222111EVGEVG。GGGGGG中的边组成的图中去掉是由的差212121,21GG 21GG2022年6月26日图的运算),(),(222111EVGEVG的交所得的图的并中去掉是的对称差图21212121,GGGGGGGG)()()()(1221212121GGGGGGGGGG2022年6月26日图的运算21212121,GG，GGGGGG记为到的图称为联图的每个顶点连接起来得的每个顶

16、点和把中的并图和在不相交的3342516532541,KKKKKKKKKKKKK2022年6月26日图的运算.)()(),(),(),(),(212111222211212121222111GGG，GGGvu，adjvuvuadjvuvuvvvuuuVVVEVGEVG记为的积图和称为连接起来所得到的图和就把时和或和当和点中的任意两个对点集设u1v1u2v2w2(u1,u2)(u1,v2)(u1,w2)(v1,u2)(v1,v2)(v1,w2)2022年6月26日二、握手定理及推论定义定义1.2.4设G=(V,E)是一个无向图。对于V中每一个顶点v，称以v作为边的端点的次数之和为度数，或简称为v

17、的度。一般记为。所有顶点度中的最小值记为，最大值记为。)()(vdvdG或思考思考：环上的顶点的度怎么计算？答：答：设环e以v为顶点，则d(v)=2。（举例说明）2022年6月26日握手定理VvEvd2)(证明证明：因每条边都与两个顶点相关联，每出现一条边就增加2，所以总次数。定理定理1.2.1对于任意有限图G，恒有其中V为顶点集合，E为边集合。VvEvd2)(2022年6月26日握手定理的推论推论推论：任图G=(V,E)，度数为奇数的顶点的个数为偶数。EvdvdvdVvVvVv2)()()(211)(Vvvd2)(Vvvd证明证明：设V1和V2分别表示图中奇次顶点和偶次顶点的集合。则为偶数。又是偶数，因此也是偶数，从而奇次顶点的总数为偶数。1V2022年6月26日握手定理的应用尝试自己建立图论模型解释下述三个命题：(1) 在一群人中，和奇数个人握手的人的个数一定是偶数；(2) 设A是正整