图论5课件.pptVIP

数学学院 杨春 Email：yc517922@126.com * 第10章 树 10.2　无向树 例1：指出下图中树与森林 树的性质 定理10.2.1设G＝V，E是一个简单无向图。则以 证明 采用循环论证方法。 即只需证1)?2)?3)?4)?5)?6)?1)即可。 证明2)?3)用反证法。 若G不连通，设G中有k个连通分支(k?2)G1,G2,…,Gk， 证明3)?4) ①、首先证明G中无回路。用第一数学归纳法证明，对n作归纳。 证明4)?5) 若G不连通，则存在两个结点vi和vj，在vi和vj之间无 定理10.2.2 任意非平凡的树T＝(n，m)中，至少有两片树叶。 10.2.2　生成树 定义13.4　若连通图G的某个生成子图是一棵树， 例2 在上图中(b)、(c)所示的树T1、T2，它们都是图(a) 定理10.2.3 任意一个无向连通图G至少存在一棵生成子树。 求生成子树的方法 破圈法　每次去掉回路中的一条边，其去掉的边的总数为m-n+1。 避圈法　每次选取G中一条与已选取的边不构成回路的边，选取的边的总数为n-1。 例3 求下图(a)所示的图的生成子树。 例4 某地要建5个工厂，拟修筑道路连接这5处。经勘测其道路可依如a图的无向边铺设。为使这5处都有道路相通，问至少要铺设几条路？怎样铺设？ 10.2.3　最小生成子树 定义10.2.3　设G＝V,E是连通的赋权图，T是G 1．克鲁斯克尔算法 在G中选取最小权边e1，置i＝1。 当i＝n-1时，结束，否则转3）。 设已选取的边为e1,e2,…,ei，在G中选取不同于e1,e2,…,ei的边ei+1，使{e1,e2,…,ei,ei+1}中无回路且ei+1是满足此条件的最小权边。 置i＝i+1，转2）。 例5 用克鲁斯克尔算法求下图a中赋权图的最小生 成树。 w(T)＝34 2．管梅谷算法 令G0＝G，置i＝0。 当i＝m-n+1时，结束，否则Gi中含回路，转3）。 设C为Gi中的一条回路，ei为C上权值最大的边。 置Gi+1＝Gi-ei，i＝i+1，转2）。 例6 用管梅谷算法求下图a中赋权图的最小生成树。 w(T)＝34 * * 定义10.2.1　连通而不含回路的无向图称为无向树，简称树。树中度数为1的结点称为树叶；度数大于1的结点称为分支点或内部结点。常用T表示树。 　　不含回路的无向图称为森林。 　　若图G是森林，则G得到的每个连通分支都是树。 下关于树的定义都是等价的： G是连通且不含回路的； G中无回路，且m＝n-1，其中：m是图G中的所有边的边数，n是图G中的所有结点的结点数； G是连通的，且m＝n-1，其中：m是图G中的所有边的边数，n是图G中的所有结点的结点数； G中无回路，但在G中任何二结点之间增加一条新边，就得到唯一的一条基本回路； G是连通的，但删除G中的任意一条边后，便不连通；(n?2) G中每一对结点之间有唯一的一条基本通路。(n?2)。 1)?2)用第一数学归纳法证明，对n作归纳。 当n＝1时，m＝0，显然有m＝n-1； 假设当n＝k时，命题成立； 当n＝k+1时，由于G连通而无回路，所以G中至少有一个度数为1的结点v0，在G中删去v0及其关联的边，便得到k个结点的连通而无回路的图，由归纳假设知它有k-1条边。再将结点v0及其关联的边加回到原来的图中得到原图G。所以G中含有k+1个结点和k条边，为此满足：m＝n-1。 其结点数分别为n1,n2,…,nk，边数分别为m1,m2,…,mk，且有： n＝n1+n2+…+nk， m＝m1+m2+…+mk， 由于G中无回路，所以每个Gi(i＝1，2，3，…,k)均为树，因此有： mi＝ni-1 (i＝1,2,3,…,k)， 于是有： m＝m1+m2+…+mk＝(n1-1)+(n2-1)+…+(nk-1) ＝n1+n2+…+nk-k＝n-kn-1， 由此得出矛盾。所以G是连通的，且m＝n-1。 当n＝1时，m＝n-1＝0，显然无回路；假设当n＝k-1时，命题成立，即图无回路；当n＝k时，因G是连通的，故G中每一个结点的度数均大于等于1。可以证明至少有一个结点v0，使得deg(v0)＝1，因若k个结点的度数都大于等于2，则有： 2m＝deg(v0)+deg(v1)+deg(v2)+……+deg(vk) ?2+2+2+……+2＝2k (其中：v0，v1，v2，……，vk是G中的所有k个结点)。从而有:m?k，即至少有k条边，但这与m＝n-1发生矛盾。在G中删去v0及其关联的边得到一个新图G1，根据归纳假设知G1无回路。由于deg(v0)＝1，所以再将结点v0及其关联的边加回得到原图G，则G也无回路。 ②、其次证明在G中任意二结点vi，vj之间增加一条边(vi，vj)，得到