《数理与信息工程学院 课程论文 课程名称 图论及其应用 题 目 余树初探》由会员分享，可在线阅读，更多相关《数理与信息工程学院 课程论文 课程名称 图论及其应用 题 目 余树初探（9页珍藏版）》请在金锄头文库上搜索。
1、1数理与信息工程学院课程论文课程名称 图论及其应用 题 目 余树初探 姓 名 程远 宋康康 学 号 06200113 06200124 专 业 信息与计算科学 06（1 ） 2余树是树的初探摘要： 本文给出余树是树的连通的简单图的存在性定理，并且给出了如何作出余树是树的方法，此方法当然也可以判断一个连通的简单图是否有余树是树，还可以找最小生成树对应的余树，并且此余树是树。关键词：树，连通图，余树。3一、 引言一个连通图 G，如果 G 中有回路，我们逐个去掉回路上的一条边，直到没有回路为止，就得到了一棵生成树 T，那么 就是余树。余树是否为树？现在的文献上也少有关于余树是树的文章。余树不仅可以是
2、树，也还可以不是树，这跟图 G 有着密切的关系。例如下图：G T T0连通图 G，它的生成树 T，以及余树 T0，可以看到余树 T0 不是连通的。那么哪一类图存在余树是树呢？4二、 正文我们先给出几个定理：T 是图定理 1：若 T 连通，且 q（t）=p （T ）-1，那么图 T 是树定理 2：若 T 没有回路且 q（T）=p(T)-1,那么 T 是树定理 3：若 T 没有回路，并且对 T 中的任意两个不相邻的顶点 u 和v，T+uv 只有一个回路，那么 T 是树。以上定理的证明请参照图论及其应用 定理 4：一个连通的简单图 G 若存在余树是树，那么至少含有 p-1 个回路。证明G 有余树是树
3、，不妨设此余树是 T0,V（G）=v 1,v2,v3，v p-1,那么肯定有对应的生成树 T，T=G- T 0,E(T)=E(G)-E(T0)已经知道了余树和生成树，那么含有生成树是 T，余树是 T0 的一类图也就确定了，G 是其中之一。下证这类图都是有 p-1 个回路的。由 E(G)=ei ej| ei E(T),ej E(T0)，1是这样的图E0 = V1, V2kEi=Vi,Vi+2， （i=1,2,2k-2 ）Ej=Vj,Vj+1, (j=1,2,3,2k-1)自然的，余树 T0=G TT0 中的仅有一条路 L（V 2,V4, ,V2k,V1, ,V2k-1） ，这条路上总共有(2k-
4、2)/2 + 1+(2k-1-1)/2 +1=2k 个顶点，而且每个顶点互不相同，因此 V(L)=V(G),因此 T0 是连通的，p(T0)=2k，q（T 0）=2k-1,即 q=p-1，故 T0 是树证毕6推论 1：上述的证明中构造的连通图 G 也是 Hamilton 图。推论 2：对于奇数顶点也存在相类似的定理。说明：（一）如果我们从一个 6 阶图来看上面构造的图 G 和生成树 TV2 V6V4V3V1 V5余树的边是绿色的，生成树的边是蓝色的。显然余树是树。此图也是Hamilton 图，但不是闭包。（二）度序列为（3,3,4,44,4,3,3 ）的图不一定是连通的，因此我们加上了连通这个
5、条件，而且并不是它的所有生成树对应的余树都是树。定理 6：若简单连通图 G没有割边，并且满足 q=2*p-2，那么存在 G的某一生成树对应的余树是树。 （余树是树的存在性定理）证明既然 G是连通的简单图，并 S 且 q=2*p-2，那么 G 是存在回路的，若 G 没有回路，则 q=p-1,这是于条件矛盾的，因此 G 有回路。那么我们可以构造这样的图 T：取回路 C 上的一条边 e1，再从（G-e 1）中的回路上取一条边 e2 ，依次这样下去，直到不存在回路，此时 G=G-ei|1是连通的，并且 q(T)=p-1,由定理 1 可以知道，T 是树，此时我们把 T 作为生成树，那么 G是余树并且是树
6、，因为G是连通的，并且 q(G)=p-1 满足定理 2。证毕说明一：可以定理 5 可以看作定理 6 的一个特例，但是定理 5 的图非常有意思，它含有 Hamilton 回路。二：不存在这样的图，这个图的所有余树都是树。因为我们只要取这样的生成树，有一个顶点，这个顶点包含了图中的所有的边，显然余树是不连通的。定理 6 说明余树是树的图是存在的，那么一个图的余树是树时，怎么样找出这样的余树呢？是否能全部找出来？我们使用去边法来找余树，假设图满足定理 6 的条件。去边法：1) 首先用破圈法，即去掉回路上的一条边。2) 重复 1 的步骤，但是去掉的边不能使与此条边相关联的顶点成为孤立点，直到没有圈就停
7、止。3) 若去掉的边少于 p-1，就再去掉一些边，同样不能使相关联的顶点成为孤立点，直到去掉边的总数为 p-1 为止。例如：8G T(生成树) T0(余树)对去边法思想的说明：对连通的简单图 G，当 G 有余树是树时可以用去边法来做出余树是树。第一：去边时，首先使用破圈法去边，那么并不改变图的连通性，而且去掉了回路。若破圈时去掉的边不到 p-1，再次去边时要求新去的边和原来去掉的边没有回路，直到去掉了 p-1 条边，而顶点数是不改变的，因此有定理 2 可知 是生成树（E 是所有去掉边的集合） 。第二：由于去边时保证了余树是连通的（只去掉回路上的边，和顶点度至少为2 的边） ，而余树又满足 q=
8、p-1，满足定理 1，因此余树是树。因此去边法得到的余树都是树推论 1：如果一个连通的简单图不能使用去边法，那么此图的余树不是树，也即去边法也可以用于余树是否为树的判断。2：如果图 G 是赋权图，那么我们应用管梅谷教授的最小树的破圈法 ，可以找到最小生成树的余树，且该余树是树，如果最小树对应的余树是树是存在的。因为去边法的第一步是利用了破圈法，如果用最小树的破圈法，那么就得到了最小生成树的余树。例如：5365862436 56664235389G T(最小生成树) T0(余树)10三、 讨论去边法是建立在破圈法的基础上，因此继承了破圈法在处理平面图 G 时的便捷。当然用去边法可以求出一个图 G 的所有余树是树的余树，只要在取回路时取不同的边，同时保证去边后的图的连通性。如果余树是树，那么余树和其对应的生成树的地位是一样的，也就是说余树和生成树可以互相转换。生成树可以成为其对应余树的余树，只要把余树当作生成树。当然依据余树是树的存在性定理，那么用去边法来判断余树是否为树就显得复杂了。最后我们也可以设计算法来实现去边法。 图论及其应用卜月华主编，东南大学出版社 求最小树的破圈法管梅谷 1975
