森

同義語：森(グラフ理論)forest非輪状グラフacyclic graph

概要

前提知識: グラフ, 木, 閉路, 連結成分(グラフ)

10 個の町があり、道路網が 3 つの互いに行き来できない地域に分かれていて、どの地域の中でも輪になった道がないとする。このとき道路はちょうど $10-3=7$ 本である。地域の数と町の数だけで道路の本数が決まってしまうのは、輪のない道路網では「道路を 1 本足すごとに、分かれていた 2 つの地域が 1 つにまとまる」からである。このように、閉路をもたないグラフを森という。各地域（連結成分）は木であり、森は木を何本か並べたものである。頂点に $1,\dots,n$ のラベルを付けた森の個数は、$n=1,2,3,4,5$ で $1,2,7,38,291$ であり、各木に 1 つずつ「根」を選んだ根付き森の個数は $(n+1)^{n-1}$、たとえば $n=4$ で $125$ になる（prop-forest-rooted-count）。

定義

以下、グラフは有限の単純グラフ $G=(V,E)$（ループも多重辺ももたない）とし、頂点の集合 $V$ は空でないとする。記法はグラフの記事の定義「歩道・道・閉路の定義」「連結性」に揃える。道は頂点が相異なる歩道、閉路は長さ $3$ 以上で始点に戻り途中の頂点が相異なる閉歩道である。$G$ の頂点数を $n(G)$、辺数を $m(G)$、連結成分の個数を $c(G)$ と書く。

森

グラフ $G$ が森（forest）であるとは、$G$ が閉路を部分グラフとして 1 つももたないことをいう。閉路をもたないことを 非輪状（acyclic）ともいう。連結な森が木である。

橋と根付き森

グラフ $G$ の辺 $e$ が橋（bridge）であるとは、$e$ を除いたグラフ $G-e:=(V,E\setminus\{e\})$ の連結成分の個数が $G$ より多いことをいう（橋(グラフ理論)）。
森 $F$ の各連結成分から頂点を 1 つずつ選んだものを根といい、森と根の組を 根付き森 という。
グラフ $G$ の 全域森 とは、頂点集合が $V$ で辺集合が $E$ の部分集合である森であって、連結成分の頂点集合が $G$ の連結成分の頂点集合と一致するものをいう。

$G$ が連結なら、全域森は全域木と同じものである。

直感

木が「頂点をすべて結ぶのに余分な辺が 1 本もない」グラフであるのに対し、森は「つなげる必要のある所だけをつなぎ、余分な辺が 1 本もない」グラフである。森の辺はどれも、除くとどこかが切れる（橋である）。逆に、辺を除いても切れない所があれば、その辺は輪（閉路）の一部である（lem-forest-edge-removal）。この「余分がない」性質が、辺の本数が頂点数と成分数だけで決まること（$m=n-c$）や、同じ成分の 2 頂点を結ぶ道が 1 本しかないことの源になっている（thm-forest-characterization）。

例と反例

森の例

辺をもたない $n$ 頂点のグラフ（グラフの記事の空グラフ）は森で、連結成分は $n$ 個の孤立点、辺数は $n-n=0$ である。
木は森である。道グラフ $P_4$ と星グラフ $K_{1,3}$ を並べた 8 頂点のグラフは、2 本の木からなる森で、辺は $3+3=6=8-2$ 本である。
森の部分グラフは森である（prop-forest-components）。特に、木から辺を何本か除くと森になる。木の記事の命題「木から辺を1本除くとちょうど2つの連結成分に分かれる」は、辺を 1 本除いた場合に成分がちょうど 2 個になることを述べている。

反例：辺の本数だけでは森と決まらない

3 頂点 $a,b,c$ を三角形に結び、孤立点 $d$ を加えたグラフ $G$ は、4 頂点 3 辺である。辺数 $3$ は $4$ 頂点の木の辺数 $4-1$ に等しく、$4$ 頂点の森の辺数の最大値 $3$（thm-forest-characterization により $m=n-c\le n-1$）とも矛盾しないが、$G$ は閉路 $a,b,c,a$ をもつので森でない。満たす性質：辺の本数が $n-1$ 以下。満たさない性質：非輪状。破る含意：「$m\le n-1$ $\Rightarrow$ 森」は成り立たない。正しい判定は「$m=n-c$」であり、$G$ では $c=2$ なので $n-c=2\neq3$ となって、森でないことが辺と成分の個数から分かる。

