第一章图的基本概念 本次课主要内容 极图理论简介 (一)、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