Trees
Definition 6.1. A graph G has another graph H as a subgraph if H
is “contained within” G. In other words, if you can take G and remove
vertices and/or edges from it until you get the graph H, then H is a
subgraph of G.
一个图G有另一个图H作为子图，如果H“包含在”G中，换句话说，如果你可以取G并移除其中的顶点和/或边，直到你得到图H，那么H就是G的子图。
例如：
Definition 6.2. A tree is a graph T that is connected and has no cycle
graph Cn as a subgraph.
树是一个连通的图T，子图没有环图Cn
例如下面就是三个树：
Theorem 6.1. If T is a tree containing at least one edge, then T has
at least two leaves.
如果T是一个至少包含一条边的树，那么T至少有两个叶。
Useful Results on Trees(关于树的结论)
如果我们说T是一个树，那么以下两点一定成立：
- 在T中的任意两个顶点之间都有一条路径。
- T是连通的，有n – 1条边
Rooted Trees(有根树)
Definition 6.4. We say that the children of a vertex v are all of the
neighbors of v at the level directly below v, and the parent of v is the
neighbor of v at the level directly above v. The height of a rooted tree is
the largest level index created when drawing the graph as above.
树的高度是树的最大索引值
二叉树是一棵有根的树，其中每个顶点要么没有子结点，要么只有一个子结点，要么有两个子结点。你可以将它推广到m个树中，对于任意m，通过改变这里的限制，要求每个顶点最多有m个子结点。
如果每个顶点都没有子结点或两个子结点，则为满。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/122141.html
