电子科技大学图论总复习解释.ppt

(1) 画出G的补图 (2) 求出关于补图的 (3) 写出关于补图的伴随多项式 (4) 将 代入伴随多项式中得到Pk(G)。 11、根树问题 定理32 在完全m元树T中，若树叶数为t , 分支点数为i , 则： (三)、图论应用 1、 偶图匹配问题 例1 有7名研究生 A, B, C, D, E, F, G毕业寻找工作。就业处提供的公开职位是：会计师(a) ,咨询师(b),编辑(c ),程序员(d), 记者(e), 秘书(f)和教师(g)。每名学生申请的职位如下： A : b, c ; B : a, b, d, f, g ; C : b, e ; D : b, c, e ; E : a, c, d, f ; F : c, e ; G : d, e, f, g ; 问：学生能找到理想工作吗？ 重点掌握如下两方面应用 问题转化为是否有饱和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中顶点连线当且仅当学生申请了该工作。于是，得到反映学生和职位之间的状态图： * * 图论及其应用 复习课件 数学科学学院 本次课主要内容 (二)、重要结论 期末复习 (一)、重点概念 (三)、应用 (一)、重点概念 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中求一棵总权值最小的生成树。该生成树称为最小生成树或最小代价树。