图论及其应用ppt2

0.810.60.40.20xt00.511.5210.500.51n1Email:[e-mail]图论及其应用任课教师：杨春数学科学学院0.810.60.40.20xt00.511.5210.500.51n2第一章图的基本概念本次课主要内容(二)、顶点的度与图的度序列(一)、完全图、偶图与补图0.810.60.40.20xt00.511.5210.500.51n3(一)、完全图、偶图与补图1、每两个不同的顶点之间都有一条边相连的简单图称为完全图.在同构意义下，n个顶点的完全图只有一个，记为KnK2K3K5容易求出：1()(1)2nmKnn0.810.60.40.20xt00.511.5210.500.51n42、所谓具有二分类（X,Y）的偶图（或二部图）是指一个图，它的点集可以分解为两个(非空)子集X和Y，使得每条边的一个端点在X中，另一个端点在Y中.完全偶图是指具有二分类（X,Y）的简单偶图，其中X的每个顶点与Y的每个顶点相连，若|X|=m，|Y|=n，则这样的偶图记为Km,n图1图2图1与图2均是偶图，图2是K2,30.810.60.40.20xt00.511.5210.500.51n5偶图是一种常见数学模型。例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。请画出老师和课程之间的状态图。x1x5x4x3x2x6y4y3y1y2y5y60.810.60.40.20xt00.511.5210.500.51n63、对于一个简单图G=（V,E），令集合1,,EuvuvuvV则称图H=（V，E1\E）为G的补图，记为HGHG例如，下面两个图互为补图。G1G20.810.60.40.20xt00.511.5210.500.51n7HG定理：若n阶图G是自补图(),则有：GG0,1(mod4)n证明：n阶图G是自补图，则有：补图是相对于完全图定义的。补图是图论中经常涉及的概念，在图论研究中有重要的作用如果图G与其补图同构，则称G为自补图。0.810.60.40.20xt00.511.5210.500.51n8HG所以：1()()()(1)2nmGmGmKnn0,1(mod4)n由于n是正整数，所以：1()(1)4mGnn自补图是很有意义的图类。它在对角型拉姆齐数方面的研究、关于图的香农容量的研究、强完美图方面的研究等都有重要作用。0.810.60.40.20xt00.511.5210.500.51n9HG(二)、顶点的度与图的度序列G的顶点v的度d(v)是指G中与v关联的边的数目，每个环计算两次。1、顶点的度及其性质分别用δ(G)和Δ(G)表示图G的最小与最大度。例2在10个顶点以下的单图中，哪些阶数的图可能为自补图？画出8阶的4个自补图(共10个)。0.810.60.40.20xt00.511.5210.500.51n10HG奇数度的顶点称为奇点，偶数度的顶点称偶点。设G=(V,E)为简单图，如果对所有，有vVd(v)=k，称图G为k-正则图定理：图G=(V,E)中所有顶点的度的和等于边数m的2倍，即：()()2vVGdvm证明：由顶点度的定义知：图中每条边给图的总度数贡献2度，所以，总度数等于边数2倍。注：该定理称为图论第一定理，是由欧拉提出的。欧拉一身发表论文886篇，著作90部。该定理还有一个名字：“握手定理”。0.810.60.40.20xt00.511.5210.500.51n11HG推论1在任何图中，奇点个数为偶数。证明：设V1,V2分别是G中奇点集和偶点集.则由握手定理有：12vVvVvVdvdvdv是偶数，由于是偶数，所以是偶数，于是是偶数。2vVdv1vVdv1V推论2正则图的阶数和度数不同时为奇数。证明：设G是k-正则图，若k为奇数，则由推论1知正则图G的点数必为偶数例4Δ与δ是简单图G的最大度与最小度，求证：2mn0.810.60.40.20xt00.511.5210.500.51n12HG()()2vVGndvmn证明：由握手定理有：所以有：2mn2、图的度序列及其性质一个图G的各个点的度d1,d2,…,dn构成的非负整数组(d1,d2,…,dn)称为G的度序列。任意一个图G对应唯一一个度序列，图的度序列是刻画图的特征的重要“拓扑不变量”。0.810.60.40.20xt00.511.5210.500.51n13HG图G的“拓扑不变量”是指与图G有关的一个数或数组(向量)。它对于与图G同构的所有图来说，不会发生改变。一个图G可以对应很多拓扑不变量。如果某组不变量可完全决定一个图，称它为不变量的完全集。定理：非负整数组(d1,d2,….,dn)是图的度序列的充分必要条件是：为偶数。1niid证明：必要性由握手定理立即得到。如果为偶数，则数组中为奇数的数字个数1niid必为偶数。按照如下方式作图G:若di为偶数，则在与之对应的点作di/2个环；对于剩下的偶数个奇数，0.810.60.40.20xt00.511.5210.500.51n14HG两两配对后分别在每配对点间先连一条边，然后在每个顶点画dj-1/2个环。该图的度序列就是已知数组。一个非负数组如果是某简单图的度序列，我们称它为可图序列，简称图序列。关于图序列，主要研究3个问题：(1)存在问题：什么样的整数组是图序列？(2)计数问题：一个图序列对应多少不同构的图？(3)构造问题：如何画出图序列对应的所有不同构图？研究现状:(1)彻底解决了，(2)解决得不好，(3)没有解决。0.810.60.40.20xt00.511.5210.500.51n15HG定理：非负整数组12121(,,,),,2nnniidddddddm是图序列的充分必要条件是：1112312(1,1,,1,,,)ddnddddd是图序列。证明：设G是Π对应的简单图，d(vi)=di情形1：点v1与点v2,v3,…,vd1+1邻接，则G-v1的度序列正好为Π10.810.60.40.20xt00.511.5210.500.51n16HG情形2：点v1与点vd1+2，….vn的某些顶点邻接。在这种情况下，作如下假设：设v1与vj0邻接，但当kj0时，v1与vk不邻接；又设v1与vi0不邻接，但当ki0时，v1与点vk邻接。v1v2v3vi0-1vj0vi0vn可以证明：在图中，必然存在点vm，使得vm与vi0邻接，但是它与vj0不邻接！0.810.60.40.20xt00.511.5210.500.51n17HG若不然，对任意的与vi0邻接的点，若都与vj0邻接，那么，有dj0≥di0+1,这和条件矛盾！现在，在图中去掉边v1vj0和vi0vm,加上边vj0vm和v1vi0,显然新图与原图度序列相同，但j0减小了，i0增大了！v1v2v3vi0-1vj0vi0vnvmv1v2v3vi0-1vj0vi0vnvm0.810.60.40.20xt00.511.5210.500.51n18HG如此进行下去，最后可以变情形2为情形1。是显然的。例5是否为图序列？如果是，作出对应的一个简单图。(6,5,4,3,2,2,2)解：1(4,3,2,1,1,1)2(2,1,0,0,1)由于是图序列，所以原序列是图序列。2(2,1,0,0,1)0.810.60.40.20xt00.511.5210.500.51n19HG定理:(厄多斯1960)非负整数组12121(,,,),,2nnniidddddddm是图序列的充分必要条件是：11(1)min,,11rniiiirdrrrdrn该定理证明很难！上世纪60年代以来，人们又研究所谓的唯一图序列问题。例5就是一个唯一图序列！0.810.60.40.20xt00.511.5210.500.51n20HG定理:一个满足d2=dn-1的图序列12(,,,)nddd1(1),,1,1,2nndddnn是唯一图序列的充分必要条件是下列条件之一满足：1(2),2,5nddn12(3),1nddd121(4),2,1,2nddddnn11(5),2nnnddd11(6),31nnnddd12(7),13,6nndddn0.810.60.40.20xt00.511.5210.500.51n21HG3、图的频序列及其性质定理：一个简单图G的n个点的度不能互不相同证明：因为图G为简单图，所以：△(G)≤n-1。情形1：若G没有孤立点，则1()1,()dvnvVG由鸽笼原理：必有两顶点度数相同；情形2：若G只有一个孤立点，设G1表示G去掉孤立点后的部分，则：11()2,()dvnvVG由鸽笼原理：在G1里必有两顶点度数相同；情形3：若G只有两个以上的孤立点，则定理显然成立。0.810.60.40.20xt00.511.5210.500.51n22HG定义：设n阶图G的各点的度取s个不同的非负整数d1,d2,…,ds。又设度为di的点有bi个(i=1,2,…,s)，则1siibn故非整数组(b1,b2,…,bs)是n的一个划分，称为G的频序列。定理：一个n阶图G和它的补图有相同的频序列。0.810.60.40.20xt00.511.5210.500.51n23作业P29—P308,9,10,110.810.60.40.20xt00.511.5210.500.51n24ThankYou!