完全图去掉几条边变成树

2021年8月14日 | 分类: 【题目】

【题目】

完全图去掉几条边变成树？

【解析】

在图论的数学领域，完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。

中文名: 完全图
分类: 有向完全图，无向完全图
外文名: complete graph
概念: 每对顶点之间都恰连有一条边的图
相关名词: 无向图

N个顶点的完全图的边的数目： $\frac{N (N - 1)}{2}$

N个顶点的树的边的数目： $(N - 1)$

相减：

\frac{N (N - 1)}{2} - (N - 1) = \frac{N * (N - 1)}{2} - \frac{2 * (N - 1)}{2} = \frac{(N - 1) (N - 2)}{2}