离散数学教案 编号:C1801 课时安排: 2学时教学课型:理论课√ 实验课口习题课口实践课口其它口 顺日《教学音、节或主原), Ch18支配集、 覆盖集、独立集与匹面 §18.1支配集、点覆盖集与点独立集 §18.2边覆盖集与匹配 §18.3二部图中的匹配 教学目的要求(分掌握、熟悉、 了解三个层次) 1.了解图的支配集、点覆盖集、点独立集、边覆盖集和匹配的概念: 2。基本掌握二部图中的匹配(Hll定理),及与其相关的简单应用问题。 教学重点、难点: 1)重点:匹配的概念,二部图中的匹配(H1定理) 2)难点:二部图中的匹配(Hal定理) 教学方法 利用黑板,CAL课件等教学 教学用具: 黑板,CA课件及其辅助设备 #难点 1.定义支配集 2.定义独立集 .定义点覆盖集 4 定理S为图G的独立集当且仅当S为G的覆盖。 二、匹配(约25分钟) 1.定义设G=<VE为无向图,E*cE。称E*为G的一个匹配,如果E*中任何两条边都没有公共端 点。如果E*中再增加一条边就不是匹配了,则称E*为极大匹配。边数最多的匹配称为最大匹配。最大 匹配中的元素(边)数叫匹配数,记为月(G,或月。 2。设∈G,M促G的一个匹配若v与M中的某一条边关联,则称v是M的饱和点,若G中 每个顶点都是M的饱和点,则称M是G的完美匹配。 [例]图8.2中各图的粗线表示匹配中的边(简称匹配边)。(b)中匹配是最大的。 1801
1801 离 散 数 学 教 案 编号:C1801 课时安排: 2 学时 教学课型:理论课√ 实验课□ 习题课□ 实践课□ 其它□ 题目(教学章、节或主题): Ch18 支配集、覆盖集、独立集与匹配 §18.1 支配集、点覆盖集与点独立集 §18.2 边覆盖集与匹配 §18.3 二部图中的匹配 教学目的要求(分掌握、熟悉、了解三个层次): 1. 了解图的支配集、点覆盖集、点独立集、边覆盖集和匹配的概念; 2. 基本掌握二部图中的匹配(Hall 定理),及与其相关的简单应用问题。 教学重点、难点: 1) 重点:匹配的概念,二部图中的匹配(Hall 定理) 2) 难点:二部图中的匹配(Hall 定理) 教学方法: 利用黑板,CAI 课件等教学. 教学用具: 黑板,CAI 课件及其辅助设备. 教学内容(注明:* 重点 # 难点 ?疑点): *一、支配集、点覆盖集与点独立集(约 25 分钟) 1.定义 支配集 2.定义 独立集 3.定义 点覆盖集 4.定理 S 为图 G 的独立集当且仅当 V\S 为 G 的覆盖。 二、匹配(约 25 分钟) 1.定义 设 G = 为无向图,E*E。称 E*为 G 的一个匹配,如果 E*中任何两条边都没有公共端 点。如果 E*中再增加一条边就不是匹配了,则称 E*为极大匹配。边数最多的匹配称为最大匹配。最大 匹配中的元素(边)数叫匹配数,记为 1 1 (G),或 。 2. 设 vV(G),M是G的一个匹配, 若 v 与 M 中的某一条边关联,则称 v 是 M 的饱和点,若 G 中 每个顶点都是 M 的饱和点,则称 M 是 G 的完美匹配。 [例] 图 8.2 中各图的粗线表示匹配中的边(简称匹配边)。(b)中匹配是最大的
X料 (a) (b) 注意:最大匹配总是存在但未必唯一。此外,完美匹配必定是最大的,但反之则不然。 为讨论最大匹配的求法及完全匹配的存在条件,需要下列术语。 玉.定义设G=称为二部图,如果有非空集合X,Y使XUY=V,XnY=O,且对每 eeE,e=(y),xeX,yeY。此时常用表示二部图G。若对X中任一x及Y中任一y恰有 边(xy)eE,则称G为完全二部图。当X=m,Y=n时,完全二部图G记为Km,n [例]图81中(a,(b)为二部图,(c)为完全二部图K3,3,(d,(e)不是二部图。 二部图的下列特征性是重要的。 2.定理至少有两个项点的无向图G为二部图的充分必要条件是G不存在奇数长度的回路。 3.定理联单定理设G=是一个二部图.以≤,G中存在1到V2的完备匹配 的充要条件是V1中任意k(k=1,2, 川)个顶点至少邻接2的k个顶点。 4.定理设G=是一个二部图,如果 (1)V1中的每个顶点至少关联(>0)条边: (2)V2中的每个顶项点至多关联〔>0)条边, 则G中存在V1到V2的完备匹配。 四、课堂小结(约5分钟)
1802 (a) (b) 注意:最大匹配总是存在但未必唯一。此外,完美匹配必定是最大的,但反之则不然。 为讨论最大匹配的求法及完全匹配的存在条件,需要下列术语。 3.定义 设 G = 是一个二部图,M 为 G 的一个最大匹配,若 min{ , } M = V1 V2 ,则称 M 为 G 的一个完备匹配。此时若 V1 V2 ,则称 V1 到 V2 的完备匹配,如果这时 V1 = V2 ,M 为 G 的 完美匹配, 三、二部图的概念(约 35 分钟) 1.定义 无向图 G = 称为二部图,如果有非空集合 X,Y 使 X∪Y = V,X∩Y = ,且对每一 eE,e = (x, y),xX,yY。此时常用表示二部图 G。若对 X 中任一 x 及 Y 中任一 y 恰有 一边(x, y)E,, 则称 G 为完全二部图。当X = m,Y = n 时,完全二部图 G 记为 Km,n。 [例] 图 8.1 中(a),(b)为二部图,(c)为完全二部图 K3,3,(d), (e)不是二部图。 二部图的下列特征性是重要的。 2.定理 至少有两个顶点的无向图 G 为二部图的充分必要条件是 G 不存在奇数长度的回路。 3.定理联单(hall 定理) 设 G = 是一个二部图, V1 V2 ,G 中存在 V1 到 V2 的完备匹配 的充要条件是 V1 中任意 k(k=1,2,., V1 )个顶点至少邻接 V2 的 k 个顶点。 4.定理 设 G = 是一个二部图,如果 (1)V1 中的每个顶点至少关联 t(t>0)条边; (2)V2 中的每个顶点至多关联 t(t>0)条边, 则 G 中存在 V1 到 V2 的完备匹配。 四、课堂小结(约 5 分钟)