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

浙江师范大学课程结业论文余树也是树的一类图性质探索

学院：数理信息学院

班级：信息与计算科学061

学号：06200126

姓名：张大伟

联系方式：x493320520@https://www.wendangku.net/doc/0f13795206.html,

2008-11-30

余树也是树的一类图的性质探索

张大伟 06200126 信息与计算科学061

摘要 连通图G 必定存在生成树T ，但是其余树即G 关于T 的导出子图未必能构成树，余树能构成树的一类图比较典型，由于其恰好有两棵不相交的生成树构成，又有类似于“对称”的性质。本文即是这类图的有关性质展开的讨论。

关键词 树 生成树；余树；连通图；边连通度；

引言 本文所讨论的是满足Q=2P-2的简单图是否存在余树为树的生成树这一命题，试图通过生成树与余树构建原连通图的方法寻找命题成立的等价条件，即从两棵树结合构成的连通图具有何等的性质出发，探求能够满足要求的连通图的性质

定义

定义[1]1：设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 的一棵生成树，称T =G-E(T)为T 的余树。T 中的边称为树枝。

定义6：连通图G 的边连通度λ

（G ）定义为 λ（G ）=0（若G ≌K ）；λ

（G ）=min {}11E E G 是的一个边割（若G ≌K ） 若1E 是G 的一个λ

（G ）边割，则称1E 是G 的一个最小边割。 定义7：对于图G 的任意边子集E ，E 的邻集是与E 相邻的所有边的集合，其数目记为N(E)。

定理一：G 是连通图当且仅当G 含有生成树。

定理二：设T 是G 的一个生成树，T 是关于T 的余树，则

（1）T 中不含G 的任何边割；

（2）对T 中的任何一条边e ，E(T +e)有且仅有G 的一个极小边割；

（3）对T 中的任何一条边e ，T+e 有唯一的一条回路。

余树是树的一类简单图所具有的性质：

设简单图G 连通，且顶点数为P ，边数为Q ，则其若含有余树为树的生成树，则必有如下条件：

[2]

1， Q=2P-2；2，最小度δ（G ）≥2；3，λ（G ）≥2；4，N(E)≥3；

2，p≤6的连通图图若满足Q=2P-2，最小度 （G）≥2则必有余树是树的生成树（这一结果只是基于大量观察，依本人能力尚无法证明）

[3]

3，图G的余树是树的充要条件是余树连通

部分结果的证明

下面给出结论3的证明：图G的余树是树当且仅当余树连通

充分性：显然若图G的余树是树，则余树必然连通，如图A，B；

必要性：若余树连通，则余树必然是树，如图B,D。可以采用反证法：若余树不是树，则其含有环，又有其边数为P-1可知其必然是非连通的如图C，故而与条件矛盾，即若余树连通，则其必然是树。

参考文献

[1] 卜月华，图论及其应用[M]，东南大学出版社

[2] 刘玉梅，李英，一类简单图的生成树[J]，2005

[3]钟铭，刘永熙，余树是树的充分必要条件[J]，《天中学刊》1996年第11卷第1期