一个有n个顶点的图最少有多少条边

Question

如题所述

Answer 1

至少要有（N-1）条边。

在数据结构中，N个顶点的连通图至少要有（N-1）条边（也就是树）才能保证图为连通图。

强连通图最多n(n-1)条边，最少n-1条边。

强连通图：任意两个顶点都相互连通的图。

数据结构知识

基本特性：输入，输出，有穷型，确定性可行性。

设计要求：正确性，可读性，健壮性，时间效率高，存储量低。

时间复杂度：随着输入规模n的增加，算法的执行时间的增长率和算法执行次数的增长率保持一致，我们成为算法的渐进时间复杂度，简称为算法的时间复杂度。

大O推导：使用常数1去替代表达式中的常数项；在修改后的表达式中，只保留最高阶次项；如果最高阶次项存在且不为1，去掉最高阶次项的系数。