证明：具有n个顶点和多于n一1条边的无向连通图G一定不是树。

admin2017-11-14 53

问题证明：具有n个顶点和多于n一1条边的无向连通图G一定不是树。

选项

答案此题考查的知识点是图的定义。具有n个顶点n—1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n一1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树(在图论中树定义为无回路的连通图)。

解析

转载请注明原文地址:https://www.kaotiyun.com/show/wDRi777K

计算机408

相关试题推荐

随机试题

最新回复(0)