Microsoft PowerPoint - 10 几种特殊的图.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - 10 几种特殊的图.ppt"

奋辑全
5 years ago
Views:

集合论与图论 10 目录二部图几种特殊的图欧拉图何英华 hyh@tju.edu.

则称 G 为二部图 ( 或称二分图, 偶图等 ), 称 V 1 和 V 2 为互补顶点子集, 常将二部图 G 记为 <V 1,V 2,E> 完全二部图若 G 是简单二部图,V 1 中每个顶点均与 V 2 中所有顶点相邻, 则称

1 集合论与图论 10 目录二部图几种特殊的图欧拉图何英华哈密顿图平面图二部图设 G=<V,E> 为一个无向图, 若能将 V 分成 V 1 和 V 2 (V 1 V 2 =V,V 1 V 2 = ), 使得 G 中的每条边的两个端点都是一个属于 V 1, 另一个属于 V 2, 则称 G 为二部图 ( 或称二分图, 偶图等 ), 称 V 1 和 V 2 为互补顶点子集, 常将二部图 G 记为 <V 1,V 2,E> 完全二部图若 G 是简单二部图,V 1 中每个顶点均与 V 2 中所有顶点相邻, 则称 G 为完全二部图, 记为 K r,s, 其中 r= V 1,s= V 2 注意,n 阶零图为二部图在完全二部图 K r,s 中, 它的顶点数 n=r+s, 边数 m=r s 判断下面的图是不是二部图? 哪些是同构的图? 下面的图都是二部图, 其中图 3 与图 5 同构, 图 5 是 K 3,3 的标准形式, 图 4 与图 6 同构, 图 6 是 K 2,3 的标准形式 1

2 二部图的判别定理 : 一个无向图 G=<V,E> 是二部图当且仅当 G 中无奇数长度的回路必要性若 G 中无回路, 结论显然成立若 G 中有回路, 只需证明 G 中无奇圈充分性不妨设 G 为连通图, 否则可对每个连通分支进行讨论设 v 0 为 G 中任意一个顶点, 令 V 1 ={v v V(G) d(v 0,v) 为偶数 } V 2 ={v v V(G) d(v 0,v) 为奇数 } 易知,V 1,V 2,V 1 V 2 =,V 1 V 2 =V(G) 下面只要证明 V 1 中任意两顶点不相邻,V 2 中任意两点也不相邻判别以下图中哪些是二部图不是是是不是今有 a,b,c,d,e,f,g 等 7 个人, 已知 a 会讲英语, b 会讲英语和汉语,c 会讲英语意大利语和俄语,d 会讲日语和汉语,e 会讲德语和意大利语,f 会讲法语日语和俄语,g 会讲法语和德语, 试问能否从这 7 个人中找出 7 名翻译, 使得每人翻译一种语言? 今有 a,b,c,d,e,f,g 等 7 个人, 已知 a 会讲英语, b 会讲英语和汉语,c 会讲英语意大利语和俄语,d 会讲日语和汉语, e 会讲德语和意大利语,f 会讲法语日语和俄语,g 会讲法语和德语, 试问能否从这 7 个人中找出 7 名翻译, 使得每人翻译一种语言? a b c d e f g 英汉意俄日德法目录二部图 a b c d e f g 欧拉图哈密顿图英汉意俄日德法平面图 2

欧拉回路 : 经过图中所有边的简单回路欧拉图 : 有欧拉回路的图在下面各图中, 图 1,4 中存在欧拉回路, 是欧拉图, 图 2 中存在欧拉通路, 但不存在欧拉回路, 不是欧拉图

3 七桥问题一笔画 1736 年, 欧拉提出七桥问题, 图论诞生 C cd A a b B e g f D 欧拉图欧拉通路 : 经过图中所有边的简单通路在下面各图中, 哪些存在欧拉回路? 哪些存在欧拉通路? 欧拉回路 : 经过图中所有边的简单回路欧拉图 : 有欧拉回路的图在下面各图中, 图 1,4 中存在欧拉回路, 是欧拉图, 图 2 中存在欧拉通路, 但不存在欧拉回路, 不是欧拉图图 3,5,6 中既没有欧拉回路, 也没有欧拉通路, 不是欧拉图无向欧拉图的判别定理 : 无向图 G 具有欧拉通路, 当且仅当 G 是连通图且无奇度顶点或有两个奇度顶点若无奇度顶点, 则通路为回路, 若有两个奇度顶点, 则它们是每条欧拉通路的端点推论 : 无向图 G 是欧拉图当且仅当 G 是连通图, 且 G 中没有奇度顶点 3