反例：非巡回有向グラフの基礎グラフ

向きのある辺で閉路（有向閉路）をもたない有向グラフでも、向きを忘れると森とは限らない。頂点 $1,2,3$ と有向辺 $(1,2),(2,3),(1,3)$ の有向グラフは有向閉路をもたないが、向きを忘れると三角形である（有向グラフの記事の例「反例：基礎グラフの閉路と有向閉路のずれ」）。「閉路をもたない」は、無向グラフと有向グラフで別の条件である。

森についてよく使う含意と、それが崩れる反例を表にまとめる。

外す条件・誤った含意	反例	成り立たなくなること
連結性（森 $\Rightarrow$ 木）	2 つの孤立点	木であること（森だが連結でない）
「$m\le n-1$ なら森」	三角形と孤立点（上の例）	非輪状（閉路 $a,b,c,a$ をもつ）
無向の閉路と有向閉路の区別	有向辺 $(1,2),(2,3),(1,3)$	基礎グラフが森であること
有限性	両側に無限に延びる道 $\mathbb{Z}$	葉の存在（prop-forest-leaves）。森だが次数 $1$ の頂点がない
単純グラフ	2 頂点を 2 本の平行な辺で結ぶ多重グラフ	すべての辺が橋であること（どちらの辺を除いても連結のまま）

表の最後の行の多重グラフは、平行な 2 辺を長さ $2$ の閉路とみなす流儀では森でなく、その流儀の下で thm-forest-characterization の 1 ⇔ 2 と整合する。閉路を長さ $3$ 以上に限るこの記事の定義をそのまま多重グラフに当てはめると、閉路をもたないのに橋でない辺があることになり、同値が崩れる。これが、この記事で単純グラフに限った理由である。

性質

部分グラフと連結成分

森の部分グラフは森である。
グラフ $G$ が森であることと、$G$ の各連結成分（その頂点と、両端がその成分に属する辺からなるグラフ）が木であることは同値である。

1：部分グラフ $H$ の閉路は、その頂点と辺がすべて $G$ の頂点と辺なので、$G$ の閉路でもある。
2：各連結成分は連結なので、それが木であることは閉路をもたないことと同値である。$G$ が森なら、1 により各成分は閉路をもたない。逆に $G$ が閉路 $C$ をもてば、$C$ の頂点は $C$ に沿って互いに結ばれるので同じ連結成分 $K$ に属し、$C$ の辺は両端が $K$ に属するので $K$ の辺である。よって $K$ は閉路をもち、木でない。$\square$

橋と辺の本数

辺を除いたときの連結成分の個数

グラフ $G$ の辺 $e=\{x,y\}$ について、$c(G-e)$ は $c(G)$ か $c(G)+1$ である。$c(G-e)=c(G)+1$ となる（$e$ が橋である）ことと、$e$ がどの閉路にも含まれないことは同値である。

前半は連結グラフの記事の補題「辺を 1 本加えたときの連結成分」の最後の主張であり、後半は閉路の記事の定理「閉路に含まれる辺と橋」である。$\square$

森の同値条件

グラフ $G$ について、つねに $m(G)\ge n(G)-c(G)$ が成り立つ。さらに、次の 4 条件は同値である。

$G$ は森である。
$G$ のすべての辺は橋である。
同じ連結成分に属する任意の 2 頂点を結ぶ道は、ちょうど 1 本である。
$m(G)=n(G)-c(G)$。

