证明：图 G 是森林，当且仅当 E=V-ω ，其中 ω 是 G 的连通片个数，ω＞1

wilsony

谁能证明？

luyuanhong

题  证明：图 G 是森林，当且仅当 E=V-ω ，其中 ω 是 G 的连通片个数，ω＞1 。

证  设在一个连通图 Gi 中，边数为 Ei，点数为 Vi ，下面证明一个结论：

    在连通图 Gi 中，必有 Ei≥Vi-1 。Ei=Vi-1 的充要条件是 Gi 是一棵树。

    因为 Gi 是连通图，所以总可以从一个点开始，在已有点上逐步添加边，得到整个图。

    在最初时，只有一个点，Ei=0 ，Vi=1 ，Ei=0=1-1=Vi-1 ，满足 Ei≥Vi-1 。

    以后每次在已有的点上添加一条边，有两种情况：

    如果添加边的另一端不与已有点重合，则边数与点数都增加 1 ，保持 Ei≥Vi-1 。

    如果添加边的另一端与已有点重合，则边数增加 1 ，点数不增加，也保持 Ei≥Vi-1 。

    所以在连通图 Gi 中始终有 Ei≥Vi-1 。

    如果 Gi 是树，则每次添加边的另一端不与已有点重合，边数与点数都增加 1 ，始终可以

保持 Ei=Vi-1 。

    反过来，如果 Gi 满足 Ei=Vi-1 ，则在添加边时，另一端不能与已有点重合，因为这样边数

增加 1 ，点数不增加，就会破坏 Ei=Vi-1 的关系。可见另一端与已有点重合的情况不可能发生。

由于每次添加边的另一端都不与已有点重合，所以这时 Gi 必定是一棵树。

    下面看分成 ω 个连通片的图 G ：

    如果 G 是森林，则 G 的每一个连通片 Gi 都是树，由上面结论可知必有 Ei=Vi-1（i=1,2,…,ω）。

G 的边数 E=∑(i=1,ω)Ei ，G 的点数 V=∑(i=1,ω)Vi ，这时显然有

    E = ∑(i=1,ω)Ei = ∑(i=1,ω)(Vi-1) = ∑(i=1,ω)Vi-∑(i=1,ω)1 = V-ω 。

    反过来，如果在 G 中有 E=V-ω ，下面用反证法证明 G 是一个森林。

    假设 G 不是森林，则 G 中至少有一个连通片不是树，不妨设这个连通片是 G1 ，由上面的结论可知，

G1 不满足 E1=V1-1 ，必有 E1＞V1-1 。G 中其他连通片 Gi 都满足 Ei≥Vi-1（i=2,…,ω）。这时有

    E = E1+∑(i=2,ω)Ei ＞ V1-1+∑(i=2,ω)(Vi-1) = ∑(i=1,ω)Vi-∑(i=1,ω)1 = V-ω 。

与 E=V-ω 矛盾，所以假设不成立，这时 G 必定是森林。

wilsony

谢谢陆老师！