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$ を含まない閉路もある

Def.7　連結なグラフ $G$ の部分グラフ $T$ が「$G$ の全域木である」とは、

1. $T$ は木で、
2. $G$ のすべての頂点を含むこと

Ex.8　$G=$ のとき、 次の部分グラフはいずれも $G$ の全域木です。 とか とか とか

Def.9　要素を一列に並べたデータ構造を「線形リスト」と言います。 線形リストのうち、要素の追加・取り出し方法が特別なもの 2 つを定義します。

1. キュー：　新しい要素はリストの最後尾に追加し、リストの先頭から要素を取り出す。
2. スタック：　新しい要素はリストの先頭に追加し、リストの先頭から要素を取り出す。

それぞれ別の呼び方としては、

1. キュー = FIFO ( First-In-First-Out )：　先に追加されたものから先に処理される
2. スタック = LIFO ( Last-In-First-Out ) ：　最後に追加されたものが先に処理される

Ex.10　

• レジに並ぶお客さん（待ち行列）は、先に並んだ人から順番に支払いをするのでキューになります。
• コンビニのペット飲料も、後ろから補給して一番前のものから売れてゆくのでキューになります。

• 本屋さんで山積みになった雑誌は、最後に乗せた一番上の物から売れてゆくのでスタックになります。
• スーパーマーケットの買い物カゴも、最後に重ねた一番上のカゴから取ってゆくのでスタックになります。

Algorithm 11（幅優先探索、BFS = Breadth-First-Search ）

• 入力：連結なグラフ $G$ と、その頂点 $v$
• 出力：$v$ を根とする $G$ のBFS木 $T$

1. $v$ を要素とするキュー $Q=\{\,v\,\}$ を作り、 $T$ の初期値は $v$ 一点からなる木とする。
2. $Q$ の先頭から $x$ を取り出し、$x$ の未探索な隣接点のすべてを、番号の小さい順に $y_1$, $y_2$, $\cdots$, $y_s$ とする。
3. $Q$ の最後尾に $y_1$, $y_2$, $\cdots$, $y_s$ をこの順で追加し、 $T$ には辺 $xy_1$, $xy_2$, $\cdots$, $xy_s$ をすべて追加する。　
4. $Q$ が空(くう)リストになれば $T$ を出力して終了。そうでなければ 2°へ戻れ。

Ex.12　まずは二分木の場合に、チョー丁寧に動作を確認してみましょう。

　次の図で $v=0$ を根として幅優先探索を実行します。 最初は、キューが $Q=\{\,0\,\}$, 赤い部分が $T$ です。 　$x=0$ を $Q$ から取り出し、これを探索点（青い点）とします。 一旦 $Q$ は空になります。 　$x=0$ の隣接点 $1$, $2$ はどちらも未探索ですから $y_1=1$, $y_2=2$ になり、 $T$ には辺 $01$ と $02$ を追加、$Q=\{\,1,2\,\}$ になります。 　$x=1$ を $Q$ の先頭から取り出し、これを探索点とします。 $Q=\{\,2\,\}$ になります。 　$x=1$ の隣接点 $0$, $3$, $4$ のうち未探索なのは $y_1=3$, $y_2=4$ の 2 つで、 $T$ には辺 $13$ と $14$ を追加、$Q=\{\,2,3,4\,\}$ になります。 　$x=2$ を $Q$ の先頭から取り出し、これを探索点とします。 $Q=\{\,3,4\,\}$ になります。 　$x=2$ の隣接点 $0$, $5$, $6$ のうち未探索なのは $y_1=5$, $y_2=6$ の 2 つで、 $T$ には辺 $25$ と $26$ を追加、$Q=\{\,3,4,5,6\,\}$ になります。 　未探索点が無くなりましたので人間がやるときはここでおしまいです。 （アルゴリズム的にはこのあと、$3$, $4$, $5$, $6$ を $Q$ から取り出して $Q$ が空になって終了します。）

Rem.13（ここ大事！）自分が探索点 $x$（青い点）に立っていて、 $x$ の隣接点までしか見ることができない、というイマジネーションを働かせてください。

　Ex.12 ではそれぞれの場面で

$x=0$ のとき		$x=1$ のとき		$x=2$ のとき

しか見えていなくて、探索済みの赤い点以外の、黒い点たち全てへ幅広く木を伸ばす、 と考えます。

※　慣れてくれば、キューを横に書くだけで作業できるようになります。

Ex.14　もうひとつ木ではないグラフで、もっとラフにやってみます。やはり $v=0$ を根とします。

　根 $v=0$ から探索を開始します。 　探索点 $0$ から未探索点 $1$, $2$ が見えますので、 $0$ から $1$, $2$ へ辺を伸ばします。 探索点は、キュー $Q=\{\, 1,2\,\}$ の先頭要素 $1$ に移します。 　探索点 $1$ から未探索点 $3$, $4$ が見えますので、 $1$ から $3$, $4$ へ辺を伸ばします。 探索点は、キュー $Q=\{\, 2, 3, 4\,\}$ の先頭要素 $2$ に移します。 　探索点 $2$ から未探索点 $5$ が見えますので、$x=2$ から $5$ へ辺を伸ばして終了です。