不等式と 1 ⇔ 4：連結グラフの記事の定理「辺の本数の下界と森」の 1 である。
1 ⇔ 2：閉路の記事の系「森と橋」である。
1 ⇒ 3：同じ成分の 2 頂点は道で結ばれる（歩道から重複する部分を切り取ればよい）。相異なる 2 本の道 $P:u=a_0,\dots,a_k=v$ と $Q:u=b_0,\dots,b_l=v$ があったとする。道は頂点が相異なるので、一方が他方の途中で終わることはなく、ある $i<\min\{k,l\}$ で $a_0=b_0,\dots,a_i=b_i$ かつ $a_{i+1}\neq b_{i+1}$ となる。$a_j$（$j>i$）が $b_{i+1},\dots,b_l$ のどれかに等しくなる最小の $j$ をとり（$a_k=v=b_l$ なので存在する）、$a_j=b_h$（$h>i$）とする。すると
$$ a_i,a_{i+1},\dots,a_j=b_h,b_{h-1},\dots,b_{i+1},b_i=a_i $$
は閉歩道で、$a_{i+1},\dots,a_{j-1}$ は $j$ の最小性から $b_{i+1},\dots,b_h$ と異なり、また $P$ が道なので $a_0,\dots,a_i$ とも異なる。$b_{i+1},\dots,b_h$ も $Q$ が道なので $b_i=a_i$ と異なる。よって途中の頂点は相異なる。長さは $(j-i)+(h-i)$ で、$j=h=i+1$ なら $a_{i+1}=b_{i+1}$ となって矛盾するので $3$ 以上である。これは閉路であり、$G$ が森であることに反する。
3 ⇒ 1：閉路 $v_0,v_1,\dots,v_{k-1},v_k=v_0$（$k\ge3$）があれば、$v_0,v_1$ と $v_0,v_{k-1},v_{k-2},\dots,v_1$ は $v_0$ から $v_1$ への相異なる 2 本の道である。$\square$

条件 4 から、森の辺の本数は頂点数と連結成分の個数だけで決まる。冒頭の 10 頂点・3 成分の森の辺は 7 本である。$G$ が連結（$c=1$）なら、条件 4 は「$n-1$ 本の辺をもつ連結グラフは木である」ことを含む。この場合の別証明は全域木の記事の命題「木の判定」にある。森の辺の本数が（森自身の連結成分の個数を $c$ として）$n-c$ であることは KT17 Proposition 12.3（p. 240。そこでの spanning forest は閉路をもたない全域部分グラフのこと）に、森であることと「どの 2 頂点を結ぶ道も高々 1 本」の同値は Lev24 Corollary 2.2.3（p. 120）にある。条件 3 で「同じ連結成分に属する」を外し「高々 1 本」とすれば、Levin の形になる。

葉と全域森

葉の存在

辺を 1 本以上もつ森には、次数 $1$ の頂点（葉）が 2 個以上ある。

$F$ の辺 $e$ の端点を含む連結成分 $K$ は木であり（prop-forest-components の 2）、頂点を 2 個以上もつ。$F$ の辺で $K$ の頂点に接続するものは $K$ の辺なので、$K$ の頂点の $K$ での次数は $F$ での次数に等しい。木の記事の命題「木の三つの基本性質」の 2 により $K$ は次数 $1$ の頂点を 2 個以上もち、それらは $F$ の次数 $1$ の頂点である。$\square$

全域森の存在

任意のグラフ $G$ は全域森をもつ。その辺はちょうど $n(G)-c(G)$ 本であり、全域森は $G$ から辺をちょうど $m(G)-n(G)+c(G)$ 本除いて得られる。

$G$ の各連結成分 $K$ は連結なので、全域木の記事の定理「全域木の存在」により全域木 $T_K$ をもつ。$T_K$ たちを合わせたグラフ $F$ は頂点集合が $V$、辺集合が $E$ の部分集合で、閉路をもたない（閉路は 1 つの $T_K$ に入るが、$T_K$ は木である）。また $F$ の連結成分はちょうど $T_K$ たちであり、その頂点集合は $G$ の連結成分と一致する。よって $F$ は全域森である。全域森は森で $c(F)=c(G)$、$n(F)=n(G)$ なので、thm-forest-characterization の 4 により辺は $n(G)-c(G)$ 本である。$\square$

除く辺の本数 $m-n+c$ は、どの全域森を選んでも $G$ だけで決まる。これは $G$ の閉路階数であり、閉路の記事の定理「閉路空間の次元と基本閉路」により閉路空間の次元に等しい。また、$G$ が森であることは $m-n+c=0$ と同値である（thm-forest-characterization の 4）。

数え上げ

根付き森の個数

$n\ge1$ とする。頂点集合 $\{1,\dots,n\}$ の上の根付き森は、ちょうど $(n+1)^{n-1}$ 個ある。

