無限グラフと木 | 数学の基礎 | 天游ヶ丘数理学院

定義 1.1 (グラフ・隣接・次数). 空でない集合 $V$ と、 $V$ の二元部分集合からなる集合 $E$ の対 $G=(V,E)$ を、単純無向グラフ (graph) という。 $V$ の元を頂点、 $E$ の元を辺といい、 $\{u,v\}\in E$ であるとき、 $u$ と $v$ は隣接するという。頂点 $v$ の隣接頂点の集合と次数を、それぞれ

N_G(v)=\{u\in V\mid\{u,v\}\in E\},\qquad \deg_G(v)=|N_G(v)|

と定める。次数が $1$ の頂点を葉という。

$V$ が有限であるグラフを有限グラフ、 $V$ が無限であるグラフを無限グラフという。これは「グラフ・木・連結性・オイラー路」で扱ったグラフの定義から、頂点集合の有限性を外した定義である。

定義 1.2 (歩道・道・閉路). グラフ $G=(V,E)$ と $n\in\N$ に対して、頂点列 $(v_0,\ldots,v_n)$ が $\{v_{i-1},v_i\}\in E$ （ $1\leq i\leq n$ ）を満たすとき、この列を $v_0$ から $v_n$ への長さ $n$ の歩道 (walk) という。頂点 $v_0$ を始点、 $v_n$ を終点という。長さ $0$ の歩道は一つの頂点だけからなる列である。

歩道 $(v_0,\ldots,v_n)$ の頂点がすべて相異なるとき、この歩道を道 (path) という。 $v_0=v_n$ のとき、この歩道は閉じているという。 $n\geq3$ 、 $v_0=v_n$ であり、 $v_0,\ldots,v_{n-1}$ が相異なるとき、この歩道を閉路 (cycle) という。

すべての $i$ （ $1\leq i<n$ ）について $v_{i-1}\neq v_{i+1}$ を満たす歩道を、後戻りのない歩道 (non-backtracking walk) という。長さ $0$ または $1$ の歩道はこの条件を満たす。道はすべて後戻りのない歩道である。閉路も後戻りのない歩道であるが、道ではない。

補題 1.3. グラフの任意の歩道に対して、その歩道の頂点と辺だけを使い、同じ始点と終点をもつ道が存在する。

証明. 与えられた歩道の頂点と辺だけを使い、同じ始点と終点をもつ歩道のうち、長さが最小のもの $(v_0,\ldots,v_n)$ を取る。そのような歩道は少なくとも与えられた歩道があり、長さは非負整数なので最小値が存在する。

$v_i=v_j$ （ $i<j$ ）であれば、 $v_{i+1},\ldots,v_j$ を除いた列は、同じ始点と終点をもつ、より短い歩道になる。 $j=n$ の場合にも、残る終点 $v_i$ は元の終点 $v_n$ と等しい。これは長さの最小性に反する。したがって頂点はすべて相異なり、選んだ歩道は道である。▨

補題 1.4. グラフの正の長さの後戻りのない閉じた歩道は、連続する部分歩道として閉路を含む。

証明. 歩道を $(v_0,\ldots,v_n)$ とする。 $n>0$ かつ $v_0=v_n$ であるから、 $i<j$ かつ $v_i=v_j$ となる添字の組が存在する。そのうち $j-i$ が最小の組を取る。辺は二元集合であるから $j-i\neq1$ であり、後戻りがないことから $j-i\neq2$ である。したがって $j-i\geq3$ である。最小性により $v_i,\ldots,v_{j-1}$ は相異なるので、 $(v_i,\ldots,v_j)$ は閉路である。▨

定義 2.1 (連結・木・全域木). グラフ $G=(V,E)$ の任意の二頂点 $u,v$ に対して、 $u$ から $v$ への歩道が存在するとき、 $G$ は連結 (connected) であるという。連結であり、閉路をもたないグラフを木 (tree) という。

グラフ $H=(W,F)$ が $W\subseteq V$ かつ $F\subseteq E$ を満たすとき、 $H$ を $G$ の部分グラフという。 $F\subseteq E$ に対して、 $(V,F)$ が木であるとき、 $(V,F)$ を $G$ の全域木 (spanning tree) という。

定理 2.2. グラフ $G=(V,E)$ に対して、次の条件は同値である。二頂点 $u,v$ は等しい場合も含める。

$G$ は木である。
任意の $u,v\in V$ に対して、 $u$ から $v$ への道がただ一つ存在する。
任意の $u,v\in V$ に対して、 $u$ から $v$ への後戻りのない歩道がただ一つ存在する。

