首页 > 试题广场 >

只要带权无向图中有全职相同的变, 其最小生成树就不可能

[单选题]
只要带权无向图中有权值相同的边,其最小生成树就不可能是唯一的。
  • 正确
  • 错误
应该是可能不唯一,而非一定
发表于 2022-04-13 12:14:26 回复(2)
答案有问题,要是相同权值的边是很大的边,然后最小生成树没有选到该权值的边,则应该有可能是唯一的。例如

发表于 2022-04-14 20:08:43 回复(2)
答案绝对错了,假如 1---2--3 这种图 边权且都是1 那么最小生成树唯一呀。
发表于 2022-08-21 14:16:24 回复(4)
恶心又刷到了,官方就不能把错误答案改一改吗?
发表于 2022-11-13 07:14:56 回复(0)
有问题,应该说带权连通图的任意一个环所包含的权值均不同时,最小生成树才唯一。
发表于 2022-12-12 15:34:24 回复(1)
可能不唯一吧,如果相同的权值边在环上就唯一,如果不在环上就不唯一
编辑于 2024-02-23 21:01:00 回复(0)

举个反例就知道了,上面这个无向图的MST是他自己
发表于 2023-10-27 21:02:29 回复(0)
最小生成树有多种可能,所以不唯一呀
发表于 2023-03-25 01:08:39 回复(0)

若无向图本身就是一棵树则最小生成树就是它本身

发表于 2022-11-09 16:24:44 回复(0)
就算重复的是权值最小的边,只要其中有足够的边是“桥”,那就有唯一的最小生成树
发表于 2022-10-22 21:01:45 回复(0)
有没有这么一种可能:带权无向图本身就是一棵有权值相同的边的最小生成树
发表于 2022-10-13 20:36:42 回复(0)
那万一本身就是就是一颗树呢
发表于 2022-08-17 21:44:14 回复(0)
v1-->v2, 1
v1-->v3,1
发表于 2022-07-10 15:40:29 回复(0)