离散数学(贾振华主编) 第七章 图论.pptVIP

第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 第7章 图论 7.5 哈密尔顿图 7.5.2 哈密尔顿图的判定 定理7.24 当且仅当一个简单图G的闭包是哈密尔顿图时，则 图G是哈密尔顿图。 定理7.25 竞赛图必有哈密尔顿通路。 定理7.26 强连通的竞赛图必有哈密尔顿通路。 7.6 树 7.6.1 无向树 1．无向树的定义与性质 定义7.32 设T是无回路的无向简单连通图，则称T为无向树， 或简称为树。在树中，度数为1的点称为树叶，度数大于1的点 称为内结点或分枝点。 7.6 树 7.6.1 无向树 1．无向树的定义与性质 定理7.27 设T是含n个结点和m条边的简单无向图，则下列各 结论都是等价的，都可作为无向树的定义。 （1）T连通且无回路。 （2）T中任意两个不同的结点间，有且仅有一条通路相连。 （3）T无回路且n=m+1。 （4）T连通且n=m+1。 （5）T连通，但删去树中任意一条边，则变成不连通图。 （6）T连通且无回路，若在T中任意两个不邻接的结点中添加一 条边，则构成的图包含唯一的回路。 7.6 树 7.6.1 无向树 2．生成树与最小生成树 定理7.29 一条回路和任何一棵生成树的补图至少有一条公共边。 定理7.30 有一个边割集和任何生成树至少有一条公共边。 定义7.34 在图的所有生成树中，树权之和最小的生成树，称为最 小生成树。 7.6 树 7.6.1 无向树 2．生成树与最小生成树 定理7.31 设图有n个结点，可用下面的算法产生最小生成树。 （1）选取最小边e1，设边数k=1； （2）若k=n-1，结束，否则转（3）； （3）设已选择边为e1，e2，…，ek，在G中选择不同于e1， e2，…，ek的边ek+1，使ek+1是满足{e1，e2，…，ek，ek+1}中无回 路的权最小的边。 （4）k=k+1，转（2）。 7.6 树 7.6.2 有向树 2．生成树与最小生成树 定义7.35 如果一个有向图的底图为无向树，则该有向图称为有 向树。 定义7.36 在有向树T中，如果有且仅有一个入度为0的点。其他 点的入度均为1，则称有向树T为有根树，简称根树。入度为0的 点称为根，出度为0的点称为树叶或叶片，出度不为0的点称为 分枝点或内结点。 7.6 树 7.6.2 有向树 2．生成树与最小生成树 定义7.37 根树包含一个或多个结点，这些结点中某一个称为根， 其他所有结点被分成有限个子根树。 定义7.38 在根树中，如果每一个结点的出度小于或等于k，则 称这棵树为k叉树。若每一个结点的出度恰好等于k或零，则称 这棵树为完全k叉树，若所有树叶的层次相同，称为正则k叉树 当k=2时，称为二叉树。 7.6 树 7.6.3 周游算法 1．前序周游算法 设需要周游的2叉树为T，其左子树为T1，右子树为T2，则前序周 游算法的递归定义为 （1）访问T的根； （2）用前序周游算法遍历左子树T1； （3）用前序周游算法遍历右子树T2。 7.6 树 7.6.3 周游算法 其递归定义如下： （1）用中序周游算法遍历T的左子树； （2）访问T的根； （3）用中序周游算法遍历T的右子树。 2．中序周游算法 7.6 树 7.6.4 前缀码与最优树 定义7.40 如果在码中，没有一个码字是另一个码字的前缀，则称 这样的码为前缀码。 定理7.32 任意一棵给定的完全2叉树，可以产生唯一的一个二元 前缀码。 定理7.