| [页数]:9 [字数]:1417 [目录] 一、 最小生成树 二、最小生成树性质（MST性质） 三、求MST的一般算法描述 四、求最小生成树的具体算法 五、生成树和最小生成树的应用举例 [正文] 一、 最小生成树 对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权，记作： 这里: TE表示T的边集 w(u，v)表示边(u，v)的权。 权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。最小生成树可简记为MST。 二、最小生成树性质（MST性质） （1）MST性质 最小生成树性质：设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中所有的一个端点在U(u∈U)里、另一个端点不在U(即v∈V-U)里的边中，具有最小权值的一条边，则一定存在G的一棵最小生成树包括此边(u，v)。 （2）MST性质的证明 为方便说明，先作以下约定： ①将集合U中的顶点看作是红色顶点，②而V-U中的顶点看作是蓝色顶点，③连接红点和蓝点的边看作是紫色边，④权最小的紫边称为轻边(即权重最"轻"的边)。于是，MST性质中所述的边(u，v)就可简称为轻边。 用反证法证明MST性质： 假设G中任何一棵MST都不含轻边(u，v)。则若T是G的一棵MST，则它不含此轻边。 ...... [原文截取] 最小生成树算法及其应用 戴希洋 200691087 计0605 一、 最小生成树 对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权，记作： 这里: TE表示T的边集 w(u，v)表示边(u，v)的权。 权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。最小生成树可简记为MST。 二、最小生成树性质（MST性质） （1）MST性质 最小生成树性质：设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中所有的一个端点在U(u∈U)里、另一个端点不在U(即v∈V-U)里的边中，具有最小权值的一条边，则一定存在G的一棵最小生成树包括此边(u，v)。 （2）MST性质的证明 为方便说明，先作以下约定： ①将集合U中的顶点看作是红色顶点，②而V-U中的顶点看作是蓝色顶点，③连接红点和蓝点的边看作是紫色边，④权最小的紫边称为轻边(即权重最"轻"的边)。于是，MST性质中所述的边(u，v)就可简称为轻边。 用反证法证明MST性质： 假设G中任何一棵MST都不含轻边(u..... |
最小生成树算法及其应用
查看评论
已有0位网友发表了看法