离散数学-第八章：几种特殊的图.ppt

几种特殊的图 2 哥尼斯堡七桥问题 哥尼斯堡城 现在俄罗斯 在18世纪属东普鲁士 它位于普雷格尔 Pregel 河畔 河中有两个岛 通过七座桥彼此相联 如下图 3 内容提要 8 1二部图8 2欧拉图与哈密尔顿图8 3平面图 4 8 1二部图 引例 今有4个工人a1 a2 a3 a4 4项任务b1 b2 b3 b4 已知工人a1熟悉任务b1 b2 b3 a2熟悉b2 b3 a3只熟悉b4 a4熟悉b3和b4 问如何分配工人 才能使每人都有任务 且每项任务都有人来完成 其实 只要以V a1 a2 a3 a4 b1 b2 b3 b4 为顶点集 若ai熟悉bj 就在ai和bj之间连边 得边集E 构成无向图G 如下图所示 5 8 1二部图 由图显而易见 分配a1去完成b1 a2去完成B2 a3去完成b4 a4去完成B3就能满足要求 在此图中 a1 a2 a3 a4彼此不相邻 b1 b2 b3 b4也彼此不相邻 像这样的图 称它为二部图 6 8 1二部图 定义8 1 1若能将无向图的顶点集V分成两个子集V1和V2 V1 V2 使得G中任何一条边的两个端点都一个属于V1 另一个属于V2 则称G为二部图 或称偶图 双图 二分图 V1 V2称为互补顶点子集 若G是二部图 也可将G记为G 又若V1中任一顶点与V2中任一顶点均有且仅有一条边相关联 则称二部图G为完全二部图 若 V1 r V2 s 则记完全二部图为Kr s 7 8 1二部图 注 在完全二部图Kr s中 它的顶点数n r s 它的边数m rs 定理8 1 1一个无向图G 是二部图当且仅当G中无奇数长度的回路 8 如图所示各图都是二部图 其中 1 2 3 为K6的子图 3 为完全二部图K3 3 常将K3 3画成与其同构的 5 的形式 K3 3是下文中经常遇到的图 4 是K5的子图 它是完全二部图K2 3 K2 3常画成 6 的形式 注意 n阶零图为二部图 9 8 2欧拉图与哈密尔顿图 引例 哥尼斯堡七桥问题如何不重复地走完七桥后回到起点 10 8 2欧拉图与哈密尔顿图 一 欧拉图定义8 2 1给定无孤立结点图G 若存在一条通路 经过图中每条边一次且仅一次 该通路称作欧拉通路 若G中欧拉通路又是回路 则称它为G中的欧拉回路 具有欧拉回路的图称为欧拉图 注意 只有欧拉通路无欧拉回路的图不是欧拉图 11 8 2欧拉图与哈密尔顿图 a 无欧拉通路 b 无欧拉回路 c 是欧拉图 12 8 2欧拉图与哈密尔顿图 定理8 2 1无向图G具有一条欧拉通路 当且仅当G是连通的 且有零个或两个奇数度结点 证明必要性设G具有欧拉通路 即有点边序列v0e1v1e2v2 eiviei 1 ekvk 其中结点可能重复出现 但边不重复 因为欧拉通路经过所有图G的结点 故图G是连通的 对任意一个不是端点 始点和终点 的结点vi 在欧拉通路中每当vi出现一次 必关联两条边 故vi虽可重复出现 但deg vi 必是偶数 对于端点 若v0 vk 则d v0 为偶数 即G中无奇数度结点 若端点v0与vk不同 则d v0 为奇数 d vk 为奇数 G中就有两个奇数度结点 13 8 2欧拉图与哈密尔顿图 充分性若图G连通 有零个或两个奇数度结点 我们构造一条欧拉通路如下 1 若有两个奇数度结点 则从其中的一个结点考试构造一条迹 即从v0出发经关联边e1 进入 v1 若deg v1 为偶数 则可由v1再经关联边e2进入v2 如此进行下去 每边仅取一次 由于G是连通的 故必可到达另一奇数度结点停下 得到一条迹L v0e1v1e2v2 eiviei 1 ekvk 若G中没有奇数度结点则从任一结点v0出发 用上述方法必可回到结点v0 得到上述一条闭迹L1 14 8 2欧拉图与哈密尔顿图 2 若L1通过了G的所有边 则L1就是欧拉通路 3 若G中去掉L1后得到子图G 则G 中每个结点度数为偶数 因为原来的图是连通的 故L1与G 至少有一个结点vi重合 在G 中由vi出发重复 1 的方法 得到闭迹L2 4 当L1与L2组合在一起 如果恰是G 即得欧拉通路 否则重复 3 可得到闭迹L3 依此类推直到得到一条经过图G中所有边的欧拉通路 15 8 2欧拉图与哈密尔顿图 由于有了欧拉回路和欧拉通路的判别准则 因此哥尼斯堡七桥问题立即有了确切的否定答案 因为从上图中可以看到deg A 5 deg B deg C deg D 3 故欧拉回路必不存在 16 8 2欧拉图与哈密尔顿图 欧拉通路和欧拉回路的概念 可以推广到有向图中去 定义8 2 2给定有向图G 通过图中每边一次且仅一次的一条单向通路 回路 称作单向欧拉通路 回路 定理8 2 2有向图G具有一条单向欧拉回路 当且仅当是连通的 且每个结点入度等于出度 一个有向图G具有单向欧拉通路 当且仅当它是连通的 而且除两个结点之外 每个结点的入度等于出度 但这两个结点中 一个结点的入度比出度大1 另一个结点的入度比出度小1 17 8 2欧拉图与哈密尔顿图 二 哈密尔顿图1859年爱尔兰数学家威廉 哈密顿首先提出在正十二面体上的一个数学游戏 即能否在如下所示的图中找到一条基本 初级 回路 或路径 使它经过每个顶点恰好一次 18 8 2欧拉图与哈密尔顿图 由于他将每个顶点看作一个城市 将两个顶点之间的边看作交通线 于是他提出的问题称为 周游世界问题 对于任何一个连通图 都可以提出这样的问题 即在图中是否存在经过所有顶点一次且仅一次的回路或通路 将这样的初级通路 回路分别称为哈密尔顿通路 回路 19 8 2欧拉图与哈密尔顿图 定义8 2 3给定图G 若存在一条通路经过图中的每个结点恰好一次 这条通路称作哈密尔顿路 若存在一条回路 经过图中的每个结点恰好一次 这条回路称作哈密尔顿回路 具有哈密尔顿回路的图称作哈密尔顿图 与欧拉图的情况不同 直到目前 人们还没有找到哈密尔顿图的简单的充要条件 寻找充要条件是图论中的一个难题 目前人们只找到一些判断存在性的充分条件和一些必要条件 下面以无向图为例加以说明 20 8 2欧拉图与哈密尔顿图 定理8 2 3设无向图G 为哈密尔顿图 V1是V的任意真子集 则其中 p G V1 为从G中删除V1后所得图的连通分支数 定理中给出的条件是必要的 因而对一个图来说 如果不满足这个必要条件 它一定不是哈密尔顿图 但是 满足这个条件的图不一定是哈密尔顿图 推论 有割点的图一定不是哈密尔顿图 21 8 2欧拉图与哈密尔顿图 下面给出一些充分条件 定理8 2 4设G是n n 3 阶无向简单图 若对于G中每一对不相邻的顶点u v 均有deg u deg v n 1则G中存在哈密尔顿通路 又若deg u deg v n则G中存在哈密尔顿回路 即G为哈密尔顿图 推论 设G是n n 3 阶无向简单图 若G是哈密尔顿图 22 8 2欧拉图与哈密尔顿图 23 8 2欧拉图与哈密尔顿图 关于有向图中的哈密尔顿通路与回路有下面的结论 定理8 2 5在n n 2 阶有向图D 中 如果略去所有有向边的方向 所得无向图中含生成子图kn 则D中存在哈密尔顿通路 推论n n 3 阶有向完全图都是哈密尔顿图 24 8 2欧拉图与哈密尔顿图 例 今有a b c d e f g7个任 已知下列事实 a会讲英语 b会讲英语和汉语 c会讲英语 意大利语和俄语 d会讲日语和汉语 e会讲德语和意大利语 f会讲法语 日语和俄语 g会讲法语和德语 问能否将这7个人安排就坐圆桌旁 使得每个人都能与两边的人交谈 25 8 2欧拉图与哈密尔顿图 解 做无向图G V a b c d e f g E u v u v V且u v且u与v有共同语言 根据已知条件得G如下图所示 26 8 2欧拉图与哈密尔顿图 在图中 u与v相邻当且仅当它们有共同语言 问题就变成了图中是否存在哈密尔顿回路 也即G为哈密尔顿图 不难看出C acegfdba为G中的一条哈密尔顿回路 因而可以按C中顶点顺序安排座次 这样 每个人都与两边的人有共同语言 因而能交谈 27 8 3平面图 在图的理论探讨和实际应用中 平面图都具有重要的意义 比如在现实生活中 常常要画一些图形 希望边与边之间尽量减少相交的情况 例如印刷线路板上的布线 交通道的设计等 定义8 3 1设G 是一个无向图 如果能够把G的所有结点和边画在平面上 且使得任何两边除了端点外没有其它的交点 就称G是一个平面图 画出的没有边交叉出现的图称为G的一个平面嵌入或平面表示 无平面嵌入的图为非平面图 28 8 3平面图 a b 29 8 3平面图 c d 30 8 3平面图 定义8 3 2设G是一个平面图 G的边将所在的平面划分成若干个区域 每个区域称为G的一个面 其中面积无限的区域称为无限面或外部面 面积有限的区域称为内部面或有限面 包围每个面的所有边构成的回路称为该面的边界 边界的长度称为该面的次数 面Ri的次数记作deg Ri 人们常把外部面记成R0 31 8 3平面图 32 8 3平面图 定理8 3 1在一个平面图G中 所有面的次数之和为边数的2倍 即其中 r为G的面数 m为边数 关于平面图的平面嵌入 还应指出两点 1 同一个平面图G 可以有不同形状的平面嵌入 但它们都是与G同构的 2 平面图G的外部面 可以通过变换由G的任何面充当 33 8 3平面图 在上图中 b c 都是 a 的平面嵌入 它们的形状不