4 有向欧拉图的判别定理 : 有向图 D 具有欧拉通路, 当且仅当 D 是连通图且 D 中除了两个例外顶点之外, 其余顶点的入度都等于出度, 这两个例外顶点中, 一个的入度比出度大 1, 另一个的出度比入度大 1 推论 : 有向图 D 是欧拉图当且仅当 D 是连通图, 且 D 中所有顶点的入度都等于出度目录周游世界问题二部图欧拉图 1859 年, 数学家哈密顿将正十二面体的每个顶点比作一个城市, 连接两个顶点之间的边看作城市之间的交通线, 提出周游世界问题 : 能否从某个城市出发沿交通线经过每个城市一次并且仅一次, 最后回到出发点? 哈密顿图平面图哈密顿图在下面各图中, 哪些是哈密顿图? 哪些具有哈密顿通路? 哈密顿通路 : 经过图中所有顶点的初级通路哈密顿回路 : 经过图中所有顶点的初级回路哈密顿图 : 有哈密顿回路的图 4

在下面各图中, 图 1,2,3 都有哈密顿回路, 是哈密顿图图 4 具有哈密顿回路, 是哈密顿图图 5 只有哈密顿通路, 但无哈密顿回路, 不是哈密顿图, 图 6

p(g-v 1 ) V 1 证明 : 设 C 是 G 中任意哈密顿回路, 则 V 1 中的顶点在 C 中有些相邻, 有些不相邻,p(C-V 1 ) V 1 因为 C 是

彼得松图中存在哈密顿通路无向哈密顿图的充分条件定理 : 设 G 是 n( 3) 阶无向简单图, 若对 G 中任意不相邻顶点 u 与 v 均有 d(u)+d(v)

5 在下面各图中, 图 1,2,3 都有哈密顿回路, 是哈密顿图图 4 具有哈密顿回路, 是哈密顿图图 5 只有哈密顿通路, 但无哈密顿回路, 不是哈密顿图, 图 6 中既无哈密顿回路, 也没有哈密顿通路, 不是哈密顿图无向哈密顿图的必要条件定理 : 设 G=<V,E> 是无向哈密顿图, 则对 V 的任意非空真子集 V 1 有 p(g-v 1 ) V 1 证明 : 设 C 是 G 中任意哈密顿回路, 则 V 1 中的顶点在 C 中有些相邻, 有些不相邻,p(C-V 1 ) V 1 因为 C 是 G 的生成子图, 所以 p(g-v 1 ) P(C-V 1 ) V 1. 推论 : 有割点的图一定不是哈密顿图举例 1. 证明 : 当 r s 时, 完全二部图 K r,s 不是哈密顿图 2. 证明 : 下图不是哈密顿图反例 : 非充分条件反例 : 彼得松图彼得松图满足 : V 1, p(g-v 1 ) V 1 彼得松图不是哈密顿图彼得松图中存在哈密顿通路无向哈密顿图的充分条件定理 : 设 G 是 n( 3) 阶无向简单图, 若对 G 中任意不相邻顶点 u 与 v 均有 d(u)+d(v) n-1, 则 G 中存在哈密顿通路又若 d(u)+d(v) n, 则 G 是哈密顿图度数为 2 的顶点关联的两条边必须出现在哈密顿回路上推论 : 设 G 是 n( 3) 阶无向简单图, 若对 G 中任意顶点 u 有 d(u) n/2, 则 G 是哈密顿图完全图 K n 当 n 3 时是哈密顿图完全二部图 K r,s 当 r=s 2 时是哈密顿图 5

问能否将这 8 个人排在圆桌旁, 使其任何人都能与两边的人交谈 2. 下面的图是哈密顿图吗?

靠破坏必要条件 ( 连通度数为 2 的顶点关联的两条边必须出现在哈密顿回路上删除顶点等等 ) 判断一个图是哈密顿图,

如果略去所有有向边的方向, 所得无向图中含有生成子图 K n, 则 D 中存在哈密顿通路推论 : n( 3) 阶有向完全图都是哈密顿图

