当前位置：文档之家 › 第9讲 生成树

第9讲 生成树

  • 格式：ppt
  • 大小：1.38 MB
  • 文档页数：53

下载文档原格式

  / 53

合集下载

生成树协议原理

生成树协议原理

生成树协议原理生成树协议是一种基于链路层的协议，它通常在以太网交换机上实现，用于管理以太网局域网中的网络拓扑。

生成树协议的工作原理是通过使用一个根桥（Root Bridge）和多个非根桥（Non-Root Bridge）来建立一颗树状结构，以确保网络中没有环路存在。

生成树协议的核心算法是通过一种称为生成树算法（Spanning Tree Algorithm）来找到从根桥到每个非根桥的最短路径，从而构建一颗最小生成树。

最小生成树是一种能够连接所有节点并且没有环路的树状结构，它是生成树协议的基础，用于确定网络中数据包的传输路径。

生成树协议的工作流程包括以下几个关键步骤：1. 选择根桥：在网络中通过比较桥（Bridge）的优先级和MAC地址来确定根桥，根桥是生成树中的根节点，所有数据包都将通过根桥进行转发。

2. 计算生成树：每个非根桥通过生成树算法计算到根桥的最短路径，确定自己在生成树中的位置，并将该信息传播到整个网络中。

3. 确定端口状态：每个桥根据生成树信息确定哪些端口可以用于数据包的传输，哪些端口需要阻断以避免环路的产生。

4. 更新生成树：在网络拓扑发生变化时，生成树协议会重新计算生成树，并更新每个桥的状态，重新确定最佳路径。

5. 数据包转发：根据生成树确定的路径，数据包会被从源地址传输到目的地址，通过生成树结构保证数据包的正常传输。

生成树协议的优点是可以有效避免数据包在网络中的循环传输，提升网络通信的稳定性和可靠性。

生成树协议能够自动适应网络拓扑的变化，快速重新计算生成树，并重新确定最佳传输路径，从而保证网络快速恢复到正常状态。

然而，生成树协议也存在一些局限性。

生成树协议在网络中设置大量的桥和端口时，会造成网络拓扑复杂，生成树的计算和更新会消耗大量的网络资源。

此外，生成树协议需要在所有交换机上进行配置和管理，当网络规模较大时，配置和管理网络可能会变得困难。

为了解决生成树协议的一些局限性，IEEE制定了一系列的生成树协议标准，包括802.1D、802.1w和802.1s等。

c2-3

c2-3


树
树
树
树
树
进一步思考：若从 进一步思考：若从K4中任去一边 e ，其生成 树棵数是多少？ 树棵数是多少？
τ ( K4 − e) = ?
τ ( Kn − e) = ?
τ ( Kn − e) = (n − 2)nn−3
树
进一步思考续….. 进一步思考续 .. 画出K 的所有非同构生成树。 画出 4的所有非同构生成树。 求如下图的所有非同构生成树。 求如下图的所有非同构生成树。
树
2 1 4
6
4 2，4， 5，5， ， ， ， ，
5 3
7
树
2，4，5，5，4 ， ， ， ，
2 4 1 5
4，5，5，4 ， ， ，
2 4 1 5
树
5，5，4 ， ，
2 4 1 3 5
5，4 ，
6 2 4 1 3 5
树
4
6 2 4 1 3 5 1 3 2 4 5 6
7
树
画出K 的所有生成树。 画出 4的所有生成树。
树
§2.3 生成树 定义1 定义 生成树 每个连通图至少包含一棵生成树 生成树的构造－－破圈法 生成树的构造－－破圈法 －－ 图G的生成树棵数计算 的生成树棵数计算
τ (G ) = τ (G − e ) + τ (G e )
树
τ(G)=
=
+
=(
+
)+(
树
+
)=
+(
+
) + (
+
) + (
+
)
树
树
更一般的呢？ 更一般的呢？ τ(Kn)=？ ？
最小生成树(Kruskal算法)

最小生成树(Kruskal算法)


三、方案解决：
在本题中我们将采用 Kruskal 算法来构造最小生成树。 从题目所给赋权图中我们可以得到该图的邻接矩阵为：
⎡ 0 20 0 0 0 23 1 ⎤ ⎢20 0 15 0 0 0 4 ⎥ ⎢ ⎥ ⎢ 0 15 0 3 0 0 9 ⎥ ⎢ ⎥ G = ⎢ 0 0 3 0 17 0 16 ⎥ ⎢ 0 0 0 17 0 28 25⎥ ⎢ ⎥ ⎢ 23 0 0 0 28 0 36⎥ ⎢ 1 4 9 16 25 36 0 ⎥ ⎣ ⎦
-3-
6.选择造价第五小的序号为 5 的边，即 S 23 ，由于加入后边 S 23 ， S 27 ， S37 将构成回路，因此 舍弃该边 如图所示：
7.选择造价第六小的序号为 6 的边，即 S 47 ，由于加入后边 S34 ， S37 ， S 47 将构成回路，因此 舍弃该边 如图所示：
8.选择造价第七小的序号为 7 的边，即 S 45 ，加入 T 中，此时 T={{6},{ S17 ， S34 ， S 27 ， S37 ，
S 45 ， S16 }}，Cost=34+23=57
如图所示：
11.算法结束 此时，所有顶点已包含在树中，整棵最小生成树已经构造完成。即应该在城市{（1,7） ， （2,7） ， （3,7） ， （3,4） ， （4,5） ， （1,6）}之间建造通信道路，可使得城市间相互通信又造价费 用最小，此时可以得到其最小的费用为 57 万元
-7-
edges[k].end = j; edges[k].weight = G->arc[i][j].weight; k++; } } } sort(edges, G); for (i = 1; i <= G->arcnum; i++) { parent[i] = 0; } printf("最小生成树为:\n"); for (i = 1; i <= G->arcnum; i++)//核心部分 { n = Find(parent, edges[i].begin); m = Find(parent, edges[i].end); if (n != m) { parent[n] = m; printf("< %d, %d > %d\n", edges[i].begin, edges[i].end, edges[i].weight); Mincost+=edges[i].weight; } } printf("使各城市间能够通信的最小费用为：Mincost=%d\n",Mincost); } int Find(int *parent, int f) { while ( parent[f] > 0) { f = parent[f]; } return f; }
生成树协议详解

