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

关于有向图的连通问题

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

  • 写回答

2条回答 默认 最新

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

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

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

报告相同问题？

悬赏问题

  • ¥15 微信小程序 用oss下载 aliyun-oss-sdk-6.18.0.min client报错
  • ¥15 ArcGIS批量裁剪
  • ¥15 labview程序设计
  • ¥15 为什么在配置Linux系统的时候执行脚本总是出现E: Failed to fetch http:L/cn.archive.ubuntu.com
  • ¥15 Cloudreve保存用户组存储空间大小时报错
  • ¥15 伪标签为什么不能作为弱监督语义分割的结果？
  • ¥15 编一个判断一个区间范围内的数字的个位数的立方和是否等于其本身的程序在输入第1组数据后卡住了(语言-c语言)
  • ¥15 Mac版Fiddler Everywhere4.0.1提示强制更新
  • ¥15 android 集成sentry上报时报错。
  • ¥15 抖音看过的视频，缓存在哪个文件