一道很有意思的证明题
来源:百度知道 编辑:UC知道 时间:2024/05/13 03:48:26
试证明若图G有n个顶点,n-1条边,不存在回路,则G是连通图。
因为一条边有两个端点那么n-1条边就有2n-2个端点
因为不存在回路也就是说不可能有两条边首尾都连在一起
又因为只有n个顶点,说明他只有两个端点是悬空的(这个应该大家都知道我就不证明了)
所以G是连通的
UC知道是一部内容开放、自由的互动网络百科全书
客观、专业、权威的知识性百科全书
来源:百度知道 编辑:UC知道 时间:2024/05/13 03:48:26
因为一条边有两个端点那么n-1条边就有2n-2个端点
因为不存在回路也就是说不可能有两条边首尾都连在一起
又因为只有n个顶点,说明他只有两个端点是悬空的(这个应该大家都知道我就不证明了)
所以G是连通的