离散数学第八章.ppt

8.1 二部图 8.2 欧拉图 8.3 哈密尔顿图 8.4 平面图,第八章 一些特殊的图,离散数学 第八章 一些特殊的图,定义8.1 若能将无向图G=的顶点集V划分成两个子集V1和V2(V1∩V2=), 使得G中任何一条边的两个端点一个属于V1, 另一个属于V2, 则称G为二部图(也称为偶图). V1,V2称为互补顶点子集, 此时可将G记成G=.若V1中任一顶点与V2中每个顶点有且仅有一条边相关联, 则称二部图G为完全二部图(或完全偶图). 若V1 =n, V2=m, 则记完全二部图G为Kn,m.,8.1 二部图(P286-287),定义,在图8.1中, (1)所示为K2,3, (2)所示为K3,3. K3,3是重要的完全二部图, 它与K5一起在平面图中起着重要作用.,8.1 二部图,8.1 二部图,定理8.1 一个无向图G=是二部图当且仅当G中无奇数长度的回路. ★ 如图8.2 均无奇数长度的回路, 都是二部图. ★ 其中图(2)所示为K2,3,图(3)所示为K3,3.,二部图的判断定理,8.1 二部图,定义8.2 设G=为无向图, E*E, 若E*中任意两条边均不相邻, 则称E*为G中的匹配(或边独立集). ① 若在E*中再加入任何1条边就都不是匹配了,则称E*为极大匹配. ②边数最多的极大匹配称为最大匹配, 最大匹配中的元素(边)的个数称为G的匹配数, 记为1(G), 简记为1. 注意: 今后常用M表示匹配. 设M为G中一个匹配. vV(G), 若存在M中的边与v关联, 则称v为M的饱和点, 否则称v为M非饱和点, 若G中每个顶点都是M饱和点, 则称M为G中完美匹配.,匹 配,在图 (1)中, {e1},{e1,e7},{e5},{e4,e6}等都是图中的匹配. 其中{e5},{e1,e7},{e4,e6}是极大匹配, {e1,e7},{e2,e6}是最大匹配, 匹配数1=2. 图中不存在完美匹配. 在图(2)中,{e2,e5},{e3,e6},{e1,e7,e4}都是极大匹配,其中{e1,e7,e4}是最大匹配, 同时也是完美匹配, 匹配数为3.,8.1 二部图,定义8.3 设G=为一个二部图, M为G中一个最大匹配, 若M=min{V1,V2}, 则称M 为G中的一个完备匹配, 此时若V1 ≤V2, 则称M为V1到V2的一个完备匹配. 如果V1= V2, 这时M为G中的完美匹配.,完备匹配,存在完备匹配吗?存在完美匹配吗?.,8.1 二部图,定理8.2 设二部图G=, V1≤V2, G中存在从V1到V2的完备匹配当且仅当V1中任意k个顶点(k=1,2,… V1)至少邻接V2中的k个顶点. 定理8.3 设二部图G=, 如果(1) V1中每个顶点至少关联t(t＞0)条边;(2) V2中每个顶点至多关联t条边, 则G中存在V1到V2的完备匹配.,Hall定理,Hall定理中的条件称为“相异性条件”, 定理8.3中的条件称为“t条件”, 满足t条件的二部图, 一定满足相异性条件. 事实上, 由条件(1)可知, V1中k个顶点至少关联kt条边. 由条件(2)可知, 这kt条边至少关联V2中的k个顶点, 于是若G满足t条件, 则G一定满足相异性条件, 但反之不真.,8.1 二部图,Hall定理,例8.1 某中学有3个课外小组: 物理组、化学组、生物组.今有张、王、李、赵、陈5名同学.若已知:(1) 张、王为物理组成员, 张、李、赵为化学组成员, 李、赵、陈为生物组成员;(2) 张为物理组成员, 王、李、赵为化学组成员, 王、李、赵、陈为生物组成员;(3) 张为物理组和化学组成员, 王、李、赵、陈为生物组成员.问在以上3种情况下能否各选出3名不兼职的组长？,解: 设v1,v2,v3,v4,v5分别表示张,王,李,赵,陈; u1,u2,u3分别表示物理组,化学组,生物组; 在3种情况下作二部图分别记为G1,G2,G3, 如下图所示.,G1满足t=2的t条件, 所以, 存在从V1={u1,u2,u3}到V2={v1,v2,v3,v4,v5}的完备匹配, 图中粗边所示的匹配就是其中的一个, 即选张为物理组组长, 李为化学组组长, 赵为生物组组长. G2不满足t条件, 但满足相异性条件, 因而也存在完备匹配, 图中粗边所示匹配就是其中的一个完备匹配. G3不满足t条件, 也不满足相异性条件, 因而不存在完备匹配, 故选不出3名不兼职的组长来.,8.2 欧拉图(即一笔画问题),18世纪在哥尼斯堡城(今俄罗斯加里宁格勒)的普莱格尔河上有7座桥, 将河中的两个岛和河岸连结, 如图所示. 城中的居民经常沿河过桥散步, 于是提出了一个问题: 能否一次走遍7座桥, 而每座桥只许通过一次, 最后仍回到起始地点. 这就是七桥问题, 一个著名的图论问题. 大数学家欧拉那里证明了这样的走法不存在.,§哥尼斯堡七桥问题,无向图的欧拉图及其判断 定义8.4 经过图中每条边一次且仅一次并且行遍图中每个顶点的通路(回路), 称为欧拉通路或欧拉迹(欧拉回路或欧拉闭迹). 存在欧拉回路的图, 称为欧拉图.只存在欧拉通路的图, 称为半欧拉图. 定理8.4 无向图G为欧拉图当且仅当G是连通的, 且G中无奇度顶点. 无向图G为半欧拉图,当且仅当G是连通的且G中有两个奇度顶点. 注: 若无奇度顶点, 则通路为回路; 若有两个奇度顶点, 则它们是每条欧拉通路的端点.,8.2 欧拉图(即一笔画问题),图中(1)(2)(3) 不是欧拉图, (4) 是欧拉图.,8.2 欧拉图(即一笔画问题),8.2 欧拉图(即一笔画问题),例.,图1是欧拉图; 图2不是欧拉图, 但存在欧拉通路; 图3既不是欧拉图, 也不存在欧拉通路.,8.2 欧拉图(即一笔画问题),有向图的欧拉回路判定定理 定理8.5 一个有向图D是欧拉图(具有欧拉回路), 当且仅当D是强连通的, 且所有顶点的入度等于出度. 一个有向图D是半欧拉图(具有欧拉通路), 当且仅当D是单向连通的, 且恰有两个奇度顶点, 其中一个入度比出度大1, 另一个入度比出度小1. 而其余顶点的入度均等于出度.,(1)既无欧拉回路, 也无欧拉通路. (2)中存在欧拉通路, 但无欧拉回路, 即为半欧拉图. (3)中存在欧拉回路, 即为欧拉图.,8.2 欧拉图(即一笔画问题),例,图(a)存在一条欧拉通路：v3v1v2v3v4v1； 图(b)中存在欧拉回路v1v2v3v4v1v3v1，因而(b)是欧拉图； 图(c)中有欧拉回路v1v2v3v4v5v6v7v8v2v4v6v8v1因而(c)是欧拉图。

