組合せとグラフの理論（塩田）第6回 (1)　木
戻る / 次へ

定義と例

　まずは木の定義から。
Def.1
  1. 閉路を持たない連結無向グラフを「木」と呼ぶ。
  2. 閉路を持たない無向グラフを「林」と呼ぶ。
　言い換えれば、林とは木の和である、ということになります。
Ex.2 　頂点数 5 の木は同型の意味で 3 種類あります：
　この 3 つのグラフの和をとってひとつのグラフと思うと林になります。
Ex.3　次のような二分木はトーナメント表でおなじみでしょう。 基本的なデータ構造としてもよく目にするはずです。
Rem.4　ランダムな木を描くのは簡単です：
  1. 頂点をひとつ描く
  2. を継ぎ足してゆく

木であることの言い換え

　木は重要な構造ですので、木である条件をいろいろ言い換えておきましょう。
Th.5　頂点数 $n$ のグラフ $T=(V,E)$ について、 次の条件は全て同値である：
  1. $T$ が木であること
  2. $T$ は閉路を持たず、辺数 $=n-1$
  3. $T$ は連結で、辺数 $=n-1$
  4. $T$ は連結で、全ての辺が橋である
  5. 任意の 2 頂点 $u$, $v$ $\in V$ に対して、$u$-$v$ 道が 1 本だけ存在する。
  6. $T$ は閉路を持たないが、$T$ にどんな辺を付加して閉路が 1 つだけできる
その証明のために補題を用意します：
Lemma 6　$e$ を $G$ の辺とする。このとき
  1. $e$ が橋である
    　$\Leftrightarrow$　$e$ を含む閉路は無い
    　$\Leftrightarrow$　$G-e$ は $G$ より連結成分が 1 つだけ多い
  2. $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}$
２つの閉路を重ねて描いておいて二重辺を削除すれば $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) の証明が書いてあります。 読んでおいてください。(証明以下省略)

戻る / 次へ