若无向图G=(V E)中含有7个顶点 要保证图G在任何情况下都是连通的 则需要的边数最少是()。【201

大学 顶点 已帮助 人

若无向图G=(V,E)中含有7个顶点,要保证图G在任何情况下都是连通的,则需要的边数最少是()。【2010年全国试题7(2分)】

A.6

B.15

C.16

D.21

请帮忙给出正确答案和分析,谢谢!

热搜:结点的度全为偶数的无向简单图一定可以一笔画

答案解析

难度★★☆ 搜索
  • 正确答案:C
    要保证n个顶点的无向图G在任何情况下都是连通的,则需要先由n-1个顶点组成完全图,从第n个顶点引一条到n-1任一顶点的边,则图肯定是连通的。本题先由6个顶点组成完全图,需要6(6-1)/2=15条边,故按题目要求“需要的边数最少”是15+1=16。