判断题
不同的求最小生成树的方法最后得到的生成树是相同的。( )【南京理工大学1998二、3(2分)】
正确
错误
【正确答案】
错误
【答案解析】
解析:是最小生成树问题。上面已说明,无向连通图的生成树可能有多棵,最小生成树是代价(权值之和)最小的那棵生成树。最小生成树的权值之和是唯一的,但在具有较小相等权值的情况下,最小生成树一般不唯一。若权值互不相同,最小生成树则是唯一的。在具有较小相等权值的情况下,有可能较小权值的边没被全包括在生成树中(如若包括会形成环)。
提交答案
关闭