图论的基本思想培训讲座课件

1、图论的基本思想培训讲座图论的基本思想培训讲座一、引言二、图的定义三、顶点的度四、K部图-托兰定理五、边数最少连通图-树六、一笔画-欧拉问题七、环游世界-哈密顿问题八、染色-拉姆赛问题一、引言一、引言图论最早起源于一些数学游戏的难题研究，如欧拉所解决的哥尼斯堡七桥问题，以及在民间广泛流传的一些游戏难题，如迷宫问题、博奕问题、棋盘上马的行走路线问题等 这些古老的难题，当时吸引了很多学者的注意在这些问题研究的基础上又继续提出了著名的四色猜想和哈密顿（环游世界）数学难题 一、引言图论最早起源于一些数学游戏的难题研究，如欧拉所解决的一、引 言1847年，图论应用于分析电路网络，这是它最早应用于工程科学，

2、以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，发挥出越来越大的用在人们的社会实践中，图论已成为解决自然科学、工程技术、社会科学、生物技术以及经济、军事等领域中许多问题的有力工具之一，因此越来越受到数学家和实际工作者的喜爱我们这里只是介绍一些基本概念、原理以及一些典型的应用实例，目的是大家在今后学习过程中，可以把图论的基本知识、方法作为工具 一、引 言1847年，图论应用于分析电路网络，这是它最早应用二、图的定义首先要注意，我们这里所讨论的图论中的“图”，并不是以前学过的通常意义下的几何图形或物体的形状图，也不是工程设计图中的“图”，而是

3、以一种抽象的形式来表达一些确定的对象，以及这些对象之间具有或不具有某种特定关系的一个数学系统也就是说，几何图形是表述物体的形状和结构，图论中的“图”则描述一些特定的事物和这些事物之间的联系它是数学中经常采用的抽象直观思维方法的典型代表 二、图的定义首先要注意，我们这里所讨论的图论中的“图”，并不二、图的定义一提到图论的起源，人们总要讲述早在1736年，欧拉就把所谓的哥尼斯堡7桥问题化为图论问题 :图G=(V,E) ; | V |=n, | E |=e;二、图的定义一提到图论的起源，人们总要讲述早在1736年，欧二、图的定义同构子图相邻环平行边简单图完全图有限图二、图的定义同构二、图的定义问题1

4、: 某大型舞会有2019个人参加，已知他们每个人都至少和其中的一个人握过手,则必有一个人至少和其中的两个人握手.问题2: 9人相遇,发现他们中的任意3人中,至少有两人可以用同一种语言.对话如果每人至多可以说3中语言,则至少有3人可以用同一种语言对话. v2把9改成8,命题不成立. 反例: 1,12表示12种颜色，则下图无同色三角形。V2V3V4V1V6V7V5V8V1V2V3V5V6二、图的定义问题1: 某大型舞会有2019个人参加，已知他们二、图的定义问题3: 一次会议有n名教授 .则可以将这n个人分为两组，使得每个人 在另一组中认识的人数 不少于他在同一组中认识的人数(i=1,2,3,n)

5、. 想法:调整法 设S为两组之间的连线条数.由于分法有限,必存在一种分法使S最大,则问题得证.否则,S增加.二、图的定义问题3: 一次会议有n名教授 三、顶点的度度 ： d(v) ;(G),(G) 表示最大度与最小度.奇顶点，偶顶点.正则图：d(v)=k(常数）.在二百多年前，欧拉给出这样的一个著名的结论：“如果许多人在见面时握了手，被握过手的人数为偶数.” 进而得到：“握过奇数次手的人有偶数个.”握手原理：d(v1)+d(vn)=2e.问题1：在n（n2)个人中，至少有两个人，他们的朋友数是一样多的.三、顶点的度度 ： d(v) ;(G),(G) 表示最三、顶点的度问题2：国际乒乓球男女混合

6、双打比赛有24对选手参加.赛前一些选手握了手，但同一对选手之间不握手.赛后某个男选手问每个选手的握手次数，个人回答各不相同，问这名男选手的女搭档和多少人握了手？三、顶点的度问题2：国际乒乓球男女混合双打比赛有24对选手参四、托兰定理1941年，匈牙利数学家托兰为了回答这样的问题：“n个顶点的图G不包含m个顶点的完全图 ,则图G的最大边数是多少？”而提出的他的著名的定理，从而开创了图论研究的一个新的方向“极图理论”.K部图完全k部图完全偶图的边数： ，四、托兰定理1941年，匈牙利数学家托兰为了回答这样的问题：四、托兰定理托兰定理1： 有n 个顶点且不含三角形的图G的最大边数为 .定理证明的想法

