n个顶点的连通图至少有几个边？

Question

如题所述

Answer 1

有n个顶点的强连通图，最少有n条边。

首先，有向连通的一个必要条件是图的无向底图连通，这意味着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条边。

最少的情况：

即n个顶点围成一个圈，且圈上各边方向一致，即均为顺时针或者逆时针，此时有n条边。

1、充分性：如果G中有一个回路，它至少包含每个节点一次，则G中任两个节点都是互相可达的，故G是强连通图。

2、必要性：如果有向图是强连通的，则任两个节点都是相互可达。故必可做一回路经过图中所有各点；若不然则必有一回路不包含某一结点v，并且v与回路上的个节点就不是相互可达，与强连通条件矛盾。