离散数学欧拉图与哈密顿图.ppt

第15章二部图 欧拉图与哈密顿图 离散数学 江苏科技大学本科生必修课程 计算机系周塔 二部图 从本节起将讨论一些特殊的图 首先讨论二部图 定义8 4 1若无向图G V E 的顶点集合V可以划分成两个子集X和Y 使G中的每一条边e的一个端点在X中 另一个端点在Y中 则称G为二部图或偶图 二部图可记为G X E Y X和Y称为互补结点子集 由定义可知 二部图不会有自回路 定义8 4 2二部图G X E Y 中 若X的每一顶点都与Y的每一顶点邻接 则称G为完全二部图 记为Km n 这里m X n Y 图8 4 1给出K2 4和K3 3的图示 图8 4 1 定理8 4 1无向图G V E 为二部图的充分必要条件为G中所有回路的长度均为偶数 定义8 4 3给定一个二部图G X E Y 如果E的子集M中的边无公共端点 则称M为二部图G的一个匹配 含有最多边数的匹配称为G的最大匹配 例如 下图中 M x1 y5 x3 y1 x4 y3 是G的一个匹配 15 1欧拉图 历史背景 哥尼斯堡七桥问题 欧拉图是一笔画出的边不重复的回路 欧拉图 定义15 1通过图 无向图或有向图 中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路 通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路 具有欧拉回路的图称为欧拉图 具有欧拉通路而无欧拉回路的图称为半欧拉图 说明欧拉通路是图中经过所有边的简单的生成通路 经过所有顶点的通路称为生成通路 欧拉回路是经过所有边的简单的生成回路 举例 欧拉图 半欧拉图 无欧拉通路 欧拉图 无欧拉通路 无欧拉通路 无向欧拉图的判定定理 定理15 1无向图G是欧拉图当且仅当G是连通图 且G中没有奇度顶点 定理15 2无向图G是半欧拉图当且仅当G是连通的 且G中恰有两个奇度顶点 半欧拉图的判定定理 有向欧拉图的判定定理 定理15 3有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度 定理15 4有向图D是半欧拉图当且仅当D是单向连通的 且D中恰有两个奇度顶点 其中一个的入度比出度大1 另一个的出度比入度大1 而其余顶点的入度都等于出度 举例 定理15 5G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈的并 15 2哈密顿图 历史背景 哈密顿周游世界问题与哈密顿图 哈密顿周游世界问题 哈密顿圈是图论中著名世界难题之一 1859年 英国数学家兼物理学家哈密顿提出以下周游世界问题 用一个正十二面体的二十个顶点表示二十个城市 怎样才能从一个城市出发 沿着棱经过每个城市恰好一次 最后返回到出发点 哈密顿图 定义15 2经过图 有向图或无向图 中所有顶点一次且仅一次的通路称为哈密顿通路 经过图中所有顶点一次且仅一次的回路称为哈密顿回路 具有哈密顿回路的图称为哈密顿图 具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图 规定 平凡图是哈密顿图 说明哈密顿通路是图中生成的初级通路 哈密顿回路是生成的初级回路 判断一个图是否为哈密顿图 就是判断能否将图中所有顶点都放置在一个初级回路 圈 上 但这不是一件易事 与判断一个图是否为欧拉图不一样 到目前为止 人们还没有找到哈密顿图简单的充分必要条件 例题 1 2 是哈密顿图 3 是半哈密顿图 4 既不是哈密顿图 也不是半哈密顿图 推论 推论1设无向图G 是哈密顿图 对于任意的V1 V且V1 均有 p G V1 V1 推论2设无向图G 是半哈密顿图 对于任意的V1 V且V1 均有 p G V1 V1 1 例15 3 例15 3在下图中给出的三个图都是二部图 它们中的哪些是哈密顿图 哪些是半哈密顿图 为什么 易知互补顶点子集V1 a f V2 b c d e 设此二部图为G1 则G1 p G1 V1 4 V1 2 由定理15 6及其推论可知 G1不是哈密顿图 也不是半哈密顿图 例15 3 设图为G2 则G2 其中V1 a g h i c V2 b e f j k d 易知 p G2 V1 V2 6 V1 5 由定理15 6可知 G2不是哈密顿图 但G2是半哈密顿图 baegjckhfid为G2中一条哈密顿通路 设图为G3 G3 其中V1 a c g h e V2 b d i j f G3中存在哈密顿回路 如abcdgihjefa 所以G3是哈密顿图 例15 6 下图所示的三个图中哪些是哈密顿图 哪些是半哈密顿图 1 存在哈密顿回路 所以 1 为哈密顿图 2 取V1 a b c d e 从图中删除V1得7