企源知识库

无向图G中含7个顶点，顶点间的边是随机设罝的，为保证图G在任何情况下都是连通的，则需要的边数最少是 。
【正确答案】：16
【题目解析】：若保证无向图在任何情况下都是连通的，即任意变动图G中的边，图G始终保持连通，首先需要G的任意6个结点构成完全联通子图G1，需要15条边，然后在添加一条边使第7结点与G 1连起来，共需16条边。