8 第一章图的基本凝念 可以得到，G是在有m1十=m一1，于是(G)<m 图的交数最早是由Erdós等所研究的.他们得出了有给定数目的点 的图的交数的最佳可能上界 定理24对于任何一个n>4个点的图G, (G)n2/4J. (1.12) 可以对每个图定义一个依赖于这个图的完全子图的交图.简单图G 的一个团是指V中的一个子集V,使GV1]是完全图.一个给定的图G 的团图是G的团的族的交图。 例3对于图1-25(a)的G,可以构造S={),4,防，%，e1, e2,e,e4,es,e6,e,eg,e},若取S1={,2,%,e1,e6,e},S2={2,h,4， e2,e,e8},S3={w4,5,6,e4,e},S={2,o4,%,e,ea,eg},显然 G[S,]=K3均是团，则得到非空子集的一个非空族F={S1,S2,S,S,}, 从而得到F的交图2(F)=K4,它就是G的团图（如图1-25(b). (b)团图K 图1-25 尽管例3中的K4是G的团图.然而，并不是每个图都是某个图的团 图.Roberts给出了团图的特征. 定理25一个图G是一个团图当且仅当它含有完全子图的一个族 F,它们的并是G,且如果F的某个子族F中每一对完全子图的交非空， 则F的所有元素的交就非空. 例4如图1-26中的K4,构造一个集合 为S={,4,g,a,.,6入.取S={h, ,4,e4,S={,4,e5,%},S {,4,%},S4={,，2，} 显然它们全是三角形K,它们构成非空子集的 一个非空族F={S,S,S,S4},它们的并是 K4,并且F的F={S,S2,S}中每一对完全子 图1-26 图的交非空，且S∩S2∩S={u)非空，故K4 必是某个图的团图，其实它就是例3中的图G(如图1-25(a)的团图
习题1 Benzer在生物遗传学的领域中发现了交图的一个特殊族.他建议将 代表一个细菌染色体的一串基因看作实轴上的一个闭区间.Erdos独立 地提出，对区间S,的每一个有限族F,可以定义一个图.用交图的语言来 说，这个图正好就是2(F).一个区间图是同构于某个图2(F)的一个图， 其中F是一族区间.Boland等还给出了区间图的特征. 习题1 1.证明在n阶连通图中 (1)至少有n一1条边： (2)如果边数大于n一1，则至少有一条闭迹； (3)如果恰有n一1条边，则至少有一个奇度点. 2.设G是n阶完全图，试问： (1)有多少条圈？ (2)包含G中某边e的圈有多少？ (3)任意两点间有多少条路？ 3.证明：图1-27中的两图不同构 图1-27 4.证明：图1-28中的两图是同构的 图1-28 5.证明：四个顶点的非同构简单图有11个 6.设G是具有m条边的n阶简单图。证明：m=(）当且仅当G是完全图。 7.证明： (1)m(Ki)=Ini
30 第一章图的基本概念 (2)若G是具有m条边的n阶简单偶图，则m≤r2/4」 8.设△和8是简单图G的最大度和最小度，则≤2m/n≤△ 9.证明：若k正则偶图具有二分类V=VUV:,则V,=V2 10.证明：由两人或更多个人组成的人群中，总有两人在该人群中恰好有相同的 朋友数 11.证明：序列(7,6,5,4,3,3,2)和(6,6,5,4,3,3,1)不是图序列。 12.证明：若6≥2，则G包含圈. 13.证明：若G是简单图且8>2，则G包含长至少是6+1的圈。 14.G的围长是指G中最短圈的长：若G没有圈，则定义G的围长为无穷大. 证明： (1)围长为4的k正则图至少有2k个顶点，且恰有2k个顶点的这样的图（在同 构意义下)只有一个： (2)围长为5的k正则图至少有k8+1个顶点 15.对具有m条边的n阶图G,证明： (1)若m≥,则G包含圈： (2)若m≥n十4，则G包含两个边不重的圈. 16.在图1-13的赋权图中，找出a到所有其他顶点的距离】 17,证明.若G不连通，则G连通 18.证明：若e∈E(G),则(G)≤w(G-e)≤w(G)十1. 19.证明：若G连通且G的每个顶点的度均为偶数，则对于任意的v∈V(G) w(G一u)≤d(v)/2成立. 20,证明：若G的直径大于3，则C的直径小于3， 21.设G是具有m条边的n阶简单图，证明：若G的直径为2且△=n一2，则 m>2n-4. 22,证明：若G是至少有三个点的简单连通图但不是完全图，则G有三个顶点 u,t和w,使得uu,∈E,而wE
第二章树 树是图论中的一种简单而重要的图.树的概念是基尔霍夫在解决电 路理论中求解联立方程问题时首先提出来的，但其发现超越了当时的时 代而长期没有引起人们的重视.树的概念与图论中的许多概念有密切的 联系，已经越来越广泛的应用到各个学科领域，如计算机和通信等领域 本章我们将讨论树的概念、性质、树的中心与形心、生成树和最小生成树 的算法. §2.1树的概念与性质 定义1(1)不包含圈的图称为无圈图，连通的无圈图称为树.树常 用字母T表示： (2)一个无圈图称为森林，树也是森林； (3)在一棵树中，度数为1的顶点称为树叶，度数大于1的顶点称为 分支点； (4)平凡图称为平凡树； 例如，在图2-1中，画出了5棵树.这些树的任意一种组合均为一个 森林 人人众 图2-1 树有许多等价的定义，在下面的定理1中列出了其中的5个等价 命题. 定理1设无向图G=(V,E)是一个(n,m)图，即顶点数为n,边数为 m的图，则下列命题等价：
第二章树 (1)G是树： (2)G中任意两顶点间有且仅有一条路相连： (3)G是连通的，且m=n-1; (4)G中无圈，且m=n一1； (5)G中无圈，但在G中任意不相邻两顶点间增加一条边，就得到惟 一一个圈. 证明(1)→(2)设图G是树，由于连通性，任意两顶点u,v之间必 有路相连.设P1=u叫2.4心和P2=uU2.Uv是图G中的两条(u,o) 路，且十1是使+1≠U+1的最小整数，)是使v+:在P上的最小整数， 即设+1=山，那么，u+1.4心，0+1.+1是G中的一个圈，这与G是 树矛盾. (2)→(3)由于图G中任意两顶点间有一条路相连，所以G是连 通的. 我们对图G的顶点个数作数学归纳，证明m=n一1. 当n=1时，m=0,结论显然成立. 设命题对n一1个顶点的图成立.现假设G是有n个顶点、m条边的 图.令e=uw是图G中任意一条边，由(2)，在G中去掉该边后，G成为两 个连通分支G,与G2.设G、G2的顶点数分别为m、,边数分别为m、 2,由归纳假设： m1=m1一1，m2=n2-1, 注意到m=m十m2十1，从而 m=m1十m2+1=m1-1+2-1+1=n-1. (3)→(4)只须证明图G中无圈.若不然，对G中每一个圈，去掉其中 一条边，则该图被去掉，但图的顶点数与连通性不变，如此作下去，最后得 到一棵树，这说明：m>n一1，得出与(3)矛盾的结论.所以，图G中不能 有圈 (4)→(5)先证明G是连通的.设G有k个分支，由(4)，G中无圈，故 每个分支是一棵树.设这k棵树分别是G1,G2,.,G,且G有n:个顶 点，m,条边，1≤<，从而m,=元-1，于是， m=h十n2十.十n4一k=n-k. 与(4)比较得k=1.因此，G是连通的，于是G是连通而无圈的图，即(1) 成立，从而(2)成立 设“和v是G中不邻接的两个顶点，由(2)，在G中有一条连接“与 v的路P,路P和边uw作成图G十uw的一个圈.因为G中无圈，所以 G十uu的任何一个圈含有边uo.于是G中若有两个不同的圈，则由此可