《图论及其应用》课程教学课件（PPT讲稿）第一章 图的基本概念 1-2 图的基本概念

第一章图的基本概念 本次课主要内容 (一)、完全图、偶图与补图 (二)、顶点的度与图的度序列

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 1 第一章 图的基本概念 本次课主要内容 (二)、顶点的度与图的度序列 (一)、完全图、偶图与补图

(一)、完全图、偶图与补图 1、每两个不同的顶点之间都有一条边相连的简单图称为 完全图. 在同构意义下，个顶点的完全图只有一个，记为K. K K3 K 容易求出： m(Kn)=号n(n-)

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 2 (一)、完全图、偶图与补图 1、每两个不同的顶点之间都有一条边相连的简单图称为 完全图 . 在同构意义下，n个顶点的完全图只有一个，记为Kn K2 K3 K5 容易求出： 1 ( ) ( 1) 2 m K n n n = −

2、所谓具有二分类(X,)的偶图（或二部图）是指一个图， 它的点集可以分解为两个（非空）子集X和Y,使得每条边的一个 端点在X中，另一个端点在Y中. 完全偶图是指具有二分类(X,Y)的简单偶图，其中X 的每个顶点与Y的每个顶点相连，若X=m,Y后，则这样 的偶图记为Km,n 图1 图 图1与图2均是偶图，图2是K23

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 3 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门课程。六位教师的代号是 x1(i=1,2,3,4,5,6,六门课程代号是y(i1,2,3,4,5,6。已知， 教师x能够胜任课程y2和y3;教师x2能够胜任课程y和ys; 教师x3能够胜任课程y2;教师x4能够胜任课程y和y3; 教师x能够胜任课程y,和yo;教师x,能够胜任课程y和y6。 请画出老师和课程之间的状态图。 Y3

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 4 偶图是一种常见数学模型。 例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 x x5 x2 x3 4 x6 y1 y y3 y4 2 y5 y6

H色0 3、对于一个简单图G=(V,E),令集合 E,={wlu≠v,w,v∈V} 则称图H=(V,EE)为G的补图，记为H=G 例如，下面两个图互为补图

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 5 3、对于一个简单图G =（V, E），令集合 E uv u v u v V 1 =    , ,  则称图H =（V，E1 \E）为G的补图，记为 H G= H G= 例如，下面两个图互为补图。 G1 G2

HG 补图是相对于完全图定义的。 补图是图论中经常涉及的概念，在图论研究中有重 要的作用 如果图G与其补图同构，则称G为自补图。 定理：若阶图G是自补图GG),则有： n=0,1(mod4) 证明：n阶图G是自补图，则有：

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 6 H G= 定理：若n阶图G是自补图( ), G G 则有： n = 0,1(mod 4) 证明：n阶图G是自补图，则有： 补图是相对于完全图定义的。 补图是图论中经常涉及的概念，在图论研究中有重 要的作用 如果图G与其补图同构，则称G为自补图

m(G)+(G)=m(K,)=2n(n-1) 所以： m(G) n(n-1) 由于n是正整数，所以： n=0,1(mod 4) 自补图是很有意义的图类。它在对角型拉姆齐数 方面的研究、关于图的香农容量的研究、强完美图 方面的研究等都有重要作用

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 7 H G= 所以： 1 ( ) ( ) ( ) ( 1) 2 m G m G m K n n + = = − n 由于n是正整数，所以： n = 0,1(mod 4) 1 ( ) ( 1) 4 m G n n = − 自补图是很有意义的图类。它在对角型拉姆齐数 方面的研究、关于图的香农容量的研究、强完美图 方面的研究等都有重要作用

H色G 例2在10个顶点以下的单图中，哪些阶数的图可能 为自补图？画出8阶的4个自补图共10个)。 (二)、顶点的度与图的度序列 1、顶点的度及其性质 G的顶点v的度d()是指G中与v关联的边的数目， 每个环计算两次。 分别用δ(G)和△(G)表示图G的最小与最大度

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 8 H G= (二)、顶点的度与图的度序列 G的顶点v的度d (v)是指G中与v关联的边的数目， 每个环计算两次。 1、顶点的度及其性质 分别用δ(G)和Δ(G)表示图G的最小与最大度。 例2 在10个顶点以下的单图中，哪些阶数的图可能 为自补图？画出8阶的4个自补图(共10个)

奇数度的顶点称为奇点，偶数度的顶点称偶点。 设G=(Y,E为简单图，如果对所有v∈V,有 d(y=k,称图G为k-正则图 定理：图G=(Y,E)中所有顶点的度的和等于边数 m的2倍，即： d(v)-2m ∈V(G) 证明：由顶点度的定义知：图中每条边给图的总 度数贡献2度，所以，总度数等于边数2倍。 注：该定理称为图论第一定理，是由欧拉提出的。 欧拉一身发表论文886篇，著作90部。该定理还有 一个名字：“握手定理

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 9 H G= 奇数度的顶点称为奇点，偶数度的顶点称偶点。 设G = (V, E)为简单图，如果对所有 v V ，有 d (v) = k，称图G为k-正则图 定理： 图G= (V, E)中所有顶点的度的和等于边数 m的2倍，即： ( ) ( ) 2 v V G d v m   = 证明：由顶点度的定义知：图中每条边给图的总 度数贡献2度，所以，总度数等于边数2倍。 注：该定理称为图论第一定理，是由欧拉提出的。 欧拉一身发表论文886篇，著作90部。该定理还有 一个名字：“握手定理

H叁G 推论1在任何图中，奇点个数为偶数。 证明：设V,V分别是G中奇点集和偶点集.则由 握手定理有： ∑d()+∑d()=∑d() 是偶数，由于三四 是偶数，所以 a() 是 偶数，于是回是偶数。 推论2正则图的阶数和度数不同时为奇数。 证明：设G是k-正则图，若k为奇数，则由推论1知 正则图G的点数必为偶数 例4△与δ是简单图G的最大度与最小度，求证： 2m 10

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 10 H G= 推论1 在任何图中，奇点个数为偶数。 证明：设V1 ,V2分别是G中奇点集和偶点集.则由 握手定理有： ( ) ( ) ( ) 1 2 v V v V v V d v d v d v       + = 是偶数，由于 是偶数， 所以 是 偶数，于是 是偶数。 ( ) 2 v V d v   ( ) 1 v V d v   V1 推论2 正则图的阶数和度数不同时为奇数。 证明 ： 设G是k-正则图，若k为奇数，则由推论1知 正则图G的点数必为偶数 例4 Δ与δ是简单图G的最大度与最小度，求证： 2m n    