離散数学 07. 木 五島

離散数学 木 とは

循環 / 非循環グラフ 木 (tree)： 連結な森，森の連結成分 {木} ⊂ {森} 森は木の集合 無向 Undirected 有向 離散数学 循環 / 非循環グラフ 無向 Undirected 有向 Directed 閉路なし 非循環グラフ Acyclic 森 forest DAG 閉路あり 循環グラフ Cyclic 無向循環 グラフ 有向循環 木 (tree)： 連結な森，森の連結成分 {木} ⊂ {森} 森は木の集合 森

離散数学 循環 / 非循環グラフの例 非循環グラフ 循環グラフ 木 木 無向循環グラフ DAG DAG DAG 有向循環グラフ

根 (root) （連結非循環グラフの）根 (root)： 頂点を1つ選んで， それが一番「上」にあると考える 木（無向）： 離散数学 根 (root) （連結非循環グラフの）根 (root)： 頂点を1つ選んで， それが一番「上」にあると考える 木（無向）： どの頂点も根になり得る 根付き木 (rooted tree) DAG（有向）： 根がない場合もある どれが根？ 根のない DAG

離散数学 木の性質

「木」 と 木（無向非循環グラフ） 「木」のイメージ： 「根があって，枝分かれして，葉に至る」 「木」＝木（無向非循環グラフ）？ 離散数学 「木」 と 木（無向非循環グラフ） 「木」のイメージ： 「根があって，枝分かれして，葉に至る」 「木」＝木（無向非循環グラフ）？ 「木」 ⇒ 木（無向非循環グラフ） 「木」なら，枝分かれした先で合流しない ⇒ 非循環 木（無向非循環グラフ） ⇒ 「木」 任意の頂点を根とみなすことができる 木なので，循環はない 連結なので，根からすべての頂点に到達可能 どれが根？

木 の 性質 任意の2頂点 x，y を結ぶ道はただ 1つ （辺の個数） = （頂点の個数） − 1 離散数学 木 の 性質 任意の2頂点 x，y を結ぶ道はただ 1つ （辺の個数） = （頂点の個数） − 1 （頂点数が2以上なら）少なくとも 2個の端末点がある 端末点： 次数 1 の頂点 頂点 −−，++ −−： 頂点数 n の木から端末点を1つ除去すると，頂点数 n − 1 の木になる． ++：頂点数 n の木に，頂点1つ（とこれらを接続する辺を1つ）を加えると， 頂点数 n + 1 の木になる．

離散数学 木 の 性質（証明 1/5） 任意の2頂点 x，y を結ぶ道はただ 1つ 2つあれば，閉路

木 の 性質（証明 2/5） −−： 頂点数 n の木から端末点を1つ除去すると，頂点数 n − 1 の木になる． 離散数学 木 の 性質（証明 2/5） −−： 頂点数 n の木から端末点を1つ除去すると，頂点数 n − 1 の木になる． 頂点を除去して閉路ができることはない． 端末点なので，除去しても非連結にはならない．

木 の 性質（証明 3/5） ++：頂点数 n の木に，頂点を1つと，これらを接続する辺を1つ加えると， 頂点数 n + 1 の木になる． 離散数学 木 の 性質（証明 3/5） ++：頂点数 n の木に，頂点を1つと，これらを接続する辺を1つ加えると， 頂点数 n + 1 の木になる． 頂点 1つと辺 1つを加えて閉路を作ることはできない．

木 の 性質（証明 4/5） 頂点数 ++ の繰り返しによって，任意の木を構築することができる． 離散数学 木 の 性質（証明 4/5） 頂点数 ++ の繰り返しによって，任意の木を構築することができる． 任意の木から，頂点数 −− を繰り返して頂点数 1 のグラフを得る． 頂点数 ++ を −− とは逆に繰り得返して元（任意の木）に戻せる． 4 3 1 2 2 1 3 4

