組合せとグラフの理論(塩田)第6回 (1) 木
定義と例
まずは木の定義から。
Def.1
- 閉路を持たない連結無向グラフを「木」と呼ぶ。
- 閉路を持たない無向グラフを「林」と呼ぶ。
言い換えれば、林とは木の和である、ということになります。
この 3 つのグラフの和をとってひとつのグラフと思うと林になります。
Ex.3 次のような二分木はトーナメント表でおなじみでしょう。
基本的なデータ構造としてもよく目にするはずです。
Rem.4 ランダムな木を描くのは簡単です:
- 頂点をひとつ描く
- を継ぎ足してゆく
木であることの言い換え
木は重要な構造ですので、木である条件をいろいろ言い換えておきましょう。
Th.5 頂点数 $n$ のグラフ $T=(V,E)$ について、
次の条件は全て同値である:
- $T$ が木であること
- $T$ は閉路を持たず、辺数 $=n-1$
- $T$ は連結で、辺数 $=n-1$
- $T$ は連結で、全ての辺が橋である
- 任意の 2 頂点 $u$, $v$ $\in V$ に対して、$u$-$v$ 道が 1 本だけ存在する。
- $T$ は閉路を持たないが、$T$ にどんな辺を付加して閉路が 1 つだけできる
その証明のために補題を用意します:
Lemma 6 $e$ を $G$ の辺とする。このとき
- $e$ が橋である
$\Leftrightarrow$ $e$ を含む閉路は無い
$\Leftrightarrow$ $G-e$ は $G$ より連結成分が 1 つだけ多い
- $e$ を含む閉路が 2 つあれば、$e$ を含まない閉路もある
証明の要点 (1) $e=uv$ を含む閉路が無ければ、
$G$ では同じ連結成分に属していた $u$ と $v$ が、
$G-e$ では異なる連結成分に属します。
| $\Rightarrow$ |
|
$G$ | | $G-e$ |
逆に $e=uv$ を含む閉路が有れば、$G-e$ においても $u$ と $v$ は同じ連結成分に属します。
| $\Rightarrow$ |
|
$G$ | | $G-e$ |
(2) たとえば次のグラフのように
$e$ を含む閉路が 2 つあれば、
$\phantom{\longrightarrow}$
2つの閉路を重ねて描いておいて二重辺を削除すれば $e$ を含まない閉路たちが残ります。
$\longrightarrow$
(証明の要点終)
Th.5 の証明 (1) ⇒ (2) 辺 $e$ をひとつ取ります。
L'a 6 より $e$ は橋で、
$T-e$ は閉路を含まないので 2 つの木 $T_1$, $T_2$ の和になります。
すると帰納法の仮定から
( $T$ の辺数 ) $=$ ( $T-e$ の辺数 ) $+1$
$=$ ( $T_1$ の辺数 ) $+$ ( $T_2$ の辺数 ) $+1$
$=$ ( $T_1$ の頂点数 $-1$ ) $+$ ( $T_2$ の頂点数 $-1$ ) $+1$
$=n-1$
(2) ⇒ (3) $T$ は閉路を持たないので林、すなわち木の和です。
その木の本数を $k$ 本とすれば、(1) ⇒ (2) は既に証明しましたので
( $T$ の辺数 ) $=n-k$.
これが $n-1$ と等しいということは $k=1$、すなわち $T$ は連結になります。
教科書にはこの後 (3) ⇒ (4) ⇒ (5) ⇒ (6) ⇒ (1) の証明が書いてあります。
読んでおいてください。(証明以下省略)