証明.(1) $\Rightarrow$ (2)を示す。連結性と補題 1.3により、任意の二頂点を結ぶ道が存在する。 $u=v$ のとき、 $u$ から $u$ への道は長さ $0$ のものに限られる。

$u\neq v$ とし、 $u$ から $v$ への相異なる二つの道 $P=(p_0,\ldots,p_m)$ と $Q=(q_0,\ldots,q_n)$ があると仮定する。両方の道は終点 $v$ を一度しか通らないので、一方が他方の真の初期部分になることはない。したがって、共通の初期部分の最後の添字 $k$ が存在し、 $p_k=q_k$ かつ $p_{k+1}\neq q_{k+1}$ である。 $p_{k+1},\ldots,p_m$ のうち、 $q_{k+1},\ldots,q_n$ のどれかと一致する最初の頂点を $p_i=q_j$ とする。終点 $v$ が共通なので、この頂点は存在する。道 $P$ の $p_k$ から $p_i$ までの部分と、道 $Q$ の $q_k$ から $q_j$ までの部分とは、端点以外の頂点を共有しない。両部分の長さの和は、最初の辺が異なることから $3$ 以上である。前者を進み後者を逆順に進むと閉路を得る。これは $G$ が木であることに反する。よって道は一意である。

(2) $\Rightarrow$ (3)を示す。 $G$ に閉路 $(v_0,\ldots,v_n=v_0)$ があれば、 $(v_0,v_1)$ と $(v_0,v_{n-1},\ldots,v_1)$ は同じ二頂点を結ぶ異なる道となる。したがって $G$ は閉路をもたない。後戻りのない歩道に反復頂点があると、その二回の出現の間は正の長さの後戻りのない閉じた歩道であり、補題 1.4により閉路を含む。よって後戻りのない歩道は道である。道の存在と一意性が、そのまま後戻りのない歩道の存在と一意性を与える。

(3) $\Rightarrow$ (1)を示す。任意の二頂点を結ぶ歩道が存在するので $G$ は連結である。閉路が存在すれば、その閉路と、その始点だけからなる長さ $0$ の歩道は、同じ頂点を始点と終点とする二つの異なる後戻りのない歩道になる。これは一意性に反する。したがって $G$ は閉路をもたず、木である。▨

例 2.3 (整数直線). 頂点集合を $\Z$ 、辺集合を $\{\{n,n+1\}\mid n\in\Z\}$ とするグラフを考える。任意の二整数は、一方から他方まで $1$ ずつ増減する道で結ばれるので、このグラフは連結である。閉路が存在すれば、その頂点の最大値を $m$ としたとき、閉路上で $m$ に隣接する相異なる二頂点はいずれも $m-1$ でなければならず、矛盾する。したがって、このグラフは木である。

各頂点 $n$ の隣接頂点は $n-1,n+1$ であり、次数は $2$ である。この木には葉がない。二頂点以上の有限の木は葉をもつ（§D2.7 補題 3.2）が、この性質は無限の木では成り立たない。

例 2.4 (整数平面格子). 頂点集合を $\Z^2$ とし、 $(a,b)$ と $(c,d)$ が $|a-c|+|b-d|=1$ を満たすときに辺で結ぶ。このグラフでは、第一座標を $1$ ずつ変え、続いて第二座標を $1$ ずつ変えることで任意の二頂点を歩道で結ぶことができる。したがって、このグラフは連結である。各頂点 $(a,b)$ は $(a+1,b),(a-1,b),(a,b+1),(a,b-1)$ と隣接し、次数は $4$ である。

列 $((0,0),(1,0),(1,1),(0,1),(0,0))$ は閉路である。したがって、このグラフは木ではない。

例 2.5 (次数が四の無限木). 空列 $\varnothing$ と、長さ $n\geq1$ の有限列 $(a_1,\ldots,a_n)$ で

a_1\in\{0,1,2,3\},\qquad a_i\in\{0,1,2\}\quad(2\leq i\leq n)

を満たすものすべてを頂点とする。一方の列から末尾の一項を除くと他方の列になるとき、その二頂点を辺で結ぶ。

各頂点から末尾を順に除けば空列に達する。二頂点から空列への歩道をつなげば、その二頂点を結ぶ歩道を得るので、このグラフは連結である。閉路があると仮定し、その上で長さが最大の列 $w$ を取る。閉路上で $w$ に隣接する二頂点は、 $w$ より長くないので、どちらも $w$ の末尾を除いた列である。しかし閉路上の二つの隣接頂点は相異なるから、矛盾する。したがって、このグラフは木である。