Algorithm 15（深さ優先探索、DFS = Depth-First-Search ）

• 入力：連結なグラフ $G$ と、その頂点 $v$
• 出力：$v$ を根とする $G$ のDFS木 $T$

1. 空スタック $S=\{\ \}$ を作り、$T$ の初期値は $v$ 一点からなる木とする。また探索点を $x=v$ とする。
2. $x$ の未探索な隣接点があれば、そのうち番号の一番小さいものを $y$ とする。 そうでなければ 4°へ。
3. $S$ の先頭に $x$ を追加し、$T$ には辺 $xy$ を付加する。探索点を $x=y$ として 2°へ。
4. $S$ が空(くう)であれば終了。 そうでなければ $S$ の先頭から $x$ を取り出して探索点とし、2°へ。

Ex.16　再び二分木でチョー丁寧に動作を確認しましょう。

　次の図で $v=0$ を根として深さ優先探索を実行します。 最初は、スタック $S$ は空、赤い部分が $T$ です。 　探索点（青い点）は $x=0$とします。 　$x=0$ の隣接点 $1$, $2$ のうち番号の小さい方を $y=1$ とします。 $S$ の先頭に $x=0$ を追加し $S=\{\,0\,\}$, $T$ には辺 $01$ を付加し、探索点を $x=1$ とします。 　$x=1$ の未探索な隣接点 $3$, $4$ のうち番号の小さい方を $y=3$ とします。 $S$ の先頭に $x=1$ を追加し $S=\{\,1,0\,\}$, $T$ には辺 $13$ を付加し、探索点を $x=3$ とします。 　$x=3$ には未探索な隣接点はありませんので、 $S$ の先頭から $x=1$ を取り出し探索点とします。$S=\{\,0\,\}$ になります。 　$x=1$ の未探索な隣接点は $4$ のみですので $y=4$ とします。 $S$ の先頭に $x=1$ を追加し $S=\{\,1,0\,\}$, $T$ には辺 $14$ を付加し、探索点を $x=4$ とします。 　$x=4$ には未探索な隣接点はありませんので、 $S$ の先頭から $x=1$ を取り出し探索点とします。$S=\{\,0\,\}$ になります。 　$x=1$ には未探索な隣接点はありませんので、 $S$ の先頭から $x=0$ を取り出し探索点とします。$S=\{\ \}$ になります。 　$x=0$ の未探索な隣接点は $2$ のみですので $y=2$ とします。 $S$ の先頭に $x=0$ を追加し $S=\{\,0\,\}$, $T$ には辺 $02$ を付加し、探索点を $x=2$ とします。 　$x=2$ の未探索な隣接点 $5$, $6$ のうち番号の小さい方を $y=5$ とします。 $S$ の先頭に $x=2$ を追加し $S=\{\,2,0\,\}$, $T$ には辺 $25$ を付加し、探索点を $x=5$ とします。 　$x=5$ には未探索な隣接点はありませんので、 $S$ の先頭から $x=2$ を取り出し探索点とします。$S=\{\,0\,\}$ になります。 　$x=2$ の未探索な隣接点は $6$ のみですので、$y=6$ とします。 $S$ の先頭に $x=2$ を追加し $S=\{\,2,0\,\}$, $T$ には辺 $26$ を付加し、探索点を $x=6$ とします。 　未探索点が無くなりましたので人間がやるときはここでおしまいです。 （アルゴリズム的にはこのあと、$2$, $0$ を $S$ から取り出して $S$ が空になって終了します。）

Rem.17（ここ大事！）　深さ優先探索の要点は

• $T$ には辺は 1 本ずつしか付加しない。
• 探索点に未探索な隣接点がある限り、深く深く進んでゆく。
• 探索点に未探索な隣接点が無い時は、$T$ の辺をたどって「親」へ戻る。（バックトラック、と言う。）

※　こちらも慣れてくればグラフの絵ひとつだけでできるようになります。

Ex.18　Ex.14と同じグラフで、やはり $v=0$ を根として、ラフにやってみます。

　根 $0$ から一番番号の小さい未探索点 $1$ へ進みます。 　探索点 $1$ から一番番号の小さい未探索点 $2$ へ進みます。 　探索点 $2$ から一番番号の小さい未探索点 $3$ へ進みます。 　探索点 $3$ から一番番号の小さい未探索点 $4$ へ進みます。 　$4$ には未探索な隣接点がありませんので 赤い辺を通って $3$ へバックトラックします。 　$3$ にも未探索な隣接点がありませんので更に 赤い辺を通って $2$ へバックトラックします。 　$2$ から $5$ へ進んで終了です。

Th.19　BFS木は、根から他の頂点への最短路を与える。

Def.20　DFS木においては親子関係が考えられ、根に近い方の頂点を祖先、根から遠い方の頂点を子孫と定める。

Th.21　DFS木に使われなかった辺は、必ず祖先と子孫をつなぐ。

Th.22　連結グラフ $G$ の頂点 $v$ を根とするDFS木を $T$ とするとき、 $v$ が $G$ のカット点であること $\Leftrightarrow$ $T$ において $v$ の子が 2 人以上いること