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

关于有向图的连通问题

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

  • 写回答

2条回答 默认 最新

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

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

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

报告相同问题?

悬赏问题

  • ¥15 VAE代码如何画混淆矩阵
  • ¥15 求遗传算法GAMS代码
  • ¥15 雄安新区高光谱数据集的下载网址打不开
  • ¥66 android运行时native和graphics内存详细信息获取
  • ¥100 求一个c#通过CH341读取数据的Demo,能够读取指定地址值的功能
  • ¥15 rk3566 Android11 USB摄像头 微信
  • ¥15 torch框架下的强化学习DQN训练奖励值浮动过低,希望指导如何调整
  • ¥35 西门子博图v16安装密钥提示CryptAcquireContext MS_DEF_PROV Error of containger opening
  • ¥15 mes系统扫码追溯功能
  • ¥40 selenium访问信用中国
手机看
程序员都在用的中文IT技术交流社区

程序员都在用的中文IT技术交流社区

专业的中文 IT 技术社区,与千万技术人共成长

专业的中文 IT 技术社区,与千万技术人共成长

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

客服 返回
顶部