题目内容
(请给出正确答案)
提问人:网友gdsdmsj
发布时间:2022-01-07
[主观题]
n个顶点的强连通图至少有(32)条边。A.nB.n-1C.n-2D.n+1
n个顶点的强连通图至少有(32)条边。
A.n
B.n-1
C.n-2
D.n+1
简答题官方参考答案
(由简答题聘请的专业题库老师提供的解答)
查看官方参考答案
n个顶点的强连通图至少有(32)条边。
A.n
B.n-1
C.n-2
D.n+1
(1)证明图G的所有前缀为x[1,i]的旅行售货员问路的费用至少为:
式中,a(u,v)是边(u,v)的费用.
(2)利用上述结论设计一个高效的上界函数,重写旅行售货员问题的回溯法,并与主教材中的算法进行比较.
(1)证明旅行售货员回路的费用不超过.
(2)在旅行售货员问题的回溯法中,用上面的界作为bestc的初始值,重写该算法,并尽可能地简化代码.
(1)以顶点①为根的DFS树,
(2)如果有关节点,请找出所有的关节点。
(3)如果想把该连通图变成重连通图,至少在图中加几条边?如何加?
为了保护您的账号安全,请在“简答题”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!