一个有n个结点的无向图最多有多少条边？

Question

如题所述

Answer 1

有n个结点的无向图的边数最多为n（n-1）/2

资料补充

n(n-1)/2

无向图的最多边是无向完全图：包含n(n-1)/2条边。因为一条边关联两个结点，有向完全图的才有n(n-1)条弧。而无向图变联通至少边数：n-1。有向图变连通图至少需要边数：n。

最多的情况：即n个顶点中两两相连，若不计方向，n个点两两相连有n（n-1）/2条边，而由于强连通图是有向图，故每条边有两个方向，n（n-1）/2×2=n（n-1），故有n个顶点的强连通图最多有n（n-1）条边。

简单来说，若一个图中每条边都是无方向的，则称为无向图。

（1）无向边的表示

无向图中的边均是顶点的无序对，无序对通常用圆括号表示。

例：无序对(vi，vj)和(vj，vi)表示同一条边。

（2）无向图的表示

例：下面(b)图中的G2和(c)图中的G3均是无向图，它们的顶点集和边集分别为：

V(G2)={v1，v2，v3，v4}

E(G2)={(vl，v2)，(v1，v3)，(v1，v4)，(v2，v3)，(v2，v4)，(v3，v4)}

V(G3)={v1，v2，v3，v4，v5，v6，v7}

E(G3)={(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7)}

每个顶点相关联的边最多有n-1条，因此n个顶点的无向图最多有n*（n-1）条边

可以这样理解当第一个结点指向其他n-1个结点时第二个结点只能指向其余n-2个结点而不能指向第一个否则成环。可以从拓扑排序角度理解为何最大，假设图用邻接矩阵存储同时编号成三角矩阵(有向无环图可以拓扑排序肯定可以编号)，当存满上(或下)三角矩阵时边达到最多，同时假设还有有向边在下(或上)三角则必定成环。