电子科越女学 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是正整数，所以：