浙江师范大学课程结业论文.docVIP

浙江师范大学课程结业论文 余树也是树的一类图性质探索 学 院：数理信息学院 班 级：信息与计算科学061 学 号姓 名：张大伟 联系方式：x493320520@163.com 2008-11-30余树也是树的一类图的性质探索 张大伟 信息与计算科学061 摘要 连通图G必定存在生成树T，但是其余树即G关于T的导出子图未必能构成树，余树能构成树的一类图比较典型，由于其恰好有两棵不相交的生成树构成，又有类似于“对称”的性质。本文即是这类图的有关性质展开的讨论。 关键词 树 生成树；余树；连通图；边连通度； 引言 本文所讨论的是满足Q=2P-2的简单图是否存在余树为树的生成树这一命题，试图通过生成树与余树构建原连通图的方法寻找命题成立的等价条件，即从两棵树结合构成的连通图具有何等的性质出发，探求能够满足要求的连通图的性质 定义 定义：设G=(V ,E ),H=(V‵,E‵)为两个图，若 V‵ V , E‵ E 则称H为G的子图。 定义2：如果H是G的子图，且V(G)= V‵(G)则称H是G的生成子图。 定义3：在G中删除E‵所有的边得到的子图称E‵的边导出子图。 定义4：图G的生成子图T是树，称T是G的生成树。 定义5：设T是连通图G的一棵生成树，称=G-E(T)为T的余树。T中的边称为树枝。 定义6：连通图G的边连通度定义为 =0（若G≌K）；=min（若G≌K） 若是G的一个边割，则称是G的一个最小边割。 定义7：对于图G的任意边子集E，E的邻集是与E相邻的所有边的集合，其数目记为N(E)。 定理一：G是连通图当且仅当G含有生成树。 定理二：设T是G的一个生成树，是关于T的余树，则 （1）中不含G的任何边割； （2）对T中的任何一条边e，E(+e)有且仅有G的一个极小边割； （3）对中的任何一条边e，T+e有唯一的一条回路。 余树是树的一类简单图所具有的性质： 设简单图G连通，且顶点数为P，边数为Q，则其若含有余树为树的生成树，则必有如下条件： ， Q=2P-2；2，最小度≥2；3，≥2；4，N(E)≥3； 2，p≤6的连通图图若满足Q=2P-2，最小度≥2则必有余树是树的生成树（这一结果只是基于大量观察，依本人能力尚无法证明） ，图G的余树是树的充要条件是余树连通 部分结果的证明 下面给出结论3的证明：图G的余树是树当且仅当余树连通 充分性：显然若图G的余树是树，则余树必然连通，如图A，B； 必要性：若余树连通，则余树必然是树，如图B,D。可以采用反证法：若余树不是树，则其含有环，又有其边数为P-1可知其必然是非连通的如图C，故而与条件矛盾，即若余树连通，则其必然是树。 参考文献 [1] 卜月华，图论及其应用[M]，东南大学出版社 [2] 刘玉梅，李英，一类简单图的生成树[J]，2005 [3] 钟铭，刘永熙，余树是树的充分必要条件[J]，《天中学刊》1996年第11卷第1期