几种特殊的图初步.PPTVIP

第8章 几种特殊的图 第8章 几种特殊的图 8.1 欧拉图 8.2 哈密顿图 8.3 二部图 8.4 平面图 8.5 树 欧拉图 问题 寻找走遍哥尼斯堡(K?nigsberg)城的7座桥, 且只许走过每座桥一次, 最后又回到原出发点(图论源于游戏). 求解 1736年瑞士大数学家欧拉(Leonhard Euler)发表了关于“哥尼斯堡七桥问题”的论文(图论的第一篇论文). 他指出从一点出发不重复的走遍七桥, 最后又回到原来出发点是不可能的. 欧拉因此被称为“图论之父”, 1736年通常被称为“图论元年”. 欧拉图 定义8.1 欧拉通路:经过所有顶点且每条边恰好经过一次的通路 欧拉回路:经过所有顶点且每条边恰好经过一次的回路 欧拉图:有欧拉回路的图 说明： 上述定义对无向图和有向图都适用 规定平凡图为欧拉图 欧拉通路是简单通路, 欧拉回路是简单回路 欧拉图判别定理 定理8.1 无向图G具有欧拉回路当且仅当G是连通的且无 奇度顶点. 无向图G具有欧拉通路、但没有欧拉回路当且仅当G是连 通的且有2个奇度顶点, 其余顶点均为偶度数的. 这2个奇 度顶点是每条欧拉通路的端点. 推论 无向图G是欧拉图当且仅当G是连通的且无奇度顶点 实例 欧拉图判别定理(续) 定理8.2 有向图D有欧拉回路当且仅当D是连通的且所有 顶点的入度等于出度. 有向图D有欧拉通路、但没有欧拉回路当且仅当D是连通 的且有一个顶点的入度比出度大1、一个顶点的入度比出 度小1, 其余的顶点的入度等于出度. 推论 有向图D是欧拉图当且仅当D是连通的且所有顶点的 入度等于出度. 实例 哈密顿图 定义8.2 哈密顿通路: 经过图中所有顶点一次且仅一次的通路. 哈密顿回路: 经过图中所有顶点一次且仅一次的回路. 哈密顿图: 具有哈密顿回路的图. 说明： 哈密顿通路是初级通路 哈密顿回路是初级回路 有哈密顿通路不一定有哈密顿回路 周游世界问题(W.Hamilton, 1859年) 存在哈密顿回路(通路)的充分条件 应用 例一次会议有20人参加，其中每个人都在其中有不下10个朋友。这20人围成一圆桌入席。有没有可能使任意相邻而坐的两个人都是朋友？为什么？ 应用 例 有7个人, A会讲英语, B会讲英语和汉语, C会讲英语、 意大利语和俄语, D会讲日语和汉语, E会讲德语和意大利 语, F会讲法语、日语和俄语, G会讲法语和德语. 问能否将 他们沿圆桌安排就坐成一圈, 使得每个人都能与两旁的人 交谈? 解 应用 二部图 定义8.3 设无向图 G=V,E, 若能将V 分成V1 和 V2 使得 V1?V2=V, V1?V2=?, 且G中的每条边的两个端点都一个 属于V1, 另一个属于V2, 则称G为二部图, 记为V1,V2,E, 称V1和V2为互补顶点子集. 又若G是简单图, 且V1中每个顶 点均与V2中每个顶点都相邻, 则称G为完全二部图, 记为 Kr,s, 其中r=|V1|, s=|V2|. 平面图与非平面图 定义8.4 如果能将图G除顶点外边不相交地画在平面上, 则称G是平面图. 这个画出的无边相交的图称作G的平面 嵌入. 没有平面嵌入的图称作非平面图. 树 8.5.1 无向树 无向树的定义及其性质 生成树 最小生成树 8.5.2 根树及其应用 根树及其分类 最优树与哈夫曼算法 最佳前缀码 8.5.1 无向树 无向树的定义及其性质 生成树 最小生成树 最短通路问题 真实的树 无向树的定义 无向树: 连通无回路的无向图 平凡树: 平凡图 森林: 每个连通分支都是树的非连通的无向图 树叶: 树中度数为1的顶点 分支点: 树中度数?2的顶点 无向树的性质 定理8.5 设G=V,E是n阶m条边的无向图, 下面各命题是等价的： (1) G是树(连通无回路); (2) G中任意两个顶点之间存在惟一的路径; (3) G是连通的且m=n?1; (4) G中无回路且m=n?1; (5) G中无回路, 但在任何两个不相邻的顶点之间加一条边 所得图中有惟一的一条初级回路. (6) G是连通的，但删去任意一条边，则变成不连通图。 定理8.5的证明 (1)?(2) 由连通性, 任意2个顶点之间有一条路径. 又, 假设 某2个顶点之间有2条路径, 则这2条路径可组合成一条回 路, 与树的定义矛盾. (2)?(3) 显然连通, 要证m=n?1. 对n作归纳证明. 当n=1时, 显然m=0, 结论成立. 假设当n?k(k?1)时结论成立, 考虑n=k+1. 任取一条边e= (u,v), 它是u,v之间惟一的通路, 删去e, G被分成2个连通分 支, 设它们分别有n1, n2个顶点和m1, m2条边, n1?k, n2?k. 由归纳假设,