8.3 哈密尔顿图,1895年爱尔兰数学家威廉.哈密尔顿首先提出了在正十二面体上的一个数学游戏, 即能否在如图所示的图上找到一条初级回路, 使它经过每个城市恰好一次, 这个问题就是“周游世界问题”. 这样的通路(回路)就是哈密尔顿通路(回路).,8.3 哈密尔顿图,定义8.5 经过图中每个顶点一次且仅一次的通路(回路)称为哈密尔顿通路(回路). 存在哈密尔顿回路的图称为哈密尔顿图. 只存在哈密尔顿通路的图称为半哈密尔顿图. 例: 图中(1)是半哈密尔顿图, (2) 为哈密尔顿图, (3)既不是半哈密尔顿图也不是哈密尔顿图.,8.3 哈密尔顿图,哈密尔顿图的判定 定理8.6 (必要条件) 若无向图G=是哈密尔顿图, 则对V的任意的非空真子集V1, 都有p(G-V1)≤V1. 其中, p(G-V1)为从G中删除V1(删除V1中各顶点及关联的边)后所得图的连通分支数. 推论 若无向图G=是半哈密尔顿图, 则对V的任意的非空真子集V1, 都有p(G-V1)≤V1+1. 注: 利用该定理可以判断某些图不是哈密尔顿图.,证明: 设C为G中的一条哈密尔顿回路. (1) 若V1中的顶点在C上彼此相邻, 则p(C-V1)=1≤ V1 (2) 设V1中的顶点在C上存在r(2≤r≤ V1)个互不相邻, 则p(C-V1)= r≤V1 一般说来,V1中的顶点在C上既有相邻的, 又有不相邻的, 因而总有 p(C-V1)≤ V1. 又因为C是G的生成子图, 故p(G-V1)≤ p(C-V1)≤ V1.,8.3 哈密尔顿图,(1)图不是哈密尔顿图. (3)取V1={a,b,c,d,e,f,g}, G-V1如图(4)所示, 图(3)也不是哈密尔顿图.,8.3 哈密尔顿图,(1),(2),8.3 哈密尔顿图,在图中, 虽然对任意的结点集合V1, 都满足p(G-V1)|V1|, 但它仍然不是哈密尔顿图. 注: 到目前为止, 只能根据定义判断一个图是否为哈密尔顿图, 只有在特殊情况下才有判断方法.,例:,定理8.7(充分条件) 设G＝是n(n≥3)阶无向简单图. 如果G中任意两个不相邻的结点u,vV. 均有： d(u)+d(v)n-1，则G中存在哈密尔顿通路. 推论 设G＝是n(n≥3)阶无向简单图, 如果对任意两个不相邻的结点u,vV, 均有: d(u)+d(v)n则G中存在哈密尔顿回路, 即G是哈密尔顿图.,8.3 哈密尔顿图,8.3 哈密尔顿图,例:在右图中,任意两个结点的度数之和为4,结点数为6,即有46,但它仍然是哈密尔顿图.,关于有向图的哈密尔顿回路与通路 定理8.8 在n(n≥2)阶有向图D=中, 如果所有有向边均用无向边代替, 所得无向图中含生成子图Kn, 则有向图D中存在哈密尔顿通路. 推论 n(n≥3)阶有向完全图为哈密尔顿图.,8.4 平面图,8.4.1 平面图的基本概念 定义8.6 一个图G如果能以这样的方式画在平面上; 除顶点处外没有边交叉出现, 则称G为平面图. 画出的没有边交叉出现的图称为G的一个平面嵌入.无平面嵌入的的图称为非平面图.,图中, (2)是(1)(K4)的平面嵌入, 所以(1)是平面图. (2)是平面图. (3),(5)都不是平面图, 即K5和K3,3都不是平面图. (4),(6)分别是(3),(5)交叉最少的画法.,8.4 平面图,8.4.1 平面图的基本概念 定义8.7 设G是一个连通的平面图(指G的某个平面嵌入), G的边将G所在的平面划分成若干个区域, 每个区域称为G的一个面. 其中面积无限的区域称为无限面或外部面, 常记成R0. 包围每个面的所有边所构成的回路称为该面的边界, 边界的长度称为该面的次数, R的次数记为deg(R). ★对于非连通的平面图G有k(k≥2)个连通分支,则G的无限面R0的边界由k个回路围成.,图(1)所示为连通的平面图, 共有3个面R0,R1,R2. R1的边界为回路v1v3v4v1,deg(R1)=3. R2的边界为回路v1v2v3v1,deg(R2)=3. R0的边界为复杂回路v1v4v5v6v5v4v3v2v1, deg(R0)=8.,8.4.1 平面图的基本概念 定理8.9 在一个平面图G中, 所有面的次数之和都等于边数n的2倍, 即(r为面数),8.4 平面图,例: 图(2)与(3)都是(1)的平面嵌入, 它们都与(1)同构. 图(2)中deg(R0)=3; 图(3)中deg(R0)=4.,8.4 平面图,8.4.1 平面图的基本概念 极大平面图、极小非平面图 定义8.8 设G为一个简单平面图, 如果在G中任意不相邻的两个顶点之间再加一条边, 所得图为非平面图, 则称G为极大平面图. 若在非平面图G中任意删除一条边, 所得图为平面图, 则称G为极小非平面图.,8.4 平面图,K5, K3,3是极小非平面图, K5任意删除一条边后所得图是极大平面图,例,8.4 平面图,8.4.1 平面图的基本概念 极大平面图有以下性质: (1) 极大平面图是连通的; (2) 任何n(n≥3)阶极大平面图中, 每个面的次数均为3. (3) 任何n(n≥4)阶极大平面图G中, 均有(G)≥3.,8.4 平面图,8.4.2 欧拉公式 定理8.10 设G为任意的连通的平面图, 则有n-m+r＝2 成立. 其中, n为G中顶点数, m为边数, r为面数. 该定理中的公式为欧拉公式. 证明: 对边数m作归纳法. (1) m＝0时, G为孤立点, 此时n＝1, r＝1, 结论自然成立. (2) 设m＝k-1(k≥1)时结论成立, 要证明m＝k时结论成立.,。