qq_37109173 2017-11-25 11:55 采纳率: 100%
浏览 2589
已采纳

关于有向图的连通问题

有n个顶点的有向图，至少需要多少条弧才能保证是连通的。我看了有个学长写的答案是n，我觉得n不可能正确。我的想法是要保证连通，得是n-1个点构成一个有向图的强连通图，那么弧数就是(n-1)*(n-2) 再将剩下的那个节点与这个强连通图相连，那么问题来了，这个时候是该加一条有向弧，还是该加两条有向弧呢？

  • 写回答

2条回答 默认 最新

  • qq_37109173 2017-11-25 14:43
    关注

    保证，重点是要保证连通，最坏情况下

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题？

悬赏问题

  • ¥15 drone 推送镜像时候 purge: true 推送完毕后没有删除对应的镜像,手动拷贝到服务器执行结果正确在样才能让指令自动执行成功删除对应镜像，如何解决？
  • ¥15 求daily translation（DT）偏差订正方法的代码
  • ¥15 js调用html页面需要隐藏某个按钮
  • ¥15 ads仿真结果在圆图上是怎么读数的
  • ¥20 Cotex M3的调试和程序执行方式是什么样的？
  • ¥20 java项目连接sqlserver时报ssl相关错误
  • ¥15 一道python难题3
  • ¥15 牛顿斯科特系数表表示
  • ¥15 arduino 步进电机
  • ¥20 程序进入HardFault_Handler