【图论】树【学生版】

课程类型课程类型 数学数学 “树”“树” 讲义编号 学员 讲师 年级 授课方式（在线或线下） 授课日期 （线下填）授课教学点 知识定位知识定位 树是一种重要的图，概念与圈相对，应用极为广泛。 知识梳理知识梳理 定义定义 没有圈的连通图称为树树， n 阶的树记为。 一个没有圈的图称为森林森林， 叶叶 （或悬挂点悬挂点） 是指树中度为 1 的顶点。 图 G 的一个生成子图生成子图是顶点集为 VG的一个子图。一棵生成树生成树是一个生成子图并且它是一棵树。 定理定理 1.n（≥2）阶的树至少有两个悬挂点，从中去掉一个悬挂点得到。 证明 2.对于 n 阶图 G，下面的命题等价 A.G 是连通的并且无圈。 B.G 是连通的并且有 n-1 条边。 C.G 有 n-1 条边并且无圈。 D.G 无圈，并且对于任意 、，G 恰有一条 u、v 路径。 证明 1 例例 1 1 n 个镇，每个镇都可以通过一些中转镇与另一个镇通话。证明至少有n-1 条直通的电话线路，每条连接两 个镇。 例例 2 2 如果 T， T’ 是连通图 G 的生成树并且， 则存在一条边使得是 G 的一个生成树。 例例 3 3 如果 T 是一棵具有 k 条边的树， G 是一个简单图且最小的顶点度是，则 T 是 G 的一个子图。 2 例例 4 4 证明最大度的任意一棵树至少有 个度为 l 的顶点。对任意选取的满足的 n 和 ，构造一 棵恰有 个悬挂点的。由此证明上述结论是最优的。 例例 5 5 n 个不同的点可以产生多少种不同的树 例例 6 6 证明在 G 中存在 n 棵两两边不相交的生成树的必要条件将G 的顶点任意划分成 r 个集合。则至少存在 G 的条边使得它们的端点位于划分后的不同集合中。 试题演练试题演练 1.简单图 G 为树的充分必要条件是图G 连通，且从图 G 中去掉任意一条边，得到的图不连通。 2.如果 T，T’ 是连通图 G 的生成树并且， 则存在一条边使得是 G 的 一个生成树。 3.令，，是正整敛，其中。证明存在一个顶点度为，，的树当且仅当。 3 4.令 T 是一棵 n 顶点树， 对于的每个 i 值， 树中有一个度为 i 的顶点； 其余的个顶点都是叶子。 确定 n 并表示成 k 的形式。 5.平面上有 n 条线段，，其中任意三条都有公共端点。证明，这n 条线段必有一个公共端点。 6.设，令 G 是一个 n 顶点图，且任意删除一个顶点之后得到的图均是一棵树。确定，并由此确定G 本 身。 7.某市街道成棋盘状，横n 条，竖m 条。现在决定封闭一些街道，使得汽车仍然能从任一个十字路口走到其他十 字路口，但决不会兜圈子。问应当封闭多少段路（每两个相邻的十字路口间的路称为一段） 8.给定和为的正整数，，， 在顶点集上恰存在棵树使得顶点i 的度为，对 任意 i 成立。 讲师评价讲师评价 知识点知识点课后掌握情况课后掌握情况所需习题编号所需习题编号 4 是否需要课时加强是否需要课时加强 课后掌握情况评分 1 对本知识点毫无所知，闻所未闻。 2 了解该知识点，能完成简单的识记题。 3 理解该知识点，能运用其分析解答简单问题。 4 把握知识的意义，但缺乏练习与手感，解答稍难的题目速度慢。 5 深刻了解知识内核，能完成相应试题，但有一定的错误率。 6 能够较熟练利用该知识点解决相关试题，但题目稍加变形就难以入手。 7 熟悉该知识点各要素，能顺利解答该知识点范围内各种题目的变形。 8 能把该知识点与其他知识相关联，解答高考中的压轴题。 9 懂得出题规律，只对该知识点范围的难题有兴趣 10 已拿下该知识点，拥有金钟罩，刀枪不入。 5