n(n-1)/2
n(n-1)
n(n+1)/2
(n-1)/2
连通图:在一个无向图中,从每一个顶点到每一个其它顶点都存在一条路径,则此无向图是连通的
有n个顶点的连通图最多有n(n-1)/2 条边,最少有n-1条边
举例说明:如图所示,设ABCD四个点构成强连通图,则:
边数最多有(4×3)/2=6条,如图所示
边数最少有3条,如图所示
强连通图:满足此连通条件的有向图叫做强连通图
有n个顶点的强连通图最多有n(n-1)条边,最少有n条边
完全图:每一对顶点间都存在一条边
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题