题目内容
(请给出正确答案)
提问人:网友yangpan98
发布时间:2022-01-07
[主观题]
将有向图G的边的方向去掉得到的无向图称为G的基础图,基础图是完全图的有向图称为竞赛图。证明:任意竞赛图的所有节点的出度平方和等于入度平方和。
简答题官方参考答案
(由简答题聘请的专业题库老师提供的解答)
查看官方参考答案
(1)如果图中有一条边处于从开始顶点到完成顶点的每一条路径上,则仅加速该边表示的活动就能减少整个工程的工期。这样的边称为桥(bridge)。证明若从连通图中删去桥,将把图分割成两个连通分量。
(2)编写一个时间复杂度为O(n+e)的使用邻接表表示的算法,判断连通图G中是否有桥,若有。输出这样的桥。
B. call on
C. call at
D. call off
为了保护您的账号安全,请在“简答题”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!