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

2.3 生成树

  • 格式：ppt
  • 大小：767.00 KB
  • 文档页数：10

下载文档原格式

  / 10

合集下载

09-STP配置(bdcom配置手册)

09-STP配置(bdcom配置手册)
STP配置
目录
目录
第 1 章 配置生成树协议（STP） ................................................................................................................................ 1 1.1 STP 概述....................................................................................................................... 1 1.2 STP 模式与型号对照表 ................................................................................................................................... 2 1.3 SSTP 配置任务列表.......................................................................................................................................... 2 1.4 SSTP 配置任务 .................................................................................................................................................. 3 1.4.1 选择 STP 模式 ...................................................................................................................................... 3 1.4.2 禁止/启动 STP ...................................................................................................................................... 3 1.4.3 配置网桥优先级 .................................................................................................................................. 3 1.4.4 配置 Hello Time ...................................................................................................................................... 3 1.4.5 配置 Max Age ......................................................................................................................................... 4 1.4.6 配置 Forward Delay................................................................................................................................ 4 1.4.7 配置端口优先级 .................................................................................................................................. 4 1.4.8 配置端口路径开销 .............................................................................................................................. 4 1.4.9 配置自动指派端口 .............................................................................................................................. 5 1.4.10 监控 STP 状态 .................................................................................................................................... 5 1.5 配置 VLAN 的生成树 ....................................................................................................................................... 5 1.5.1 概述 ........................................................................................................................................................ 5 1.5.2 VLAN STP 配置任务 .............................................................................................................................. 5 1.6 RSTP 配置任务列表 ......................................................................................................................................... 6 1.7 RSTP 配置任务 .................................................................................................................................................. 7 1.7.1 开启/关闭交换机的 RSTP .................................................................................................................. 7 1.7.2 配置网桥优先级 .................................................................................................................................. 7 1.7.3 配置 Forward Time ................................................................................................................................. 7 1.7.4 配置 Hello Time ...................................................................................................................................... 8 1.7.5 配置 Max Age ......................................................................................................................................... 8 1.7.6 配置端口路径开销 .............................................................................................................................. 9 1.7.7 配置端口优先级 .................................................................................................................................. 9 1.7.8 重启协议转换检查 .............................................................................................................................. 9

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)=？ ？

天大《数据结构》学习笔记五

天大《数据结构》学习笔记五

主 题： 《数据结构》学习笔记内 容：《数据结构》学习笔记五——图一、图的概念：1、术语：有向图，无向图，子图，顶点，边，弧，邻接点，出度，入度，路径，连通图。

2、图的存储：2.1邻接矩阵：0 1 1 0 0 1 0 1 00 0 0 0 1 0 1 0 10 0 0 1 0 1 0 1 11 0 0 0 1 0 1 0 00 1 1 0 02.2邻接表：2 3 ^4 ^1 ^Struct node{int data;struct node *next;}struct node V[n+1];3、程序：3.1已知邻接表，建立邻接矩阵。

{……for(I=1;I<=n;I++)for(j=1;j<=n;j++)w[I][j]=0;for(I=1;I<=n;I++){p=v[I].next;while(p){j=p->data;w[I][j]=1;p=p->next;}}}3.2已知邻接矩阵，建立邻接表。

