一个有n个顶点的无向连通图，最少有几条边

Question

如题所述

Answer 1

有n个顶点的强连通图最多有n（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与回路上的个节点就不是相互可达，与强连通条件矛盾。

扩展资料

对一个图G= (V,E)中的两点x和y，若存在交替的顶点和边的序列  （在有向图中要求有向边  属于E），则两点 x和y是连通的。

 是一条x到y的连通路径，x和y分别是起点和终点。当x=y时， 被称为回路。如果通路  中的边两两不同，则  是一条简单通路，否则为一条复杂通路。如果图G中每两点间皆连通，则G是连通图。

一个无向图 G=(V,E) 是连通的，那么边的数目大于等于顶点的数目减一：|E|>=|V|-1，而反之不成立。

参考资料来源：百度百科-强连通图