【正确答案】
A
【答案解析】 所谓连通无向图,指的是对图中任意顶点u、v,都存在路径使u、v连通,即任何两个点都有边相连。本题中,8个点中任选择两个,都可以有一条边,所以,最多有8*7/2=28条边,选项A正确。
所以,本题的答案为A。
结论1:一个有n个顶点的有向强连通图最多有n(n-1)条边,最少有n条边。
强连通图必须从任何一点出发都可以回到原处,每个结点至少要一条出路(单结点除外),至少有n条边,正好可以组成一个环。
结论2:一个有n个顶点的无向连通图最多有n(n-1)/2条边,最少有n-1条边。
可以通过数学归纳法进行证明。有兴趣的读者可以自行验证。
引申:若一个非连通的无向图最多有28条边,则该无向图至少有多少个顶点?
9个。假设有8个顶点,则8个顶点的无向图最多有28条边且该图为连通图。连通无向图构成条件:边=顶点数*(顶点数-1)/2。顶点数>=1,所以,该函数存在单调递增的单值反函数,边与顶点为增函数关系。故28条边的连通无向图顶点数最少为8个。
因此,28条边的非连通无向图为9个(加入一个孤立点)。