G是一个非连通无向图，共有22条边，则该图至少有（）个顶点。
至少有 9 个顶点
全连通图的定点n 和边数 m 满足：
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 个顶点
扩展资料
任意一条边都代表u连v以及v连u。无向图是相对于有向图来说明的，就是说每条边都是双向边，而有向图每条边都是单向边，也就是说只能由一个点指向另一个点。
证明:
假设有8个顶点,则8个顶点的无向图最多有28条边且该图为连通图
连通无向图构成条件:边=顶点数*(顶点数-1)/2
顶点数>=1，所以该函数存在单调递增的单值反函数
所以边与顶点为增函数关系
所以28个条边的连通无向图顶点数最少为8个
所以28条边的非连通无向图为9个(加入一个孤立点)
光派通信
2024-09-03 广告
无向图的边数：n（n-1）/2
所以n=8
又因为非连通再加1
所以是9
例如：
证明：
假设有8个顶点,则8个顶点的无向图最多有28条边且该图为连通图
连通无向图构成条件：边=顶点数*(顶点数-1)/2
顶点数>=1，所以该函数存在单调递增的单值反函数
所以边与顶点为增函数关系
所以28个条边的连通无向图顶点数最少为8个
所以28条边的非连通无向图为9个(加入一个孤立点)
扩展资料：
任意一条边都代表u连v以及v连u。无向图是相对于有向图来说明的，就是说每条边都是双向边，而有向图每条边都是单向边，也就是说只能由一个点指向另一个点。
直观来说，若一个图中每条边都是无方向的，则称为无向图。
无向边的表示
无向图中的边均是顶点的无序对，无序对通常用圆括号表示。
【例】无序对(vi，vj)和(vj，vi)表示同一条边。
参考资料来源：百度百科-无向图
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 个顶点
所以n=8
又因为非连通再加1
所以是9
