当前位置：文档之家 › 树与生成树

树与生成树

  • 格式：ppt
  • 大小：685.51 KB
  • 文档页数：38

下载文档原格式

  / 38

合集下载

5_3树的概念和算法

5_3树的概念和算法
第10页
定理.1(证明(3)(4))

Ⅱ、增加任何新边，得到一个且仅有一个回路


若在连通图T中加入新的边(ui,uj)，则该边与T中ui到 uj的一条路构成一个回路，则该回路必是唯一的。 否则（即回路不唯一），若删去此新边，T中必有回 路，得出矛盾。

综述，T连通且e=v-1则T无回路但增加任何新边，得 到一个且仅有一个回路。
第 7页
定理.1(证明(2)(3))
(2) T无回路 且e=v-1 (3) T连通且e=v-1 证明(2)(3)： 证明T连通： (反证法） 假设T有s个连通分支, 则每个连通分支都是连通无 回路即树, 所以 e=e1+e2+…+ es=(v1-1)+(v2-1)+…+(vs-1) =v1+v2+…+vs-s=v-s=v-1, 所以s=1，与s>1矛盾， 所以T连通。

第 6页
定理.1(证明(1)(2))
(1) 无回路的连通图 (2) T无回路且e=v-1 证明(1)(2)： e=v-1(归纳法)：


v=1时,e=0（平凡树）。 设vk-1时成立,即ek-1=vk-1-1。 当v=k时, 要证ek=vk-1。 因为无回路且连通，故至少有一边其一个端点u的度数为 1,设该边为(u,u*）。删除结点u,得到一个k-1个结点的 连通图T’，T’的边数e’=v’-1=(k-1)-1=k-2,于是将结点u 与边(u,v)加入图T’得到原图T，此时T的边数为e=e’+1=k2+1=k-1， 结点数v=v’+1=(k-1)+1=k，故e=v-1。 综上所述， T无回路且e=v-1。

离散数学中的图的树与生成树的计数

离散数学中的图的树与生成树的计数

在离散数学中，图是一个由点和边组成的抽象数学模型。

其中，树是一种特殊的图，它是一个无环连通图。

在图论中，树扮演了重要的角色，它具有许多有趣的性质和应用。

而生成树则是树的一个特殊子集，它由给定图中的所有顶点和部分边构成。

本文将介绍图的树的基本概念，并探讨生成树的计数方法。

首先，让我们来看看图的树。

树是一种无环连通图，其中任意两个顶点之间存在唯一一条路径。

它具有以下性质：1.n个顶点的树有n-1条边。

这可以通过归纳法证明：当n=1时，结论成立；假设n=k时成立，那么n=k+1时，只需要添加一个顶点和一条边，即可构成n=k+1个顶点的树。

因此，结论成立。

2.连接树上任意两个顶点的边都是桥。

即如果一条边被删除，那么树就会变成两个或更多个不相连的子树。

3.树是一个高度平衡的结构。

对于一个n个顶点的树，任意两个叶子结点之间的路径长度至多相差1。

4.树的任意两个顶点之间有唯一一条路径，路径长度为顶点之间的边数。

接下来，让我们来讨论生成树的计数方法。

生成树是树的一个特殊子集，它是由给定图中的所有顶点和部分边构成。

生成树的计数在图论中具有重要的意义和应用。

对于一个具有n个顶点的连通图来说，其生成树的个数可以通过Cayley公式计算得到。

Cayley公式是由亚瑟·凯利于1889年提出的，它给出了完全图的生成树数目。

据此，我们可以得到生成树的计数公式为：T = n^(n-2)，其中T表示生成树的个数。

此外，还有一种常见的计数方法是基于度数矩阵和邻接矩阵的矩阵树定理。

矩阵树定理由高斯于1847年提出，它提供了一种计算图的生成树个数的方法。

根据矩阵树定理，一个无向图G的生成树数目等于该图度数矩阵的任意一个(n-1)阶主子式的行列式的值。

其中，度数矩阵是一个对角矩阵，它的对角线上的元素为各个顶点的度数。

邻接矩阵则是一个关于顶点间连接关系的矩阵，其中1表示相邻顶点之间存在边，0表示不存在边。

除了数学方法，还存在一种基于图的遍历的计数方法，称为Kirchhoff矩阵树定理。

离散数学中的生成树与生成树计数

离散数学中的生成树与生成树计数

离散数学是计算机科学中的重要学科，其中生成树是一个重要的概念。

在图论中，生成树是一棵树，它包含了图中的所有顶点，并且是由图边组成的无环连通子图。

生成树在图论中有着重要的应用，特别是在计算机网络、运筹学和电路设计等领域。

生成树的概念与基础就是组成它的边是有限的，并且连接图中的所有顶点，但没有形成圈回到起点。

生成树通常是用来描述一个系统的最小连接方式。

生成树可以应用于计算机网络的设计中，用于构建最小生成树算法，以便在网络中选择最小的数据传输路径。

此外，在运筹学中，生成树被用于求解最小生成树问题，即为一个加权图找到一棵包含所有顶点的生成树，使得树中边的权重之和最小。

在离散数学中，生成树计数是一个重要的研究分支。

生成树计数是指对给定图，计算其生成树的数目。

生成树计数的问题可以通过使用基于图论和组合数学的算法来解决。

通常，生成树计数的问题与相应图的特性和性质密切相关。

对于一个简单图来说，如果图中任意两点之间至少有一条边，那么该图一定存在生成树。

对于有 n 个顶点的连通图来说，它的生成树数量可以通过Cayley公式计算得到。

Cayley公式表明，一个有 n 个标号的顶点的完全图的生成树数量等于 n^(n-2)。

而对于非完全图，生成树的计数问题则较为困难。

在处理非完全图的生成树计数问题时，可以使用基于递归和动态规划的算法来解决。

一个常见的方法是使用Kirchhoff矩阵树定理，它将生成树计数的问题转化为计算矩阵的行列式的问题。

Kirchhoff矩阵树定理提供了一种计算给定图的生成树数目的有效算法，通过计算图的基尔霍夫矢量的一个特征值，可以得到图的生成树的数目。

另一个常见的方法是使用Prufer编码，它是一个用于描述无环连通图的序列。

通过Prufer编码，我们可以将计算生成树的问题转化为计数树的问题。

通过对无向图进行Prufer编码，我们可以计算出生成树的数目，并且可以根据生成树的数目来确定该无向图的种类和特征。

《离散数学》课件-第16章树

《离散数学》课件-第16章树
解：易见所求为该图的一棵最小生成树，如图所示 总造价为57
18
16.3 根树及其应用
19
定义（有向树）设D是有向图，如果D的基图是无向 树，则称D为有向树。
在有向树中最重要的是根树。 定义16.6（根树）一棵非平凡的有向树，如果恰有 一个顶点的入度为O，其余所有顶点的入度均为1,则称该 树为根树。 入度为0的顶点称为树根，入度为1出度为0的顶点称 为树叶，入度为1出度不为0的点称为内点，内点和树根统 称为分支点。 树根到一个顶点的有向通路的长度称为该顶点的层数。 层数最大顶点的层数称为树高。 平凡树也称为根树。
2
16.1 树及其性质
3
定义16.1（树和森林） 连通且无回路的无向图称为无向树，简称为树，常用
T表示树。 平凡图为树，称为平凡树。 非连通且每个连通分支是树的无向图称为森林。 T中度数为1的顶点（悬挂顶点）称为树叶，度数大于
1的顶点称为分支点。 称只有一个分支点，且分支点的度数为n-1的n（n≥3）
定义16.8（子树）设T为一棵根树，则其任一顶点v 及其后代导若将层数相同的顶点都 标定次序，则称T为有序树。
根据每个分支点的儿子数以及是否有序，可将根树 分成如下若干类：
定义（跟树分类）设T为一棵根树 （1）若T的每个分支点至多有r个儿子，则称T为r叉 树。又若r叉树是有序的，则称它为r叉有序树。 （2）若T的每个分支点恰好有r个儿子，则称T为r叉 正则树。又若r叉正则树是有序的，则称它为r叉正则有 序树。 （3）若T为r叉正则树，且每个树叶的层数均为树高， 则称T为r叉完全正则树。又若r叉完全正则树是有序的， 则称它为r叉完全正则有序树。
8
平均编码长度为：L = ∑ P( i )× l( i ) = 2.53bit i=1

生成树的名词解释

生成树的名词解释

生成树的名词解释生成树（Spanning Tree）是图论中的一个重要概念，用来描述在一个无向连通图中连接所有顶点的极小连通子图。

在一个无向连通图中，如果能够找到一颗包含所有顶点且边数最少的子图，那么这个子图就是该图的生成树。

生成树的概念最早由Otto Schönflies于1885年提出，并且在图论研究和实际应用中得到了广泛的运用。

生成树在电网规划、通信网络设计、计算机网络以及城市交通规划等领域都有着重要的应用价值。

生成树的定义可以用简洁的方式表述：在一个无向连通图中，生成树是保留了原图的所有顶点，但只保留了足够的边来使得这个子图连通，并且不包含任何环的一种连通子图。

换句话说，生成树是一个无向连通图中的极小连通子图，它连接了所有的顶点，并且不存在回路。

生成树具有很多重要的性质和应用。

首先，生成树的边数比原图的顶点数少一个。

这是因为生成树是一个连通子图，而且不包含任何环。

因此，生成树中的边数等于原图的顶点数减去1。

这个性质经常用于生成树的构造和推导。

其次，生成树可以用于表示图中的最小连接网络。

在一个无向连通图中，如果存在多个连通子图，那么通过连接这些子图的最少的边，就可以得到一个生成树。

这个生成树可以看作是一个最小的连通网络，其中所有顶点都能够通过最短路径相互到达。

此外，生成树还可以用于网络设计和优化问题。

在电网规划、通信网络设计和计算机网络中，生成树常常被用于实现信息的传输和路由的优化。

通过构造合适的生成树，可以使得信息的传输路径更加简洁和高效。

生成树有多种构造算法，其中最常用的是Prim算法和Kruskal算法。

Prim算法是一种贪心算法，它从一个任意选定的顶点开始，逐步构建生成树。

具体地，Prim算法每次选择与已有的生成树连接边权值最小的顶点，并将其加入生成树。

重复这个过程，直到生成树包含了所有的顶点。

Kruskal算法是一种基于边的方法，它首先将图中的边按照权值从小到大排序，然后依次将边加入生成树，直到生成树包含了所有的顶点为止。

第八章 图论8.4树及其应用.ppt

第八章 图论8.4树及其应用.ppt

⑥ G中每一对结点之间有惟一一条基本通路。(n≥2)
2017/10/10 82-9
定理4.2.1 分析
直接证明这 6 个命题两两等价工作量太大，一 般采用循环论证的方法，即证明
(1) (2) (3) (4) (5) (6) (1) 然后利用传递行，得到结论。
2017/10/10
证明 TG = <VT, ET> 是 G = <V, E> 的生 分析 必要性：假设 必要性由树的定义即得，充分性利用构造性 成树，由定义 4.2.1 ， TG 是连通的，于是 G 也是连通的。 方法，具体找出一颗生成树即可
充分性：假设G = <V, E>是连通的。如果G中无回 路， G 本身就是生成树。如果 G 中存在回路 C1 ，可删除 C1中一条边得到图G1，它仍连通且与G有相同的结点集。 如果G1中无回路，G1就是生成树。如果G1仍存在回路C2， 可删除 C2 中一条边，如此继续，直到得到一个无回路 的连通图H为止。因此，H是G的生成树。
2017/10/10 82-22
思考题
1、一个图的生成树是不是唯一的呢？
2、如果不是唯一的，3个顶点的无向完全图有几棵 生成树？4个顶点的无向完全图又有几棵生成树？n 个顶点的无向完全图又有几棵生成树？
完全图是边数最 多的简单无向图
2017/10/10
82-23
定理4.2.3
一个图G = <V, E>存在生成树TG = <VT, ET>的充分 必要条件是G是连通的。
由定理4.2.1(4) 在结点给定的无向图中， 由定理4.2.1(5) 树是边数最多的无回路图 树是边数最少的连通图 由此可知，在无向图G = (n, m)中， 若m＜n-1，则G是不连通的 若m＞n-1，则G必含回路

代数结构-树


384
(1，2，5，6) (8，3，4，3)
6
7
离散数学 中国地质大学 计算机学院
18
生成树 (Spanning TCaryeleey定) 理：n个顶点的标号完全图Kn有nn-2棵生成树
384 7
(1，2，5，6，3) (8，3，4，3，8)
离散数学 中国地质大学 计算机学院
19
生成树 (Spanning TCaryeleey定) 理：n个顶点的标号完全图Kn有nn-2棵生成树
w(e1)<=w(e1’)，从而w(T1)<=w(T*)。 依此进行，可以将ek加入到Tk-1中，将形成环，此环中必然然存在边ek’在T*中而不在T中，于是，删除ek’， 则得到生成树Tk。而显然，两边序列e1e2e3…ek 与 e1e2e3…ek’均不构成环，而按kruskal算法，必然有 w(ek)<=w(ek’)， 从而 w(Tk)<= w(Tk-1)<=w(T*) ……， 最后可以将em加入到Tm-1中，得到生成树Tm，且w(Tm)<=…<=w(Tk)<= w(Tk-1)<=… <=w(T1)<=w(T*)。 而此时， T所有边都加入到Tm中，即Tm=T。故w(T)<=w(T*) 因此，T为最小生成树。
(3，2，2，3，4，1)
S:(5，6，7，2，3，4)
5
1
32 6
4
8
7
因此，序列集合{t1,t2,…,tn}与Kn的生成树集合存在双射关系。
离散数学 中国地质大学 计算机学院
29
2 生成树(Spanning Tree) 最小生成树(minimum spanning tree)
算法？ Kruskal算法

离散数学-树

该n元有序树又称n元位置树。2元位置树各分支结点 的左右儿子分别称为左儿子和右儿子。
离散数学导论
. 树
1.2 生成树
➢定义9.10
图T称为无向图G的生成树（spanning tree）， 如果T为G的生成子图且T为树。
✓定理9.17
任一连通图G都至少有一棵生成。
.. 树树
1.2 生成树
✓ 定理9.18
设G为连通无 向图，那么G的 任一回路与任一生 成树T的关于G的补 G – T ，至少有一 条公共边。
1.3 根树
➢ 定义9.15
每个结点都至多有两个儿子的根树称为 二元树（quasibinary tree）。类似地，每个结点都
至多有n个儿子的根树称为n元树。 对各分支结点 的诸儿子规定了次序（例如左兄右弟）的n 元树称
为n元有序树；若对各分支结点的已排序的诸儿子
规定了在图示中的位置（例如左、中、右），那么
弦组成G的一个割集，它被称为枝t-割集（t-cut set）；
而每一条弦e与T中的通路构成一回路，它被称为弦e-回
路（e-circuit）。
. 树
1.2 生成树
✓ 定理9.20
在连通无向图G中，任一回路与任 一割集均有偶数条公共边。
. 树
1.2 生成树
✓ 定理9.21
设G为一连通无向图，T是G的生成树， S = {e1, e2, e3,…,ek}
✓ 定理9.19
设G为连通无 向图，那么G的任 一割集
与任一生成树至少
有一条公共边。
.. 树树
1.2 生成树
➢ 定义9.11
设T为图G的生成树，称T中的边为树枝（branch） 称G – T 中的边为弦（chord）。对每一树枝t，T–t分为

无向树及生成树


一、无向树及其性质
1、 无向树 定义 5-17:不包括回路的无向连通图称为无向树， 简称树,记为 T . （1）两棵以上的图称为森林。 （2）设 T 是树，则 T 的边称为树枝。 （3）树中度数为 1 的结点，称为树叶。 （4）树中度数大于等于 2 的结点称为分支点。
一、无向树及其性质
2、 树的性质 性质 1 设 v1 , v 2 是 T 的两个不同结点， 则连接 v1 , v 2 有 且仅有一条通路，而且这条通路是初级通路。 性质 2 设 v1 , v 2 是 T 的两个结点， 如果 v1 , v 2 不邻接， 则在 T 中添加边 v1 , v 2 后所得的图有且仅有一条回 路，而且这条回路是初级回路。
一、无向树及其性质
2、 树的性质 性质 3 树中任意删除一条边后所得的图是不连通 的。 性质 4 设 T 是 (n, m) 树，则 m n 1。 性质 5 设树 T 的结点数为 n(n 2) ，则至少两片树 叶。
一、无向树及其性质
2、 树的性质
例 5-7：设树 T 中有 7 片树叶，3 个 3 度结点，其余 都是 4 度结点，问: T 中有几个 4 度结点？ 例 5-8．设树 T 中有 1 个 3 度结点，2 个 2 度结点， 其余结点都是树叶，问 T 中有几片树叶？ 例 5-9 画出所有 6 个顶点非同构的无向树。
e1 , e2 ,, em ，它们带的权分别为 a1 , a2 ,, am ，不妨
设 a1 a2 am （1） 一开始取权最小的边 e1 ， 且 w(e1 ) a1 ， 取
e1 在 T 中。
三、求最小生成权的克鲁斯科尔算法
（ 2）若 e2 不与 e1 构成回路，将 e2 添加在 T 中，否 则放弃 e2 ，再查 e 3 ，继续这一过程，直到得到的子 图就是所求的一棵最小生成树 T 为止。

VLAN与生成树和生成树配置

ＶＬＡＮ与生成树和生成树的配置一ＶＬＡＮ与生成树在缺省的ＣＩＳＣＯＳＴＰ模式中，每个ＶＬＡＮ定义一个ＳＴＰ．ＩＥＥＥ８０２．１Ｑ标准是在整个交换ＶＬＡＮ网络中使用一个ＳＴＰ，但并不排除在每个ＶＬＡＮ中实现ＳＴＰ．１ＶＬＡＮ与生成树的关系＞ＩＥＥＥ通用生成树（ＣＳＴ）＞ＣＩＳＣＯＰＥＲＶＬＡＮ生成树（ＰＶＳＴ）＞带ＣＳＴ的ＣＩＳＣＯＰＥＲＶＬＡＮ生成树（ＰＶＳＴ＋）ＣＳＴ是ＩＥＥＥ解决运行虚拟局域网ＶＬＡＮ生成树的方法．ＣＳＴ定义，整个第２层交换网络所有实现了的ＶＬＡＮ，仅使用一个生成树实例．这个生成树实例运行在整个交换局域网上．ＰＶＳＴ是解决在虚拟局域网上处理生成树的ＣＩＳＣＯ特有解决方案．ＰＶＳＴ为每个虚拟局域网运行单独的生成树实例．一般情况下ＰＶＳＴ要求在交换机之间的中继链路上运行ＣＩＳＣＯ的ＩＳＬ．ＰＶＳＴ＋是ＣＩＳＣＯ解决在虚拟局域网上处理生成树问题的另一个方案．ＰＶＳＴ＋允许ＣＳＴ信息传给ＰＶＳＴ，以便与其他厂商在ＶＬＡＮ上运行生成树的实现方法进行操作．２按ＶＬＡＮ生成树（ＰＶＳＴ）为每个ＶＬＡＮ建立一个独立的生成树实例（ＰＶＳＴ）．生成树算法计算整个交换型网络的最佳无环路径．ＰＶＳＴ的优点：＞生成树拓扑结构的总体规模减少．＞改进了生成树的扩展性，并减少了收敛时间．＞提供更快的收敛恢复能力和更高的可靠性．ＰＶＳＴ的缺点：＞为了维护针对每个ＶＬＡＮ而生成的生树，交换机的利用率会更高＞为了支持各个ＶＬＡＮ的ＢＰＤＵ，需要占用更多的ＴＲＵＮＫ链路带宽生成树仅可运行在６４个ＶＬＡＮ上．３公共生成树（ＣＳＴ）ＣＳＴ是ＩＥＥＥ在虚拟局域网上处理生成树的特有方法，这是一种ＶＬＡＮ解决方案，称为单一或者公共生成树．生成树协议运行在ＶＬＡＮ１即缺省的ＶＬＡＮ上．所有的交换机都举出同一个根网桥，并建立与该根网桥的关系．公共生成树不能针对每个ＶＬＡＮ来优化根网桥的位置．公共生成树优点：＞最小数量的ＢＰＤＵ通信，带宽占用少．＞交换机负载保持最小．公共生成树的缺点如下：＞只用一个根网桥，这不能为所有的ＶＬＡＮ做到网桥的优化放置，导致对某些设备来说可能存在次优化路径．＞为包括交换架构中的所有端口，生成树的拓扑结构较大，这就会导致较长的收敛时间和更频繁的重新配置．４增强型的按ＶＬＡＮ生成树（ＰＶＳＴ＋）ＰＶＳＴ＋有以下特征：＞它是ＣＩＳＣＯ发展的，可以与８０２．１Ｑ公共生成树（ＣＳＴ）互操作．＞通过ＩＳＬ中继，ＰＶＳＴ＋与现存的ＣＩＳＣＯ交换机ＰＶＳＴ协议向后兼容，同时，ＰＶＳＴ＋也通过８０２．１Ｑ中继与ＣＳＴ连接互操作．＞如果ＰＶＳＴ区域和ＣＳＴ区域之间要互操作，一定要通过ＰＶＳＴ＋区域．二生成树配置生成树配置涉及下面一些任务：＞选举和维护一个根网桥．＞通过配置一些生成树的参数来优化生成树．（如端口优先级端口成本）＞通过配置上行链路来减少生成树的收敛时间．２９５０交换机上生成树的缺省配置：＞ＳＴＰ启用：缺省情况下ＶＬＡＮ１启用＞ＳＴＰ模式：ＰＶＳＴ＋＞交换机优先级：３２７６８＞ＳＴＰ端口优先级：１２８＞ＳＴＰ路径成本：１０００Ｍ：４１００Ｍ：１９１０Ｍ：１００＞ＳＴＰＶＬＡＮ端口成本：（同上）＞ＳＴＰ计时器：ＨＥＬＬＯ时间：２秒转发延迟：１５秒最大老化时间：２０秒１启用生成树：switch(config)#spanning-tree vlan vlan-list步骤：switch#config tswitch(config)# spanning-tree vlan 10switch(config)#endswitch#show spanning-tree summary(detial)summary摘要detial详细Bridge Identifier has priority 8912,address 0006.eb06.1741 (本地交换机网桥ＩＤ）desigated root has priority 8912,address 0006.eb06.1741 (根网桥ＩＤ）designated port is 7,path cost 0 (路径成本）times: hold1, topology change 35, notification 2hello 2, max age 20, forward delay 15 （根计时器）２人为建立根网桥在生成树网络中，最重要的事情就是决定根网桥的位置．可以让交换机自己根据一定的原则来选择根网桥以及备份或从（secondary）根网桥，也可使用命令人为指定根网桥．ＰＳ：不要将接入层的交换机配置为根网桥．ＳＴＰ根网桥通常是汇聚层或者核心层的交换机．通过命令直接建立根网桥：spanning-tree vlan vlan-id root primary步骤：switch#config terminalswitch(config)#spanning-tree vlan vlan-id root primary dianmeternet-diameter hello-time sec为ＶＬＡＮ配置根网桥网络半径以及ＨＥＬＬＯ时间ＲＯＯＴ关键字：指定这台交换机为根网桥diameter netdianmeter：该关键字指定在末端口主机任意两点之间的网段的最大数量．net-diameter的值是２－７．这个直径应该从根网桥开始计算，根网桥是１switch(config)#endswitch#show spanning-tree vlan vlan-id detail让交换机返回缺省的配置，可以使用如下命令：no spanstree vlan vlan-id root２＞修改网桥的优先级别：多数情况下做如下配置：spanning -tree vlan vlan-id root primary （主ＲＯＯＴ）spanning-tree vlan vlan-id root secondary（备份ＲＯＯＴ）修改网桥优先级：spanning-tree vlan vlan-id priority bridge-priority３确定到根网桥的路径生成树协议依次用ＢＰＤＵ中这些不同域来确定根网桥的最佳路径：＞根路径成本（ＲＯＯＴＰＡＴＨＣＯＳＴ）＞网桥ＩＤ（ＢＲＩＤＧＥＩＤ）＞端口优先级（ＰＯＲＴＰＲＯＩＲＩＴＹ）从端口发出ＢＰＤＵ时，它会被施加一个端口成本，所有端口成本的总和就是路径成本．生成树首先查看路径成本，以确定哪些端口应该转发，哪些端口应该阻塞．报告最低路径成本的端口被选为转发端口．如果对多个端口来说，其中路径成本相同，那么，生成树将查看网桥ＩＤ．报告有最低网桥ＩＤ的ＢＰＤＵ端口被允许进行转发，而其他所有端口被阻断．如果路径成本和网桥ＩＤ都相同（如在平行链路中），生成树将查看端口ＩＤ．端口ＩＤ低的优先级高，将作为转发端口．４修改端口成本如果想要改变某台交换机和根之间的数据所走的路径，就要仔细计算当前的路径成本，然后，改变所希望路径的端口成本．我们可以更改交换机端口的成本，端口成本更低的端口更容易被选为转发帧的端口．spanning-tree vlan vlan-id cost costno spanning-tree vlan vlan-id cost(删除)配置步骤：＞１config terminal 进入配置状态＞２interface interface-id 进入端口配置界面＞３spanning-tree vlan vlan-id cost cost值为某个ＶＬＡＮ配置端口成本＞４end＞５show spanning-tree interface interface-id detail查看配置＞６write５修改端口优先级在路径成本和网桥ＩＤ都相同的情况下，有最低优先级的端口将为vlan转发数据帧．对应基于ＣＬＩ的命令的交换机，可能的端口优先级别范围为０～６３，缺省为３２．基于ＩＯＳ的交换机端口的优先级别范围是０～２５５，缺省为１２８．spanning-tree vlan vlan-id port-priority priority值no spanning-tree vlan vlan－id port-priority１＞config terminal 进入配置状态２＞interface interface-id 进入端口配置界面３＞spanning-tree vlan vlan-id port-priority４＞end５＞show spanning-tree interface interface-id detail６＞write６修改生成树计时器使用缺省的ＳＴＰ计时器配置，从一条链路失效到另一条接替，需要花费５０秒．这可能使网络存取被耽误，从而引起超时，不能阻止桥接回路的产生，还会对某些协议的应用产生不良影响，会引起连接、会话或数据的丢失。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
|E(T1)|=|V(T1)|-1， |E(T2)|=|V(T2)|-1 故m=|E(T1)|+|E(T2)|+1
=|V(T1)|-1+ |V(T2)|-1+1 =n-1。
⑸ T连通的且m=n-1.
⑹ T无回路且m=n-1.
⑸⑹:只需证明T无回路。对T关于顶点 数归纳。
当n=1或n=2时，显然成立。
八.遍历二叉树 在二叉树的一些应用中, 常常要在树中查找具有某些
特征的结点,或者对所有结点逐一进行某种处理, 这就提 出了遍历二叉树问题. 即按照一定规律巡访树中每个结点 一次.
由于二叉树是一个非线性结构, 每个结点都可能在左右 两棵子树上, 为此要寻找一种规律, 以便使二叉树上结点 的信息排成一个线性队列上, 从而便于遍历.
⑷ T连通的,且每条边都是割边.
⑸ T连通的且m=n-1.
⑷⑸:关于点数用归纳法证明。
当n=1或2时，T是平凡图或K2，显然有m=n-1。 假设nk时结论成立，往证n=k+1时成立。
当n=k+1时。取T的一条边e，由⑷，e是割边，
所以T-e有两个分支T1和T2， 因为|V(T1)|k, |V(T2)|k, 所以，由归纳假设，有
⑴后序遍历左子树
⑵后序遍历右子树
⑶访问根结点.
后序遍历:32x2－×－x3x＋÷＋
九. 最优树(哈夫曼树 Huffman)
二叉树的一个重要应用就是最优树.
1.带权二叉树的定义:设有一组权值:w1, w2, w3,… , wm, 不仿设w1≤w2≤w3≤…≤wm, 设有一棵二叉树有m片 叶子,分别带有权值w1, w2, w3,… , wm,称此树为带权二 叉树.
此树是m叉树.
2.完全m叉树:在根树中,如果每个结点的出度都是m或者
等于0, 则称此树是完全m叉树.
3. 正则m叉树:在完全m叉树中,如果所有树叶的层次相 同,
则称之为v1 正 则m叉树. v1
v1
v2
v3 v2
v3 v2
v3
v4 v5 v6 v4 v5
N
取ej使得
ai=ej i=i+1
S∪{ ej}有回路?
|S|=n-1, 说明是树
Y
最后S={a1, a2, a3,… ,an-1}
j=j+1
边按升序排序:边(vi, vj)记成eij 边 e28 e34 e23 e38 e17 e24 e45 e57 e16 权1 1 2 2 2 3 3 3 4
a:b
<
=
a:c
a:c
> a:cFra bibliotek<=
< =>
=>
a轻 b重 c重 a:d c轻 b轻 a重
< => d重 全真 d轻
d)搜索树:八数码游戏:
283 164
75
283 64
17 5
283 14
765
…………………..
搜索策略: 宽度优先, 深度优先, 启发式搜索,….
Step2. 构造[Sk , Sk ], 若[Sk , Sk ] , 则G不连
通, 停止. 否则, 设
w(ek ) min w(e) ek vk vk' , vk Sk .

e[Sk , Sk ]

令
S k 1

Sk

{v
' k
},
Ek1 Ek {ek }.
置k=k+1. 返回Step1.
1.每个结点保留左儿子结点, 剪掉右边其分支. 被剪掉 的结点如下处理(重新嫁接). 2.同一个层次的结点, 从左到右依次画出(被剪掉的结 点 嫁接到它的哥哥结点上).
r
a
b
c d e f g h i jk l
r
a
b
c d e f g
h
i j k l
3.分支结点(内结点):度数大于1的结点. (b)
4.森林:一个无向图的每个连通分支都是树.如(b)
5.与树定义等价的几个命题 定理1给定图T, 以下关于树的定义是等价的. ⑴ T无回路的连通图. ⑵T无环且每对结点之间有一条且仅有一条路. ⑶ T无回路但在任一对不相邻的顶点间添加一条
新边e，则T+e包含唯一的回路. ⑷ T连通的,且每条边都是割边. ⑸ T连通的且m=n-1. ⑹ T无回路且m=n-1. 证明:⑴⑵:已知T是连通无回路图,所以T中无环。
v1 8 v8 7 v5 3 v4
4 2 v7 4
34 6 6 v6
Kruskal算法: 设G是有n个结点,m条边(m≥n-1)的连通 图. S=Φ i=0 j=1
将所有边按照权升序排序: e1, e2, e3,… ,em
S=S∪{ai} j=j+1
|S|=n-1 Y 输出S 停 N
v4 v5 v6 v7
定理1 T是棵完全m叉树, 有t个叶结点, i个分支结点,
则(m-1)i=t -1 . 证明:T的所有结点的出度总和为 mi. 入度总和(i-1)+t. 故 mi=i-1+t 所以(m-1)i=t-1
七. m叉有序树转化成二叉树 因为二叉树便于存贮, 也便于处理, 所以通常可以将多叉 树化成二叉树.方法是:
最小生成树很有实际应用价值.例如结点是城市名,边的权
表示两个城市间的距离, 从一个城市出发走遍各个城市,
如何选择最优的旅行路线.又如城市间的通信网络问题,如
何布线,使得总的线路长度最短.
例如:右图所示 2.求最小生成树算法 ---Kruskal算法: (贪婪算法)
v2 71
2 3 2
v3 51
v7
的一条边,则称vi是vj的父结点, vj是vi的子结点.
5.祖先结点与后裔结点: 在根树中,如果从vi到vj有路,则 称
vi是vj的祖先结点, vj是vi的后裔结点. 6.根树结点的层次:从根结点到某个结点的路径的长度,称
为该结点的层次. 同一层次的结点称为兄弟结点.
7.树高:从树根到各个叶结点的路径中, 最长路径的长度,
v2
v3
如果G中有回路,可以通过反复删去回路 v4
v5
中的边,使之既无回路,又连通.就得到生成树.
思考题:设G是有n个结点,m条边的连通图, 问要删去多少
条边,才得到一棵生成树?
三.赋权图的最小生成树
1.定义:一棵生成树中的所有边的权之和称为该生成树的
权. 具有最小权的生成树,称为最小生成树.
称为该树的高度(树高).
三.举例: a)语法树
主语
句子
谓语短语
冠词 形容词 名词 动词
宾语


