74最小生成树 、最小生成树概念 1.设无向连通图G(V,{E}), 其子图G=(V,{})满足: ①V(G)=V(G)n个顶点 ②G是连通的 ③G中无回路 则G是G的生成树
7.4 最小生成树 一、最小生成树概念 1. 设无向连通图G=（V，{E}）， 其子图G’=（V，{T}）满足： ① V(G’)=V(G) n个顶点 ② G’是连通的 ③ G’中无回路 则G’是G的生成树
74最小生成树 具有n个顶点的无向连通图G 其任一生成G恰好含n-1条边 生成树不一定唯一,如 4个顶点选择3条边有 如下5种形状(5×4=20种) 其中16种为生成树,(保证了连通)
7.4 最小生成树 具有n个顶点的无向连通图G • 其任一生成G’恰好含n-1条边 • 生成树不一定唯一，如 4个顶点选择3条边有 如下5种形状(5×4= 20种): 其中16种为生成树,（保证了连通）
7.4最小生成树 生成树代价 对图中每条边赋于一个权值(代价),则构成一个网, 网的生成树G=N,{}的代价是T中各边的权值之和, 最小生成树就是网上所有可能的生成树中,代价最小 的一类生成树 最小生成树也不一定唯一
生成树代价 对图中每条边赋于一个权值（代价），则构成一个网， 网的生成树G’=(V，{T})的代价是T中各边的权值之和， 最小生成树就是网上所有可能的生成树中，代价最小 的一类生成树。 最小生成树也不一定唯一。 7.4 最小生成树
7.4最小生成树 最小生成树的实用例子很多 顶点表示 computer 例1:N台计算机之间建立通讯网边表示通讯线 权值表示通讯线的代价(通讯 线长度, computer间距离等) 要求: ①n台计算机中的任何两台能通过网进行通讯; ②使总的代价最小。 求最小生成树[们
最小生成树的实用例子很多 例1： N台计算机之间建立通讯网 顶点表示computer 边表示通讯线 权值表示通讯线的代价（通讯 线长度，computer间距离等） 要求： ① n台计算机中的任何两台能通过网进行通讯； ② 使总的代价最小。-------求最小生成树[T] 7.4 最小生成树
7.4最小生成树 最小生成树的实用例子 顶点表示投递点 例2:邮递员送信线路]边表示街道 权值表示街道的长度 要求: ①完成n个投递点的投递; ②使总路径长度最短,即求最小生成树[们
最小生成树的实用例子 例2：邮递员送信线路[T] 顶点表示投递点 边表示街道 权值表示街道的长度 要求： ① 完成n个投递点的投递； ② 使总路径长度最短, 即求最小生成树[T] 7.4 最小生成树