生成树协议详解

⽣成树协议详解⽣成树协议详解⽣成树协议是由Sun微系统公司著名⼯程师拉迪亚?珀尔曼博⼠(Radia Perlman)发明的。

⽹桥使⽤珀尔曼博⼠发明的这种⽅法能够达到2层路由的理想境界:冗余和⽆环路运⾏。

你可以把⽣成树协议设想为⼀个各⽹桥设备记在⼼⾥的⽤于进⾏优化和容错发送数据的过程的树型结构。

我们要介绍的这个问题在图1中进⾏了描述。

图1.如果这些交换机不采⽤⽣成树协议并且以这种⽅式连接，每⼀台交换机将⽆限地复制它们收到的第⼀个数据包，直到内存耗尽和系统崩溃为⽌。

在2层，没有任何东西能够阻⽌这种环路的事情发⽣。

在图1中，管理员必须要⼿⼯关闭这个红⾊连接线路才能让这个以太⽹⽹络运⾏。

⽣成树协议在当前可⽤连接有效时关闭⼀个或者更多其它冗余连接，⽽在当前连接出现故障后，再启⽤这些被关闭的冗余连接。

⽣成树协议决定使⽤哪⼀个连接完全取决于⽹络的拓扑结构。

⽣成树协议拓扑结构的思路是，⽹桥能够⾃动发现⼀个没有环路的拓扑结构的⼦⽹，也就是⼀个⽣成树。

⽣成树协议还能够确定有⾜够的连接通向这个⽹络的每⼀个部分。

它将建⽴整个局域⽹的⽣成树。

当⾸次连接⽹桥或者发⽣拓扑结构变化时，⽹桥都将进⾏⽣成树拓扑的重新计算。

当⼀个⽹桥收到某种类型的“设置信息”(⼀种特殊类型的桥接协议数据单元，BPDU)时，⽹桥就开始从头实施⽣成树算法。

这种算法从根⽹桥的选择开始的。

根⽹桥(root bridge)是整个拓扑结构的核⼼，所有的数据实际上都要通过根⽹桥。

顺便提⽰⼀下，有⼿⼯设置根⽹桥时要特别注意。

对于思科设备来⾔其根⽹桥的选择过程暴露出⼀些问题，就是过分简单化。

思科硬件通常使⽤最低的MAC地址，具备这些地址的设备通常是⽹络中最古⽼的设备，因⽽其交换速度常是最慢的，⽽从根⽹桥在⽹络中的位置看，它负荷却最重。

⽣成树构建的下⼀步是让每⼀个⽹桥决定通向根桥的最短路径，这样，各⽹桥就可以知道如何到达这个“中⼼”。

这⼀步会在每个局域⽹进⾏，它选择指定的⽹桥，或者与根桥最接近的⽹桥。

离散数学课件_9 树与平面图

离散数学课件_9 树与平面图


1.概念:有向树,根树,树叶,内点,分支
点,层数,树高,祖先,后代,父亲,儿子,
兄弟,有序树,m叉树,完全m叉树,根子树,
左子树,右子树,带权二叉树,最优二叉
树,前缀,前缀码,二元前缀码,二叉树遍
历等;
4
返回本章首页
2019/12/4
第三节 有向树与根树(2)
2.定理: 设T是一棵根树，r是T的树根,则 对于T的任一顶点v,存在唯一的有向路 从r到v；
3.算法:最优二叉树的Huffman算法;
4.前缀码问题:前缀码与二叉树的对应关 系；
5.二叉树的遍历:三种遍历方法,即先根遍 历,中根遍历,后根遍历法.
返回本章首页
5 2019/12/4
第四节 平面图
平面图是很多实际问题的模型. 例如在 集成电路的布线设计中就遇到了平面图 的问题.
1.基本概念:平面图,平面嵌入,面,无限 面(外部面),内部面,边界,次数等;
第九章 树与平面图
树是一类结构较为简单的图，是用途极 为广泛的离散数学模型，特别是二叉树， 它在计算机科学中用得最多.因此在学习 时应很好地掌握好诸如树的充要条件、 生成树、最优生成树、根树、树的各种 算法、及二叉树的访问次序等内容.平面 图是实际背景很强的一类图，能用本章 介绍的方法判断一个图是否为平面图.
2.基本非平面图:K3,3与K5； 3.平面图的欧拉公式； 4.平面图的判定:库拉图斯基定理.
返回本章首页
6 2019/12ቤተ መጻሕፍቲ ባይዱ4
本章小结
本章我们介绍树与平面图，但以介绍树 为主.给出树的定义及树的充要条件， 生成树、最优生成树及最优生成树的克 鲁斯卡尔算法，特别是二叉树，我们讨 论 了 二 叉 树 的 Huffman 算 法 、 前 缀 码 、 二叉树的遍历等问题.最后介绍了一类 实际背景很强的一类图——平面图.
第二章 生成树