6 反例 : 非必要条件 1. 某国际会议共有 8 人参加, 他们来自不同的国家已知他们中任何两个无共同语言的人中的每一个, 与其余有共同语言的人数之和大于或等于 8, 问能否将这 8 个人排在圆桌旁, 使其任何人都能与两边的人交谈 2. 下面的图是哈密顿图吗? 证明你的结论反例, 例如圈图 C 6 目前尚未找到哈密顿图的简单的充要条件, 只有一些必要条件和充分条件判断一个图不是哈密顿图, 靠破坏必要条件 ( 连通度数为 2 的顶点关联的两条边必须出现在哈密顿回路上删除顶点等等 ) 判断一个图是哈密顿图, 看是否能找出一条哈密顿回路, 或是否满足充分条件有向哈密顿图的充分条件目录定理 : 设 D 是 n( 2) 阶有向简单图, 如果略去所有有向边的方向, 所得无向图中含有生成子图 K n, 则 D 中存在哈密顿通路推论 : n( 3) 阶有向完全图都是哈密顿图二部图欧拉图哈密顿图平面图平面图的概念欧拉公式库拉图斯基定理平面图的对偶图平面图定义 : 如果图 G 能以这样的方式画在平面上, 即除顶点处外无边相交, 则称 G 为平面图画出的无边相交的图称为 G 的平面嵌入或平面表示无平面嵌入的图称为非平面图库拉图斯基图 K 3,3 库拉图斯基图 K 5 6

面和面的次数定义 : 设 G 是平面图, 由 G 的边将 G 所在的平面划分成若干个区域, 每个区域都称为 G 的一个面

R 0, 内部面为 R 1, R 2,,R k, 面 R i 的次数记为 deg(r i ) 定理 : 平面图 G 中所有面的次数之和等于边数 m 的两倍有

)=1 R 4 的边界为圈 kjl,deg(r 4 )=3 外部面 R 0 的边界由一个简单回路 abefgdc 和一个复杂回路 kjihil

只有 (3) 是极大平面图 K n, 当 n 4 时都是极大平面图 K 5 删除任意一条边所得图也是极大平面图定理 : 设 G 为 n(n 3)

7 面和面的次数定义 : 设 G 是平面图, 由 G 的边将 G 所在的平面划分成若干个区域, 每个区域都称为 G 的一个面其中面积无限的面称为无限面或外部面, 面积有限的面称为有限面或内部面包围每个面的所有边组成的回路组称为该面的边界, 边界的长度称为该面的次数常记外部面为 R 0, 内部面为 R 1, R 2,,R k, 面 R i 的次数记为 deg(r i ) 定理 : 平面图 G 中所有面的次数之和等于边数 m 的两倍有 5 个面 R 1 的边界为圈 abdc,deg(r 1 )=4 R 2 的边界是 efg,deg(r 2 )=3 R 3 的边界为环 h, deg(r 3 )=1 R 4 的边界为圈 kjl,deg(r 4 )=3 外部面 R 0 的边界由一个简单回路 abefgdc 和一个复杂回路 kjihil 组成,deg(R 0 )=13 极大平面图极大平面图是简单平面图, 但是在任意两个不相邻顶点之间加边就变成非平面图极大平面图在下面所示的各平面图中, 只有 (3) 是极大平面图 K n, 当 n 4 时都是极大平面图 K 5 删除任意一条边所得图也是极大平面图定理 : 设 G 为 n(n 3) 阶简单连通的平面图,G 为极大平面图当且仅当 G 的每个面的次数均为 3 极小非平面图极小非平面图是非平面图, 但是删除任意一条边就是平面图 K 5 和 K 3,3 都是极小非平面图库拉图斯基图 K5 库拉图斯基图 K3,3 7

8 欧拉公式欧拉公式 : 对于任意的连通的平面图 G 有 n-m+r=2, 其中,n,m,r 分别为 G 的顶点数, 边数和面数平面图的边数 m 与顶点数 n 的关系定理 : 设 G 是连通平面图, G 的各面的次数至少是 l ( 3), 则 m (n-2) l/(l-2) 欧拉公式的推广 : 对于具有 k(k 2) 个连通分支的平面图 G, 有 n-m+r = k+1 其中 n,m,r 分别为 G 的顶点数, 边数和面数平面图的边数 m 与顶点数 n 的关系推论 :K 5 与 K 3,3 都不是平面图平面图的边数 m 与顶点数 n 的关系定理 : 设 G 是有 k(k 2) 个连通分支的平面图, G 的各面的次数至少是 l ( 3), 则 m (n-k-1) l/(l-2) 库拉图斯基图 K5 库拉图斯基图 K3,3 证明 : 设 G 是 n(n 3) 阶 m 条边的简单连通平面图, 则 m 3n-6 证明 : 设 G 是 n(n 3) 阶 m 条边的简单平面图, 则 m 3n-6 8

