杨春 图论ppt2.pptVIP

* * Email: yc517922@126.com 图论及其应用 任课教师：杨春 数学科学学院 第一章 图的基本概念 本次课主要内容 (二)、顶点的度与图的度序列 (一)、完全图、偶图与补图 (一)、完全图、偶图与补图 1、每两个不同的顶点之间都有一条边相连的简单图称为 完全图 . 在同构意义下，n个顶点的完全图只有一个，记为 Kn K2 K3 K5 容易求出： 2、所谓具有二分类（X, Y）的偶图（或二部图）是指一个图， 它的点集可以分解为两个(非空)子集X和Y，使得每条边的一个 端点在X中，另一个端点在Y中. 完全偶图是指具有二分类（X, Y）的简单偶图，其中X的每个顶点与Y的每个顶点相连，若|X|=m，|Y|=n，则这样的偶图记为 K m, n 图1 图2 图1与图2均是偶图，图2是K2,3 偶图是一种常见数学模型。 例1 学校有6位教师将开设6门课程。六位教师的代号是 xi（i=1,2,3,4,5,6)，六门课程代号是yi （i=1,2,3,4,5,6)。已知，教师x1能够胜任课程y2和y3；教师x2能够胜任课程y4和y5；教师x3能够胜任课程y2；教师x4能够胜任课程y6和y3； 教师x5能够胜任课程y1和y6；教师x6能够胜任课程y5和y6。请画出老师和课程之间的状态图。 x1 x5 x4 x3 x2 x6 y4 y3 y1 y2 y5 y6 3、对于一个简单图G =（V, E），令集合 则称图H =（V，E1\E）为G的补图，记为 例如，下面两个图互为补图。 G1 G2 定理：若n阶图G是自补图( ),则有： 证明：n阶图G是自补图，则有： 补图是相对于完全图定义的。 补图是图论中经常涉及的概念，在图论研究中有重要的作用 如果图G与其补图同构，则称G为自补图。 所以： 由于n是正整数，所以： 自补图是很有意义的图类。它在对角型拉姆齐数方面的研究、关于图的香农容量的研究、强完美图方面的研究等都有重要作用。 (二)、顶点的度与图的度序列 G的顶点v的度d (v)是指G中与v关联的边的数目， 每个环计算两次。 1、顶点的度及其性质 分别用δ(G)和Δ(G)表示图G的最小与最大度。 例2 在10个顶点以下的单图中，哪些阶数的图可能为自补图？画出8阶的4个自补图(共10个)。 奇数度的顶点称为奇点，偶数度的顶点称偶点。 设G = (V, E)为简单图，如果对所有 ，有 d (v) = k，称图G为k-正则图 定理： 图G= (V, E)中所有顶点的度的和等于边数 m的2倍，即： 证明：由顶点度的定义知：图中每条边给图的总 度数贡献2度，所以，总度数等于边数2倍。 注：该定理称为图论第一定理，是由欧拉提出的。 欧拉一身发表论文886篇，著作90部。该定理还有 一个名字：“握手定理”。 推论1 在任何图中，奇点个数为偶数。 证明：设V1,V2分别是G中奇点集和偶点集.则由 握手定理有： 是偶数，由于 是偶数， 所以 是 偶数，于是 是偶数。 推论2 正则图的阶数和度数不同时为奇数 。 证明 ： 设G是k-正则图，若k为奇数，则由推论1知 正则图G的点数必为偶数 例4 Δ与δ是简单图G的最大度与最小度，求证： 证明：由握手定理有： 所以有： 2、图的度序列及其性质 一个图G的各个点的度d1, d2,…, dn构成的非负整数组 (d1, d2,…, dn)称为G的度序列 。 任意一个图G对应唯一一个度序列，图的度序列是 刻画图的特征的重要“拓扑不变量”。 图G 的“拓扑不变量”是指与图G有关的一个数 或数组(向量)。它对于与图G同构的所有图来说，不会发生改变。 一个图G可以对应很多拓扑不变量。如果某组不变量可完全决定一个图，称它为不变量的完全集。 定理：非负整数组(d1,d2,…., d n)是图的度序列的 充分必要条件是： 为偶数。 证明：必要性由握手定理立即得到。 如果 为偶数，则数组中为奇数的数字个数 必为偶数。按照如下方式作图G:若di为偶数，则在 与之对应的点作di/2个环；对于剩下的偶数个奇数， 两两配对后分别在每配对点间先连一条边，然后 在每个顶点画dj-1/2个环。该图的度序列就是已知 数组。 一个非负数组如果是某简单图的度序列，我们称 它为可图序列，简称图序列。 关于图序列，主要研究3个问题： (1) 存在问题：什么样的整数组是图序列？ (2) 计数问题：一个图序列对应多少不同构的图？ (3) 构造问题：如何画出图序列对应的所有不