第二章 生成树

第二章树教学安排的说明章节题目：§2.1树的特性；§2.2割边与割点，§2.3生成树学时分配：共2课时本章教学目的与要求：会正确表述关于树的一些基本概念（如树、生成树、割边与割点），会用避圈法和破圈法找生成树，会用树的方法描述一些简单的实际问题．课 堂 教 学 方 案课程名称：§2.1树的特性；§2.2割边与割点；§2.3 生成树授课时数：2学时授课类型：理论课教学方法与手段：讲授法教学目的与要求：会正确表述关于树的一些基本概念（如树、生成树、割边与割点），会用避圈法和破圈法找生成树，会用树的方法描述一些简单的实际问题． 教学重点、难点：（1） 理解树的概念以及树的等价命题；（2） 掌握割边与割点的概念；（3） 理解生成树的定义；（4） 掌握找生成树的两种方法——避圈法和破圈法。

教学内容：树是图论中的一个重要概念。

树是一种极为简单而又非常重要的特殊图，它在计算机科学以及其它许多领域都有广泛的应用。

在1847年克希霍夫就用树的理论来研究电网络，1857年凯莱在计算有机化学中222n C H 的同分异构物数目时也用到了树的理论。

各类网络的主干网通常都是树的结构。

本节介绍树的基本知识，其中谈到的图都假定是简单图。

2.1 树的特性定义2.1.1 连通无圈的无向图称为无向树，简称为树（Undirected tree ）。

记作T ，树中的悬挂点（或称T 中度数为1的顶点）又称为树叶（leave ）（或叶顶点），其它顶点称为树枝（Branch Point 或内点(Inner Point)）。

诸连通分支均为树的图称为森林（forest ），树是森林。

例1 图1中（a ），（b ）为树，（c ）为森林。

图1由于树无环也无重边（否则它有圈）,因此树必定是简单图。

树还有等价命题：设T 是一个无向(,)n m 图，则以下关于T 的命题是等价的。

(1) T 是树；（2）T 无圈且1m n =-；(3) T 连通且1m n =-；（4）T 无圈，但增加任一新边，得到且仅得到一个圈。

图论生成树的概念与性质PPT课件

图论生成树的概念与性质PPT课件

充分性 如果Am的列对应的边作成G的一棵生成树，因树是连通的，所以，它对应的 基本关联矩阵Am非奇异。
该定理给出了求连通图G的所有生成树的方法：
(1) 写出G的关联矩阵，进一步写出基本关联矩阵，记住参考点；
8
第8页/共32页
(2) 找出基本关联矩阵的非奇异主子阵，对每个这样的主子阵，画出相 应的生成树。
第19页/共32页
n 2 1
C
1
n 1
0 1
于是由矩阵树定理：
0
1
n 2
n 1 1 1 n 1 (Kn e) 1 1 1 1
1 1 1 1
n 1 1 1 n 2
n 1 1
1 1 n 1 1
1 0
1 n 1 1 1 1 n 1 1 0
1 1 n 1 1 1 1 n 1 0
1 1
例6 求下图G的回路空间的一个基底和它的全部元素。
25
第25页/共32页
a
f
cd
g
e
b
h
G
解：取G的一棵生成树T为：
a
d
g
b T
G对于生成树T的基本回路为：
C1 ,b, d, g, h C4 d, f , g
26
第26页/共32页
图形为：
a c
b
利用破圈法，显然也可以求出任意图的一个生成森林。
3
第3页/共32页
推论 若G是(n, m)连通图，则m≧n-1 连通图G的生成树一般不唯一！
(二)、生成树的计数
1、凯莱递推计数法 凯莱(Cayley 1821—1895): 剑桥大学数学教授，著名代数学家，发表
论文数仅次于Erdos ,Euler, Cauchy. 著名成果是1854年定义了抽象群，并 且得到著名定理：任意一个群都和一个变换群同构。同时，他也是一名出 色的律师，作律师14年期间，发表200多篇数学论文，著名定理也是在该 期间发表的。
最小生成树算法及应用

最小生成树算法及应用


最小生成树算法及应用
二、求图的最小生成树算法小结 Prim算法和Kruskal算法 三、应用举例
例2、最优布线问题（wire.???） 学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们时 间有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。
算法分析
2、套用最小生成树的经典算法求解
以机器蛇为顶点，以不受屏蔽的通信线路为边构建图，就可以直 接套用最小生成树的经典算法求解。由于几乎每两条机器蛇间都 会有一条边，因此应选用Prim算法。
设


