在一个包含8个顶点的无向连通图中使用克鲁斯卡尔算法构建最小生成树,当算法执行过程中已经选取的边的数量为3时,若此时所有顶点的度均为偶数,则接下来要选取的下一条边的性质必然是:
答案解析
克鲁斯卡尔算法每次选取权重最小且不形成环的边。如果所有顶点的度均为偶数,意味着所有已选取的边所连接的顶点形成若干个子图,且每个子图内的度均为偶数。这说明不存在一个连通分量中只有一个顶点度为奇数,因为度为奇数的顶点总是成对出现。由于此时已选取3条边,所以至少存在两个连通分量(极端情况下是三个,但题目已经说明了所有顶点都是偶数),因此必然至少存在两个尚未连通的分量。此时,要继续构建最小生成树,下一条边必然需要连接不同的连通分量,以此来减少连通分量,直至构建出覆盖所有顶点的树。选项A描述的是连接同一个连通分量内的顶点,这将导致形成回路(因为已经满足偶数顶点的条件),不满足最小生成树的要求;选项C违反了克鲁斯卡尔算法的原则;选项D等同于选项A,因此正确答案是B。此时的连通分量可以是1个(形成回路),2个,3个。由于已经选取了3条边,最极端的情况3个顶点连接,此时也无法形成环。
正确答案:B