book_opt_network_ans :2015/10/13(21:0)

1１章 章末問題解答
1. 頂点数 n の木は n − 1 本の辺を持つことを数学的帰納法で証明する．まず頂点数 1 の木は辺を持たないため，明らかに成り立つ，頂点数 k(≤ n − 1)の木が k − 1 本の辺を持つと仮定する．頂点数 n の木 T から一つの辺を削除したグラフは，２つの木 T1 と T2 からなる森である．T1 と T2 の頂点数をそれぞれ n1 と n2 とすると，帰納法の仮定より，T1 と T2 の辺数はそれぞれ n1 − 1 と n2 − 1 である．したがって，元の木 T の辺数は，(n1 − 1) + (n2 − 1) + 1 = (n1 + n2 ) − 1 = n − 1 であるため，k = nのときも成り立つ．したがって，数学的帰納法より題意が成り立つ．

2. 各頂点の次数を順に足しあげていくことを考える．これは，頂点において接続している辺を一つずつ数えてカウントアップしていき，それを終えると次の頂点に移って同様にカウントアップを続けていくことを意味する．その際，一つの辺はその両端点のそれぞれで数えられるため，一つの辺によってカウンタ値は 2 だけアップされる．したがって，このカウントアップを終えたときは，辺の総数の 2 倍のカウンタ値になっている．つまり，次数の和は辺数の 2 倍である．

3. 次数 di の頂点を vi とする．左辺は，頂点 v1 から vk までの次数の和を意味する．S = {v1 , v2 , ..., vk } の頂点に接続している辺集合は，両端点がS の頂点であるような辺の集合 E1 と，片方の端点が S の頂点で，他方がS 以外の頂点であるような辺の集合 E2 に分割できる．したがって，次数の和は，E1 に属する辺のみを数え上げた値と，E2 に属する辺のみを数え上げた値の合計になっている．前者は高々 k(k − 1) である．なぜなら，

S は k 個の頂点集合なので，|E1 | ≤ k(k − 1)/2（k 個の頂点からなる完全グラフの辺数が上限）だからである．S 以外の頂点 vj (k + 1 ≤ j ≤ n)と S との間の辺の数は高々 min{dj , k} なので，E2 に属する辺のみに関book_opt_network_ans :2015/10/13(21:0)2する次数の総和は，左辺は，k(k − 1) +n∑
j=k+1n∑min{dj , k} を超えることはない．以上から，min{dj , k} 以下であることがわかる．

j=k+1

この結果からも，グラフの各頂点の次数は任意の値をとることはできず，とりうる範囲が限定されることがわかる．

4. 略．
5.

(a) O(n2 )(b) O(nlog n )(c) O(n2 · 2n / log n)

6. 「大きさ p のナップザックに k 個目までの要素を入れる場合の価格の合計の最大値」に関して最適性原理が成り立つことに着目すればよい．

book_opt_network_ans :2015/10/13(21:0)

3２章 章末問題解答
1. 辺重みが全て 1 の場合は，経路長は経路に含まれる辺の本数に一致する．
幅優先探索によって得られる探索木において，頂点から始点までの唯一の経路の経路長より短い経路があるとすると，その経路に沿って先に訪問されているはずであるので矛盾する．したがって，辺重みが全て 1 の場合は，幅優先探索による探索木は最短路木になっている．

2. 図 1 に最短路木のみ示す．
v1 Ǜ‫ڼ‬ໜƱƢǔஇჺែஙv2 Ǜ‫ڼ‬ໜƱƢǔஇჺែஙv153v2v513v24v54214v3v1512v41
図1v3ネットワーク N1 の最短路木

3. 略
4. 図 2 に最大フローのみ示す．
v6
3 (3)

4 (8)
1 (1)

v2v45 (7)1 (2)v12 (2)v33 (3)

0 (5)

0 (2)

140 (1)v5

ͤ a (b) ƸᲦƦƷᡀǛ්ǕǔȕȭȸƷ‫ٻ‬Ɩƞƕ aᡀܾ᣽ƕ b ưƋǔƜƱǛॖԛƢǔ

図 2 ネットワーク N2 における最大フロー

1v4

book_opt_network_ans :2015/10/13(21:0)

4３章 章末問題解答
1. グラフ G1 における頂点 v, w 間の局所辺連結度は 4，局所点連結度は 4である．グラフの辺連結度は 3，点連結度も 3 である．

2. グラフ G2 における頂点 v1 と領域 W の間の NA 辺連結度は 3，NA 点連結度は 2 である．頂点 v2 と領域 W の間の NA 辺連結度は 3，NA 点連結度は 3 である．

3. 略
4.

(a) 図 3 に MA 順序と辺の順位の一例を挙げる．

351132336224712112211
図3218G3 の MA 順序と辺の順位(b) G3 における２辺連結性を保存する全域部分グラフの例を図 4 に挙げる．

(c) 本文では３辺連結化のためのアルゴリズムは紹介していないが，問題例の程度のグラフサイズであれば，３辺連結グラフの定義を理解していれば容易に見つけられるだろう（図 5）．

book_opt_network_ans :2015/10/13(21:0)

