一些特殊的图.ppt

离散数学第8章一些特殊的图**二部图欧拉图哈密尔顿图平面图第8章一些特殊的图**:若能将无向图G=(V,E)的顶点集V划分成两个子集V1和V2(V1∩V2=),使得G中任何一条边的两个端点一个属于V1,另一个属于V2,则称G为二部图。若V1中任一顶点与V2中任一顶点均有且仅有一条边相关联,则称此二部图为完全二部图。**定理:一个无向图是二部图当且仅当G中无奇数长度的回路。**匹配二部图G=(V,E)中,若ME,且M中任意两条边都没有公共顶点,则称M为G中的匹配。极大匹配若在M中再加入任何1条边就不是匹配了,则称为极大匹配。最大匹配边数最多的极大匹配称为最大匹配。最大匹配中边的个数称为匹配数。基本术语**饱和点与非饱和点属于匹配M的边的所有顶点称为关于M饱和点,否则称为M非饱和点。完美匹配若G中的每个顶点都是M的饱和点,称M是G的完美匹配。完备匹配设V1和V2是二部图G的互补顶点集,若G中的匹配M使得|M|=min{|V1|,|V2|},称该匹配是完备匹配。**Hall定理相异性定理二部图G=(V1,V2,E),|V1|≤|V2|,存在从V1到V2的完备匹配当且仅当V1中任意k(=1,2,…|V1|)个顶点至少连接V2中的k个顶点。t条件定理**例:某中学有3个课外小组:物理组、化学组、生物组。今有张、王、李、赵、陈5名同学,若已知:(1)张、王为物理组成员,张、李、赵为化学组成员,李、赵、陈为生物组成员;(2)张为物理组成员,王、李、赵为化学组成员,王、李、赵、陈为生物组成员;(3)张为物理组和化学组成员,王、李、赵、陈为生物组成员。问在以上3种情况下能否各选出3名不兼职的组长?**解:设v1,v2,v3,v4,v5分别表示张、王、李、赵、陈。u1,u2,u3分别表示物理组、化学组、生物组。在3种情况下作二部图分别记为G1,G2,G3,如图所示。**练****在下图所示的各图中,是二部图的为 A 。在二部图中存在完美匹配的是 B ,它们的匹配数是 C 。