9 证明 : 设 n( 3) 阶简单极大平面图 G 有 m 条边, 则 m=3n-6. 证明 : 设 G 是简单平面图, 则 G 的最小度 δ 5 同胚插入 2 度顶点 : 把 (u,v) 变成 (u,w),(w,v) 删除 2 度顶点 : deg(w)=2, 把 (u,w),(w,v) 变成 (u,v) u v u w v 收缩图 G 中边 (u,v) 的收缩由下面的方法给出 : 删除边 (u,v), 将 u 与 v 重合, 所得顶点记为 u( 或 v), 使 u( 或 v) 关联除边 (u,v) 外, 原来 u 与 v 关联的一切边. 同胚 : 反复插入或删除 2 度顶点后同构 v 2 v 2 v 1 v 3 v 1 v 4 v 4 库拉图斯基定理第 1 种叙述形式 : 一个图是平面图当且仅当它不含与 K 5 同胚子图, 也不含与 K 3,3 同胚子图. 判断以下两个图是否是平面图第二种叙述形式 : 一个图是平面图当且仅当它没有可以收缩到 K 5 的子图, 也没有收缩到 K 3,3 的子图. 9

10 K 5 K 3,3 K 5 K 3,3 K 6 的含 K 3,3 的非同构子图有哪些? 对偶图设平面图 G=<V,E>,G 有 r 个面,n 个顶点,m 条边用如下的方法构造 G*: (1) 在 G 的面 R i 中任取一个顶点 v i * 作为 G* 的顶点,G* 的顶点集 V*={v 1 *,v 2 *,...,v r *}, 解 : K 6 有 15 条边, K 3,3 有 9 条边, 分别给 K 3,3 加 0,1,2,3,4,5,6 条边, 共 10 种. (2) 若面 R i 和 R j 的边界中有公共边 e k, 连接对应顶点 v i * 和 v j *, 得 G* 的边 e k * 与 e k 相交当 e k 只在 G 的一个面 R j 的边界中出现时, 以 R i 中的顶点 v i * 为顶点做环 e k *,e k * 为 G* 中一个环设 G* 的边集为 E*, 由于 G* 的边数与 G 的边数相同, 则 E*={e 1 *,e 2 *,,e m *}, 称 G*=<V*,E*> 为 G 的对偶图. 例性质 (a) (b) 设 G* 是连通平面图 G 的对偶图,n*,m*,r* 和 n, m,r 分别为 G* 和 G 的顶点数, 边数, 面数,G* 的顶点 v i * 位于 G 的面 R i 中, 则 (1) n*=r (2) m*=m (3) r*=n (4) d G* (v i *)=deg(r i ) 同构平面图的对偶图, 不一定是同构的若前提改为 G 具有 k( 2) 个连通分支则 r*=n-k+1 10

11 证明 : 平面图 G 的对偶图 G* 为欧拉图当且仅当 G 的每个面的次数均为偶数证明 : 若 G 为二部图并且是平面图, 则 G 的对偶图均为欧拉图作业

<4D F736F F F696E74202D20CDBCC2DB2D31342ECDBCB5C4BBF9B1BEB8C5C4EE2E707074>

<4D F736F F F696E74202D20CDBCC2DB2D31342ECDBCB5C4BBF9B1BEB8C5C4EE2E707074> 图论王智慧复旦大学计算机学院图的基本概念图的概念通路与回路图的连通性图的矩阵表示图的运算 2 无序积, 多重集定义 : 设 A 和 B 为任意的两个集合, 称 { {a, b} a A, b B } 为 A 与 B 的无序积, 记做 A&B. 定义 : 元素可以重复出现的集合称为多重集, 其中某元素重复出现的次数称为该元素的重复度. 例如 : {a, a, b} 为一个多重集, 其中元素