§1.6极图 名 其次，置V=N()以及V2=八V1,并且用G2表示其顶点集是V2 而边集是空集的图.考查G和G2的联图GVG(如图1-19(d) 由于 Nc()三NGva,(o),对于∈V (1.3) 成立.而且V2的每个顶点在GVG2中有度△，所以G度弱于G,VG2, 因而G也就度弱于完全t部图H=HVG2(如图1-19(e). 现在假设G和H有相同的度序列，则G与G,VG2有相同的度序 列，同时在(1.3)式中等式必然成立.于是在G中，V1的每个顶点必然和 V2的每个顶点相连.由此推知G=G,VG2.由于G=GVG2和H= H1VG2有相同的度序列，因而图G1和H1必然有相同的度序列，于是由 归纳法假设，它们是同构的.我们得到G空H 定理20(Turn)若G是简单图，并且不包含K+1,则边数m(G)≤ m(T.n).此外，仅当G=T,时有m(G)=m(Tt). 证明设G是不包含K+1的简单图.由定理19，G度弱于某个完全 1部图H.由定理19得 m(G)≤m(H). (1.4) 由定理18知 m(H)≤m(T,.). (1.5) 从而由(1.4)式和(1.5)式即得 m(G)≤m(T. (1.6) 这就证明了定理的第一个结论， 现在假设(1.6)式中等式成立.则(1.5)式和(1.4)式中等式也必然 成立.由于m(G)=m(H)以及G度弱于H,所以G和H必然有相同的 度序列.因而由定理19，G空H.又由于m(H)=m(Tm),所以由定理18 知H会T.我们得到G空T. ☑ 定理20是极图理论中的一个问题的第一种情形：对于一个给定的图 H,求有n个点而不含禁用子图H的一个图中最多能够含有的边数，记 为m(n,H).现有的成果是 m(n,K)-n2/4」， (1.7) m(n,K+)=-D-2+r (1.8) 2 其中n=r(mod)且0≤r<l
24 第一章图的基本概念 m(m,C)=1+n-1(n-2 (1.9) m(n,K4-e)n2/4j, (1.10) m(n,K1.3十e)-n/4」， (1.11) 其中Cn表n个点的圈，K.3是星形图， 下面给出Turan定理的一个应用. 有这样一个问题：一个小组个人在一个平原地区执行一项排雷任 务.其中任意的两个人，若其距离不超过g米，则可用无线电保持联系； 若发生触雷意外，地雷的杀伤半径为h米.问：在任意的两个人之间均能 保持联系的条件下，若发生意外，平均伤亡人数最低的可能值为多少？对 此问题，按问题的条件若某人A触雷，则与A的距离大于h米的人将是 安全的，但究竞哪个人会发生触雷意外，事先是不知道的，所以此问题实 际上是求在任意的两个人之间的距离不超过g米的条件下，距离大于等 于h米的人数对最多能达到多少对.为建立此问题的数学模型，先引入 平面点集的直径这一概念 设A是一个有限平面点集，A的直径是指A中点对的距离的最大 值.其中距离是指欧氏距离，所以点集的直径与图的直径是两个不同的 概念 现在来看先前提出的问题，该问题可转化为计算在直径为g的点集 {x1,x2,.,x}中最多有多少点对，其距离大于h.下面我们对g=1,h= 1/W2展开讨论. 先观察n=6时平面点集的分布的两种特殊情况。一种情况为六个 点，x2,x3,x4,x和x6位于一个正六边形的顶点上，使点对(x1,x), (x2,x5)和(x,x6)的距离为1，如图1-20.容易计算该点集的直径为1， 线段1A的长√5/4，Ax5的长为3/4，从而可计算出与x5的距离为 3/2.同理，点对(x1,x),(2,x4),(,x6),(x,),(x4,x6)均为 3/2.因3/2>√2/2.所以此种情况距离大于√2/2的点对有9对. 另一种情况如图1-21所示.其中x,x2和x处于一个边长为1的 正三角形的顶点上x,和也位于一个正三角形的顶点上.由于线 段x2A的长为1/2，可使线段xB的长大于2/4.这是可以实现的.这 样，除点对(x,x),(x2,x),(x,x6)外，其余十二个点对的距离均大于 √2/2.下面的定理回答了l2已是最大数目.该定理的证明用到Turan 定理
51.6极图 25 图1-20 图1-21 定理21设A={x,x2,x}为任意一个直径为1的平面点集，则 A中距离大于2/2的点对的最大数目机/3」.并且对每个n,存在直径 为1的点集A·={x1,x2,.,xn},它恰有/3个点对，其距离大于√2/2. 证明定义图G=(V,E),使V=A, E={xx,ld(x,x)>√/2/2} 其中d(x,x,)表示欧氏距离.下证G不含K4, 首先注意到在平面上任意四个点必然确定一个不小于90°的角.这是 因为这四点的凸包，或是一条直线，或是一个三角形，或是一个四边形，分别 如图1-22的(a),(b)和(c)所示.所以在每个情况下都存在一个不小于90 的角xxx.对这三个点x,x,和x4(如图1-22)；若d(x,x)>√2/2， d(x,x)>√/2，则将导致d(x,xa)>1,这与A的直径为1矛盾.所以 d(x,x)和d(x,x)中必有一个，比如d(x,x)不大于√2/2，这表明 xxE,因此G中不含K4.由Turan定理（定理20） 图1-22 |E(G)≤IE(T.)|Hn/3J 下面我们构造一个直径为1的点集A·={x1,x2,·,x.},使其恰有 /3个点对，其距离大于√2/2.方法如下：
26 第一章图的基本概念 (1)将A"分为三个子集：A={x1,x2,},A2={工/+1， /+2.,w/图}，A,={1/+12n/+2,x}. (2)选择r,使0<r<(1-√2/2)/4； 画出三个半径为r的圆，使其三个圆的 中心彼此相距1一2r(如图1-23). (3)将A1,A2,A3中的点各放于一 个圆中，并使d(x1,x)=1. 显然A·的直径为1，并且容易验 证d(x,x,)>√2/2当且仅当x与x 位于不同的圆.所以A·恰有n/3个 图1-23 点对，其距离大于2/2. ◇ §1.7交图与团图 定义1令S是一个集，F={S,S2,.,S}是S的不同的非空子 集的一个非空族，这些子集的并是S.F的交图，记作2(F),定义为 V(2(F))=F,当i≠j且S,∩S,≠⑦时S,与S,邻接.于是，如果存在 S的子集的一个族F,对于这个族，G三n(F),就称为G是S上的一个 交图. 例1对于图1-24(a)的图G,可以构造一个集S={,2,4, e1,e2,e,e},若取S1={,e},S2={h,e,e,e},S={5,2,e},S, {4,3,e4),则得到非空子集的一个非空族F={S,S2,S,S,},从而得到 F的交图2(F)(如图1-24(b).显然G产2(F),故G是S上的一个交 图.一般的有 (a)G (b)(F 图1-24 定理22每一个图都是一个交图. 证明对于G的每个点v,令S,是{》与关联于的边的集的并. 于是立即可以得到，G与2(F)同构，其中F={S,S2,.,S
多1.7交图与团图 27 有了这个定理，我们就可以定义另外一个不变量。 定义2给定的图G是S上的一个交图，G的交数(G)是构成一个 集S所需要的最少的元素的数目 例2对于图1-24(a)的G图，若集S={e1,2,e,e},当取S= (e},S=(e2,ea,S={ee,S={e,ea,则得到非空子集的-个 非空族F=(S,S2,S3,S4),从而得到与图1-24(b)相同的交图2(F). 显然G≥2(F),故G也是S'上的一个交图. 对比一下例1,2知|S引=8，S1=4,故由定义2知，例中G的交数 v(G)≤4=|E(G)1,一般地有 推论1n阶连通图G有m条边，n≥3，则v(G)≤m 证明在这种情况下，可以从定理22的证明中所用到的各个集S 中把各个点略去，于是有S=E(G). 推论2若图G有m条边，个孤立点，且没有K2支，则(G)≤ m十no. 下面这个结果告诉我们什么时候可以达到推论1中的上界 定理23设G是一个有”>3个点的连通图，则当且仅当G中没有 三角形时，(G)=m, 证明我们先证充分性.因为有了推论1，只要对于任何一个至少有 四个点而没有三角形的连通图G有(G)≥m就好了.按交数的定义，G 同构于在一个集S上的一个交图，而引S引=(G).对于G的每个点，令 S,是相应的集.因为G没有三角形，所以S中没有一个元素可以属于两 个以上的集S.而且S∩S,≠必当且仅当v,是G的一条边.于是我们 可以在G的边与S的那些正好属于两个集S:的元素之间建立一个一 对应.从而(G)=S≥m,因此(G)=m. 为了证明必要性，令v(G)=m,并且假定G有一个三角形.令G1是 一个最大的没有三角形的生成子图，再令G=2(F),此处F是某个基数 为m1的集S的子集的一个族.令e是G的一条不在G1中的边.考查 G2=G十.因为G是一个最大的没有三角形的生成子图，G2中一定有 某个三角形，例如出2w,其中e=w,用S1,S2,S来记S相应于u1 2,w的子集.现在，假如2在G中只与山和山邻接，用一个从S∩S 中选取的单元素集来代替S2,并且将这个元素加人S3.否则，从S,∩S 中选出任何一个元素加人S,来作为新的S.无论在哪一种情形，这样给 出S的不同的子集的一个族F',使得G2=2(F).于是v(G2)=m1,但 是，|E(G2)川=m1.如果G2≥G,就已经证明了；而如果G2≠G则令 |E(G)|-|E(G2)川=mo