数理与信息工程学院 课程论文 课程名称 图论及其应用 题 目 余树初探.docVIP

数理与信息工程学院 课程论文 课程名称 图论及其应用 题 目 余树初探 姓 名 程远 宋康康 学 号 专 业 信息与计算科学06（1） 余树是树的初探 摘要： 本文给出余树是树的连通的简单图的存在性定理，并且给出了如何作出余树是树的方法，此方法当然也可以判断一个连通的简单图是否有余树是树，还可以找最小生成树对应的余树，并且此余树是树。 关键词：树，连通图，余树。 引言 一个连通图G，如果G中有回路，我们逐个去掉回路上的一条边，直到没有回路为止，就得到了一棵生成树T，那么V,E(G-T)就是余树。余树是否为树？现在的文献上也少有关于余树是树的文章。 余树不仅可以是树，也还可以不是树，这跟图G有着密切的关系。例如下图： G T T0 连通图G，它的生成树T，以及余树T0，可以看到余树T0不是连通的。那么哪一类图存在余树是树呢？ 正文 我们先给出几个定理： 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有余树是树，不妨设此余树是T0V(G),E(T0),V（G）={v1,v2,v3……，vp-1},那么肯定有对应的生成树T，T=G- T0,E(T)=E(G)-E(T0) 已经知道了余树和生成树，那么含有生成树是T，余树是T0的一类图也就确定了，G是其中之一。 下证这类图都是有p-1个回路的。 由E(G)={ei ej| eiE(T),ejE(T0)，1=i≠j=p-1},又由于E(T)是生成树，因此每添加一条边ej至少有一个回路（根据定理3），一共添加了p-1条，因此至少有p-1个回路。由定理2可知新添加的p-1条边不构成回路，因为ejE(T0)。则这类图有p-1个回路，因此G也有这么多回路。 定理5：存在一个偶数阶连通图G的度序列为（3,3,4,4……4,4,3,3），即有四个顶点的度是3，其它所有定点的度都是4，那么存在G的某一生成树所对应的余树是树。 证明： 对于上述度序列，我们不妨取这样的图： 取生成树T为 GV,E是这样的图 E0 = [ V1, V2k] Ei=[Vi,Vi+2]，（i=1,2,……2k-2） Ej=[Vj,Vj+1], (j=1,2,3,……2k-1) 自然的，余树T0=G – T T0中的仅有一条路L（V2,V4, ……,V2k,V1, ……,V2k-1），这条路上总共有 [(2k-2)/2 + 1+(2k-1-1)/2 +1]=2k个顶点， 而且每个顶点互不相同，因此V(L)=V(G),因此T0是连通的， p(T0)=2k，q（T0）=2k-1,即q=p-1，故T0是树 证毕 推论1：上述的证明中构造的连通图G也是Hamilton图。 推论2：对于奇数顶点也存在相类似的定理。 说明：（一）如果我们从一个6阶图来看上面构造的图G和生成树T 余树的边是绿色的，生成树的边是蓝色的。显然余树是树。此图也是Hamilton图，但不是闭包。 （二）度序列为（3,3,4,4……4,4,3,3）的图不一定是连通的，因此我们加上了连通这个条件，而且并不是它的所有生成树对应的余树都是树。 定理6：若简单连通图GE,V没有割边，并且满足q=2*p-2，那么存在G的某一生成树对应的余树是树。（余树是树的存在性定理） 证明 既然GE,V是连通的简单图，并S且q=2*p-2，那么G是存在回路的，若G没有回路，则q=p-1,这是于条件矛盾的，因此G有回路。 那么我们可以构造这样的图T：取回路C上的一条边e1，再从（G-{e1}）中的回路上取一条边e2 ……，依次这样下去，直到不存在回路，此时G’=G-{ei|1ip}。如果ip-1,只要再次取这样的边，与这些边相关联的顶点的度至少是2,直到i=p-1为止,最终G’=G-{ei|i=1,2,……,p-1}。由于G没有割边，因此此时G’还是连通的。 设E’={ei| i=1,2……p-1},TE’,V是连通的，并且q(T)=p-1,由定理1可以知道，T是树，此时我们把T作为生成树，那么G’是余树并且是树，因为G’是连通