空列に隣接する頂点は、長さ $1$ の四つの列である。空列以外の頂点には、末尾を除いた列が一つと、末尾に $0,1,2$ を加えた列が三つ隣接する。よって、すべての頂点の次数は $4$ である。任意の長さの零だけからなる列が頂点なので、この木は無限である。整数平面格子とこの木はともにすべての頂点の次数が $4$ であるが、閉路の有無が異なる。

注意 2.6.§D2.7 定理 3.6により、有限の連結グラフでは、木であることを「辺の個数が頂点の個数より一つ少ない」という条件で特徴づけることができる。無限集合の濃度については、有限の場合と同じように一つの差を読み取ることはできない。

たとえば整数直線では、 $n\mapsto\{n,n+1\}$ が頂点集合と辺集合の全単射である。整数直線に辺 $\{0,2\}$ を一つ加えたグラフでも、頂点集合と辺集合の全単射が存在する。実際、 $e_n=\{n,n+1\}$ とおくと、 $0$ を新しい辺に、 $n>0$ を $e_{n-1}$ に、 $n<0$ を $e_n$ に送る写像が全単射である。しかし後者には閉路 $(0,1,2,0)$ がある。頂点集合と辺集合の濃度の一致から、無限グラフが木であるかどうかを判定することはできない。

定義 3.1 (距離). 連結グラフ $G$ の二頂点 $u,v$ に対して、 $u$ から $v$ への歩道の長さの最小値を、 $u$ と $v$ の距離 (graph distance) といい、 $d_G(u,v)$ と書く。連結性により長さの集合は空でない非負整数の集合なので、この最小値は存在する。

定理 3.2. 選択公理を仮定する。任意の連結グラフは全域木をもつ。

証明. 連結グラフ $G=(V,E)$ の頂点 $r$ を一つ固定し、 $d(v)=d_G(r,v)$ とおく。 $v\neq r$ ならば $d(v)>0$ である。 $r$ から $v$ への最短の歩道の最後から二番目の頂点を $u$ とすると、 $d(u)\leq d(v)-1$ である。一方、 $r$ から $u$ への最短の歩道に辺 $\{u,v\}$ を付け加えると $d(v)\leq d(u)+1$ を得る。したがって $d(u)=d(v)-1$ であり、集合

A_v=\{u\in N_G(v)\mid d(u)=d(v)-1\}

は空でない。

§E1.20 定義 1.1の選択公理を族 $(A_v)_{v\in V\setminus\{r\}}$ に適用して、各 $v\neq r$ に $p(v)\in A_v$ を対応させる写像 $p$ を取る。辺集合を

F=\{\{v,p(v)\}\mid v\in V\setminus\{r\}\}

と定める。 $F\subseteq E$ である。頂点 $v$ から $p$ を一回適用するたびに $d$ の値は $1$ ずつ減り、 $d(v)$ 回後には距離 $0$ の頂点 $r$ に達する。したがって $(V,F)$ では各頂点と $r$ が歩道で結ばれ、 $(V,F)$ は連結である。

$(V,F)$ に閉路があると仮定する。閉路上で $d$ が最大となる頂点を $w$ とする。 $F$ の各辺の両端では $d$ の値がちょうど $1$ 異なるので、閉路上で $w$ に隣接する二頂点の $d$ の値は、どちらも $d(w)-1$ である。 $F$ の定義により、この二頂点はどちらも $p(w)$ に等しい。しかし閉路上の二つの隣接頂点は相異なるから、矛盾する。よって $(V,F)$ は閉路をもたず、 $G$ の全域木である。▨

注意 3.3. ZF の公理系のもとでは、「任意の連結グラフは全域木をもつ」という主張から選択公理を導くこともできる。したがって、この主張は選択公理と同値である。この同値は Höft–Howard の論文で示され、逆向きの含意の証明は Delhommé–Morillon の論文にも与えられている。

定義 4.1 (局所有限・片側無限道). グラフ $G=(V,E)$ の任意の頂点 $v$ に対して $N_G(v)$ が有限であるとき、 $G$ は局所有限 (locally finite) であるという。

$\N$ を添字集合とする相異なる頂点の列 $(v_n)_{n\in\N}$ が、すべての $n\in\N$ に対して $\{v_n,v_{n+1}\}\in E$ を満たすとき、この列を $v_0$ から始まる片側無限道 (ray) という。

定理 4.2 (Kőnig の無限補題). 従属選択公理を仮定する。無限連結局所有限グラフ $G=(V,E)$ の任意の頂点 $r$ に対して、 $r$ から始まる片側無限道が存在する。

証明. $n\in\N$ に対して $B_n=\{v\in V\mid d_G(r,v)\leq n\}$ とおく。 $B_0=\{r\}$ は有限であり、

