最少应该有（n-1）条边吗？
我不确定最多的情况
2个回答
7
是的.. 无向连通图的最小边数为(n-1)条。为了看清这一点，因为图是连通的，那么每个顶点到每个其他顶点都必须有唯一的路径，并删除任何边都将使图变为不连通状态。
对于最大边数（假设是简单图），每个顶点都连接到所有其他顶点，这就产生了n(n-1)/2 条边（使用握手引理）。另一种方式是查看 K_n（具有 n 个顶点的完全图），它具有最大数量的边。
- Xline
1
删除任何一条边都会使图形不连通。为什么？ - Kakaji
7
声明：如果有N个顶点，则最小值为N-1，最大值为N*(N-1)/2。
证明：
考虑一个邻接矩阵，其中元素要么是1（表示存在一条边），要么是0（表示不存在一条边）。对于一个连通的图来说，在上三角的每一行中至少必须有一个“1”。
通过在上三角的每一行中仅放置一个“1”，可以实现最小值。现在，如果邻接矩阵是N×N的，则第一行在上三角中有N-1个元素，第二行在上三角中有N-2个元素，......，最后一行在上三角中没有元素。也就是说，“带有上三角”的总共有N-1行，每行只有一个“1”。因此，边的数量为N-1。 最大值发生在上三角的每个元素都是1的情况下。现在，整个矩阵的上三角的元素数为
1 + 2 + ... + (N-2) + (N-1) = N*(N-1)/2。
对于最后一个等式，请回忆你的微积分课程中的有限和。请参见此处的第二个公式，并用“(N-1)”替换“m”：https://en.wikipedia.org/wiki/List_of_mathematical_series#Sums_of_powers PS：我真希望在SO上能使用LaTeX！
证明：
考虑一个邻接矩阵，其中元素要么是1（表示存在一条边），要么是0（表示不存在一条边）。对于一个连通的图来说，在上三角的每一行中至少必须有一个“1”。
通过在上三角的每一行中仅放置一个“1”，可以实现最小值。现在，如果邻接矩阵是N×N的，则第一行在上三角中有N-1个元素，第二行在上三角中有N-2个元素，......，最后一行在上三角中没有元素。也就是说，“带有上三角”的总共有N-1行，每行只有一个“1”。因此，边的数量为N-1。 最大值发生在上三角的每个元素都是1的情况下。现在，整个矩阵的上三角的元素数为
1 + 2 + ... + (N-2) + (N-1) = N*(N-1)/2。
对于最后一个等式，请回忆你的微积分课程中的有限和。请参见此处的第二个公式，并用“(N-1)”替换“m”：https://en.wikipedia.org/wiki/List_of_mathematical_series#Sums_of_powers PS：我真希望在SO上能使用LaTeX！
- RMurphy
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接