有向图边的数量与连通性关系分析
这个说法是不正确的。
一个有向图边的个数达到n*(n-1)时,可以构造出一个不连通的有向图。具体构造方法如下:
将n个顶点划分为两个集合A和B,且A∪B={1,2,...,n}且A∩B=∅,其中A和B的大小均为n/2(当n为奇数时,可以将其中一个集合大小为(n-1)/2,另一个集合大小为(n+1)/2)。对于任意的a∈A和b∈B,连一条从a到b的有向边。
这样构造出来的有向图有n*(n-1)条有向边,但是A和B之间没有任何边连接,因此该图是不连通的。
原文地址: https://www.cveoy.top/t/topic/osUV 著作权归作者所有。请勿转载和采集!