5_1图论基础讲义.ppt

第5章 图论 本章讨论图的基本概念及有关术语，研究图的最基本的性质。 5.1　图的基本概念 5.5.1 图的起源 一、哥尼斯堡七桥问题 18世纪的东普鲁士有个哥尼斯堡城，在横贯全城的普雷格尔河两岸和两个岛之间架设了7座桥，它们把河的两岸和两个岛连接起来。从河岸或小岛出发，七座桥每座桥恰好通过一次，再回到原地，是否可能？ 数学大师欧拉对七桥问题给出否定回答，并给出严格的证明(Euler图)。 1736年，欧拉对七桥问题的抽象和论证思想，开创了图论的研究，这一年可以看成是图论的元年。 二、Hamilton环球旅行游戏 1895年，Hamilton设计一个“环球旅行”游戏： 在一个正12面体的20个顶点上各标志一个城市，如果从一城市出发，沿正12面体的棱行走，每个城市恰好经过一次，再回到出发点，则算旅行成功。 5.1.2 图的定义 一、图的概念 子图示例: （g）二部图 【例】 求解下列各题: (1) 图G的度数列为2，2，3，5，6，则边数m为多少? 解：由握手定理： 2m=∑deg(v)=2+2+3+5+6=18，知m=9。 (2) 图G有12条边，度数为3的顶点有6个，余者度数均小于3，问G至少有几个顶点？ 解：由握手定理∑deg(v)=2m=24，度数为3的顶点有6个占去18度，还有6度由其余顶点占有; 而由题意，其余顶点的度数可为0，1，2; 当均为2时所用顶点数最少，所以应有3个顶点占有此6度，即G中至少有9个顶点。 【例】 证明: 在n（n≥2）个人的团体中，必有两个人有相同个数的朋友。 解：以顶点代表人，二人如果是朋友，则在代表他们的顶点间连上一条边，这样可得简单无向图G，每个人的朋友数即图中代表它的顶点的度数，于是问题转化为： n阶简单无向图G中必有两个顶点的度数相同。 用反证法： 设G中各顶点的度数均不相同，则度数序列为 0，1，2，…，n-1 说明图中有孤立顶点，这与有n-1度顶点相矛盾（因为是简单图），所以必有两个顶点的度数相同。 三、图的同构 由于在画图的图形时，顶点的位置和边的几何形状是无关紧要的，因此表面上完全不同的图形可能表示的是同一个图。　　 直观理解: G1 ? G2是指其中一个图仅经过下列两种变换可以变为另一个图: (a) 挪动结点的位置； (b) 伸缩边的长短。 两个图同构的必要条件: （1）结点数目相同； （2）边数相同； （3）度数相同的结点数相同。 例： 例： 【例】证明下图中，G与G’不同构。 在图的集合上定义二元关系R： 对于图G1、G2，G1RG2当且仅当G1和G2同构，称R为图的同构关系。 　　容易证明，图的同构关系是等价关系。 　　 作业： P82: 1 5.1.3 通路与回路 右图是中国铁路交通图的一部分，旅客乘火车旅行，相当于从一个结点出发，沿着一些边连续移动到另一个结点，这就引出了通路的概念。 一、通路 【例】一个人带着一只狼、一只羊和一捆草要渡河，由于船太小，人做摆渡者一次只能运送一个“乘客”，很显然，如果人不在，狼要吃羊，羊要吃草，问人怎样才能把它们安全地渡过河去？ 解：这是通路问题的一个典型实例。用f表示人，w表示狼，s表示羊，h表示草。 集合{f，w，s，h}中能安全在一起的子集有： {f，w，s，h}，{f，w，s}，{f，s，h}， {f，w，h}，{f，w}，{f，s}，{f，h}， {w，h}，{f}，{w}，{s}，{h}。 用顶点表示渡河过程中的状态，状态是二元组：第一元素是集合{f，w，s，h}在渡河过程中留在原岸的子集，第二元素是在彼岸的子集。 将一次渡河后代表状态变化的顶点间连边，得下图。容易看出，一条路径就是一种渡河方案。 二、回路 三、图的连通性 由于结点v到v总存在一条长度为0的路, 因此规定：任意结点v可达v自身。 【例】下图所示： 图G1是连通图； 图G2是一个非连通图。 【例】在一次国际会议中，由七人组成的小组{a, b, c, d, e, f, g}中： a会英语、阿拉伯语； b会英语、西班牙语； c会汉语、俄语； d会日语、西班牙语；