题目
一个无向连通图的生成树是含有该连通图的全部顶点的( )。A. 极小连通子图B. 极小子图C. 极大连通子图D. 极大子图
一个无向连通图的生成树是含有该连通图的全部顶点的( )。
A. 极小连通子图
B. 极小子图
C. 极大连通子图
D. 极大子图
题目解答
答案
A. 极小连通子图
解析
步骤 1:理解生成树的定义
生成树是无向连通图的一个子图,它包含原图的所有顶点,且是一个无环的连通图。生成树是原图的一个极小连通子图,因为它包含了原图的所有顶点,但边数最少,且保持连通性。
步骤 2:分析选项
A. 极小连通子图:生成树是原图的一个极小连通子图,因为它包含了原图的所有顶点,但边数最少,且保持连通性。
B. 极小子图:极小子图不一定保持连通性,因此不正确。
C. 极大连通子图:极大连通子图是指包含尽可能多的边的连通子图,而生成树是极小连通子图,因此不正确。
D. 极大子图:极大子图不一定保持连通性,因此不正确。
步骤 3:选择正确答案
根据生成树的定义和分析,正确答案是A. 极小连通子图。
生成树是无向连通图的一个子图,它包含原图的所有顶点,且是一个无环的连通图。生成树是原图的一个极小连通子图,因为它包含了原图的所有顶点,但边数最少,且保持连通性。
步骤 2:分析选项
A. 极小连通子图:生成树是原图的一个极小连通子图,因为它包含了原图的所有顶点,但边数最少,且保持连通性。
B. 极小子图:极小子图不一定保持连通性,因此不正确。
C. 极大连通子图:极大连通子图是指包含尽可能多的边的连通子图,而生成树是极小连通子图,因此不正确。
D. 极大子图:极大子图不一定保持连通性,因此不正确。
步骤 3:选择正确答案
根据生成树的定义和分析,正确答案是A. 极小连通子图。