gpt4 book ai didi

algorithm - 向图的所有边添加权重 - 生成树和最短路径的变化

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:44:55 26 4
gpt4 key购买 nike

<分区>

(a) Let T be a minimum spanning tree of a weighted graph G. Construct a new graph G by adding a weight of k to every edge of G. Do the edges of T form a minimum spanning tree of G. Prove the statement or give a counterexample.

(b) Let P = {s, . . . , t} describe a shortest weighted path between vertices s and t of a weighted graph G. Construct a new graph G by adding a weight of k to every edge of G. Does P describe a shortest path from s to t in G. Prove the statement or give a counterexample.

我的解决方案:

a) T 的边仍然形成 G 的最小生成树,因为所有边的权重都增加了相同的量。

b) P仍然描述了G中s到t的最短路径(同理)

有人可以验证答案吗?

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com