621树的定义及其性质 任两点之间有且只有一条路径的图称为树(re),记为T 树的性质 最少边的连通子图,树中必不存在回略 任何树必存在次数为1的点 具有n个节点的树T的边恰好为n-1条,反之,任何有 n个节点,n-1条边的连通图必是一棵树 622图的生成树 树T是连通图G的生成树( spanning tree),若T是G的 子图且包含图G的所有的节点;包含图G中部分指定节 点的树称为 steiner tree 每个节点有唯一标号的图称为标记图,标记图的生成树 称为标记树( Labeled tree) Caylay定理:n(≥2)个节点,有m-2个不同的标记树9 6.2.1 树的定义及其性质 • 任两点之间有且只有一条路径的图称为树(tree)，记为T 树的性质： • 最少边的连通子图，树中必不存在回路 • 任何树必存在次数为 1 的点 • 具有 n 个节点的树 T 的边恰好为 n−1 条，反之，任何有 n 个节点， n−1 条边的连通图必是一棵树 6.2.2 图的生成树 • 树 T 是连通图 G 的生成树(spanning tree)，若 T 是 G的 子图且包含图 G 的所有的节点；包含图 G 中部分指定节 点的树称为 steiner tree • 每个节点有唯一标号的图称为标记图，标记图的生成树 称为标记树(labeled tree) Caylay 定理：n (2)个节点，有n n−2个不同的标记树