第二章 树
§2.1 树
树:连通的无圈图称为树。
例子:6 个顶点的不同构的树(见图 2.1)
森林:无圈的图(不一定连通)称为森林。例子:
定理 2.1:在一棵树中,任意两个顶点均由唯一的路连接。
证:用反证法。设 G 是树,假设在 G 中存在两条不同的路
和
。因为
,所以存在
的一条边 ,它不是
的边。显
然,图
是连通的。所以它包含一条(x, y)路 P。于是
就是无圈图 G 中的圈,导致矛盾。
定理 2.2:若 G 是树,则 。
证:对用归纳法。当 时,
且 。
假设定理对少于个顶点的所有树均成立,并设 G 是 个顶点的
树。设 。因为是 G 中唯一的路,所以不包含
路。从而不连通且
。 的分支
和
是无圈
且连通的,因此是树。并且
和
的顶点数均小于。所以由归纳假
设
对 成立。
从而
。
推论 2.2:每棵非平凡树至少有两个 1 度顶点。
证:设 G 是非平凡树,则
评论0