5351123312132472313241181722121(a) ᢿЎǰȩȕ F118(b) ᢿЎǰȩȕ F23512312621332411122262132135111627221218(c) ᢿЎǰȩȕ G’
図4G3 における２辺連結性を保存する全域部分グラフ

5. 本文では２本の辺削除の場合の保護辺決定アルゴリズムについては紹介していないが，頂点保護問題のところで紹介した２頂点削除の場合と同様の考え方で扱うことができる．まず，どのような一本の辺削除に対しても条件を満たす．次に，２本の同時辺削除に対して，条件を満たさなくなるような辺の組を列挙する（辺番号は図 6 を参照）
．２本の辺の組{e3 , e4 }, {e5 , e6 }, {e5 , e8 }, {e6 , e7 }, {e6 , e8 }, {e7 , e8 }, {e9 , e10 } のそれぞれは，その２辺が削除されるとサーバに対応する頂点を含む連結成分のサイズが 8 未満になってしまって条件を満たさないため，すくなくともいずれか一本の辺は保護されていなければならない．そのような最小本数の保護辺集合を求めることは，辺を頂点とするグラフ（図 7）において最小サイズの頂点被覆を求めることと等価である．最小頂点被覆問題
は一般には NP 困難問題ではあるが，この問題例の場合はグラフのサイズが小さいのですぐに最適解がわかり，{e3 , e5 , e6 , e7 } である．これがbook_opt_network_ans :2015/10/13(21:0)

6

˄ьᡀ

図5

G3 を３辺連結化する付加辺最小本数の保護辺集合である．なお，２本の辺削除の場合に対する多項式時間アルゴリズムも存在するが，ここで述べた考え方とは異なる．関心のある読者は参考文献 52 を参照してほしい．

e1

e3 e5e7 e9e11e2e4 e 6e8 e10e12̬ᜱᡀ
図6G4 における保護辺集合

6. 本文で紹介した頂点保護問題とは少し異なるが，同様の考え方で扱うことができる．一つの頂点削除に対して連結であるような保護頂点集合は，{v7 , v10 } である．2 個の頂点削除に対して連結であるような保護頂点集合は，頂点被覆問題に帰着して考えればよい．一般には NP 困難問題ではあるが，この問題例の場合はグラフのサイズが小さいのですぐに最適解がわかり，{v2 , v3 , v5 } である．あわせて，{v2 , v3 , v5 , v7 , v10 } が最小個数の保護頂点集合である．

book_opt_network_ans :2015/10/13(21:0)

7e1e12e2e11e3e10e4e9e8e5e6
図7e7

保護辺決定のための頂点被覆問題

v3v2v1v6v5v4v7v8v10v9
図8v11v12

G5 における保護頂点集合

book_opt_network_ans :2015/10/13(21:0)

8

４章 章末問題解答
1. できる．もっとも右の x3 節点から出る 0 枝を x5 節点につなぎ直しても，BDD の意味は変わらず，同じ確率を得られる．

2. 本章で紹介したアルゴリズムは，リンク順序によらず適用でき，同じ確率を得られる．ただし，得られる BDD の形状や圧縮度は，リンク順序によって異なる．BDD の節点数を最小にするリンク順序を求める問題
は NP 困難であり，経験的に幅優先探索による順序づけが用いられることが多い．

3. リンクを縮退するとき，そのリンクの両端ノードが同じ角括弧に属していると閉路が構成される．よって，その先の探索を終了し，終端節点 ⊥につなげばよい．たとえば，図 4.11 において，もっとも左の x3 節点が表すネットワーク状態は [v2 v3 ]∗ である．つまり，ノード v2 と v3 はすでに連結されている．ここで，リンク e3 = (v2 , v3 ) を稼働に決定すると(x3 = 1)，すでに連結されている v2 と v3 にさらにリンクを追加することで，閉路を構成することになる．このように，同じ角括弧に属するノードをさらにつながないように，BDD を構築していけばよい．このようにして得られる閉路を含まないサブグラフは「木の集合」となるため，一般に「森」と呼ばれる．

4. 連結対象ノード数を変更するのは簡単なので，次数の管理について述べる．ノードの次数が変化するのは，そのノードがフロンティアにあるときだけであるため，フロンティアのノードについてのみ次数を管理する．
各ノードについて次数の初期値を 0 とし，隣接リンクの状態を稼働に決定したら，次数を +1 する．ノードがフロンティアから外れると，そのノードの次数はもう変化しない．よって，フロンティアから外れるときに次数が指定された値になっていなければ，その先の探索を終了し，終book_opt_network_ans :2015/10/13(21:0)

9

端節点 ⊥ につなぐ．

book_opt_network_ans :2015/10/13(21:0)

10５章 章末問題解答
1. 本文では，ハミング制約を表す BDD の節点数を (N + 1)(m − 1) − 1 と述べたが，図 5.6b 左下のふたつの節点は分岐しないために省略でき，節点数は (N + 1)(m − 2) となる．この (N + 1)(m − 2) の BDD 節点を以下のルールに従ってつなぐと，ハミング制約を表す BDD になる (節点番号は図 5.6b と異なる)．なお，a%b は，a を b で割った余りとする．

