题目

有n个顶点的有向连通图最少有多少条边?
如题,给个结果,

提问时间：2020-10-12

答案

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