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

第一章图的基本概念 本次课主要内容 极图理论简介 (一)、1部图的概念与特征 (二)、托兰定理 (三)、托兰定理的应用 (四)、交图与团图简介

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 第一章 图的基本概念 本次课主要内容 极图理论简介 (一)、l 部图的概念与特征 (二)、托兰定理 (三)、托兰定理的应用 (四)、交图与团图简介

极图属于极值图论讨论的范畴，主要研究满足某 个条件下的最大图或最小图问题。 P.Erd6s是该研究领域的杰出人物。他是数学界 的传奇人物，国际图论大师，获过Wolf数学奖。他 是20世纪最伟大的数学家之一，也是人类历史上发 表数学论文最多的数学家(1000多篇)，第二名是欧拉 (837篇)。他于1996年9月20日因心脏病去世，享年 83岁，他的逝世当时惊动了整个数学界。 1978年，数学家Bollobas2写了一本书《极值图论》 (Extremal Graph),是关于极值图论问题的经典著作。 上世纪70年代末，极值图论已经形成了相对完整的 理论体系，但还有很多引人入胜的公开性问题没有解决， 所以，直到现在，它仍然是重要研究方向。但是，该方 向是比较困难的数学研究方向之一

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 1978年，数学家Bollobas写了一本书《极值图论》 (Extremal Graph）,是关于极值图论问题的经典著作。 P. Erdồs是该研究领域的杰出人物。他是数学界 的传奇人物，国际图论大师，获过Wolf数学奖。他 是20世纪最伟大的数学家之一，也是人类历史上发 表数学论文最多的数学家(1000多篇),第二名是欧拉 (837篇)。他于1996年9月20日因心脏病去世，享年 83岁，他的逝世当时惊动了整个数学界。 极图属于极值图论讨论的范畴，主要研究满足某 个条件下的最大图或最小图问题。 上世纪70年代末，极值图论已经形成了相对完整的 理论体系，但还有很多引人入胜的公开性问题没有解决， 所以，直到现在，它仍然是重要研究方向。但是，该方 向是比较困难的数学研究方向之一

本次课，主要介绍极值图论中的一个经典结论： 托兰定理。 (一)、1部图的概念与特征 定义1若简单图G的点集V有一个划分： ,y,V,=Φ，i≠ i=l 且所有的V非空，V内的点均不邻接，称G是一个l 部图。 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 3 本次课，主要介绍极值图论中的一个经典结论： 托兰定理。 (一)、l 部图的概念与特征 定义1 若简单图G的点集V有一个划分： V = Vi i=1 l ,Vi Vj = F,i ¹ j 且所有的Vi非空，Vi内的点均不邻接，称G是一个l 部图。 4部图

定义2如果在一个1部图G中，任意部V中的每个顶点 同G中其它各部中的每个顶点均邻接，称G为完全部 图。记作： G=Kn,n(n,=|1≤i≤) 例如： K122 显然： V=∑n,(G)=∑n,n l≤i<j≤l

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 定义2 如果在一个l 部图G中，任意部Vi中的每个顶点 同G中其它各部中的每个顶点均邻接，称G为完全l 部 图。记作： 例如： K1, 2, 2 显然： 1 , ( ) l i i j i i j l V n m G n n    = =  

定义3如果在一个个点的完全l部图G中有： n=kl+r,0≤r<1 =W==|=k+1 ,+1=|V,+2=.=V升=k 则称G为阶完全l几乎等部图，记为T4m V1=V=.=y1的完全1几乎等部图称为完 全1等部图。 定理1：连通偶图的2部划分是唯一的。 证明设连通偶图G的2部划分为VUV,=V

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 如果在一个n个点的完全l 部图G中有： n kl r r l = +   , 0 V V V k 1 2 = = = = + r 1 V V V k r r l + + 1 2 = = = = 则称G为n阶完全l 几乎等部图，记为T l, n |V1 | = |V2 | = . = |Vl | 的完全 l 几乎等部图称为完 全 l 等部图。 定理1： 连通偶图的2部划分是唯一的。 证明 设连通偶图G的2部划分为V1∪V2 =V

取v∈V,由于G连通，对任何u∈VUV,G中有 联结u和v的路，故d(,n)有定义。 因为任何一条以为起点的路交替地经过和V,的点， 可知一个点u∈Y当且仅当d(心，u是奇数。这准则唯一地 决定了G的2部划分。 定理2：n阶完全偶图Kml.2的边数m=n1n2,且有： 证明：m=n1n2显然。下面证明第二结论： mK)=K)=(n-%)n= n 4( 5-n2)2s

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 取v∈V1 ，由于G 连通，对任何u∈V1∪V2 ， G中有 联结u 和v的路，故d (v, u)有定义。 因为任何一条以v为起点的路交替地经过V1和V2 的点， 可知一个点u∈V2 当且仅当d (v, u)是奇数。这准则唯一地 决定了G的2部划分。 定理2： n阶完全偶图 Kn1,n2的边数m=n1n2 ,且有： 2 4 n m        证明：m=n1n2显然。下面证明第二结论： 1 2 2 2 2 2 2 , , 2 2 2 ( ) ( ) ( ) ( ) 4 2 4 n n n n n n n n m K m K n n n n −   = = − = − −     

