图论及应用-电子科技大学第一章.pptVIP

§1.6 极图 (一)、l 部图的概念与特征 (二)、托兰定理 1978年，数学家Bollobas写了一本书《极值图论》(Extremal Graph）,是关于极值图论问题的经典著作。 P. Erd?s是该研究领域的杰出人物。他是数学界的传奇人物，国际图论大师，获过Wolf数学奖。他是20世纪最伟大的数学家之一，也是人类历史上发表数学论文最多的数学家(1000多篇),第二名是欧拉(837篇)。他于1996年9月20日因心脏病去世，享年83岁，他的逝世当时惊动了整个数学界。 极图属于极值图论讨论的范畴，主要研究满足某个条件下的最大图或最小图问题。 上世纪70年代末，极值图论已经形成了相对完整的理论体系，但还有很多引人入胜的公开性问题没有解决，所以，直到现在，它仍然是重要研究方向。但是，该方向是比较困难的数学研究方向之一。 定义1 若简单图G的点集V有一个划分 V= ，Vi∩Vj =Φ i≠j 且所有Vi非空， Vi内的点均不相邻，则称G是一个l 部图。 说明: (1) 如果l=2，则G就是偶图； (2) 任何一个n阶图必是一个n部图； (3) 若l1l2≤n，易知任意的 l1部图也是l2部图。 4部图 (一)、l 部图的概念与特征 定义2 如果在一个l 部图G中，|Vi|=ni，任何两点 u∈Vi ,v ∈Vj , i≠j , i,j =1,2,…, l 均邻接，则称G为完全l 部图。记作 v1 v2 v3 v5 v4 v6 K1,2,3 例 注: 它有 个点和 条边。 定义3 如果在一个n个点的完全l 部图G中， n = kl + r 0≤rl |V1| = |V2| = … = |Vr| = k + 1; |Vr+1| = |Vr+2 | = … = |Vl | = k 则称 G 为n 阶完全 l 几乎等部图，记为Tl ,n。 |V1| = |V2| = … = |Vl | 的完全 l 几乎等部图称为完全l 等部图。 v1 v2 v3 v4 v5 v6 考察 1. 这是一个连通的3部图, 点集 V 的划分为: V1= {v4}， V2 = {v3 ,v5}，V3 ={v1 ,v2 ,v6 } 2. V 的划分也可为 V1= {v1,v5}，V2 = {v2 ,v3}，V3 = {v4 ,v6 } 3. 这也是一个2部图, 点集 的划分为: V1= {v4 ,v2 ,v6 }， V2 = {v1,v3 ,v5},且划分唯一 定理16 连通偶图的2部划分是唯一的。 证明 设连通偶图G 的2部划分为V1∪V2 =V 。取v∈V1 ，由于G 连通，对任何 u∈V1∪V2 ，G 中有联结 u 和 v 的路，故d (v, u)有定义。因为任何一条以v为起点的路交替地经过V1和V2 的点，可知一个点u∈V2 当且仅当d (v, u)是奇数。这准则唯一地决定了G的2部划分。 证明 m = n1n2 是显然的。 又 m = n1n2 = n1(n-n1) = n1n - n12 = n2 /4 - (n1-n/2)2 （配方） ≤ n2 /4 考虑到 m 是正整数，故 定理17 n阶完全偶图 的边数 m = n1n2 ，且有 符号 表示不大于实数 x 的最大整数； 表示不小于实数x的最小整数。 定理18 n阶l 部图G有最多边数的充要条件是 G≌Tl,n。 证明：首先有： 其次，考虑： 则 f 取最大值的充分必要条件为：1≦ij ≦l,有: 而G的对应的顶点划分形成的 l 部图正好为T l, n 从而证明了该定理。 (二)、托兰定理 定义4 设G和H是两个n阶图，称G度弱于H，如果存在双射μ：V(G)→V(H),使得： 注意：若G度弱于H，一定有： 但逆不成立！例如：(1,1,4,2)与(3,3,3,3)没有度弱关系！ 定理19 若n阶简单图G不包含Kl+1，则G度弱于某个完全 l 部图 H，且若G具有与 H 相同的度序列，则: 证明：对 l 作数学归纳证明。 当 l =1时，结论显然成立； 设对 l t