具有n个顶点的有向图至少需要n条弧，n-1不行吗？
答案:1 悬赏:80
解决时间 2021-01-15 21:26
- 提问者网友：缘字诀
- 2021-01-15 17:35
具有n个顶点的有向图至少需要n条弧，n-1不行吗？
最佳答案
- 二级知识专家网友：爱难随人意
- 2021-01-15 19:02
这里的有向图，应该指强连通有向图。如果允许孤点，有1条弧也行。
强连通有向图，满足两个条件：
（1）没有孤点；
（2）任何两点A、B，至少存在1条路径，从A到B；也至少存在1条路径，从B到A。
A>B>C>D,A-->D,存在；D--->A不存在。
n个顶点排在一个圆周上，需要的弧最少。n条。
强连通有向图，满足两个条件：
（1）没有孤点；
（2）任何两点A、B，至少存在1条路径，从A到B；也至少存在1条路径，从B到A。
A>B>C>D,A-->D,存在；D--->A不存在。
n个顶点排在一个圆周上，需要的弧最少。n条。
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息！
大家都在看
推荐信息