电子科越女学 r街y时Bectrele8 cad Tecaology af Chiaa /956 本次课内容 一、完全图、偶图与补图 二、顶点的度与图的度序列
本次课内容 一、完全图、偶图与补图 二、顶点的度与图的度序列
电子科越女学 r街y时Bectrele8 ciad Tecaology af Chins /956 一、完全图、偶图与补图 (一)、完全图 1、在图论中，完全图是一个简单图，且任意一个 顶点都与其它每个顶点有且只有一条边相连接。 2、n个顶点的完全图用K表示，常称为n阶完全图。 1阶完全图K, 2阶完全图K2 3阶完全图K3 5阶完全图K 注：有人认为符号来源于Kuratowski图论
一、完全图、偶图与补图 (一)、完全图 1、在图论中，完全图是一个简单图，且任意一个 顶点都与其它每个顶点有且只有一条边相连接。 2、n个顶点的完全图用Kn表示，常称为n阶完全图。 1阶完全图K1 2阶完全图K2 3阶完全图K3 5阶完全图K5 注：有人认为符号来源于Kuratowski图论
电↓科越女学 r街y时Bectrele8 cad Tecaology af Chiaa /956 很明显，K的边数为： m(K)=5n(n-1) 完全图在图论中是一个很基本的图，经常用到。 (二)、偶图（双图或者二部图） 1、一个实例 例1学校有6位教师将开设6门课程。六位教师的代号是 x(i=1,2,3,4,5,6),六门课程代号是y1(i=1,2,3,4,5,6)。已知， 教师x1能够胜任课程y2和y3;教师x2能够胜任课程y4和ys: 教师x3能够胜任课程y2;教师x4能够胜任课程y和y3; 教师x能够胜任课程y1和y6;教师x,能够胜任课程ys和y6 请画出老师和课程之间的状态图
很明显，Kn的边数为： 1 ( ) ( 1) 2 mK nn n 完全图在图论中是一个很基本的图，经常用到。 (二)、偶图(双图或者二部图) 1、一个实例 例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。 请画出老师和课程之间的状态图
电子科越女学 r街y时Bectrele8 ciad Tecaology af Chins /956 X X3 X4 X5 X6 y1 y3 y4 ys y6 y2 注：1、该例代表了两类事物之间联系问题； 2、这类图的特征：(1)顶点分成不相交的两部分； (2)任意一条边两个端点分属于两部分顶点
注：1、该例代表了两类事物之间联系问题； x 1 x x 5 x 2 x 3 4 x 6 y 1 y y 3 y 4 2 y 5 y 6 2、这类图的特征：(1)顶点分成不相交的两部分； (2)任意一条边两个端点分属于两部分顶点
电子科越女学 r街y时Bectrele8 ciad Tecaology af Chins /956 2、偶图的定义 定义1所谓具有二分类(X,Y)的偶图（或二部图）是指一 个图，它的点集可以分解为两个（非空）子集和Y,使得每条 边的一个端点在X中，另一个端点在Y中. X1 X2 X3 X1 X2 X3 y2 y3 y2 y3 偶图G1 非偶图G2 非偶图Gg 偶图G4 注：偶图中不能有环，不能有三角形！可以有重边！
2、偶图的定义 定义1 所谓具有二分类（X, Y）的偶图（或二部图）是指一 个图，它的点集可以分解为两个(非空)子集X和Y，使得每条 边的一个端点在X中，另一个端点在Y中. y4 x1 x2 x3 y3 y1 y2 偶图G1 非偶图G2 非偶图G3 注：偶图中不能有环,不能有三角形！可以有重边！ y4 x1 x2 x3 y3 y1 y2 偶图G4
电子科越女学 r街y时Bectrele8 cad Tecaology af Chiaa /956 3、完全偶图(Klm) 定义2完全偶图是指具有二分类（X,Y)的简单偶图，其中 X的每个顶点与Y的每个顶点相连，若X=n1,Y=2,则这 样的偶图记为Kl,2· y2 y2 图2 y3 图1 图1是偶图，但非完全偶图，图2是K2.3
定义2 完全偶图是指具有二分类（X, Y）的简单偶图，其中 X的每个顶点与Y的每个顶点相连，若|X|=n1，|Y|=n2，则这 样的偶图记为 K n1, n2 . 3、完全偶图(K n1, n2 ) 图1是偶图，但非完全偶图，图2是K2,3. 图1 y4 x4 y1 x1 x3 y2 x2 y3 图2 y1 x1 x2 y3 y2
电子科越女学 r街y时Bectrele8 ciad Tecaology af Chins /956 (三)、简单图的补图 在图论中，对于一个阶简单图G,基于完全图K,定义了 所谓的简单图G的补图。 1、简单图G的补图的定义 定义3对于一个简单图G=(V,E),令集合 B={awlu≠v,u,v∈r} 则称图H=(V,EE)为G的补图，记为H=G· 0 0 G的补图 G2 G2的补图 G3 G的补图
(三)、简单图的补图 在图论中，对于一个n阶简单图G，基于完全图Kn，定义了 所谓的简单图G的补图。 1、简单图G的补图的定义 定义3 对于一个简单图G =（V, E），令集合 则称图H =（V，E1\E）为G的补图，记为 . G1 G1的补图 G2 G2的补图 G3 G3的补图
电子科越女学 r街时Bectrele8 cad Tecaology afCh /956 几点说明：()只有简单图才能定义补图； (2)n阶简单图和其补图的顶点集合是相同的； 3)阶简单图任意一对顶点邻接的充分必要条件是这对顶点 在其补图中不邻接； (④)阶简单图的边数与其补图的边数之和等于K的边数； (⑤)补图是经常涉及的概念，在图结构分析中有重要的作用
几点说明: (1) 只有简单图才能定义补图； (2) n阶简单图和其补图的顶点集合是相同的； (3) n阶简单图任意一对顶点邻接的充分必要条件是这对顶点 在其补图中不邻接； (4) n阶简单图的边数与其补图的边数之和等于Kn的边数； (5)补图是经常涉及的概念，在图结构分析中有重要的作用
电子科越女学 r街y时Bectrele8 ciad Tecaology af Chins /956 2、自补图的定义与性质 定义4如果图G与其补图同构，则称G为自补图。 G G2 注：并不是任意一个简单图都是自补图，例如： G G的补图
定义4 如果图G与其补图同构，则称G为自补图。 2、自补图的定义与性质 G1 G2 注：并不是任意一个简单图都是自补图，例如： G G 的补图
电子科越女学 r街y时Bectrele8 ciad Tecaology af Chins /956 定理1：若n阶图G是自补图，则有： n≡0,1(m0d4) 证明：n阶图G是自补图，则有： m(G)+m(G=m(K.)=}n(n-) 所以：m(G)=子n(m-1 由于n是正整数，所以：n=0,1(mod4)
定理1：若n阶图G是自补图，则有： . 证明：n阶图G是自补图，则有： 所以： 由于n是正整数，所以：