定理3n阶部图G有最多边数的充要条件是G≌Tm。 证明：首先有： (G)≤m(K,m 其次，考虑： 则f取最大值的充分必要条件为：1i<j≤1，有： n,-n,l≤1 而G的对应的顶点划分形成的1部图正好为T。 从而证明了该定理

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 证明：首先有： 1 2 , , , ( ) ( ) n n nl m G m K  定理3 n阶l部图G有最多边数的充要条件是G ≌ Tl,n。 其次，考虑： 则 f 取最大值的充分必要条件为：1≦i<j ≦l,有: n n i j − 1 而G的对应的顶点划分形成的l 部图正好为T l, n 从而证明了该定理

(二)、托兰定理 定义4设G和H是两个阶图，称G度弱于H,如果 存在双射μ：V(G)→V),使得： v∈V(G),有：dc(v)≤dH(u(v) 注意：若G度弱于H,一定有： m(G)≤m(H) 但逆不成立！例如：(1,1,4,2)与3,3,3,3)没有度弱关系 定理4若阶简单图G不包含K41,则G度弱于某个完 全I部图H,且若G具有与H相同的度序列，则： G兰I

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 (二)、托兰定理 定义4 设G和H是两个n阶图，称G度弱于H，如果 存在双射μ：V(G)→V(H),使得： ( ), ( ) ( ( )) G H    v V G d v d v 有：  注意：若G度弱于H，一定有： m G m H ( ) ( )  但逆不成立！例如：(1,1,4,2)与(3,3,3,3)没有度弱关系！ 定理4 若n阶简单图G不包含Kl+1，则G度弱于某个完 全 l 部图 H，且若G具有与H 相同的度序列，则: G H

证明：对1作数学归纳证明。 当1=1时，结论显然成立； 设对1<t时，结论成立。考虑I=t时的情况。 令u∈V(G),且d(u)=△(G. 设G=GN(川，则G,不含K,否则，G含K+1,矛盾！ 由归纳假设，G,度弱于某个完全t-1部图H1· 又令V1=N(u),V2=V-V1,用G,表示顶点集合为V2的 空图，则G度弱于G,VG,当然度弱于G,VH1。 令H=G,VH,则H是完全t部图。 下面证明定理的第二个结论

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 证明：对 l 作数学归纳证明。 当 l =1时，结论显然成立； 设对 l <t 时，结论成立。考虑l = t 时的情况。 令u ∈V(G), 且d (u) = Δ(G). 设G1= G[N(u)],则G1不含Kt , 否则，G含Kt+1,矛盾！ 由归纳假设，G1度弱于某个完全t-1部图H1 . 又令V1=N (u) , V2=V-V1 , 用G2表示顶点集合为V2的 空图，则G度弱于G2VG1，当然度弱于G2V H1。 令H= G2V H1 ,则H是完全t部图。 下面证明定理的第二个结论

44 若G与H有相同的度序列，而H=G,VH,所以，G 与GVG,有相同的度序列。 由此可以推出：G=GVG2 因为G=GVG,和H=G2VH有相同度序列，于是 得到G,和H有相同度序列，所以： 定理5(Turn)若G是简单图，并且不包含K41,则： n(G)≤n(T.n) 仅当 GTT)n时，有 m(G)=m(Tn) 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 若G与H有相同的度序列，而H= G2V H1 ,所以，G 与 G1VG2有相同的度序列。 由此可以推出：G= G1V G2 因为 G= G1V G2和H= G2V H1有相同度序列，于是 得到G1和H1有相同度序列，所以： G H 定理5（Turán）若G是简单图，并且不包含Kl+1,则： , ( ) ( ) m G m T  l n 仅当 G T  l n, 时，有 , ( ) ( ) m G m T = l n