{……for(I=1;I<=n;I++)v[I].next=0;for(I=1;I<=n;I++)for(j=1;j<=n;j++)if (w[I][j]= =1){p=(……)malloc(……)；p->data=j;p->next=v[I].next;v[I].next=p;}}1、广度优先遍历1.1作法:(i)初始化(打印,加标记,进队)(ii)出队.(J)(iii)扫描(J)链,遇未访问点,则打印,加标记,进队.返回ii,直至队空.1.2 结果:2、深度优先遍历：2.1作法:从某点进入,打印,加标记,扫描此链:如没遇到未访问点,则返到原转来点.算法结束于进入点那个链的链尾.2.2 结果:1,2,4,8,5,3,6,73、广度优先程序：bfs(I)int I;{……f=0; r=0;for(t=1;t<=n;t++)v[t].data=0;printf(“%d”,I);v[I].data=1;r++; q[r]=I;while(f!=r){f++; j=q[f];p=v[j].next;while(p){k=p->data;if(v[k].data= =0){printf(“%d”,k);v[k].data=1;r++;q[r]=k;}p=p->next;}}}4、深度优先程序：dfs(I)int I;{……v[I].data=1;printf(“%d”,I);p=v[I].next;while(p){j=p->data;if(v[j].data= =0)dfs(j);p=p->next;}}三、最小生成树：1、解法11.1问题：选哪几条边，使得（I）能连到各点（II）边长之和最小？1.2思路：i. 从当前点集的发出边中选最小者，打印。

第2章 树

第2章 树

