| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2863 人关注过本帖
标题:最小生成树
只看楼主 加入收藏
ivapple
Rank: 1
等 级:新手上路
帖 子:46
专家分:0
注 册:2008-7-31
收藏
 问题点数:0 回复次数:16 
最小生成树
对于一个各边权值均不相等的简单连通图,它的最小生成树唯一吗,
 我感觉不唯一,可就是很难画出个图来验证,难道是唯一的,还请高手指点。
搜索更多相关主题的帖子: 成树 小生 
2008-11-15 03:08
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
在下不才,俺想请教一下"简单连通图"是啥子图?
我只知道简单路径这个概念,无向图连通与非连通的概念,
有向图的强连通的概念.
2008-11-15 23:07
ivapple
Rank: 1
等 级:新手上路
帖 子:46
专家分:0
注 册:2008-7-31
收藏
得分:0 
没有自环和多重边的图叫简单图
2008-11-16 01:24
ivapple
Rank: 1
等 级:新手上路
帖 子:46
专家分:0
注 册:2008-7-31
收藏
得分:0 
是不是应该说成连通的简单图好些
简单连通图在理解上有误导,会让人有“简单连通”和“复杂连通”的感觉。
2008-11-16 03:05
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
直觉觉得可能是唯一的,不过可以考虑用反证法证明一下,
分析中...
2008-11-16 13:36
ivapple
Rank: 1
等 级:新手上路
帖 子:46
专家分:0
注 册:2008-7-31
收藏
得分:0 
再多些人讨论啊?
2008-11-17 01:41
ivapple
Rank: 1
等 级:新手上路
帖 子:46
专家分:0
注 册:2008-7-31
收藏
得分:0 
顶起
2008-11-29 03:15
jdshaoheyi
Rank: 1
等 级:新手上路
帖 子:133
专家分:5
注 册:2008-11-6
收藏
得分:0 
对于一个各边权值均不相等的简单连通图,它的最小生成树唯一
2008-11-30 15:03
jdshaoheyi
Rank: 1
等 级:新手上路
帖 子:133
专家分:5
注 册:2008-11-6
收藏
得分:0 
首先最小生成树是在n个节点构成的网中,选取n-1条边,可以建立一个连通图,现在假设,我们用普里姆算法或者是克鲁斯卡尔算法,计算出一棵最小生成树(记住你已经计算出了一个最小生成树了),现在你又有幸的到了一个最小生成树,和上一次计算出的权值和是一样的,但是要知道这棵最小生成树也只有n-1条边啊!也就是说第一次算出的最小生成树和第二次算出的生成树只有一条边不一样,那会发生什么事情呢?
2008-11-30 15:11
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
"也就是说第一次算出的最小生成树和第二次算出的生成树只有一条边不一样"
-----------啥意思?怎么解释?我们只知道图中一共有
n个顶点,但不知道多少条边啊?请多多指教,

我感觉也应该是唯一的,可感觉很难证明,我在试图用
反证法证明.
2008-11-30 15:25
快速回复:最小生成树
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.036385 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved