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

admin2013-04-26  49

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

选项 A、6
B、15
C、16
D、21

答案C

解析 考查图的连通性。要保证无向图G在任何情况下都是连通的,即任意变动图G中的边,G始终保持连通,首先需要G的任意6个结点构成完全连通子图G1,需15条边,然后再添一条边将第7个结点与G1连接起来,共需16条边。
转载请注明原文地址:https://kaotiyun.com/show/55xi777K
0

最新回复(0)