树与林
贡献者： 零穹
[1] 林是不含圈的图，树是连通的林。也就是说，林的连通分支都是树。
定义 1 树，林
设 是图。若 上无圈，则称 为林（forest）；若 无圈且连通，则称 为树（tree）。
定义 2 叶子，内部点
设 是树，。若 （定义 1 ），则称 是 的叶子（leaf）。树中非叶子的点称为内部点。
由例 1 可知，林和树都是简单图。
定理 1
下面命题是等价的：
- 是树；
- 中任意两个不同点被 的唯一路连接；
- 是极小连通的，即 是连通的，但对任一边 ，（记号见定义 23 ）不连通；
- 是极大无圈的，即 不包含圈，但任意不相邻的点 ， 包含圈（其中 是连接 的边）。
证明：
1. ：设 。同于树是连通的，所以存在 到 的（长为 ）路 。设 是连接 的另一（长为 ）路。由于 无圈，所以链 中在 两边一定有两个内点相同，否则该链就是一个圈。由于左边和右边分别是路，因此两个内点只能一个在一边。设这两个内点是 ，于是 是 链。
由于 端点相同，我们仍可以重复上面的论述。若 ，不是一般性
设 ，于是至多重复 次后得到链 ，继续重复操作，则将出现 。这和 是路矛盾。这一矛盾表明只能是 。若 则重复 次又会出现上面的情况，于是只能是 。于是重复最多重复 次，我们就会发现 。
然后对路 继续上述操作，可以得到 。如此重复，最终得到 。
2.：由 2 可知 是连通的。，设 其端点为 ，无圈表明 。而 ， 是连接 的唯一路，所以 中不能有连接 的路了。否则这条路只能是 ，但是 。
3.：a.设 包含圈 ，那么 是连接 的路，但这是不可能的，所以 不包含圈。b.设 不相邻，记 。那么由于 上有连接 的路 ，所以此时 包含圈 。
4. ：任意 ，记 。由于 不含圈， 含圈，所以所含的圈必然包含 ，否则 有圈。以 作为端点，记该圈为 。由于除了 以外其它圈的元素都在 内，因此路 属于 ，即 连通。所以 是树。
证毕！
注意定理的 3 相当于 连通且连通分支 。于是得下面的推论。
推论 1
若 是树等价于 ，则 连通分支数为 2，即 。
1. 支撑树与支撑林
定义 3 支撑树，支撑林
设 是 的支撑子图，且它们的连通分支相同，即 。若 是林，则称 是 的支撑林（spaning forest）；若 是树，则称 是 的支撑树（spaning tree）。
证明：
设 是连通图 的边最少的连通支撑子图。那么 。事实上，如若不然，则 仍是连通的，且点数不变，而边数却少了 1，这和 是边最少的连通支撑子图矛盾。由推论 1 ， 是树。
证毕！
[1] ^ 徐俊明.图论及应用. 中国科学技术大学出版社, 合肥.1998.
致读者： 小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此，我们请求广大读者
热心打赏 ，使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损， 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款， 他们的付出帮助了 99% 的读者免费获取知识， 我们在此表示感谢。