题目
若图G不是连通图,则G的补图一定是连通图。A. 正确B. 错误
若图G不是连通图,则G的补图一定是连通图。
A. 正确
B. 错误
题目解答
答案
A. 正确
解析
步骤 1:定义连通图和补图
连通图是指图中任意两个顶点之间都存在路径的图。补图是指在原图的基础上,将所有未连接的顶点对之间添加一条边,而将所有已连接的顶点对之间的边删除后得到的图。
步骤 2:分析非连通图的补图
假设图G不是连通图,那么G中至少存在两个顶点u和v,使得u和v之间不存在路径。在G的补图中,u和v之间会有一条边,因为它们在G中没有边。因此,u和v之间存在路径,即u和v是连通的。
步骤 3:证明补图是连通图
由于G不是连通图,所以G中至少存在两个连通分量。在G的补图中,每个连通分量中的顶点之间都会有一条边,因为它们在G中没有边。因此,每个连通分量中的顶点之间存在路径,即每个连通分量中的顶点是连通的。此外,由于G中至少存在两个连通分量,所以在G的补图中,至少存在两个连通分量中的顶点之间存在边,即至少存在两个连通分量中的顶点是连通的。因此,G的补图是连通图。
连通图是指图中任意两个顶点之间都存在路径的图。补图是指在原图的基础上,将所有未连接的顶点对之间添加一条边,而将所有已连接的顶点对之间的边删除后得到的图。
步骤 2:分析非连通图的补图
假设图G不是连通图,那么G中至少存在两个顶点u和v,使得u和v之间不存在路径。在G的补图中,u和v之间会有一条边,因为它们在G中没有边。因此,u和v之间存在路径,即u和v是连通的。
步骤 3:证明补图是连通图
由于G不是连通图,所以G中至少存在两个连通分量。在G的补图中,每个连通分量中的顶点之间都会有一条边,因为它们在G中没有边。因此,每个连通分量中的顶点之间存在路径,即每个连通分量中的顶点是连通的。此外,由于G中至少存在两个连通分量,所以在G的补图中,至少存在两个连通分量中的顶点之间存在边,即至少存在两个连通分量中的顶点是连通的。因此,G的补图是连通图。