[礼品回收公司网站建设制作报价方案.ppt

第三十二讲 上节知识回顾 上节知识回顾 上节知识回顾 本节内容安排 第七章 图论 第七章 图论 第七章 图论 第七章 图论 第七章 图论 第七章 图论 第七章 图论 第七章 图论 第七章 图论 第七章 图论 第七章 图论 第七章 图论 第七章 图论 第七章 图论 第七章 图论 第七章 图论 第七章 图论 第七章 图论 第七章 图论 第七章 图论 第七章 图论 第七章 图论 第七章 图论 第七章 图论 小 结 结束语 信息科学与工程学院 * 第 四 部 分 7-8 根树及其应用 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 图 G=V,E，其中V是非空点集，E是边集 无向图 有向图 连通图 非连通图 树 ：是一种特殊的图 无向树 有向树 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 7-7 无向树及其性质 定义7-7.1 连通无回路的无向图称为无向树，简称树,常用T表示树。 平凡图称为平凡树。 若无向图G的每个连通分支都是树，则称G为森林。 在无向树中，度为1的结点称为树叶，度数大于或等于2的结点称为分枝点或内点。 。 。 。 。。 。 。 。 。 。 。。 。 。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 定理7-7.1 设G=V,E是n阶m条边的无向图,则下面各命题是等价的： （1）G是树。 （2）G中任意两个结点之间有且仅有一条路。 （3）G中无回路且m=n-1。 （4）G是连通的且m=n-1。 (5) G是连通的且G中任何边均为桥。 (6) G中没有回路，但在任何两个不同的结点之间加一条新边，在所得的图中得到唯一的一个含新边的圈。 。 。 。 。。 。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 7-8 根树及其应用 1、根树的相关定义 2、根树的性质及应用 ——二叉树、m叉树 3、小结 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 定义7-8.1 设D是有向图，若不考虑D图边的方向时是一棵无向树，则称D为有向树。 V1。 V2。 V5。 V3。 V4。 V6。 V7。 V8。 V9。 如： 结点度 的概念如前所讲 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 设T是n(n ≥ 2)阶有向树，若T中恰好有一个结点的入度为0，其余结点的入度均为1，则称T为根树 定义7-8.2——根树 入度为0的结点称为根 层次最大结点的层次称为树高 入度为1出度为0的结点称为叶 出度不为0的结点称为内点或分枝点 从树根到T的任意结点v的单向通路长度称为v的层次 定义7-8.3：根树包含一个或多个结点，这些结点中某一个称为根，其他所有结点被分成有限个子根树 平凡树也称为根树。 V1。 V2。 V5。 V3。 V4。 V6。 V7。 V8。 V9。 。 。 。 。 。 。 。 。 。 。 。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 由于各有向边的方向一致，故常省略，并且树根在最上方。 V1。 V2。 V5。 V3。 V4。 V6。 V7。 V8。 V9。 V1。 V2。 V5。 V3。 V4。 V6。 V7。 V8。 V9。 。 。 。 。