Question

有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条边。