设无向图G包含n个顶点和m条边,且G的连通分量个数为k。若G中存在一条边(u, v),使得添加该边后G的连通分量个数变为k-1,则下列哪项一定成立?

答案解析

**A. 正确** 根据连通分量的定义,如果u和v属于同一个连通分量,那么添加边(u, v)后连通分量个数不会减少。 **B. 错误** 如果u和v属于同一个连通分量,那么添加边(u, v)后连通分量个数不会减少。 **C. 错误** 添加边(u, v)后,u和v所在的连通分量会合并,因此连通分量个数减少1。不存在边(x, y)使得删除后连通分量个数增加1。 **D. 错误** 根据连通分量的定义,如果G中不存在边(x, y)使得删除后连通分量个数增加1,那么G一定是连通的,与题设矛盾。
正确答案:A
随机推荐
开始刷题