si .x′j ← s1<=i<= (N + 1)(m − 3) ⊤(N + 1)(m − 3) < ii+N

si .((x′j + 1)%2) ← si%(N + 1) ̸= 0 ⊥i%(N + 1) = 0i+1(1)(2)

2. まとめてよい．これらの節点をまとめる前の BDD と，まとめた後の BDDは，いずれも同じ論理関数を表す．つまり，すべてのネットワーク状態x に対し，同じ値 (⊤ あるいは ⊥) に対応付けられている．
3. ４つの節点，sc,9 ∧ sh,11 ，sc,9 ∧ sh,9 ，sc,9 ∧ sh,10 ，⊤ ∧ sh,11 が等価になる．

4. sc,9 ∧ sh,11 と sc,9 ∧ sh,9 , sc,9 ∧ sh,10 , ⊤ ∧ sh,11 は，いずれも 0 枝が ⊥,1 枝が前問でまとめた節点を指しており，ひとつにまとめられる．このようにして，下から等価な節点をまとめ直す (規約化する) ことで，BDDをさらに小さく圧縮できる．本書はアルゴリズムではなくネットワークの教科書であるため規約化についての詳細な説明は行わないが，BDD における重要な技術であり，興味のある読者は 5 章のコーヒーブレイクを参照されたい．

5. 可能である．アルゴリズムが論理演算の種類に依存するのは，終端節点を処理する部分だけである．たとえば，論理積と論理積のアルゴリズムを比べると，1–4 行目は演算ごとに定義されるが，他の行はほぼ同じで

book_opt_network_ans :2015/10/13(21:0)

11Algorithm 1: s1 ⋄ s2 : 任意の論理演算 ⋄ を実行する A PPLY アルゴリズム
Input: s1 , s2 , ⋄/* ふたつの節点と演算子 */Output: s1 ⋄ s2
1if (s1 = ⊤ or s1 = ⊥) and (s2 = ⊤ or s2 = ⊥) then /* 終端節点を処理する */2

return s1 ⋄ s2

3else if (s1 , s2 ) ∈ S then4

return S[s1 , s2 ]5/* 等価な節点が S にある *//* 新たに節点を生成する (図 6.8) */else

6s′ ← N EW B DD N ODE

7s′ .0 ← s1 .0 ⋄ s2 .0/* 0 枝に対して再帰的に呼び出す */8s′ .1 ← s1 .1 ⋄ s2 .1/* 1 枝に対して再帰的に呼び出す */′9S[s1 , s2 ] ← s10

return s′/* S[s1 , s2 ] に保存する */ある．よって，演算対象が終端節点 (⊤ あるいは ⊥) であるときは演算ごとの処理を呼び出すが，それ以外は演算によらない再帰アルゴリズムとして記述できる．ある演算を行う演算子を ⋄ と表すとき，s1 ⋄ s2 を行う
アルゴリズム A PPLY を示す．

6. (略)

book_opt_network_ans :2015/10/13(21:0)

12６章 章末問題解答
1. IP アドレス x と接頭辞長 l が与えられたとき，l の節点を以下のルールに従って接続する．

si .xi ← s1<i<l ⊤i=li+1

si .((x′j + 1)%2) ← ⊥(3)(4)

2. 接尾辞を l ビットとすると，32 − l の節点を以下のルールに従って接続する．

si .xi ← s32 − l < i < 32 ⊤i = 32i+1

si .((x′j + 1)%2) ← ⊥(5)

(6)

3. 直線状であったアドレス部分の BDD は，下位に移動することで幅を持つようになる．これは，上位に移動したポート番号によってアドレスに関する条件が異なるためである．この例ではビットを入れ替えても節点数は変わらないが，一般には変化する．ただし，BDD を再構築することなく節点数を正確に予測することは難しく，ビット順の最適化は重要な課題となっている．

4. BDD ベクトルについて説明する．k 種類の処理を行うとき，処理番号を l = ⌈log2 k⌉ ビットにエンコードする．i 番目の処理番号を ai とすると，(a1 = 00 · · · 0, a2 = 00 · · · 1, · · · , ak ) のようになる．各ビットj ∈ {1, 2, · · · , l} について，ビット値を 0 → ⊥, 1 → ⊤ のように読み替
えて BDD を構築する．このようにして，処理番号のビットごとに l のBDD を得る．与えられたパケット x に対して l の BDD を辿り，0 ← ⊥,book_opt_network_ans :2015/10/13(21:0)

13

1 ← ⊤ のように逆に読み替えると，処理番号を得られる．BDD ベクト
ルが l 回の探索を行うのに対し，Multi-valued decision diagram は一回の探索で処理番号を得られる (詳細は参考文献 60 を参照)．

5. アルゴリズム R EACH 5 行目で代入を行う前に，書き換えルールに従ってBDD を修正する．BDD の修正方法は書き換えルールによるが，多くの場合は指定されたビットを特定の値に変更するだけなので，容易である．

book_opt_network_ans :2015/10/13(21:0)

14

７章 章末問題解答
1. 略
2. 略