const maxn=200 ； oo=2000000000；{ 机器蛇数的上限和无穷大} type TPoint=record {坐标} x，y：longint； end； var s，w1，w2：array[1..maxn] of TPoint； { 机器蛇的坐标和屏蔽线的坐标 } n，m，i，j，k：integer； ba：array[1..maxn] of boolean； { 机器蛇的访问标志} d：array[1..maxn] of longint； {d[i]以机器蛇i为头的最短边长} min：longint； ans：double；
题目中要求信息可以在任意两条机器蛇间传递、通讯网 络的总长度要尽可能的短，显然这是一个求图的最小生 成树问题。这道题在构造图的过程中还涉及到一点计算 几何的知识。 1、判断线段相交 两条线段AB、CD，相交的充要条件是：A、B在直线CD 的异侧且C、D在直线AB的异侧。也就是说从AC到AD的 方向与从BC到BD的方向不同，从CA到CB的方向也与从 DA到DB的方向不同。
机器蛇
生成树算法的三个步骤

生成树算法的三个步骤

生成树算法的三个步骤生成树是图论中的重要概念，它描述了一个连通图的一个子图，该子图包含了图中的所有顶点，并且是无环的。

生成树算法是用来找到一个连通图的生成树的一种方法。

本文将介绍生成树算法的三个步骤：图的遍历、边的选择和生成树的构建。

一、图的遍历图的遍历是生成树算法的第一步，它的目的是将图中的所有顶点访问一遍。

常用的图的遍历算法有深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索是通过递归的方式进行遍历，从某个顶点开始，先访问它的一个邻接顶点，然后再递归地访问该邻接顶点的邻接顶点，直到所有顶点都被访问过。

广度优先搜索是通过队列的方式进行遍历，从某个顶点开始，先访问它的所有邻接顶点，然后再依次访问这些邻接顶点的邻接顶点，直到所有顶点都被访问过。

二、边的选择边的选择是生成树算法的第二步，它的目的是选择一些边，使得这些边构成一个连通图的生成树。

常用的边的选择算法有最小生成树算法和最大生成树算法。

最小生成树算法的目标是选择一些边，使得这些边的权值之和最小。

常用的最小生成树算法有普里姆算法和克鲁斯卡尔算法。

普里姆算法是从一个顶点开始，每次选择一条最小权值的边，将该边连接的顶点加入到生成树中，直到所有顶点都被加入到生成树中。

克鲁斯卡尔算法是先将所有边按照权值从小到大排序，然后依次选择权值最小的边，如果这条边连接的两个顶点不在同一个连通分量中，则将这条边加入到生成树中。

最大生成树算法的目标是选择一些边，使得这些边的权值之和最大。

常用的最大生成树算法有逆克鲁斯卡尔算法和逆普里姆算法。

逆克鲁斯卡尔算法和逆普里姆算法的原理与克鲁斯卡尔算法和普里姆算法相反。

三、生成树的构建生成树的构建是生成树算法的第三步，它的目的是根据选择的边构建一个生成树。

生成树可以用邻接矩阵或邻接表来表示。

邻接矩阵是一个二维数组，其中的元素表示两个顶点之间是否有边。

邻接表是一种链表的数据结构，其中的每个节点表示一个顶点，节点的值表示该顶点的邻接顶点。

树的诞生故事(数学)

树的诞生故事(数学)

树的诞生故事(数学)【最新版4篇】目录（篇1）1.引言：介绍树的概念及其在数学中的应用2.树的基本结构：节点、边、叶子节点、度、生成树等3.树的种类：满二叉树、完全二叉树、平衡二叉树（AVL 树）和二叉搜索树4.树的遍历：前序遍历、中序遍历和后序遍历5.树的应用：图论、数据结构和算法6.结论：总结树的重要性和在数学领域的发展正文（篇1）树的诞生故事 (数学)树的概念在生活中非常常见，它既是生物学中的基本结构，也是数学中的一个重要研究对象。

在数学领域，树被广泛应用于图论、数据结构和算法等方面，为我们理解和解决许多实际问题提供了有力的工具。

接下来，我们将探讨树的诞生故事，了解其在数学中的基本结构、种类和应用。

首先，让我们来了解一下树的基本结构。

在数学中，树是由节点（vertex）和边（edge）组成的一种非线性数据结构。

树的节点表示元素，边表示元素之间的关系。

树中还存在叶子节点（leaf node），即没有子节点的节点。

度（degree）是树中节点的子节点数量，根节点的度为 0，而叶子节点的度为 1。

生成树（spanning tree）是指一个树覆盖一个图的所有节点，且保持图的连通性。

接下来，我们来探讨树的种类。

满二叉树是一种特殊的完全二叉树，它的每一层都充满了节点，且最后一层可能不完全填充。

完全二叉树是一种特殊的平衡二叉树（AVL 树），它的每一层都充满了节点，且最后一层可能不完全填充。

平衡二叉树是一种保持左右子树高度差不超过 1 的二叉树，它的调整操作使其保持平衡。

二叉搜索树是一种特殊的平衡二叉树，它的左子树中的所有节点的值都小于根节点的值，右子树中的所有节点的值都大于根节点的值。

在树的遍历方面，有前序遍历、中序遍历和后序遍历三种方式。

前序遍历是指先访问根节点，然后遍历左子树，最后遍历右子树。

中序遍历是指先遍历左子树，然后访问根节点，最后遍历右子树。

后序遍历是指先遍历左子树，然后遍历右子树，最后访问根节点。

无向树及生成树

无向树及生成树

