无向图#

无向简单图的一对顶点之间至多有一条边，因此最多有 $\binom n2$ 条边。

边界的构造方法如下：

• 非连通图的边数最大时，由一个孤立顶点和一个 $n-1$ 阶完全图 $K_{n-1}$ 组成。
• 连通图至少含有一棵生成树，因此 $e \geqslant n-1$。
• $n$ 主导时，如果不要求连通，可以不断加入孤立顶点，所以 $n$ 没有上界。

无向图中的环#

无环的无向图称为森林，连通的森林称为树。

若森林有 $c$ 个连通分量，则

因此，无向图满足 $e \geqslant n$ 时一定含环；反过来不成立，因为“一个三角形加若干孤立顶点”在 $e<n$ 时也可以含环。

“含环图”表示图中至少有一个环；“环图” $C_n$ 特指所有顶点度数均为 $2$ 的连通图，此时 $n \geqslant 3$ 且 $e=n$。

有向图#

有向简单图中，一对不同顶点 $u,v$ 之间可以同时存在 $u\to v$ 和 $v\to u$，所以最多有 $n(n-1)$ 条弧。

有向图的“连通”需要区分：

• 弱连通：忽略所有弧的方向后，得到的无向图连通。
• 强连通：任意两个顶点 $u,v$ 之间都同时存在从 $u$ 到 $v$ 和从 $v$ 到 $u$ 的有向路径。

其中：

• 弱连通有向图至少需要 $n-1$ 条弧；给一棵无向生成树的每条边指定方向即可达到下界。
• $n \geqslant 2$ 时，强连通有向图至少需要 $n$ 条弧；一个经过全部顶点的有向环可以达到下界。
• 非强连通图最多有 $(n-1)^2$ 条弧。达到上界的一种方法是：取一个顶点 $v$，其余 $n-1$ 个顶点构成完全有向图，并只保留 $v$ 与其余顶点之间同一方向的弧。

有向图中的环#

不含有向环的有向图称为有向无环图（Directed Acyclic Graph，DAG）。

DAG 一定存在拓扑序。按照拓扑序，弧只能从前面的顶点指向后面的顶点，因此每对顶点之间至多选一个方向，最多有 $\binom n2$ 条弧。把所有靠前的顶点都指向靠后的顶点即可达到上界。

这里把 $u\to v\to u$ 视为长度为 $2$ 的有向环，因此含有向环图最少可以只有 $2$ 条弧。

需要注意：DAG 只要求不存在有向环。忽略方向后，它对应的无向图仍然可能含环。例如 $1\to2$、$1\to3$、$2\to3$ 是 DAG，但忽略方向后得到一个三角形。

常用判定结论#

• 无向图中，$e>\dfrac{(n-1)(n-2)}2$ 时一定连通。
• 无向图中，$e\geqslant n$ 时一定含环；$e=n-1$ 只有在图连通时才能判定它是一棵树。
• 有向图中，$e>(n-1)(n-2)$ 时一定弱连通。
• 有向图中，$e>(n-1)^2$ 时一定强连通。
• 有向图中，$e>\dfrac{n(n-1)}2$ 时一定含有向环。