The little boy
b)算术表达式树
((a+b)÷c)×(d－e) ÷
冠词 saw
The
×
－
名词
apple
+
c d e
a b
c)判定树:有四枚金币a,b,c,d,已知道三个是真的,最多一 个是假的,它们的外表完全相同,只是重量有点差别.给你 一架天平找出假币.
⑷ T连通的,且每条边都是割边.
⑵⑶:显然T无回路，否则对回路上的任一对顶 点都至少存在两条路，与⑵矛盾。设u，v是T 中任意两个不相邻的点，令e=uv，由⑵，T中 有一条唯一的u-v路，所以T+e中包含唯一的回 路。
⑶⑷:因为T无回路，所以T的每条边都是割边； 若T不连通，设T1，T2是T的两个分支，设 uV(T1), vV(T2), 则uvE(T)，显然T+uv 不存在回路，与⑶矛盾。
假设nk时结论成立，往证n=k+1时成 立。
因为T连通，所以(T)1，由m=n-1及 d(v)=2m得，T中至少存在一点u，使 得d(u)=1。考虑T’=T-u，显然T’连通， 且|E(T’)|=|V(T’)|-1，由归纳假设，T’ 无回路，所以T无回路。
⑹ T无回路且m=n-1. ⑴ T无回路的连通图. ⑹k由⑴⑹2:得。假，对设任T不意连的通Ti，，设Ti是T1无, T回2,路…,的T连k为通T图的，连所通以分T支i是，树则，
例：求图G的最小生成树。 v2
1
3
v1
2
4 4
v4 2
v5
2
4
v3
破圈法
----Prin算法的对偶方法. 最适合于在图 上作业. 当图比较大时, 还可以几个人同 时在各个局部作业.
Step0. 令G0=G. k=0.
Step1. 若Gk不含圈, 转Step2. 若Gk中
含有圈C.
v6
Prin算法(边割法)
实质: 在n-1个边割集中, 取每个边割集的一条 权最小的边, 构成G的一个生成树.
定义：[Sk , Sk ] {uv | u Sk，v Sk}。 Step0. 设v为V的任一顶点. 令S0={v}, E0=,
k=0.
Step1. 若Sk=V, 结束. 以Sk为点集, Ek为边集 的图即是G的最优树. 否则转Step2.
v6 v5
二.根树:如果一棵有向树,恰有一个结点的入度为0,其余
所有结点的入度均为1,则称此树为根树.
v1
1.树根:入度为0的结点. 2.叶:出度为0的结点.
v2
v3
3.分支结点(内结点):出度不为0的结点. v4 v5 v6
4.父结点与子结点:如果<vi,vj>是根树中
有三种遍历方式 1.先序遍历 2.中序遍历 3.后序遍历
1.先序遍历 ⑴访问根结点. ⑵先序遍历左子树
+