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

admin2018-08-12 15

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

选项

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

解析

转载请注明原文地址:https://jikaoti.com/ti/FPfjFFFM

计算机408

相关试题推荐

随机试题

最新回复(0)