根付き森 $(F,R)$（$R$ は根の集合）に、新しい頂点 $0$ と、$0$ と各根 $r\in R$ を結ぶ辺を加えたグラフ $\Theta(F,R)$ を対応させる。$\Theta(F,R)$ は、各成分の木が根で $0$ につながるので連結であり、頂点が $n+1$ 個、辺が $(n-c(F))+c(F)=n$ 本なので、thm-forest-characterization の 4 により閉路をもたず、$\{0,1,\dots,n\}$ の上の木である。
逆に、$\{0,1,\dots,n\}$ の上の木 $T$ から頂点 $0$ と $0$ に接続する辺を除いたグラフを $F$ とし、$0$ に隣接していた頂点の集合を $R$ とする。$F$ は森であり（prop-forest-components の 1）、$F$ の各成分はちょうど 1 つの $R$ の元を含む。実際、$F$ の成分 $K$ の頂点 $a$ から $T$ の中で $0$ へ向かう道の、$0$ の直前の頂点は $R$ の元であり、その道の $0$ より前の部分は $F$ の中にあるので $K$ は $R$ の元を含む。$K$ が $R$ の元 $r\neq r'$ を含めば、$F$ の中の $r$ から $r'$ への道と $r',0,r$ から $T$ の閉路ができ、矛盾する。よって $(F,R)$ は根付き森であり、この対応は $\Theta$ の逆写像である。
したがって根付き森の個数は $\{0,1,\dots,n\}$ の上のラベル付き木の個数に等しく、Cayleyの公式（頂点数 $n+1$ のラベル付き木は $(n+1)^{(n+1)-2}$ 個）により $(n+1)^{n-1}$ である。$\square$

小さい $n$ で根付き森を数える

$n=3$、頂点 $\{1,2,3\}$ で、森の形ごとに根の選び方を数える。辺のない森は 3 つの孤立点からなり、根は各点で決まるので $1$ 通りである。辺が 1 本の森は辺の選び方が $3$ 通りで、辺でつながった 2 点の成分から根を $2$ 通り選び、孤立点の根は決まるので $3\cdot2=6$ 通りである。辺が 2 本の森は長さ $2$ の道で、真ん中の頂点の選び方が $3$ 通り、根の選び方が $3$ 通りなので $9$ 通りである。辺が 3 本だと三角形になって森でない。合計は $1+6+9=16=4^2$ で、prop-forest-rooted-count の $(n+1)^{n-1}$ と一致する。たとえば道 $1-2-3$ に根 $2$ を選んだ根付き森は、対応 $\Theta$ で頂点 $0$ を $2$ につないだ $\{0,1,2,3\}$ 上の星形の木に移る。$n=2$ でも、辺のない森（$1$ 通り）と辺 $12$ に根を選んだもの（$2$ 通り）で $3=3^1$ である。

$n=4$ なら $5^3=125$ である。根を選ばない森の個数 $1,2,7,38,291$（$n=1,\dots,5$）には、このような簡単な閉じた式はない（この 5 つの値は、各 $n$ についてすべての辺の部分集合を調べて数えた）。1 本の木の場合は、根付き木の個数 $n\cdot n^{n-2}=n^{n-1}$ が Cayleyの公式の記事の系「完全グラフの全域木と根付き木」にある。

森の彩色と流儀

森は二部グラフである（二部グラフの記事の例「木と森の二部性」）。奇数長の閉路どころか閉路を 1 つももたないからである。したがって、辺を 1 本以上もつ森の彩色数は $2$ である。
定義は KT17 §5.1（p. 73。閉路をもたないグラフを forest と呼ぶ）、Lev24 Definition 2.2.1（p. 117）と同じである。ループや多重辺を許すグラフでは、ループは長さ $1$ の閉路、平行な 2 辺は長さ $2$ の閉路とみなすのがふつうで（全域木の記事の定義「ループを許す多重グラフと基本用語」）、その流儀では森はループも多重辺ももたないので、本記事の単純グラフの森と同じものになる。
無限グラフでも「閉路をもたない」という定義は意味をもつが、辺の本数の式や葉の存在は有限性に依存する（両側に無限に延びる道は葉をもたない森である）。