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

admin2015-12-30  14

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

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

答案C

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

最新回复(0)