如果无向完全图G中有36条边,则G的生成树有 条边。
时间: 2024-04-03 07:34:32 浏览: 305
用顶点数组和边数组存放顶点和边信息-数据结构课件
无向完全图有n个顶点时,共有n*(n-1)/2条边。因此,当无向完全图G中有36条边时,它有n个顶点,满足n*(n-1)/2 = 36,解得n=9。
在无向完全图中,任意n个顶点形成的子图都是一个无向完全图。因此,G的生成树中必须包括图中的所有9个顶点,否则无法覆盖整个图。
而包括9个顶点的生成树是一个连通的无向图,恰好包含8条边。具体地,我们可以使用普通的 Prim 算法或 Kruskal 算法来构建这样一棵生成树。 因此,无向完全图G的生成树有8条边。
阅读全文