第8章一些特殊的图

1第8章一些特殊的图8.1二部图一、二部图的定义若能将无向图G=V,E的顶点集V划分成两个子集V1和V2(V1∩V2=),使得G中任何一条边的两个端点一个属于V1,另一个属于V2,则称G为二部图(也称为偶图).V1,V2称为互补顶点子集,此时可将G记成G=V1,V2,E,若V1=n,V2=m,则记完全二部图G为Kn,m.在下图中,(1)所示为K2,3,(2)所示为K3,3.K3,3是重要的完全二部图,它与K5一起在平面图中起着重要作用.判断二部图的定理一个无向图G=V,E是二部图当且仅当G中无奇数长度的回路.二、匹配设G=V,E为无向图,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中完美匹配.完备匹配：设G=V1,V2,E为一个二部图,M为G中一个最大匹配,若M=min{V1,V2},则称M为G中的一个完备匹配.此时若V1≤V2,则称M为V1到V2的一个完备匹配.如果V1=V2,这时M为G中的完美匹配.如何判断是否存在完备匹配：1、Hall定理：设二部图G=V1,V2,E,V1≤V2,G中存在从V1到V2的完备匹配当且仅当V1中任意k个顶点(k=1,2,…V1)至少邻接V2中的k个顶点.2、设二部图G=V1,V2,E,如果(1)V1中每个顶点至少关联t(t＞0)条边;(2)V2中每个顶点至多关联t条边,则G中存在V1到V2的完备匹配.Hall定理中的条件称为“相异性条件”,定理8.3中的条件称为“t条件”,满足t条件的二部图,一定满足相异性条件.事实上,由条件(1)可知,V1中k个顶点至少关联kt条边.由条件(2)可知,这kt条边至少关联V2中的k个顶点,于是若G满足t条件,则G一定满足相异性条件,但反之不真。例8.1某中学有3个课外小组:物理组、化学组、生物组.今有张、王、李、赵、陈5名同学.若已知:(1)张、王为物理组成员,张、李、赵为化学组成员,李、赵、陈为生物组成员;(2)张为物理组成员,王、李、赵为化学组成员,王、李、赵、陈为生物组成员;2(3)张为物理组和化学组成员,王、李、赵、陈为生物组成员.问在以上3种情况下能否各选出3名不兼职的组长？38.2欧拉图一、定义哥尼斯堡七桥问题：经过图中每条边一次且仅一次并且行遍图中每个顶点的通路(回路),称为欧拉通路或欧拉迹(欧拉回路或欧拉闭迹).存在欧拉回路的图,称为欧拉图.定理无向图G具有欧拉通路,当且仅当G是连通图且有零个或两个奇度顶点.若无奇度顶点,则通路为回路;若有两个奇度顶点,则它们是每条欧拉通路的端点.推论无向图G为欧拉图(具有欧拉回路)当且仅当G是连通的,且G中无奇度顶点.例1：a)是欧拉图；b)不是欧拉图，但存在欧拉通路；c)即不是欧拉图，也不存在欧拉通路。例2：蚂蚁比赛问题甲、乙两只蚂蚁分别位于如下图中的结点a，b处，并设图中的边长度是相等的。甲、乙进行比赛：从它们所在的结点出发，走过图中的所有边最后到达结点c处。如果它们的速度相同，问谁先到达目的地？4例3：一笔画问题二、有向图的Euler图给定G是一个无孤立结点的有向图，若存在一条单向通路(回路)，经过图中每边一次且仅仅一次，则称此单向通路(回路)为该图的一条单向欧拉通路(回路)。具有单向欧拉回路的图称为欧拉图。定理一个有向图D具有欧拉通路,当且仅当D是连通的,且除了两个顶点外,其余顶点的入度均等于出度.这两个特殊的顶点中,一个顶点的入度比出度大⒈另一个顶点的入度比出度小1.推论一个有向图D是欧拉图(具有欧拉回路),当且仅当D是连通的,且所有顶点的入度等于出度.只具欧拉通路,无欧拉回路的图不是欧拉图.例1：(a)存在一条欧拉通路：v3v1v2v3v4v1；(b)中存在欧拉回路v1v2v3v4v1v3v1，因而(b)是欧拉图；(c)中有欧拉回路v1v2v3v4v5v6v7v8v2v4v6v8v1因而(c)是欧拉图。58.3哈密尔顿图一、定义经过图中每个顶点一次且仅一次的通路(回路)称为哈密尔顿通路(回路).存在哈密尔顿回路的图称为哈密尔顿图.哈密尔顿图的判定定理(必要条件1)设无向图G=V,E是哈密尔顿图,V1是V的任意的非空子集,p(G-V1)≤V1.其中,p(G-V1)为从G中删除V1(删除V1中各顶点及关联的边)后所得图的连通分支数.证明:设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.定理(充分条件1)设G＝V，E是简单无向图。如果对任意两个不相邻的结点u，vV，均有：deg(u)+deg(v)|V|-1，则G中存在哈密尔顿通路；如果对任意两个不相邻的结点u，vV，均有：deg(u)+deg(v)|V|，则G中存在哈密尔顿回路，即G是哈密尔顿图。推论n阶简单无向图G中，n2,任意顶点的度数大于等于n/2，则G有Hamilton回路。充分条件2：完全图Kn，n2，是Hamilton图。归纳可证。定理在n(n≥2)阶有向图D=V,E中,如果所有有向边均用无向边代替,所得无向图中含生成子图Kn,则有向图D中存在哈密尔顿通路.推论n(n≥3)阶有向完全图为哈密尔顿图.例1：考虑在七天内安排七门课程的考试，使得同一位教师所任的两门课程考试不排在接连的两天中，试证明如果没有教师担任多于四门课程，则符合上述要求的考试安排总是可能的，证明：设G为具有七个结点的图，每个结点对应于一门课程考试，如果这两个结点对应的课程考试是由不同教师担任的，那么这两个结点之间有一条边，因为每个教师所任课程数不超过4，故每个结点的度数至少是3，任两个结点的度数之和至少是6，故G总是包含一条汉密尔顿路，它对应于一个七门考试课目的一个适当的安排。