一个有n个顶点的无向连通图,最少有几条边
一、有n个顶点的强连通图最多有n(n-1)条边,最少有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个点两两相连有n(n-1)/2条边,而由于强连通图是有向图,故每条边有两个方向,n(n-1)/2×2=n(n-1),故有n个顶点的强连通图最多有n(n-1)条边。
扩展资料:
有n个顶点的强连通图最多有n(n-1)条边,最少有n条边。
(1)最多的情况:即n个顶点中两两相连,若不计方向,n个点两两相连有n(n-1)/2条边,而由于强连通图是有向图,故每条边有两个方向,n(n-1)/2×2=n(n-1),故有n个顶点的强连通图最多有n(n-1)条边。
(2)最少的情况:即n个顶点围成一个圈,且圈上各边方向一致,即均为顺时针或者逆时针,此时有n条边。
下面举例说明:如图1所示,设ABCD四个点构成强连通图,则:
(1)边数最多有4×3=12条;
(2)边数最少有4条;
参考资料来源:百度百科-强连通图
一个有n个顶点的无向连通图最多有n(n-1)/2条边,最少有n-1条边。
有向图的强连通图才是最少n条边。看到两个回答都是错的。
强连通图是指一个有向图中任意两点v1、v2间存在v1到v2的路径(path)及v2到v1的路径的图。
最多的情况:即n个顶点中两两相连,若不计方向,n个点两两相连有n(n-1)/2条边,而由于强连通图是有向图,故每条边有两个方向,n(n-1)/2×2=n(n-1),故有n个顶点的强连通图最多有n(n-1)条边。
最少的情况:即n个顶点围成一个圈,且圈上各边方向一致,即均为顺时针或者逆时针,此时有n条边。
1、充分性:如果G中有一个回路,它至少包含每个节点一次,则G中任两个节点都是互相可达的,故G是强连通图。
2、必要性:如果有向图是强连通的,则任两个节点都是相互可达。故必可做一回路经过图中所有各点。若不然则必有一回路不包含某一结点v,并且v与回路上的个节点就不是相互可达,与强连通条件矛盾。
首先,有向连通的一个必要条件是图的无向底图连通,这意味着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条边.
广告 您可能关注的内容 |