推论2.4.1 每一连通图 都包含一生成树。 每一连通图G都包含一生成树 都包含一生成树。 推论
证明：令 T 为G的极小 minimal)连通生成子图 极小( 极小 连通生成子图 （即 T 的任一真子图都不是G的连通生成子图） （由定义知，T 可在保持连通性 保持连通性的前提下，用逐步 保持连通性 从G中去边的办法求出（ ∴所去的边一定在一圈中 边 （即非割边 非割边）（∴每步至少破坏一圈））。 由T的 非割边 定义知，ω(T) = 1 ， ω(T - e) = 2 ∀ e ∈ E(T) 。 即 T 的每边为割边，故由定理2.4知T为树。
2.1.4 G为 林 ⇔ ε = ν - ω。 2.1.5 若林G 恰有2k个奇点 奇点，则G 中存在k条边不重 奇点 的路 1 ,P2 ,..,Pk ,使得E(G) = E(P1 )∪E(P2 )∪ ... ∪E(Pk )。 2.1.6 正整数序列 (d 1 ,d 2 ,...,d ν )是一 棵树的度序 ν 列，当且仅当
定理2.5 设 T 为G的一生成树，e为G中不属于 定理 T的边，则T+e 含唯一的圈。 证明： 若e为环（即1-圈），结论显然成立。 不然，由于T 无圈，T + e 中的每个圈（若存 在的话）都包含e 。又，C为 T + e 的一圈 ⇔ C - e 为T 中连接e的两个端点的路。但， 由定理2.1知，T中恰只有一条这样的路，因 此 T + e中包含唯一的圈。
⇔ 不含圈的图。 树（tree） ⇔ 连通无圈图。 叶 (leave) ⇔ 树中度为1的顶点。 例：六个顶点的树
称边e为图G的割边( cut edge) ⇔ ω(G-e) > ω(G) 。 （或即 ω(G-e) = ω(G) + 1 ） （称边e为图G的非割边 ⇔ ω(G-e) = ω(G) 。）

图论——树

图论——树

森林
推论： 具有k个分支的森林有nk条边， 其中n是G的顶点数。
无向树的性质
定理2.2
证明
设T是n阶非平凡的无向树，则T中至少有两片树叶。
设T有x片树叶，由握手定理及定理2.1可知，
2(n 1) d (vi ) x 2(n x)
由上式解出x≥2。
例2.1
例2.1 画出6阶所有非同构的无向树。 解答 设Ti是6阶无向树。
唯一性（反证法）。 若路径不是唯一的，设Г1与Г2都是u到v的路径， 易知必存在由Г1和Г2上的边构成的回路， 这与G中无回路矛盾。
(2)(3)
如果G中任意两个顶点之间存在唯一的路径， 则G中无回路且m＝n-1。 首先证明 G中无回路。 若G中存在长度大于2的圈， 则圈上任何两个顶点之间都存在两条不同的路径， 这也与已知矛盾。
说明
注意：T 不一定连通，也不一定不含回路。
生成树的存在条件
定理2.3 无向图G具有生成树当且仅当G连通。 证明 必要性，显然。 充分性（破圈法）。 若圈，任取一圈，随意地删除圈上的一条边，
若再有圈再删除圈上的一条边，直到最后无圈为止。 易知所得图无圈(当然无回路)、连通且为G的生成子图， 所以为G的生成树。
分支点—— 7个
高度—— 5
家族树
常将根树看成家族树，家族中成员之间的关系如下定义。 定义2.7 设T为一棵非平凡的根树， vi、vj∈V(T)，若vi可达vj，则称vi为vj的祖先，vj为vi的后代。 若vi邻接到 vj（即 <vi,vj>∈E(T)）， 则称vi 为 vj的父亲，而 vj为 vi 的儿子。 若vj、vk的父亲相同，则称vj与vk是兄弟。 定义2.8 设v为根树T中任意一顶点，称v及其后代的导出子图为 以v为根的根子树。

生成树的名词解释

生成树的名词解释

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

生成树协议(STP)在计算机网络中的应用

生成树协议(STP)在计算机网络中的应用1. 引言1.1 引言生成树协议(STP)是计算机网络中一个重要的协议，它被广泛应用于以太网LAN 中，用来避免网络环路的产生，提高网络的可靠性，优化网络带宽的利用，以及支持网络的快速恢复。

在现代网络架构中，STP扮演着至关重要的角色，保障了网络的稳定运行和高效传输。

本文将详细探讨生成树协议在计算机网络中的应用，从其如何避免网络环路的产生、如何提高网络的可靠性、如何优化网络带宽的利用，以及如何支持网络的快速恢复等方面展开讨论。

通过深入分析STP的工作原理和应用场景，读者将更加深入了解这一协议的重要性和价值。

在现代网络环境下，随着数据量不断增加和对网络稳定性要求日益提高，STP的作用变得愈发重要。

通过学习和理解STP的应用，可以帮助网络管理员更好地管理网络拓扑结构，确保网络的高可靠性和高性能。

在本文的后续部分中，我们将更详细地探讨STP在计算机网络中的具体应用，希望能对读者有所启发和帮助。

2. 正文2.1 生成树协议(STP)在计算机网络中的应用生成树协议(STP)是一种用于计算机网络中的链路层通信协议，用于避免网络环路的产生，并提高网络的可靠性、优化网络带宽的利用和支持网络的快速恢复。

STP通过计算网络拓扑中的最小生成树来选择一条主干链路，使得网络中所有的交换机都能通过这条链路进行通信，从而避免网络中出现环路。

在计算机网络中，STP的应用非常广泛。

它可以确保网络中数据包的顺利传输，避免数据包在网络中无法到达目的地或造成数据包重复传输的情况。

通过STP，网络管理员可以配置网络拓扑，确保网络中所有的交换机都能按照同一个最小生成树来进行通信，从而保证网络的稳定性。

此外，STP还能提高网络的可靠性。

当网络中出现故障或链路故障时，STP能够及时检测到故障点，并重新计算最小生成树，选择新的主干链路，保证网络的正常运行。

这样，即使网络中某个链路出现问题，整个网络仍可以继续正常工作。

锐捷交换机路由器---生成树协议

生成树协议：（三层交换机与二层交换机下配置）1、Switch(config)#spanning-tree2、Switch(config)#spanning-tree mode rstp3、Switch(config)#spanning-tree pri 0 根协议注：第3步在二层交换机中不用做，只需在三层交换机上做就可以了。

在三层交换机上配置路由功能：1、Switch(config)#ip routing 开启路由功能2、Switch(config)#ip default-gateway 192.168.56.1 设置默认网关安全地址绑定：Switch(config)#interface fastethernet 0/1Switch(config-if)#switchport mode accessSwitch(config-if)#no shutdownSwitch(config-if)#switchport port-securitySwitch(config-if)#switchport port-security mac-address 0017.816D.AF10 ip-address 192.168.2.3 IP与MAC地址绑定（手工配置）Switch(config-if)#no shutdown启动网络诊断程序来诊断本地网络：1、开始运行cmd 输入“netsh”,按“Enter”键，进入“netsh >”提示符状态中。

在“netsh >”提示符状态后输入“diag”，按“Eneter”键，进入“netsh diag >”提示符状态中。

2、接着在“netsh diag > ”提示符状态后输入“gui”，按“Enetsh”键，即可启用网络诊断。

3、先单击“设置扫描选项”选项，展开网络诊断设置选项。

4、用户在下面的选项中选中要进行网络诊断的选项，点击“保存选项”按钮，即可将设置选项保存。

图论 第二章 树(tree)


定义2.2.2 如果在图G中去掉一个顶点（自然同 时去掉与该顶点相关联的所有边）后图的分 支数增加，则称该顶点为G的割点。
定理2.2.1 当且仅当G的一条边e不包含在G 的 圈中时，e才是割边。
u x
e
v
Hale Waihona Puke yCG推论2.2.1 当且仅当连通图G的每一条边均为 割边时，G才是一棵树。
对割边有下面的等价命题：
推论2.1.3 设G的边数为q，顶点数为p,如果 G无圈且q=p-1，则G是一棵树。
推论2.1.4 在树中至少存在两个度为1的顶点。
关于树有下列的等价命题：
（1）G是一棵树 （2）G的任意两个顶点由唯一道路联结 （3）G是连通的，且q=p-1 （4）G是无圈的，且q=p-1 （5）G无圈，且若G的任意两个不邻接的顶点 联一条边e，则G+e中恰有一个圈。
A directed graph is Eulerian if it is connected and can be decomposed into arc-disjoint directed cycles.
An undirected graph is traversable if it is connected and at most two vertices in the graph are of odd degree
条包含G的所有边的闭链； ❖ （4）两个欧拉图的环和仍是欧拉图。
理定3.1.2和推论3.1.1反映了图的一 个重要性质，即图的连绘性。一个连 绘的图是指这个图可以用一笔画成而 没有重复的笔划。换句话说就是在这 个图中存在一条能过每条边的链。
3.3 哈密顿图
1856 年 hamilton 周游世界的游戏，十 二面体，有20个顶点，三十条边，十二 个面

生成树选举规则示例

近期自己在学习生成树，有了一点小小的认识，记下此文档，也是为了避免自己以后忘记。

一、生成树作用生成树，（spanning-tree protocol，简称STP协议），主要是用于防止二层环路。

相关的资料在网上已经很多了，不再赘述。

二、生成树的选举2.1BPDUBPDU的数据包中主要4个方面的内容：根网桥的BID、cost值、网桥的BID、端口ID。

下面是BPDU的截图：2.2交换机角色1）根交换机，有且只有一个根，最低的桥ID(优先级+MAC地址）（扩展BID：优先级+VLAN +MAC地址），见下面BPDU的截图：2）非根交换机：其余交换机，就是非根交换机2.3端口角色生成树中交换机之间相互连接的交换机端口角色：1.根端口：a)非根桥有且只有一个根端口：要拥有去往根桥的最低成本，成本与链路带宽有关系（10M cost:100, 100M:19, Gi: 4; 10G:1)b)要拥有最低的Brige ID（比Brigde ID，是比对端交换机的Brigde-ID，比的是接收到的BPDU的Bridge-ID）c)要拥有最低的Port ID（比端口ID,Port-ID，比的是对端的Port-ID）2.指定端口：每个链路段只且只有一个指定端口：a)要拥有去往根桥的最低成本，成本与链路带宽有关系（10M cost:100, 100M:19, Gi: 4;10G:1)b)要拥有最低的Brige ID（注意：这个Bridge ID是自己要从这个端口发出去的BPDU的Bridge ID，即两台交换机自身的Bridge-ID作对比）c)要拥有最低的Port ID（比Port ID，是拿自己接收到的BPDU中的Port ID来比，因此，比的是对端连接的Port-ID)3.既不是指定端口，又不是根端口的端口是阻塞端口：（往往位于冗余链路上）三、例子讲解3.1例子一S0：0010.117B.DB92S1：00D0.FFE3.8BB8S2：0001.C994.6402【其它】1.所有交换机均属于VLAN1；2.所有接口均是FastEthernet；3.所有交换机均未修改优先级，均为默认优先级：32768【分析思路】1.选举根网桥时，需要比较各自的BPDU。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

