摘要:最小生成树1、 最小生成树对于连通的带权图(连通网)G,其生成树也是带权的。生成树T各边的权值总和称为该树的权,记作:这里:TE表示T的边集w(u,v)表示边(u,v)的权。权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。最小生成树可简记为MST。2、生成树和最小生成树的应用生成树和最小生成树有许多重要的应用。【例】网络G表示n各城市之间的通信线路网线路(其中顶点表示城市,边表示两个城市之间的通信线路,边上的权值表示线路的长度或造价。可通过求该网络的最小生成树达到[阅读全文]
摘要:定义即生成树协议——STP(SpanningTreepProtocol)能够提供路径冗余,使用STP可以使两个终端中只有一条有效路径。STP在大的网络中定义了一个树,并且迫使一定的备份路径处于备用状态。如果生成树中的网络一部分不可达,或者STP值变化了,生成树算法会重新计算生成树拓扑,并且通过启动备份路径来重新建立连接。STP操作对于终端来说是透明的,而不管终端连在LAN的某一部分或者多个部分。当创建网络时,网络中所有节点存在多条路径。生成树中的算法计算出最佳路径。因为每个VLAN是一个逻辑LA[阅读全文]