解设T的阶数为n,则边数为n1, 4度顶点的个数为n7.由握手定理得
2m=2(n1)=51+21+31+4(n7)
解出n=8, 4度顶点为1个.
T的度数列为1,1,1,1,1,2,3,4
有3棵非同构的无向树
生成树
生成树的存在性
定理任何无向连通图都有生成树.
证用破圈法.若图中无圈,则图本身就是自己的生成树.
否则删去圈上的任一条边,这不破坏连通性,重复进行
直到无圈为止,剩下的图是一棵生成树.
推论1设n阶无向连通图有m条边,则mn1.
推论2设n阶无向连通图有m条边,则它的生成树的余树
有mn+1条边.
基本回路与基本回路系统
定义设T是n阶m条边的无向连通图G的一棵生成
树，设e1, e2, … , emn+1为T的弦.设Cr为T添加弦er
（1）G是树(连通无回路);
（2）G中任意两个顶点之间存在惟一的路径;
（3）G中无回路且m=n1;
（4）G是连通的且m=n1;
（5）G是连通的且G中任何边均为桥;
（6）G中没有回路,但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈.
下次课预习要点：
有向树
根树、树根、树叶、内点、分支点
设G=<V,E,W>,将非环边按权从小到大排序：e1, e2, …, em.
(1)取e1在T中
(2)检查e2,若e2与e1不构成回路,则将e2加入T中,否则弃去e2.
(3)检查e3,…,重复进行直至得到生成树为止.
实例
例求图的一棵最小生成树
复习思考题、作业题：
设G=<V,E>是n阶m条边的无向图，则下面各命题是等价的：

离散数学(第二版)第9章树


e10， 则分别产生初级回路e1e3e4， e1e4e5e2， e6e8e9，
•
•
•
e7e6e9e10。
•
第九章 树
这些初级回路有一个共同特点： 它们中均只含一条弦，
其余的边均是树枝， 我们称这样的回路为基本回路。 对于
G的每棵生成树T， m-n+1条弦对应着m-n+1个基本回路，
这些基本回路构成的集合称为对应T的基本回路系统。 显
例如图9.1.3中， T1和T2是图G的两棵生成树， 1 和2 是 分别对应于它们的余树。
第九章 树
图9.1.3 图的生成树和余树
第九章 树
由图9.1.3可见， G与T1、 T2的区别是G中有回路， 而 它的生成树中无回路， 因此要在一个连通图G中找到一棵 生成树， 只要不断地从G的回路上删去一条边， 最后所得 无回路的子图就是G的一棵生成树。 于是有如下定理。
这个问题的数学模型为： 在已知的带权图上求权最小 的生成树。
定义9.1.4 设无向连通带权图G=〈V, E, ω〉， G中带 权最小的生成树称为G的最小生成树(最优树)。
定理9.1.4 设连通图G的各边的权均不相同， 则回路 中权最大的边必不在G的最小生成树中。
证明略。
第九章 树
定理的结论是显然的， 由此寻找带权图G的最小生成 树， 可以采用破圈法， 即在图G中不断去掉回路中权最大 的边。
(5) 1， 1， 1， 1， 1， 2， 5
(6) 1， 1， 1， 1， 1， 3， 4
(7) 1， 1， 1， 1， 1， 1， 6
第九章 树
注意到， 不同构的度数列对应不同的树， 但对应同一 度数列的非同构的树不一定唯一， 所以对应(1)有T1， 对应 (2)有T2、 T3和T4， 对应(3)有T5和T6， 对应(4)有T7和T8， 对应(5)有T9， 对应(6)有T10， 对应(7)有T11(见图9.1.2)。

9图论-欧拉图-树11-17


作为哈密顿图的应用：
是解决在正十二面体图上确定一条初级回路L，使它含有所有结点。
将结点比作城市，连接两个结点的边看做是城市之间的路线，那么该问题就是所谓 《周游世界》(货郎担问题）：
能否从某一城市出发沿路线经过每个城市一次且仅一次，最后回到出发点
三、带权图与货郎担问题 1、定义 给定图G=<V，E>(G为无向图或有向图)， 设W：E → R(R为实数集) 对G中任意的边e=(vi，vj） （有向图时，e=<vi,vj>)， 设W(e)=wij 称实数wij为边e上的权，并将wij标注在边e上， 称G为带权图，此时常将带权图G记作<V，E，W>． 带权图应用的领域是相当广的，许多图论算法也是针对带权图的．下 面介绍的货郎担问题就是针对n阶无向完全带权图的．
必要条件： 定理15.6 无向图G是哈密顿图，则对于任意V1⊂ V 且 V1 ≠ φ 均有 p(G-V1)≤ |V1| （p(G)为图G的连通分支数） 定理15.8 设u,v为n阶无向简单图G中两个不相邻的结点，且 d(u)+d(v)>=n则G为哈密顿图当且仅当 G∪(u,v)为哈 密顿图 定理15.9 n（≥2)阶竞赛图G中都有哈密顿通路 （有向简单图D的基图为无向完全图，则称D是竞赛图） 对于哈密顿图中的哈密顿回路未必的唯一的 结论：对于n阶无向完全图Kn，当n是不小于3的奇数时， 该图恰有（n-1)!/2条互不相同的哈密顿回路 恰有（n-1)/2条互相无公共边的哈密顿回路
A3= 0 0 1 1
0 0 1 2 0 0 2 3 0 2 4 4 B3= 0 0 2 2 0 0 2 4 0 0 4 6
根据B矩阵得到： 主对角线全1 B中非零元素设为1 1 1 1 1 P= 0 1 1 1 0 0 1 1

