福州大学：《离散数学》课程教学资源（教案讲义）第十八章 支配集、覆盖集、独立集与匹配

离散数学教案 编号：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． 设 vV(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 = ，且对每一 eE，e = (x, y)，xX，yY。此时常用表示二部图 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 分钟）