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