题目
16.关于图的割点与割边,下列说法正确的是(D).A. 有割边的图一定有割点B. 有割点的图一定有割边C. 有割边的简单图一定有割点D. 割边不在图的任一圈中
16.关于图的割点与割边,下列说法正确的是(D).
A. 有割边的图一定有割点
B. 有割点的图一定有割边
C. 有割边的简单图一定有割点
D. 割边不在图的任一圈中
题目解答
答案
D. 割边不在图的任一圈中
解析
步骤 1:理解割点和割边的定义
割点是指在无向图中,去掉该点后图的连通分量数增加的点。割边是指在无向图中,去掉该边后图的连通分量数增加的边。
步骤 2:分析选项A
选项A:有割边的图一定有割点。这个说法不正确,因为存在割边的图不一定有割点。例如,一个由两个点和一条边组成的图,这条边是割边,但没有割点。
步骤 3:分析选项B
选项B:有割点的图一定有割边。这个说法也不正确,因为存在割点的图不一定有割边。例如,一个由三个点和三条边组成的三角形图,每个点都是割点,但没有割边。
步骤 4:分析选项C
选项C:有割边的简单图一定有割点。这个说法不正确,因为即使在简单图中,存在割边的图也不一定有割点。例如,一个由两个点和一条边组成的简单图,这条边是割边,但没有割点。
步骤 5:分析选项D
选项D:割边不在图的任一圈中。这个说法正确,因为割边的定义是去掉该边后图的连通分量数增加,而如果割边在图的某个圈中,去掉该边后图的连通分量数不会增加。
割点是指在无向图中,去掉该点后图的连通分量数增加的点。割边是指在无向图中,去掉该边后图的连通分量数增加的边。
步骤 2:分析选项A
选项A:有割边的图一定有割点。这个说法不正确,因为存在割边的图不一定有割点。例如,一个由两个点和一条边组成的图,这条边是割边,但没有割点。
步骤 3:分析选项B
选项B:有割点的图一定有割边。这个说法也不正确,因为存在割点的图不一定有割边。例如,一个由三个点和三条边组成的三角形图,每个点都是割点,但没有割边。
步骤 4:分析选项C
选项C:有割边的简单图一定有割点。这个说法不正确,因为即使在简单图中,存在割边的图也不一定有割点。例如,一个由两个点和一条边组成的简单图,这条边是割边,但没有割点。
步骤 5:分析选项D
选项D:割边不在图的任一圈中。这个说法正确,因为割边的定义是去掉该边后图的连通分量数增加,而如果割边在图的某个圈中,去掉该边后图的连通分量数不会增加。