图论及其应用(29)复习.ppt

* 问题转化为是否有饱和X每个顶点的一个匹配。 F E D C B A G a b c d e f g 解：如果令X=｛A, B, C, D, E, F, G｝,Y=｛a, b, c, d, e, f , g｝,X中顶点与Y中顶点连线当且仅当学生申请了该工作。于是，得到反映学生和职位之间的状态图： * 当S取X中四元点集时，若取S=｛A,C,D,F｝,则有3=|N(S)||S|=4 所以，不存在饱和X每个顶点的匹配。 2、 着色问题 1)、 边着色问题 例2 (排课表问题) 在一个学校中，有7个教师12个班级。在每周5天教学日条件下，教课的要求由如下矩阵给出： * x1 x2 x3 x4 x6 x5 x7 y2 y1 y8 y7 y6 y5 y4 y3 y10 y9 y11 y12 其中，pij表示xi必须教yj班的节数。求： (1) 一天分成几节课，才能满足所提出的要求？ (2) 若安排出每天8节课的时间表，需要多少间教室？ * * 本次课主要内容 (二)、重要结论 期末复习 (一)、重点概念 (三)、应用 * (一)、重点概念 1、图、简单图、图的同构与自同构、度序列与图序列、补图与自补图、两个图的联图、两个图的积图、偶图； (1) 图：一个图是一个序偶V,E，记为G=(V,E),其中： 1) V是一个有限的非空集合，称为顶点集合,其元素称为顶点或点。用|V|表示顶点数； 2) E是由V中的点组成的无序对构成的集合，称为边集，其元素称为边，且同一点对在E中可以重复出现多次。用|E|表示边数。 (2) 简单图：无环无重边的图称为简单图。 * (3) 图的度序列： 一个图G的各个点的度d1, d2,…, dn构成的非负整数组(d1, d2,…, dn)称为G的度序列 。 注：度序列的判定问题是重点。 (4) 图的图序列： 一个非负数组如果是某简单图的度序列，我们称它为可图序列，简 称图序列。 注：度序列的判定问题是重点。 (5) 图的同构： * 设有两个图G1=(V1,E1)和G2=(V2,E2),若在其顶点集合间存在双射，使得边 之间存在如下关系：设u1?u2v1?v2, u1,v1 V1, u2,v2 V2; u1v1 E1,当 且仅当u2v2 E2,且u1v1与u2v2的重数相同。称G1与G2同构，记为： 例1 指出4个顶点的非同构的所有简单图。 分析：四个顶点的简单图最少边数为0，最多边数为6，所以 可按边数进行枚举。 * (6) 补图与自补图 1) 对于一个简单图G =（V, E），令集合 则图H =（V，E1\E）称为G的补图，记为 2) 对于一个简单图G =（V, E），若 ，称G为自补图。 注：要求掌握自补图的性质。 * (7) 联图 设G1,G2是两个不相交的图，作G1+G2，并且将G1中每个顶点和G2中的每个顶点连接，这样得到的新图称为G1与G2的联图。记为 ： (8) 积图 设 是两个图。对点集 的任意两个点u=(u1,u2)与v=(v1,v2),当(u1=v1和u2adjv2)或(u2=v2和u1adjv1)时，把u与v相连。如此得到的新图称为G1与G2的积图。记为 * (9) 偶图 所谓具有二分类（X, Y）的偶图（或二部图）是指一个图，它的点集可以分解为两个(非空)子集X和Y，使得每条边的一个端点在中，另一个端点在Y中. 注: 掌握偶图的判定。 2、树、森林，生成树，最小生成树、根树、完全m元树。 (1) 树 不含圈的图称为无圈图，树是连通的无圈图。 (2) 森林 称无圈图G为森林。 * (3) 生成树 图G的一个生成子图T如果是树，称它为G的一棵生成树；若T为森林，称它为G的一个生成森林。 生成树的边称为树枝，G中非生成树的边称为弦。 (4) 最小生成树 在连通边赋权图G中求一棵总权值最小的生成树。该生成树称为最小生成树或最小代价树。 注：要求熟练掌握最小生成树的求法。 (5) 根树 一棵非平凡的有向树T，如果恰有一个顶点的入度为0，而其余所有顶点的入度为1，这样的的有向树称为根树。其中入度为0的点称为树根，出度为0的点称为树叶，入度为1，出度大于1的点称为内点。又将内点和树根统称为分支点。 * (6) 完全m元树