离散数学第九章树知识点总结


生成树的存在性 定理 任何无向连通图都有生成树. 证 用破圈法. 若图中无圈, 则图本身就是自己的生成树.
否则删去圈上的任一条边, 这不破坏连通性, 重复进行 直到无圈为止,剩下的图是一棵生成树. 推论 1 设 n 阶无向连通图有 m 条边, 则 mn1. 推论 2 设 n 阶无向连通图有 m 条边, 则它的生成树的余树 有 mn+1 条边.
{0,10,010, 1010} 不是前缀码
例 在通信中，设八进制数字出现的频率如下：
0：25%
1：20%
2：15%
3：10%
4：10%
5：10%6：5% Nhomakorabea7：5%
采用 2 元前缀码, 求传输数字最少的 2 元前缀码 (称作最佳前
缀码), 并求传输 10n(n2)个按上述比例出现的八进制数字需
要多少个二进制数字？若用等长的 (长为 3) 的码字传输需要
推论 3 设
为 G 的生成树 T 的余树，C 为 G 中任意一个
圈，则 C 与
一定有公共边.
基本回路与基本回路系统
定义 设 T 是 n 阶 m 条边的无向连通图 G 的一棵生成 树，设 e1, e2, … , emn+1 为 T 的弦. 设 Cr 为 T 添加弦 er 产生的 G 中惟一的圈(由 er和树枝组成), 称 Cr 为对应 弦 er的基本回路或基本圈, r=1, 2, …, mn+1. 称{C1, C2, …, Cmn+1}为对应 T 的基本回路系统. 求基本回路的算法: 设弦 e=(u,v), 先求 T 中 u 到 v 的路径 uv, 再并上弦 e, 即得对应 e 的基本回路. 基本割集与基本割集系统定义 设 T 是 n 阶连通图 G 的一棵生成树, e1, e2, …, en1 为 T 的树枝，Si 是 G 的只含树枝 ei, 其他边都是弦

生成树计数算法

⽣成树计数算法⽣成树计数问题：给出⼀个⽆向图，求它的⽣成树的个数。

预备知识（1）⼀个n个顶点的⽆向图G，定义它的度数矩阵D，D是⼀个n*n的矩阵。

对于顶点u，设度数为deg[u]，如果i=j，那么D[i][j]=deg[i],否则D[i] [j]=0.（2）⼀个n个顶点的⽆向图G，定义它的邻接矩阵A，A是⼀个n*n的矩阵。

如果i和j之间有边，那么A[i][j]=1,否则等于0。

（3）⼀个n个顶点m条边的⽆向图G，定义它的关联矩阵B，B是⼀个n*m的矩阵。

对于第i条边e[i]=(u,v)，那么B[u][i]和B[v][i]中⼀个是1，⼀个是-1，第i列其他值为0。

那么我们有所以对于如果i=j，它是顶点i的度数，否则，如果i和j之间有边，那么它等于-1，否则它等于0.（4）对于⼀个n个顶点m条边的⽆向图G，定义它的Kirchhoff矩阵C,C是⼀个n*n的矩阵，很显然,C=D-AMatrix-Tree定理对于⼀个⽆向图G，它的⽣成树个数等于其Kirchhoff矩阵任何⼀个n-1阶主⼦式的⾏列式的绝对值。

所谓n-1阶主⼦式，就是对于任意⼀个r，将C的第r⾏和第r列同表⽰时删去后的新矩阵，⽤下⾯的字母表⽰C_{r}接下来，我们⾸先证明下⾯四个性质：性质1：对于任何⼀个图的Kirchhoff矩阵C，它的⾏列式为0。

性质2：对于不连通的图，它的Kirchhoff矩阵C的任⼀个n-1阶主⼦式的⾏列式均为0。

性质3：如果G是⼀棵树，它的Kirchhoff矩阵C的任⼀个n-1阶主⼦式的⾏列式均为1。

性质4：柯西-⽐内公式。

设A和B分别是n*m和m*n的矩阵，那么其中S是⼀个⼦集，⼤⼩为n，也就是S取遍所有的n⼦集，相应的As和Bs为从A和B中取出S元素下标的所有列和所有⾏。

性质1证明：由C的性质可得，它的每⼀⾏每⼀列和均为0，那么我们把第2到第n⾏都加到第⼀⾏，那么第⼀⾏就全部是0了。

有⼀⾏全部是0，那么它的⾏列式就是0了。

树与生成树


定理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叉有序树转化成二叉树 因为二叉树便于存贮, 也便于处理, 所以通常可以将多叉 树化成二叉树.方法是: 1.每个结点保留左儿子结点, 剪掉右边其分支. 被剪掉 的结点如下处理(重新嫁接). 2.同一个层次的结点, 从左到右依次画出(被剪掉的结 点 嫁接到它的哥哥结点上).
先将权按照升序排序设为w为儿子结点构造它们的父结点且其权为再与其余权一起排序再从此队列中取出前面两个权值为儿子结点同的方法构造它们的父结点
8-9 树与生成树
树是一种特殊的图, 它是图论中重要的概念之一, 它有 着广泛的应用.在计算机科学中有如判定树、语法树、分 类树、搜索树、目录树等等. 一.树 (Tree) (a) 1.树的定义:一个连通无回路的 无向图T,称之为树. 如(a) 2.叶结点:度数为1的结点, 称为叶结点. (b) 3.分支结点(内结点):度数大于1的结点. 4.森林:一个无向图的每个连通分支都是树.如(b)
⑷ 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, 所以，由归纳假设，有 |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。

