第第8 8章章 特殊图特殊图 树树第第8 8章章 特殊图特殊图 .1.1 无向树及生成树无向树及生成树定义定义 9.1 9.1 连通无回路的无向图称为连通无回路的无向图称为无向树无向树,简称简称树树,常用常用T T表示树。表示树。(即即树是不包含回路的连通图树是不包含回路的连通图)平凡图称为平凡树。平凡图称为平凡树。若无向图若无向图G G至少有两个连通分支至少有两个连通分支,则称则称G G为森林。为森林。在无向树中,悬挂顶点称为树叶,度数大于或在无向树中,悬挂顶点称为树叶,度数大于或等于等于2 2的顶点称为分支点。的顶点称为分支点。第第8 8章章 特殊图特殊图 例例 9.1 9.1 判断下列哪些图是树?判断下列哪些图是树?v1v2v3v4v5v1v2v3v4v5v1v2v4v3v5(a)(b)(c)解解:图图(a)是树是树,因为它连通又不包含回路。图因为它连通又不包含回路。图(b),(c)不是树不是树,因为图因为图(b)虽连通但有回路虽连通但有回路,图图(c)虽无回路但不连通。虽无回路但不连通。在图在图(a)中中,v1、v4、v5为均为叶,为均为叶,v2、v3均为均为分支节点。分支节点