计算机数学基础⑥(Trees)

计算机数学基础⑥(Trees)

文章目录

​​Trees​​​​Useful Results on Trees(关于树的结论)​​​​Rooted Trees(有根树)​​

Trees

Definition 6.1. A graph G has another graph H as a subgraph if His “contained within” G. other words, if you can take G and removevertices and/or edges from it until you get the graph H, then H is asubgraph 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 cyclegraph Cn as a subgraph.

树是一个连通的图T，子图没有环图Cn

例如下面就是三个树：

Theorem 6.1. If T is a tree containing at least one edge, then T hasat 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 theneighbors of v at the level directly below v, and the parent of v is theneighbor of v at the level directly above v. height of a rooted tree isthe largest level index created when drawing the graph as above.

树的高度是树的最大索引值

二叉树是一棵有根的树，其中每个顶点要么没有子结点，要么只有一个子结点，要么有两个子结点。你可以将它推广到m个树中，对于任意m，通过改变这里的限制，要求每个顶点最多有m个子结点。

如果每个顶点都没有子结点或两个子结点，则为满。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。