B_{n+1}=B_n\cup\bigcup_{v\in B_n}N_G(v)

が成り立つ。実際、距離が $n+1$ の頂点は最短の歩道の最後から二番目の頂点と隣接し、その頂点は $B_n$ に属する。逆に、 $B_n$ の頂点に隣接する頂点には、長さ $n+1$ 以下の歩道で到達する。局所有限性により各 $N_G(v)$ は有限である。有限個の有限集合の合併は有限であるから、数学的帰納法により各 $B_n$ は有限である。この合併の有限性は、二つの有限集合の合併の個数が両者の個数の和以下であることを有限回適用して得られ、選択公理を要しない。

$V$ は無限なので、各 $n$ について $V\setminus B_n$ は空でない。その頂点 $v$ を一つ取ると、連結性と補題 1.3により、 $r$ から $v$ への道が存在する。その道の長さは $d_G(r,v)$ 以上であり、 $d_G(r,v)>n$ である。したがって $r$ から始まる任意に長い有限の道が存在する。

$r$ から始まる有限の道 $s$ が、任意の $m\in\N$ に対して長さ $m$ 以上の道の初期部分となるという性質を考える。この性質をもつ道すべての集合を $X$ とする。有限の頂点列はそのグラフを $\N\times V$ の部分集合とみなすことができるので、 $X$ は集合である。長さ $0$ の道 $(r)$ は $X$ に属する。

$s=(v_0,\ldots,v_k)\in X$ とする。 $s$ に一頂点を付け加えて得られる道の集合を $C_s$ とおく。付け加える頂点は $N_G(v_k)$ に属し、すでに $s$ に現れた頂点とは異なるので、 $C_s$ は有限である。 $s\in X$ であるから $s$ は長さ $k+1$ 以上の道に延長され、 $C_s$ は空でない。

$C_s$ のどの元も $X$ に属さないと仮定する。各 $t\in C_s$ に対して、 $t$ を初期部分とする長さ $m$ 以上の道が存在しないような最小の自然数 $m$ を $b(t)$ と定める。この値は最小性によって一意に定まり、選択公理を要しない。 $C_s$ は空でない有限集合なので、 $M=\max\{b(t)\mid t\in C_s\}$ が存在する。 $s\in X$ により、 $s$ を初期部分とする長さ $\max(M,k+1)$ 以上の道を取る。その最初の $k+1$ 本の辺からなる道を $t$ とすれば、 $t\in C_s$ である。取った道の長さは $M$ 以上であり、 $M\geq b(t)$ なので $b(t)$ 以上でもある。これは $b(t)$ の定義に反する。したがって、 $C_s$ の少なくとも一つの元は $X$ に属する。

$s,t\in X$ に対して、 $t$ が $s$ に一頂点を付け加えた道であることを $sRt$ と定める。前段の結論は、各 $s\in X$ に対して $sRt$ を満たす $t\in X$ が存在することを述べている。§E1.20 定義 4.2の従属選択公理を初期値 $(r)$ に対して適用すると、 $s_0=(r)$ かつ $s_nRs_{n+1}$ を満たす列 $(s_n)_{n\in\N}$ を得る。

$s_n$ の長さは $n$ であり、各 $s_{n+1}$ は $s_n$ を初期部分としてもつ。 $s_n$ の最後の頂点を $v_n$ とおくと、 $s_n=(v_0,\ldots,v_n)$ である。任意の $i<j$ に対して、 $v_i$ と $v_j$ は道 $s_j$ 上の異なる位置の頂点なので相異なる。また、 $\{v_n,v_{n+1}\}\in E$ であり、 $v_0=r$ である。よって $(v_n)_{n\in\N}$ は求める片側無限道である。▨

例 4.3 (局所有限性を外した場合). 頂点集合を $\N$ 、辺集合を $\{\{0,n\}\mid n\in\NN\}$ とする。任意の二頂点は $0$ を経由する歩道で結ばれるので、このグラフは無限連結グラフである。正の整数を表す頂点の次数は $1$ であり、 $0$ の隣接頂点はすべての正の整数なので、このグラフは局所有限でない。

道の内点には、その前後の相異なる二頂点が隣接する。したがって、このグラフで道の内点になることがあるのは $0$ だけであり、道の長さは高々 $2$ である。片側無限道があれば長さ $3$ の初期部分をもつはずなので、このグラフに片側無限道は存在しない。Kőnig の無限補題から局所有限性の仮定を外すことはできない。

§E1.24無限グラフと木

1 グラフと有限長の歩道

2 木の特徴づけ

3 選択公理と全域木

4 Kőnig の無限補題

参考文献

前提記事