一个连通图G的边数是多少?
发布网友
发布时间：2024-04-16 10:01
共1个回答
热心网友
时间：2024-04-18 09:06
m = n(n-1)/2
那么边 m = 22 时, 图 G:
n(n-1)/2 >= 22
n >= 8
而且，当 n = 7 时，全连通图 G' 的边数 m = 21
当我们把第 8 个定点加上来，必然还要再在这个定点和上面7个定点相连，以便构成第 22 边
(8个顶点不足以构成22边非连通图)
加上第 9 个定点后，可以在 (8, 9) 之间构成第22边，或者，选择 8, 或 9 作为孤立点，构成非连通图
至少有 9 个顶点