7、是：用极端性原理. 问题2：设图G有20个顶点，101条边，则G中一定有两个具有公共边的三角形.托兰定理2：设n阶图G不含 ，则G的边数 . 当且仅当四、托兰定理托兰定理1： 有n 个顶点且不含三角形的图G的最四、托兰定理四、托兰定理四、托兰定理问题3： 设 是平面上的6点，其中任意三点不共线. （1）如果这些点之间连13条线段，则必存在4点，它们每两点之间都有线段连接； （2）如果这些点之间只有12条线段，请你画一个图形，说明（1）结论不成立. 分析：（1）问题等价存在 ; （2）构造完全3部图 ，从中任取4点，总有两点属于同一部分，而这两点是不相邻的，因此任4点均不构成 .四、托兰定理问题

8、3：五、树链圈连通图树树叶（悬挂点）连通分支生成树（图G的一个生成子图是一棵树） 常用的方法是：破圈法 避圈法五、树链五、树如果树T的顶点数 2，则T中至少有两个悬挂点；设树T的顶点数为n，则它的边数e=n-1;设T是有n个顶点，e条边的图，则 （1）图T是树； （2）图T无圈, 且e=n-1； （3）图T连通，且e=n-1. 这三个命题是等价的.五、树如果树T的顶点数 2，则T中至少有两个悬挂点；五、树问题1： n 个城市，每个城市都可以通过一些中转城市与另一个城市通话，则至少有n-1条直通的电话线路，每条连结两个城市. 分析：破圈法，得到树.问题2： 在一次讲演中，有五位数学家每人打2次盹

9、，并且每两人均有同时在打盹的时刻，则一定有三人，他们有同时打盹的时刻. 分析：每两个数学家均有同时打盹的时刻连边，图G中至少有 条边，而图G的顶点为10,问题得证. 五、树问题1：六、欧拉问题一笔画定理：有限图G是一条链（即可以一笔画成）的充分必要条件是：G是连通的，且奇顶点个数等于0或2.当且仅当奇顶点的个数等于0时，连通图G是一个圈.推广：如果连通图G有2k个奇顶点，则图G可以用k 笔画成，且至少要用k笔画成. 将2k个奇顶点分成k对，每对连边，构成一个圈。六、欧拉问题一笔画定理：有限图G是一条链（即可以一笔画成）的六、欧拉问题如图，大三角形的三个顶点分别涂以A、B、C三种.颜色在大三角形

10、内取若干个点，将它分为若干个小三角形，每两个三角形或者有一条公共边，或有一个公共顶点，或者完全没有公共点.将每个小三角形的顶点也分别涂以A、B、C三种颜色之一，则不管怎样涂色，都有一个小三角形，它的三个顶点的颜色全不相同. 分析： 当两个三角形有一条公共边AB时，连一边，如图.反证.假设没有，则度为0或者2，由于d(u)=1,所以至少有一个奇顶点v.六、欧拉问题如图，大三角形的三个顶点分别涂以A、B、C三种.七、哈密顿问题1856年，英国著名数学家哈密顿提出一个名为“环游世界”的游戏，他用一个正十面体的二十个顶点代表二十个大城市，要求沿着棱，从一个城市出发经过每个城市恰好一次，然后回到出发点。

11、这种链（圈）（它经过图上各顶点一次且仅一次），称为哈密顿链（圈），一个圈若包含哈密顿圈，则称这个图是哈密顿图。七、哈密顿问题1856年，英国著名数学家哈密顿提出一个名为“七、哈密顿问题一般地，对于一个偶图 ，如果 那么G一定无哈密顿圈。如果 的差大于1 那么G一定无哈密顿链。 证明的想法是如图：七、哈密顿问题一般地，对于一个偶图 七、哈密顿问题问题1： 下图中是国际象棋盘，一匹马在右下角，试问：马能否连续地把棋盘上所有的格都跳到一次且仅仅一次？如果去掉了棋盘对角上的两个黑格，又将怎样？ 问题 是否存在一条哈密顿链？1518722112852482116276232291714191031122

12、54209321326330马七、哈密顿问题问题1：1518722112852482116七、哈密顿问题对于一个连通图，是否存在哈密顿链（圈）的问题.这是个充分条件，不必要，比如：七、哈密顿问题对于一个连通图，是否存在哈密顿链（圈）的问题.七、哈密顿问题七、哈密顿问题七、哈密顿问题问题3：一只老鼠吃333立方体乳酪，其方法是借助于打洞通过所有的27个111正立方体。如果它在一个角上开始，然后依次走向未吃的立方体，问它吃完时能否恰在立方体的中心。分析：作图G：顶点表示111的立方体，当且仅当两个小正方体有公共面时，对应的两顶点以边相连。则G是偶图， 则G无哈密顿链。七、哈密顿问题问题3：一只老鼠吃333立方体乳酪，其方法八、拉姆赛问题英国逻辑学家拉姆赛通常，我们把与图的染色、拉姆赛数、抽屉原则关联的问题拉