第八章-图论8.1

1、第八章 图论(Graph Theory) 初步,图论学科简介 （1）,图论是组合数学的一个分支，它交叉运用了拓扑学、群论、数论等学科，有时将其归为离散数学的一个分支。,哥尼斯堡七桥问题 图论是组合数学的一个分支，它交叉运用了拓扑学、群论、数论等学科，有时将其归为离散数学的一个分支。,图论之父,莱昂哈德欧拉（Leonhard Euler ，1707年4月15日1783年9月18日），瑞士数学家、自然科学家。1707年4月15日出生于瑞士的巴塞尔，1783年9月18日于俄国圣彼得堡去世。欧拉出生于牧师家庭，自幼受父亲的影响。13岁时入读巴塞尔大学，15岁大学毕业，16岁获得硕士学位。欧拉是18世纪

2、数学界最杰出的人物之一，他不但为数学界作出贡献，更把整个数学推至物理的领域。他是数学史上最多产的数学家，平均每年写出八百多页的论文，还写了大量的力学、分析学、几何学、变分法等的课本，无穷小分析引论、微分学原理、积分学原理等都成为数学界中的经典著作。欧拉对数学的研究如此之广泛，因此在许多数学的分支中也可经常见到以他的名字命名的重要常数、公式和定理。1此外欧拉还涉及建筑学、弹道学、航海学等领域。瑞士教育与研究国务秘书Charles Kleiber曾表示：“没有欧拉的众多科学发现，今天的我们将过着完全不一样的生活。”法国数学家拉普拉斯则认为：读读欧拉，他是所有人的老师。,19世纪末期，图论应用于电网

3、络方程组和有机化学中的分子结构 20世纪中叶，由于计算机的发展，图论用来求解生产管理、军事、交通运输、计算机和网络通信等领域中的离散性问题 物理学、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学、管理科学等领域应用。,图论学科简介 （2）,课程目标,通过本课程学习，要求学生掌握图论的基本理论及推理方法，为通信网络、电路辅助设计、信息工程、密码学等打下理论基础。 掌握图论的基本理论与基本方法，并用这些理论与方法解决一些实际问题，了解图论在现代信息科学和现代通信系统中的应用。本课程特别强调理论与工程实践相结合，以提高学生的学习知识、运用知识能力。,8.1 图的基本概念,8.1

4、.1 图的定义 8.1.2 相邻 8.1.3 顶点的度数 8.1.4 多重图、简单图和完全图,2007年3月，新乡回龙景区新增景点“迷桥”，并悬赏百万破解。,如果谁可以从其中任何一座桥出发，走遍七座桥且没有重复回到出发点，就有机会获得100万元的现金大奖。,哥尼斯堡七桥问题,18世纪著名古典数学问题之一,哥尼斯堡（现今叫加里宁格勒，在波罗的海南岸）是一座古老而景致迷人的城市，普勒格尔河的两条支流在这里汇合，流入大海。河心有一个小岛，河水把整座城市分割成4个区域：河的两岸，河中的岛和两条支流之间的半岛。政府建了七座各具特色的桥，把哥尼斯堡连成一体。,无数的行人从桥上路过。不知不觉中城市里流传了一

5、个问题：谁能够一次走遍这所有的七座桥 ，而且每座桥都只通过一次。,哥尼斯堡七桥问题,欧拉解决问题的方法：抽象,地图的抽象,问题的抽象,把问题转化为数学方式的叙述,人们关心的只是一次不重复的走过这七座桥，而不关心桥的长短和岛的大小。因此岛和岸都可以看成一个点，而桥可以看成连接这些点的一条线。,地图的抽象,三步抽象,地图的抽象： “点线图”,问题的抽象：“一笔画的问题”,1. 笔不离开纸 2. 每条线都只画一次而不能重复,把问题转化为数学方式的叙述：找到“一个点线图可以一笔画”的充分必要条件，并且对可以“一笔画”的图形，给出“一笔画”的方法。,课堂讨论与欧拉共思考，同探索,欧拉把图形上的点分成了两

6、类；请考虑，如果是你，会分成哪两类？ 为了一笔画成功，图中的？ ？,一笔画问题,有奇数条边相连的点叫奇点。如：,问题分析,问题的答案如何呢？先来了解二个新概念。,有偶数条边相连的点叫偶点。如：,点线图中 “点的分类”： 偶点 ；奇点,要想一笔画出点线图，首先它必须是连通图（即图形上任意两点都必须有路径相连）。,另外，如果一个图能一笔画成，那么一定有一个起点开始画，也有一个终点。图上其它的点是“过路点”画的时候要经过它.,“过路点”有什么特点呢？,它应该是“有进有出”的点，有一条边进这点，那么就要有一条边出这点，不可能是有进无出或有出无进。 如果只进无出，它就是终点； 如果有出无进，它就是起点。

7、,因此，在“过路点”进出的边总数应该是偶数，即“过路点”是偶点。,如果起点和终点是同一点，那么它也是属于“有进有出”的点，因此必须是偶点，这样图上全体点都是偶点。 如果起点和终点不是同一点，那么它们必须是奇点，因此这个图最多只能有二个奇点。,把上面所说的归纳起来，说简单点就是： 能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。,欧拉定理：,凡是由偶点组成的连通图，一定可以一笔画成；画时可以任一偶点为起点，最后一定能以这个点为终点画完此图。 凡是只有两个奇点（其余均为偶点）的连通图，一定可以一笔画完；画时必须以一个奇点为起点，另一个奇点为终点。 其他情况的图，都不能一