木 の 性質（証明 5/5） （頂点数が2以上なら）少なくとも2個の端末点がある 頂点数2 の木には，2個の端末点がある． 離散数学 木 の 性質（証明 5/5） （頂点数が2以上なら）少なくとも2個の端末点がある 頂点数2 の木には，2個の端末点がある． 頂点 ++ すると… 端末点につなぐと，1つ減って 1つ増える． 非端末点につなぐと，1つ増える． （辺の数） = （頂点の数） − 1 頂点数2の木では，辺の数は 1，頂点の数は 2． 頂点 ++ すると，1ずつ増える． 1 2 3 4

離散数学 木の巡回

離散数学 visit() class Graph { private: /* … */ int left(int u); int right(int u); public: void visit(int u); }; void Graph::visit (int u) { if (left(u)) visit(left(u)); if (right(u)) visit(right(u)); } u の左の子の頂点の番号 u の右の子の頂点の番号 visit() の宣言 u： 頂点の番号 (> 0) u に左の子があれば，訪れる u に右の子があれば，訪れる

再帰呼び出しによる二分木の巡回 call call visit (int u) { if (left(u)) visit(left(u)); 離散数学 再帰呼び出しによる二分木の巡回 call call visit (int u) { if (left(u)) visit(left(u)); if (right(u)) visit(right(u)); } visit (int u) { if (left(u)) visit(left(u)); if (right(u)) visit(right(u)); } visit (int u) { if (left(u)) visit(left(u)); if (right(u)) visit(right(u)); } return visit (int u) { if (left(u)) visit(left(u)); if (right(u)) visit(right(u)); } visit (int u) { if (left(u)) visit(left(u)); if (right(u)) visit(right(u)); } c b a d e

再帰呼び出しによる二分木の巡回 行きがけ： call 直後 call visit (int u) { if (left(u)) 離散数学 再帰呼び出しによる二分木の巡回 行きがけ： call 直後 call visit (int u) { if (left(u)) visit(left(u)); if (right(u)) visit(right(u)); } visit (int u) { if (left(u)) visit(left(u)); if (right(u)) visit(right(u)); } visit (int u) { if (left(u)) visit(left(u)); if (right(u)) visit(right(u)); } return 帰りがけ： return 直前 visit (int u) { if (left(u)) visit(left(u)); if (right(u)) visit(right(u)); } visit (int u) { if (left(u)) visit(left(u)); if (right(u)) visit(right(u)); } 行きがけ c left b a d 帰りがけ e right

巡回の順序 木の巡回順序： 頂点の処理順序 行きがけ順 (pre-order) 通りがけ順 (in-order) （二分木のみ） 離散数学 巡回の順序 木の巡回順序： 頂点の処理順序 行きがけ順 (pre-order) 通りがけ順 (in-order) （二分木のみ） 帰りがけ順 (post-order) 頂点を訪れる (visit) 順番は変わらない が， 頂点を処理する順番が変わる 処理： コードでは頂点番号の表示 (print)．

二分木の巡回 (binary tree traversal) 離散数学 二分木の巡回 (binary tree traversal) 行きがけ順 (pre-order) 通りがけ順 (in-order) 帰りがけ順 (post-order) visit (int u) { print u; if (left(u)) visit(left(u)); if (right(u)) visit(right(u)); } visit (int u) { if (left(u)) visit(left(u)); print u; if (right(u)) visit(right(u)); } visit (int u) { if (left(u)) visit(left(u)); if (right(u)) visit(right(u)); print u; } c c c left b b b d d d a a a f f f e e e right g g g > abcdefg > cbdafeg > cdbfgea

木の巡回 (tree traversal) 行きがけ順 (pre-order) 帰りがけ順 (post-order) 離散数学 木の巡回 (tree traversal) 行きがけ順 (pre-order) 帰りがけ順 (post-order) visit (int u) { print u; foreach (v in adjacent(u)) visit(v); } visit (int u) { foreach (v in adjacent(u)) visit(v); print u; } 3 1 2 4 4 2 5 3 1 9 7 5 6 8 8 6 9 7

離散数学 次回の内容 グラフの探索 木の巡回の先 pre-order と post-order の理解が必要