二、 生成树的计数
前面我们介绍了生成树的存在性问题。因此在下面内容中， 我们皆假设 G 是连通图，除非特别指出 G 不连通。 既然我们已经知道了在一个连通图中肯定存在生成树，很 自然地我们就要去考察连通图的生成树的数目——我们把 它称之为生成树的计数问题。
返回 结束
1、一些概念
T , T 分别是 是一个连通图。 G 的两个生成树，如果 G 的两个不同的生成树。 G 的 T ,T 是 • E (T ) E (T ) ，则认为 (G ) 表示。 • 不同的生成树个数用
返回 结束
2、求 (G ) 的递推公式
e 是图的一条边，则 定理3.2.4 设G 是无环图，
(G) (G e) (G e)
注： 1. 为了简洁，我们在求解过程中仍 然用图本身来表示该图的生成树个数。 2.由于一个图的环不包含在任何生成 树中，在计算的过程中，如果出现环， 可以不予考虑。
例1
G
T
T'
返回 结束
下面考虑：若 G 连通，则 G 中是否存在生成树？ 方法一：破圈法。 1。若 G 本身是树，则 G 本身可以看成是 G 的一个生成树。
e E (C ),G e 仍连通， 2。若 G 不是树，则至少有一个回路 C 。
即 G e
是G 的连通生成子图 。
可以继续这一过程，直到从最后一个回路中去掉一条边，所得的 一个连通、无回路生成子图，就是 的生成树。
返回 结束
证明：用 T 1 表示图 G 的生成树全体 用 T 表示图 G 中不含边 e 的生成树全体 e T 用 表示图 G 中含边 e 的生成树全体 T (G e ) 则易验证 T (G e) ， ，T (G) 1 2 e T T T 和 所以有 (G) (G e) (G e)
返回 结束
例2
G
G1
T'
返回 结束
方法二：避圈法。
G 连通，在V (G )中逐次添加 G 的边，要求每次添加边之后所得
子图都不含回路。把上述过程进行到无法进行为止，所得子图 T 是G 的一个无回路的子图，是 G 的连通的生成子图。
定理3.2.1 G 连通当且仅当 G 含有生成树 T 。
返回 结束
G ①设
如：
v1 v1 v1 v1
v3
v2
v3
v 2 v3
v 2 v3
v2
则： ( K3 ) 3。
返回 结束
② 收缩运算： e uv 是图 G 的边（不是环），在 G 中删去边 e ， 再在 G e 中重合 e 的两个端点 u , v 为一个新的顶点 w(u, v)。而 G e 中一切与 v 和 u 关联的边都改成与这个新的顶点相关联。这样所得 到的图称为 G 收缩边 e ，记为 G e 。
2
2
e
例
(G )


e


e

e






1 1 2 1 1 2 3 11
返回 结束
例：
v1 e1
v2
e2 v3 e3
v1
e1
v2
e2 v3 e3
v1
e1
e5 v5
e6 e4
e
v45
e6 e4
e2 v3
w(v4 , v2 ) e3
G
G e
G e
q(G e) q(G) 1, p(G e) p(G); q(G e) q(G) 1, p(G e) p(G) 1
§2.3 生成树 讨论树作为生成子图的情况： 一、生成树 定义2.3.1 给定一个图 G ，若图G 中存在一个生成子图 T 是树， 则称 T 是 G 的一个生成树。 由定义可见下面性质成立： 1.若 T 是 G 的一个生成树，则 V (T ) V (G), q(T ) p(G) 1
2.若 G 有生成树 T ，由于 T 连通，则 G 本身一定连通。