Question

数据结构 要连通具有n个顶点的有向图，至少需要n条边，这是为什么啊

Answer 1

设边数为E

首先，有向连通的一个必要条件是图的无向底图连通，这意味着E >= n-1。

其次，证明E > n-1，因当E=n-1时，无向底图为树，任取两顶点s，t，从s到t有且只有一条无向路径，若有向路径s->t连通，则有向路径t->s必不存在，得证。

再次，证明E可以=n。设n个顶点v1，v2，...vn，顺次连接有向边v1v2，v2v3...vn-1vn，vnv1，这个环是有向连通的，

因此最少有n条边。

扩展资料：

给定有向图G=(VE)，并且给定该图G中的任意两个结点u和v，如果结点u与结点v相互可达，即至少存在一条路径可以由结点u开始，到结点v终止，同时存在至少有一条路径可以由结点v开始，到结点u终止。

对于有向图最短路问题，计算步骤与求解无向图最短路问题相同，主要区别在于：无向图最短路问题使用单标号法。单标号法是对每一点赋予一个路权标号；而有向最短路问题使用双标号法．双标号法是对每一点赋予两个标号：路径和路权。

对于一个无向图来说，如果它是连通的，那么它的任意两个顶点之问必存在一条路径，因此，通过这一路径可从一个顶点“到达”另一个顶点，若从顶点“可以到达u，则从u也可以到达“，也即v和u之间是互相可以到达的。

参考资料来源：百度百科--有向图

Answer 2

设边数为E
首先,有向连通的一个必要条件是图的无向底图连通,这意味着E >= n-1
其次,证明E > n-1.因当E=n-1时,无向底图为树,任取两顶点s,t,从s到t有且只有一条无向路径,若有向路径s->t连通,则有向路径t->s必不存在.得证
再次,证明E可以=n.设n个顶点v1,v2,...vn,顺次连接有向边v1v2,v2v3...vn-1vn,vnv1,这个环是有向连通的.
因此最少有n条边.