8、笔画出。,“一笔画”的充要条件：图形是连通的，而且奇点的个数是0或者2.,例如,回到“七桥问题”,3,3,3,5,奇点的个数为4个，所以不能一笔画出。,知道了一笔画的规律后，亲自体验一下，来看看下面图形能否一笔画出,4个奇点,0个奇点,例1 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？,例2 中国邮递员问题（CPPChinese postman problem） 一名邮递员负责投递某个街区的邮

9、件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。,一笔画的规律对于旅游景点或博物馆参观路线设计等问题具有实际意义。,图1 哥尼斯堡七桥问题, 8.1 图的基本概念,现实世界中许多现象能用某种图形表示,这种图形是由一些点和一些连接两点间的连线所组成。 【例1】a， b， c， d 4个篮球队进行友谊比赛。 为了表示个队之间比赛的情况，我们作出图1。在图中个小圆圈分别表示这个篮球队，称之为顶点（结点）。如果两队进行过比赛，则在表示该队的两个结点之间用一条线连接起来，

10、称之为边。这样利用一个图形使各队之间的比赛情况一目了然。,1. 图的定义, 8.1 图的基本概念,图8.1,如果图8.1中的个结点a，b，c，d分别表示个人，当某两个人互相认识时，则将其对应点之间用边连接起来。这时的图又反映了这个人之间的认识关系。, 8.1 图的基本概念,定义8.1.1 按图G的边有无方向可以分为有向图、无向图 和混合图。 有向图：图G每条边都是有方向的（如图所示） 其边称为有向边； 无向图：图G每条边都是无方向的，其边称为无向边； 混合图：既有无向边, 又有有向边的图称为混合图。, 8.1 图的基本概念,定义8.1.2 一个图G是一个有序二元组(序偶) (V, E) ,记为

11、G(V, E)。其中V是图G所有顶点构成的集合，E是图G所有边构成的集合。 在用集合表示一个图时，如果从顶点u到顶点v之间有一条有向边，则该有向边表示成 u, v;如果从顶点u和顶点v之间有一条无向边，则该无向边表示成 (u, v) 或 (v, u) ;, 8.1 图的基本概念,一个图G可用一个图形来表示且表示是不唯一的。,定义8.1.3 设e = (u, v)是无向图G(V, E)的一条边,则称u和v是边e的端点,称u和v是相邻的,同时称顶点u和v关联于边e。 设e =u, v是有向图G(V, E)的一条边,则称u和v是有向边e的端点, 其中u是边e的起点, v是边e的终点，称u和v是相邻的

12、,同时称顶点u和v关联于边e。, 8.1 图的基本概念,2. 相邻,定义8.1.4 （1）设e 1和e 2是无向图G(V, E)的两条边, 如果e 1和e 2至少有一个公共端点，则称边e 1和e 2是相邻的。 （2）设e 1和e 2是有向图G(V, E)的两条有向边, 如果e 1的终点是e 2的起点，则称边e 1和e 2是相邻的。, 8.1 图的基本概念,定义8.1.5 （1）如果图中某一个顶点没有一条边以其为端点，则称该顶点是孤立点。 （2）如果图中有一条边其两个端点重合，则称该边是环。 （3）图中不与任何边相邻接的边称为孤立边。, 8.1 图的基本概念,我们常常需要关心图中有多少条边与某一

13、顶点关联，这就引 出了图的一个重要概念顶点的度数。 定义8.1.6 设G(V, E)是无向图或有向图， v是G的顶点，称以v为端点的边的数目(每个环算2次)为该顶点的度数或度，记为d ( v )。,3. 顶点的度数,定义8.1.7 在有向图中, 以v为终点的边数称为结点v 的入度，记为 ; 以v为始点的边数称为结点v的出度，记为 。结点v的入度与出度之和称为结点v的度数，记为d(v)。, 8.1 图的基本概念,顶点2入度：1 出度：3 顶点4入度：1 出度：0,顶点5的度：3 顶点2的度：4,定理 8.1.1 设 G(V, E) 是无向图或有向图，G中所有顶点度数的总和等于G的边数的两倍，即

14、证明: 因为每条边都与两个结点关联，所以加上一条边就使得各结点度数的和增加 2，由此结论成立。, 8.1 图的基本概念,定理 8.1.2 对于任意一个图 G(V, E) ，其度为奇数的顶点的个数是偶数。, 8.1 图的基本概念,定理 8.1.3 对任一个有向图 D(V, E) ，其所有顶点的出度之和等于所有顶点的入度之和，即,4. 多重图、简单图和完全图, 8.1 图的基本概念,定义8.1.8（1）设u和v是无向图G(V, E)的两个顶点。如果G中有两条或两条以上的边分别以u和v为端点, 则称这些边是平行边。 （2）设u和v是有向图D(V, E)的两个顶点。如果D中有两条或两条以上的边分别以u和v为端点, 且它们的起点相同，终点也相同，则称这些边是有向平行边，简称平行边。,定义8.1.9 （1）包含平行边的图称为多重图。 （2）既无平行边又无环的图称为简 单图。 （3）非多重图称为线图；, 8.1 图的基本概念,G1、G2是多重图,G3是线图,G4是简单图, 8.1