第9章 图算法设计-算法设计与分析(第2版)-李春葆-清华大学出版社


{ lowcost[j]=g.edges[k][j];
closest[j]=k;
}
}
}
Prim()算法中有两重for循环，所以时间复杂度为O(n2)，其中n为 图的顶点个数。
3. 普里姆算法的正确性证明
普里姆算法是一种贪心算法。对于带权连通无向图G=(V，E)，采用 通过对算法步骤的归纳来证明普里姆算法的正确性。
8
2
4
3
6
lowcost[1]最小，将k=1添加到U中
U
0
6
1
仅修改V-U中顶点j：
1
4 3
g.edges[k][j]<lowcost[j] 调整
5
6
2
lowcost[j]=g.edges[k][j]
7
5
8
4
3
6
2
V-U
closest[j]=k
Prim(g，v)算法利用上述过程构造最小生成树，其中参数g为带权 邻接矩阵，v为起始顶点的编号。
k=j;
//k记录最近顶点的编号
}
printf(" 边(%d,%d)权为:%d\n",closest[k],k,mincost);
lowcost[k]=0;
//标记k已经加入U
for (j=0;j<g.n;j++)
//修改数组lowcost和closest
if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j])
void Prim(MGraph g,int v)
//Prim算法
{ int lowcost[MAXV];
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
STP工作原理归纳为以下3个过程： ◎选择根网桥（Root Bridge） ◎选择根端口 (Root Ports) ◎选择指定端口(Designated Ports)
主讲人：曾东波
相关知识---STP工作原理
1.选择根网桥
依据:选择BID（网桥ID）值最小的交换机作为网
络中的根网桥。
网桥ID结构：
100
155 622 1000 10000
Chapter
路径成本
19
14 6 4 2
16
相关知识---STP工作原理
端口ID的组成
端口优先级
端口编号
8位 取值范围：0 ～ 255 缺省值：128
8位
Chapter
17
STP选择根端口举例
在非根桥上， 选择一个根端口（RP）
在B和C上，到达 A最近的端口是B 和C的根端口 Root Port
主讲人：曾东波
相关知识：
◎STP作用 ◎STP工作原理 ◎PVST配置
◎以太网通道
主讲人：曾东波
重点：
◎STP作用 ◎PVST配置 ◎以太网通道
难点：
◎ PVST配置 ◎ STP工作原理
主讲人：曾东波
相关知识---STP概述
STP叫做生成树，就是把一个环形的结构改变成一个
树状的结构，组成一个逻辑无环网络。在使用STP的网络
构建网桥表 构建“活动”拓朴 只接收BPDU 强制关闭
25
相关知识-生成树计时器
• 交换机开机需要等待30秒时间开始转发数据 • 当某个正在使用的链路断掉，阻塞的端口需要50 秒时间开始转发数据
50秒 15秒 35秒 15秒 20秒 20秒 阻断
Chapter 26
转发 转发延迟 学习 转发延迟 倾听 最大寿命
◎通过show spanning-tree查看生成树，找出阻塞端口，
画出vlan1-3、vlan4-6逻辑工作拓扑图，分析负载分担；
◎测试相同Vlan内是否可以通信，当其中一条线路出现问 题，是否可以继续通信，要等待多久才能恢复通信；
◎通过show etherchannel summary查看以太网通道信息。
素质目标：
◎培养团队协作能力、领悟能力、工作协调能力。 主讲人：曾东波
拓扑结构及说明
三层交换机A通过f0/3-5与三层交换机B的f0/3-5相连， 三层交换机A通过f0/1与二层交换机C的f0/1相连，通过f0/2 与交换机D的f0/2相连，三层交换机B通过f0/1与二层交换机 D的f0/1相连，通过f0/2与交换机C的f0/2相连。
Root Port 100M B
DP
A
优先级：4096 MAC地址： 000d.2800.b100
Chapter
优先级：32768 MAC地址： 000d.2800.b101
20
STP计算结果
经过STP计算，最终的逻辑结构为无环拓朴
C
优先级：32768 MAC 地址： 备份线路 000d.2800.b102
主讲人：曾东波
任务要求：
◎完成上面拓扑图连接；
◎在每个交换机上都创建vlan 2-6；
◎交换机级联端口都设置trunk；
◎配置PVST，设置交换机A在vlan1-3是根交换机，交换
机B在vlan4-6是根交换机；
◎将交换机A、B上的f0/3-5端口加入到以太网通道中。
主讲人：曾东波
验证与测试：
◎通过show running-config 命令查看配置文件内容；
ቤተ መጻሕፍቲ ባይዱ
A
C
B
相关知识- RSTP/802.1W
RSTP(快速生成树协议 Rapid Spaning Tree
Protocol)在IEEE 802.1W中定义，由802.1D发展而来。这 种协议进一步处理了网络临时失去连通性的问题，在网络 结构发生变化时能更快的收敛网络。实际上它是把减少 STP收敛时间的一些措施融合在802.1D中形成新的协。它 比802.1D多了两种端口类型：预备端口类型(Alternate Port)和备份端口类型(Backup Port)
Chapter
Root Bridge
DP
A
100M RP Block
D BID：32768 00aa.1003. c003
23
逻辑拓朴
BID：32768 00aa.1000.c000 BID：32768 00aa.1001.c001 100M B
Root Bridge
A
100M 100M
C BID：32768 00aa.1002. c002
VLAN1
VLAN2
VLAN1
VLAN2
Vlan1,Vlan2
VLAN1
VLAN2
相关知识--PVST
PVST(每VLAN生成树 Per VLAN Spanning Tree)为每
个VLAN构建一棵单独的生成树实例，可以独立地为每个
VLAN控制哪些端口要转发数据，从而能实现对每个VLAN
作二层负载平衡，进而确保能够使用所有的链路，而不会
中，如果在网络建设初期对STP没有很好的规划，就可能
导致配置、故障排除和维护工作量的加大。
主讲人：曾东波
相关知识---STP作用
●解决环型网络引起的广播风暴、帧复制及MAC地址表 的不稳定等问题。 ●自动起用备用链路接替主链路的工作，不需要任何人 工干预。
B
主讲人：曾东波
相关知识---STP工作原理
过度使用某条链路。
相关知识-PVST配置
1.配置步骤 ◎启用生成树 ◎设置根交换机 ◎配置上行速链路(可选) ◎配置端口速链路
相关知识-PVST配置
2.配置命令 ◎启用生成树 SA(config)#spanning-tree vlan vlan-list spanning-tree vlan:命令 vlan-list:启用生成树的VLAN 例如:在vlan1-4中启用生成树 SA(config)#spanning-tree vlan 1-4
优点： 1.MSTP设置VLAN映射表(VLAN和生成树的对应关系 表)，把VLAN和生成树联系起来，通过增加“实例”(将多 个VLAN整合到一个集合中)这个概念，将多个VLAN捆 绑到一个实例中，以节省通信开销和资源占用率； 2.MSTP把一个交换网络划分成多个域，每个域内形成 多棵生成树，生成树之间彼此独立； 3.MSTP将环路网络修剪成为一个无环的树型网络，避 免报文在环路网络中的增生和无限循环，同时还提供 了数据转发的多个冗余路径，在数据转发过程中实现 VLAN数据的负载分担； 4.MSTP兼容STP和RSTP。
C
优先级：32768 MAC地址： 000d.2800.b102
100M
100M 下一步：选择指定端口 Root Bridge
Root Port
A
优先级：4096 MAC地址： 000d.2800.b100
100M
B 优先级：32768 MAC地址： 000d.2800.b101
Chapter
18
相关知识---STP工作原理
相关知识- RSTP/802.1W
优点： 1.集成了IEEE 802.1D的很多增强技术，这些增强功能 不需要额外配置； 2.RSTP使用第2类和第2版BPDU，能够与IEEE 802.1D 兼容； 3.RSTP能够主动确认端口是否能安全转换到转发状态， 而不需要依靠任何计时器来做出判断。 缺点： 1.仍是单生成树结构，不能做负载均衡，链路被阻塞后 不承载任何流量造成了带宽浪费； 2.收敛速度仍无法应对大型网络。
3.选择指定端口 要求： ◎在每个网段上，选择1个指定端口 ◎根桥上的端口全是指定端口
非根桥上的指定端口依据：
◎根路径成本最低
◎端口所在的网桥的ID值较小
◎端口ID值较小
主讲人：曾东波
STP选择根端口举例
在每个网段选择1个指定端口（DP）
这个端口既不是根端 口，也不是指定端口， STP将这个端口阻塞 C （Block） 100M Root 根网桥上的端口 Bridge 都是指定端口 DP DP 在这个网段上，B的 优先级：32768 网桥ID较小，所以B MAC地址： 上的端口为指定端口 000d.2800.b102 100M
网桥优先级 2字节 优先级取值范围：0 ～ 65535 网桥的MAC地址 6字节
缺省值：32768
主讲人：曾东波
STP选择根网桥举例
根据网桥ID选择根网桥
优先级：32768 MAC地址： 000d.2800.b102
C 以本拓朴为例， 介绍STP的计算 过程 下一步：选择根端口
Root Bridge
相关知识- MSTP/802.1S
MSTP(多实例生成树协议 Multiple Spanning Tree Protocol)将环路网络修剪成为一个无环的树型网络，避免 报文在环路网络中的增生和无限循环，同时还提供了数据
转发的多个冗余路径，在数据转发过程中实现VLAN数据的 负载均衡。
相关知识- MSTP/802.1S
相关知识-PVST配置
◎设置根交换机 SA(config)#spanning-tree vlan vlan-list priority Bridgepriority spanning-tree vlan:命令 vlan-list:表示vlan Bridge-priority：交换机优先级，优先级的值为4096 的倍数。 例如：设置交换机SA在vlan1-2中是根交换机。 SA(config)#spanning-tree vlan 1-2 priority 0
回顾
1.前阶段学习了哪些网络技术，每种网络技术有什么 作用？
主讲人：曾东波