練習問題

\(S\) を要素数 \(n > 0\) の非空集合、\(f\colon S \to S\) と全域関数とする。\(D_{f}\) を頂点集合 \(S\) と辺集合 \(\left\{ \langle s \to f(s) \rangle \; | \; s \in S \right\}\) を持つ有向グラフとする。

1. \(D_{f}\) の頂点の出次数として可能な値は何か？

2. \(D_{f}\) の頂点の入次数として可能な値は何か？

3. \(f\) が全射のとき、\(D_{f}\) の頂点の入次数として可能な値は何か？

握手補題 (補題 10.1.2) の証明は「任意の有向グラフにおいて、各頂点の入次数の和は図に書かれる矢印の本数に等しい」という事実を証明せずに使っている。つまり次の主張である:

しかし、この主張を自明だと考えない人もいるだろう。矢印の個数 \(\left| E (G) \right|\) に関する数学的帰納法でこの主張を証明せよ。

補題 10.2.5 は有向グラフの任意の頂点 \(x\), \(u\), \(v\) で不等式 \(\operatorname{dist}(u,v) \leq \operatorname{dist}(u,x) + \operatorname{dist}(x,v)\) が成り立つと主張する。また、等号の成立と「\(x\) が \(u\) から \(v\) への最短路上にある」が同値だとも主張する

1. 同値関係の右方向の含意を示せ。

2. 同値関係の左方向の含意を示せ。

1. 二つの頂点を含む閉歩道を持つものの、それら二つの頂点を含む閉路が存在しない有向グラフを示せ。

2. 補題 10.2.6「有向グラフの特定の頂点を通る長さが正の最短閉歩道は、その頂点を通る閉路である」を証明せよ。

\(3\) ビット列とは \(\texttt{0}\) または \(\texttt{1}\) を \(3\) 個並べた列である。\(8\) 個ある全ての \(3\) ビット列を連続する部分文字列に持つ文字列を得たいとする (\(3\) ビット列が現れる順序は何でも構わない)。例えば二進数として読んだときの順序で並べた \(\texttt{000}\), \(\texttt{001}\), \(\texttt{010}\), \(\ldots\), \(\texttt{111}\) を全て連結すると、条件を満たす長さ \(3 \cdot 8 = 24\) の文字列 \(\texttt{000001010\ldots111}\) が得られる。

しかし、この文字列の先頭部分を \(\texttt{00010}\ldots\) に変更すると条件を満たす長さがより短い文字列が得られる。このとき \(\texttt{000}\) は位置 \(1\) から位置 \(3\) に含まれ、\(\texttt{001}\) は位置 \(2\) から \(4\) に含まれ、\(\texttt{010}\) は位置 \(3\) から位置 \(5\) に含まれる。

1. 全ての \(3\) ビット列を連続する部分文字列に持つ文字列を \(3\text{-good}\) と呼ぶことにする。長さ \(10\) の \(3\text{-good}\) 文字列を見つけ、それより短い \(3\text{-good}\) 文字列が存在しない理由を説明せよ。

2. 図 \(\text{10.10}\) に示す有向グラフを \(G\) とする。\(G\) の全ての辺を含む歩道から \(3\text{-good}\) 文字列が構築できる理由を説明せよ。\(\text{(a)}\) で答えた \(3\text{-good}\) 文字列を構築する歩道を答えよ。

3. \(G\) の全ての辺をちょうど一つずつ含む歩道から最短の \(3\text{-good}\) 文字列を構築できると示せ¹。

4. 図 \(\text{10.10}\) の \(2\)-ビットグラフを一般化した、頂点集合が \(\left\{ 0, 1 \right\}^{k}\) の \(k\)-ビットグラフを \(B_{k}\) とする。\(B_{k}\) の全ての辺をちょうど一つずつ含む歩道²が最短の \((k+1)\text{-good}\) 文字列を決定する。

   この最短の長さを求めよ。\(B_{k}\) の「遷移」を定義し、任意の頂点の入次数が出次数と等しいことを示せ。さらに、任意の二頂点 (同一の二頂点を含む) を結ぶ長さ \(k\) 以下の路が存在すると示せ。

1. 長さが正の偶数である閉歩道に含まれるものの、奇数長の閉歩道には含まれない頂点を持つ有向グラフの例を示せ。

2. 奇数長の閉歩道に含まれるものの、奇数長の閉路には含まれない頂点を持つ有向グラフの例を示せ。

3. 奇数長の全ての閉歩道は、奇数長の閉路に含まれる頂点を含むと示せ。

グラフの Eulerオイラー 周遊 (Euler tour) とは、全ての辺をちょうど一度ずつ含む閉歩道を言う³。この名前は十八世紀に活躍した有名な数学者 Leonhardレオンハルト Eulerオイラー から来ている (彼の名前は定数 \(e \approx 2.718\) にも、トーシェント関数 \(\phi\) にも現れる ── Euler は様々な業績を残した)。

グラフが Euler 周遊を持つかどうかを一般的に判定するにはどうすればいいだろうか？ この問題は一見すると非常に難しく思える (この問題によく似た「全ての頂点を一度ずつ通る閉路を見つける」という Hamiltonハミルトン 閉路問題 (Hamiltonian circuit problem) は NP-完全であり、ミレニアム問題の一つである)。しかし、実際には簡単な判定法が存在する。

1. グラフが Euler 周遊を持つなら、任意の頂点の入次数と出次数は等しいと示せ。

有向グラフが弱接続 (weakly connected) とは、辺を両方向にたどれるとしたとき任意の二頂点を結ぶ「路」が存在することを言う⁴。以降の設問では \(\text{(a)}\) の (ほぼ) 逆を証明する: 任意の頂点の入次数と出次数が等しい弱接続なグラフは Euler 周遊を持つと示す。

任意の辺を高々一度しか含まない歩道を小道 (trail) と呼ぶ。

2. 弱接続なグラフの小道 \(\textbf{w}\) が全ての辺を含まないと仮定する。このとき、\(\textbf{w}\) に含まれる頂点を始点または終点に持ち、かつ \(\textbf{w}\) に含まれない辺が存在することを示せ。

以降の設問では、考えているグラフが弱接続で任意の頂点の入次数と出次数が等しいと仮定する。また、グラフの最長の小道を \(\textbf{w}\) とする。

3. もし \(\textbf{w}\) が閉歩道なら \(\textbf{w}\) は Euler 周遊だと示せ。

   ヒント: \(\text{(b)}\) を使う。

4. \(\textbf{w}\) の終点を始点とする辺は全て \(\textbf{w}\) に含まれると示せ。

5. もし \(\textbf{w}\) が閉歩道でないなら、\(\textbf{w}\) の終点の入次数が出次数より大きいと示せ。

   ヒント: \(\text{(d)}\) を使う。

6. 任意の頂点の入次数と出次数が等しい弱接続なグラフには Euler 周遊が存在すると結論付けよ。

重み付きグラフの歩道の重さ (weight) は歩道に含まれる辺の和と定義される。\(n\) 個の頂点を持つグラフ \(G\) の長さ \(k\) の最小重み歩道行列 (minimum weight matrix for length \(k\) walk) とは、任意の \(u, v \in V(G)\) が次の条件を満たす行列 \(W\) を言う:

\(\mathbb{R} \cup \left\{ \infty \right\}\) を要素に持つ二つの \(n \times n\) 行列 \(W\), \(M\) の \(\text{min+}\) 積 (\(\text{min+}\) product) は次の規則で定義される \(n \times n\) 行列 \(W \hspace{-5pt} \underset{\text{\scriptsize min+}}{\cdot} \hspace{-5pt}M\) である:

次の定理を証明せよ。

集合 \(A\), \(B\), \(R\), \(S\) を次のように定める:

ただし \(R\) は \(A\) から \(B\) への二項関係、\(S\) は \(B\) から \(B\) への二項関係とする。

次の二項関係のグラフに含まれる組を具体的に示せ:

1. \(S \circ R\)
2. \(S \circ S\)
3. \(S^{-1} \circ R\)

総当たり戦 (round-robin tournament) では、任意の異なる二人のプレイヤーが一度だけ対戦する。引き分けがないとき、総当たり戦の結果はトーナメント有向グラフ (tournament digraph) と呼ばれる有向グラフで表現できる。トーナメント有向グラフの頂点はプレイヤーを表し、辺 \(\langle x \to y \rangle\) は \(x\) が \(y\) に勝利したことを表す。

トーナメント有向グラフのランキング (ranking) とは、全てのプレイヤーを含む路を意味する。任意のプレイヤーはランキングで次に位置するプレイヤーに勝利するものの、さらに下位に位置するプレイヤーに敗北する可能性がある ── そのためランキングの作り方には様々な選択肢がある。

1. 一つ以上のランキングを持つトーナメント有向グラフの例を示せ。

2. トーナメント有向グラフが DAG ならランキングは高々 \(1\) 個だと示せ。

3. 任意の有限トーナメント有向グラフはランキングを持つと示せ。

\(R\) を集合 \(A\) 上の二項関係とする。\(R\) を有向グラフとみなし、その有向グラフ上の長さ \(n\) の歩道関係を \(W^{(n)}\) とする。つまり、次のように定める:

1. 全ての \(m, n \in \mathbb{N}\) で次の等式が成り立つと示せ:

   \[ W^{(n)} \circ W^{(m)} = W^{(m+n)} \tag{10.11}\]

   ここで \(\circ\) は二項関係の合成を表す。

2. \(n \geq 0\) に対して、\(n\) 個の \(R\) を合成した結果を \(R^{n}\) と表記すると定める。つまり \(R^{0} ::= \text{Id}_{A}\) および \(R_{n+1} ::= R \circ R^{n}\) と定義する。このとき全ての \(n \in \mathbb{N}\) で次の等式が成り立つと示せ:

   \[ R^{n} = W^{(n)} \tag{10.12}\]

3. 次の等式が成り立つと結論付けよ:

   \[ R^{+} = \bigcup_{i=1}^{|A|} R^{i} \]

   ここで \(R^{+}\) は \(R\) によって定まる \(A\) 上の正歩道関係 (第 10.4 節) である。

二つの集合 \(A = \left\{ a_{1},\ \ldots,\ a_{n} \right\}\), \(\,B = \left\{ b_{1},\ \ldots,\ b_{m} \right\}\) 間の二項関係 \(S\colon A \to B\) は、次の規則で定義される \(0\) と \(1\) を要素に持つ \(n \times m\) 行列 \(M_{S}\) で表現できる:

このように二項関係を行列で表現すると、二つの二項関係 \(R\), \(S\) の合成を対応する行列の「真理値」乗算 \(\otimes\) で計算できる。行列の真理値乗算は通常の行列乗算の加算を \(\operatorname{\text{\footnotesize OR}}\) に、乗算を \(\operatorname{\text{\footnotesize AND}}\) に置き換え、さらに \(0\), \(1\) をそれぞれ \(\textbf{False}\), \(\textbf{True}\) と同一視すると計算できる。具体的には次の通りである。\(C = \left\{ c_{1},\ \ldots,\ c_{p} \right\}\) および \(R\colon B \to C\) とする。このとき \(M_{R}\) は \(m \times p\) 行列であり、\(M_{S} \otimes M_{R}\) は次の規則で定義される \(n \times p\) 行列と定義される:

\(R \circ S\) の行列表現 \(M_{R \circ S}\) が \(M_{S} \otimes M_{R}\) に等しいと示せ (\(R\) と \(S\) の順番が逆なことに注意せよ)。

ニワトリは意外にも攻撃的な鳥であり、他のニワトリをつつくことで上下関係を形成する習性がある ── peckingつつき order順序 (上下関係) という言葉もここから来ている。農家の庭にいる任意の二羽のニワトリは必ず一方がもう一方をつつく関係にあり、逆方向につつきが起こることはない。次のいずれかの条件が成り立つとき、ニワトリ \(u\) がニワトリ \(v\) を事実上つつく (virtually pecks) と言うことにする:

1. \(u\) が \(v\) をつつく。

2. \(u\) が他のニワトリ \(w\) をつつき、\(w\) が \(v\) をつつく。

自分以外の全てのニワトリを事実上つつくニワトリを王 (king) と呼ぶ。

この状況は有向グラフで表現できる。この有向グラフの頂点はニワトリを表し、辺 \(\langle u \to v \rangle\) は \(u\) が \(v\) をつつくことを表す。図 \(\text{10.11}\) に示すグラフでは、\(4\) 羽のうち \(3\) 羽が王である。ニワトリ \(c\) は王でない: \(c\) は \(b\) をつつかず、加えて \(b\) をつつくどのニワトリもつつかない。ニワトリ \(a\) は王である: \(a\) は \(d\) をつつき、\(d\) は \(b\) と \(c\) をつつく。

一般に、任意の異なる二頂点間に辺がちょうど \(1\) 個ある有向グラフをトーナメント有向グラフ (tournament digraph) と呼ぶ。

1. 出次数が \(1\) の王が存在するような \(10\) 羽のニワトリからなるトーナメント有向グラフを定義せよ。

2. 全てのニワトリが王であるような \(5\) 羽のニワトリからなるトーナメント有向グラフを定義せよ。

3. 次の定理を証明せよ:

   定理[ニワトリの王定理 (king chicken theorem)]

   トーナメント有向グラフで出次数が最大のニワトリは王である。

   この定理からは次のことが分かる: 総当たり戦で勝利数が最も多かった選手は、ある選手 \(x\) に敗北していたとしても、\(x\) に勝利している別の選手に必ず勝利している。この意味で、最も多く勝利した選手は他の全ての選手に向かって「俺の方が強い」と言う権利を持つ。しかし図 \(\text{10.11}\) が示すように、勝利数が最大でないにもかかわらず同じことを言う権利を持つ選手が他にも (多く) 存在する可能性は残念ながらある。

\(n\) 要素の半順序集合は、どれだけの長さの鎖を持つことが保証されているか？ 反鎖についてはどうか？

完了させる必要があるタスクの集合が \(\left\{ A,\ \ldots,\ H \right\}\) で、タスク間の直接的な依存関係が次の DAG の通りだとする。この DAG の辺 \(\langle S \to T \rangle\) は \(S\) を開始する前に \(T\) を完了させる必要があることを示す:

1. 最長の鎖を示せ。

2. 最長の反鎖を示せ。

3. それぞれのタスクにかかる時間が \(1\) 分で同じとき、並列スケジュールを使うと全てのタスクを終わらせるのに最短で何分かかるか？

\(1\) から \(10{,}000\) まで整数を全て並べた列であって、長さ \(101\) の増加列または減少列が存在しないものを示せ。

頂点が単位時間で完了できるタスクを表し、辺がタスク間の直接的な依存関係を表す DAG がある。並列に実行可能なタスクの個数に制限はないと仮定する。

最短時間で全てのタスクを完了させる並列スケジュールが複数存在する DAG の頂点 (タスク) 数の最小値は何か？ 解答を注意深く正当化せよ。

次に示す DAG はタスク \(\left\{ 1,\ \ldots,\ 9 \right\}\) 間の直接的な依存関係を表す:

1. それぞれのタスクを完了させるのに \(1\) 時間かかるとき、全タスクの最短並列実行時間を求めよ。解答が正しい理由を簡単に説明せよ。

2. 並列に実行できるタスクの個数が最大で \(2\) 個のとき、最短並列実行時間を求めよ。解答が正しい理由を簡単に説明せよ。

次に示す DAG はタスク \(\left\{ 1,\ \ldots,\ 9 \right\}\) 間の直接的な依存関係を表す:

1. それぞれのタスクを完了させるのに \(1\) 時間かかるとき、全タスクの最短並列実行時間を求めよ。解答が正しい理由を簡単に説明せよ。

2. 並列に実行できるタスクの個数が最大で \(2\) 個のとき、最短並列実行時間を求めよ。解答が正しい理由を簡単に説明せよ。

図 \(\text{10.12}\) に示す DAG がタスク間の直接的な依存関係を表し、各頂点が表すタスクはどれも \(1\) 秒で実行できるとする。

1. この DAG が持つ最長の鎖は何か？ 複数ある場合は一つ答えれば十分である。

2. 最長の反鎖は何か？ 複数ある場合は一つ答えれば十分である。解答より長い反鎖が存在しないことを証明せよ。

3. 単一のプロセッサで全てのタスクを完了させるのにかかる時間はどれだけか？

4. 無限個のプロセッサが利用可能なとき、全てのタスクを完了させるのにかかる時間はどれだけか？

5. 全てのタスクを最適な時間で完了できる最小のプロセッサ数を求めよ。解答の正しさを示す並列スケジュールを示せ。

2006 年に MIT の情報科学科で開講される科目に指定される必須科目を次の表に示す。この表は間接的な必須科目関係を定義し、これは科目を頂点とする DAG で表される。

1. 貪欲 (greedy) な戦略を用いるとき、各タームで履修可能な科目を全て履修することになる。この貪欲な戦略を使ったときに各タームで履修する科目を表す完全なスケジュールを示すことで、各タームで履修できる科目の個数に制限がないとき全ての科目を履修するのに必要なターム数は最短で \(6\) であることを説明せよ。

2. 貪欲なスケジュールでは、第 \(2\) タームで \(\text{18.03}\) を含む \(5\) 個の科目を履修する。\(\text{18.03}\) を含まない \(5\) 要素集合であって、最適並列スケジュールの \(1\) ステップになれるものを示せ。そのような集合がいくつあるか計算できるか？

3. 各タームに科目を一つだけ履修しながら全ての科目を履修するスケジュールを示せ。

4. あなたは全ての科目を履修しようと考えているものの、タームごとに \(2\) 個の科目しか履修できないとする。卒業までに必要なターム数はどれだけか？ 解答が正しい理由を説明せよ。

5. タームごとに \(3\) 個の科目を履修できる場合はどうなるか？

情報科学科で TA を務める Lisaリサ と Annieアニー は、空いている暇な時間に銀河系を征服することにした。これが野心的なプロジェクトであると気が付いた二人は、Annie が持っていた講義ノートの裏側に必要なタスクを書き出した:

1. ロゴを考える: クールで帝国的な音楽も必要になる ── \(8\) 日

2. 艦隊を作る: Lobdellロブデル から食器をくすねて、超時空滅星艦をたっぷり建造する ── \(18\) 日

3. 国連を占拠する ── \(9\) 日 (タスク \(1\) の後)

4. Lisa の猫 Tailspinテールスピン に予防接種を受けさせる ── \(11\) 日 (タスク \(1\) の後)

5. コーヒースタンドを作る: 軍隊にカフェインを注入するため ── \(10\) 日 (タスク \(3\) の後)

6. 軍隊を訓練する: The Phantom Menace を数十回見ないと出られない部屋に閉じ込めることで、エリート星間兵士を生み出す ── \(4\) 日 (タスク \(3\), \(4\), \(5\) の後)

7. 艦隊を出撃させる: 超時空滅星艦隊で異星人を全て滅ぼし、栄えある銀河帝国を樹立する ── \(6\) 日 (タスク \(2\), \(6\) の後)

8. 巨大テック企業を撲滅する ── \(8\) 日 (タスク \(2\), \(6\) の後)

以上の情報を DAG として図 \(\text{10.13}\) に示す。頂点がタスクを表し、ラベルとして名前と所要時間が書かれている。二頂点を結ぶ辺は、始点のタスクを完了させてから終点のタスクを始める必要があることを表す。

1. タスクに一つずつ取り組みながら全てのタスクを完了させる順序の例を示せ。

Lisa と Annie は全てのタスクを可能な限り短い時間で完了させたいと思っている。ただし、次の労働条件を守ることに二人は同意した:

• 特定のタスクに割り当てられるのは一人だけ: 一つのタスクを二人が協力して進めることはできない。

• タスクの中断は不可: タスクに割り当てられた人物は、そのタスクを完了するまで続ける。例えば「Lisa は \(2\) 日間だけ艦隊を作り、そのタスクを中断して Tailspin に予防接種を受けさせ、それから艦隊の作成に戻る」といったことはできない。

2. Lisa と Annie は銀河征服にかかる時間を考えている。Annie はタスクにかかる日数の和をタスクに取り掛かる人数 (\(\text{=}\,2\)) で割った値が答えだと考えた。この値を求めよ。実際にかかる時間がこれより長くなる可能性があるのはなぜか？

3. Lisa は銀河征服にかかる時間を求める別の方法を提案した。彼女はクリティカルパス (各要素が一つ前の要素に依存するようなタスクの列の中で最も時間のかかるもの) の時間をタスクに取り掛かる人数で割った値が答えだと考えた。この値を求めよ。実際にかかる時間がこれより長くなる可能性があるのはなぜか？

4. Lisa と Annie が銀河を征服するのにかかる最短の日数を答えよ。証明は必要ない。

冪集合 \(\operatorname{pow}(\left\{ 1, 2, 3, 4 \right\})\) と真の包含関係 \(\subsetneq\) による半順序に関する次の問いに答えよ:

1. 最長の鎖を一つ答えよ。

2. 要素数 \(6\) の反鎖を一つ答えよ。

3. \(\operatorname{pow}(\left\{ 1, 2, 3, 4 \right\})\) のトポロジカルソートを一つ答えよ。

4. この半順序が \(16\) 個のタスクの依存関係を表すと考える。つまり、

   \[ A \subsetneq B \subseteq \left\{ 1, 2, 3, 4 \right\} \]

   が成り立つとき \(A\) を完了させてから \(B\) を開始しなければならないとする (いつも通り、それぞれのタスクにかかる時間は全て同じと仮定する)。最短並列時間で全てのタスクを完了させるとき、必要となるプロセッサの個数の最小値を答えよ。解答の正しさを証明せよ。

5. プロセッサが同時に \(3\) 個しか利用可能でないときの最短実行時間を求めよ。解答の正しさを証明せよ。

次の操作は任意の有向グラフ \(G\) に適用できる:

1. 閉路に含まれる辺を削除する。

2. 辺 \(\langle u \to v \rangle\) を含まない \(u\) から \(v\) への路が存在するとき、辺 \(\langle u \to v \rangle\) を削除する。

3. \(u\) と \(v\) を結ぶ路がいずれの方向にも存在しないとき、辺 \(\langle u \to v \rangle\) を追加する。

これらの操作を全て適用不可能になるまで適用し続ける手続きを \(P\) とする。\(P\) は状態機械でモデル化できる。初期状態は \(G\) であり、状態集合は \(G\) と同じ頂点を持つグラフ全体の集合である。

1. \(G\) の頂点集合が \(\left\{ 1, 2, 3, 4 \right\}\) で、辺集合が次の集合だとする:

   \[ \left\{ \langle 1 \to 2 \rangle,\ \langle 2 \to 3 \rangle,\ \langle 3 \to 4 \rangle,\ \langle 3 \to 2 \rangle,\ \langle 1 \to 2 \rangle \right\} \]

   \(P\) をモデル化する状態機械で \(G\) から到達可能な最終状態を全て答えよ。

線グラフ (line graph) とは、全ての辺が一つの路に含まれるグラフを言う。\(\text{(a)}\) で解答した最終的なグラフは全て線グラフである。

2. \(P\) が終了するときの有向グラフを \(H\) とする。\(H\) は \(G\) と同じ頂点を持つ線グラフだと示せ。

   ヒント: 有向グラフ \(H\) が線グラフでないなら操作が適用可能だと示す。

3. 「DAG である」が \(P\) の保存不変条件だと示せ。

4. \(G\) が DAG で \(P\) が終了するなら、最終的な線グラフの歩道関係が \(G\) のトポロジカルソートを与えると示せ。

   ヒント: DAG の任意の二頂点 \(u\), \(v\) に関する次の述語が保存不変条件だと示す:

   \[ P(u, v) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ \text{\(u\) から \(v\) への有向路が存在する} \]

5. \(G\) が有限なら \(P\) が終了することを証明せよ。

   ヒント: \(s\) を閉路の個数、\(e\) を辺の個数、\(p\) をいずれかの方向に路が存在する頂点の組の個数とする。このとき \(G\) の頂点数を \(n\) とすれば \(p \leq n^{2}\) が成り立つ。\(as + bp + e + c\) が遷移ごとに減少する非負整数になるような係数 \(a\), \(b\), \(c\) を見つける。

\(\prec\) を集合 \(A\) 上の狭義半順序とする。\(k \in \mathbb{N}\) に対して \(A_{k}\) を次のように定める:

1. \(A_{0}\), \(A_{1}\), \(\ldots\) が定義 10.5.7 の意味で \(\prec\) の並列スケジュールだと示せ。

2. \(A_{k}\) が反鎖だと示せ。

\(n\) 個のタスクがあり、それらの間の直接的な依存関係が DAG によって表されている。

1. \(p\) 個のプロセッサが同時に利用可能なとき、任意のスケジュールは \(\lceil n / p \rceil\) 以上の時間がかかることを示せ。

2. \(t - 1\) 要素の鎖と、その鎖の最後の要素に依存する \(n - (t - 1)\) 個の要素からなる \(n\) 頂点の DAG を \(D_{n,t}\) とする (下図)。

   

   \(D_{n,t}\) に対する並列最短時間スケジュールは何か？ それが一意だと説明せよ。いくつのプロセッサが必要となるか？

3. \(p\) 個のプロセッサが利用可能なときの \(D_{n,t}\) に対するスケジュールの最短時間を表す単純な式 \(M(n, t, p)\) を示せ。

4. 最大の鎖の要素数が \(t\) であるような任意の \(n\) 要素半順序には、\(p\) 個のプロセッサを用いるスケジュールであって所要時間が \(M(n, t, p)\) であるものが存在することを示せ。

   ヒント: \(t\) に関する数学的帰納法を使う。

\(\left\{ 1, \ldots, 12 \right\}\) 上の整除関係を表す DAG を図 \(\text{10.14}\) に示す。「この DAG に頂点 \(a\) から頂点 \(b\) への路の存在する」と「\(a \; | \; b\)」は同値である。この DAG に頂点 \(24\) を加えて集合 \(\left\{ 1, \ldots, 12, 24 \right\}\) の整除関係を表す DAG を作るには、最低で何本の辺を追加する必要があるか？ 追加すべき辺を具体的に示せ。

1. 任意の狭義半順序が DAG だと示せ。

2. 推移性を持たない最小の DAG を示せ。最小性を証明せよ。

3. 任意の DAG の正歩道関係が狭義半順序だと示せ。

1. \(n\) を正整数とする。冪集合 \(\operatorname{pow}(\left\{ 1, \ldots, n \right\})\) 上の空関係における極大要素および極小要素を (存在するなら) 答えよ。

2. 非負整数全体の集合 \(\mathbb{N}\) 上の整除関係における極大要素と極小要素を (存在するなら) 答えよ。最大要素および最小要素は存在するか？

3. \(1\) より大きい整数全体の集合上の整除関係における極大要素と極小要素を (存在するなら) 答えよ。

4. 極大要素と極小要素をどちらも持たない半順序集合の例を示せ。

5. 極小要素を一つだけ持ち、かつ最小要素を持たない半順序集合の例を示せ。

   ヒント: 解答は無限集合になるはずである。

真の包含関係 \(\subsetneq\) は \([1..6]\) の部分集合に関する (\(\operatorname{pow}([1..6])\) 上の) 狭義半順序を定義する。

1. この狭義半順序における鎖の要素数の最大値は何か？ 要素数最大の鎖を一つ示せ。

2. この狭義半順序における要素数最大の反鎖を一つ示せ。

3. 極大要素および極小要素を示せ。それらは最大要素または最小要素か？

4. 集合 \(\operatorname{pow}([1..6]) - \varnothing\) 上の狭義半順序 \(\subsetneq\) に対して \(\text{(c)}\) の質問に答えよ。

\(a\), \(b\) を有向グラフの異なる二頂点とする。\(a\) が \(b\) を被覆 (cover) するとは、辺 \(\langle a \to b \rangle\) が存在して、この辺が \(a\) から \(b\) への任意の路に含まれることを言う。このとき辺 \(\langle a \to b \rangle\) を被覆辺 (covering edge) と呼ぶ。

1. 図 \(\text{10.15}\) に示す DAG が持つ被覆辺は何か？

2. 任意の有向グラフ \(G\) に対して、辺として \(G\) の被覆辺だけを残した \(G\) の部分グラフを \(\operatorname{covering}(G)\) と表記する。\(D\) が有限 DAG のとき、\(\operatorname{covering}(D)\) と \(D\) が同じ正歩道関係を持つと示せ。

3. 二つの DAG が同じ正歩道関係を持つなら、両者の被覆辺全体の集合も等しいと示せ。

4. \(D\) を任意の有限 DAG とする。\(D\) と同じ正歩道関係を持つ有向グラフの中で辺の個数が最小のものは \(\operatorname{covering}(D)\) であり、他に存在しないと結論付けよ。

5. 頂点集合が \(\left\{ 1,2 \right\}\) であり同じ被覆辺を持つものの、正歩道関係が異なる二つの有向グラフを示せ。

   ヒント: 自己ループを利用する。

6. 1. 自己ループを持たない完全グラフ (complete graph) とは、任意の異なる二点間に両方向の辺が存在するグラフを言う。頂点集合が \(\left\{ 1, 2, 3 \right\}\) である自己ループを持たない完全グラフの被覆辺を答えよ。

   2. 頂点 \(1\), \(2\), \(3\) と辺 \(\langle 1 \to 2 \rangle\), \(\langle 2 \to 3 \rangle\), \(\langle 3 \to 1 \rangle\) を持つグラフの被覆辺は何か？

   3. \(\text{(i)}\), \(\text{(ii)}\) で考えたグラフの正歩道関係を答えよ。

任意の非空集合 \(D\) に対して、非対称性と対称性を両方持つ \(D\) 上の二項関係が一つだけ存在することを示せ。

\(D\) を要素数が \(n > 0\) の集合とする。対称性と反対称性を持つ \(D\) 上の二項関係がちょうど \(2^{n}\) 個あることを示せ。

集合 \(A\) 上の二項関係 \(R\) が推移性を持つなら \(R = R^{+}\) だと示せ。

\(R\) を集合 \(D\) 上の二項関係とする。\(R\) に関する基礎的な性質を次に示す:

1. 反射性

2. 非反射性

3. 対称性

4. 非対称性

5. 反対称性

6. 推移性

次の命題と同値な性質はどれかそれぞれ解答し、その理由を簡単に説明せよ:

1. \(R \cap \text{Id}_{D} = \varnothing\)
2. \(R \subseteq R^{-1}\)
3. \(R = R^{-1}\)
4. \(\text{Id}_{D} \subseteq R\)
5. \(R \circ R \subseteq R\)
6. \(R \cap R^{-1} = \varnothing\)
7. \(R \cap R^{-1} \subseteq \text{Id}_{D}\)

1. 上記の表は MIT で開講される科目の必須科目の関係を表す。この関係を表す有向グラフを書け。頂点に科目番号のラベルを付け、任意の科目からその必須科目へ向かう下向きの矢印が伸びるようにすること。

2. 真の包含関係 \(\subsetneq\) による半順序を持つ集合族であって \(\text{(a)}\) で考えた科目の関係と同型な (「同じ形を持つ」) ものを答えよ。

3. 空関係が狭義半順序である理由を説明し、\(5\) 個の要素を持つ集合上の空関係と同型な真の包含関係を持つ集合族を答えよ ── 空関係とは、任意の二要素が関係しない二項関係を言う。

4. \(\operatorname{pow}(\left\{ 1, 2, 3, 4 \right\})\) 上の真の上位集合関係 \(\supsetneq\) と同型な真の包含関係を持つ単純な集合族を答えよ。

この問題では補題 10.7.2 を証明する。この補題は「全ての弱半順序は包含関係 \(\subseteq\) による半順序を持つ集合族で表現できる (同型な包含関係を持つ集合族が存在する)」と主張する。これを言い換えた主張を次に示す:

1. 関数 \(L\colon A \to \mathcal{L}\) が全単射だと示せ。

2. 全ての \(a, b \in A\) で次の関係が成り立つと示すことで証明を完成させよ:

   \[ a \preceq b \ \ \longleftrightarrow \ \ L(a) \subseteq L(b) \tag{10.14}\]

第 10.7 節で説明したように、任意の狭義半順序には同型な真の包含関係を持つ集合族が存在する。具体的に言えば、集合 \(A\) 上の狭義半順序を \(R\) とするとき、任意の \(a \in A\) に対して \(L(a)\) を次のように定める:

このとき、全ての \(a, b \in A\) で次の関係が成り立つ:

1. 関係 \(\text{(10.16)}\) を狭義半順序と真の包含関係 \(\subsetneq\) の定義から始めて注意深く証明せよ。

2. \(L(a) = L(b)\) なら \(a = b\) だと示せ。

3. \(L(a)\) の定義 \(\text{(10.15)}\) から「\(\left\{ a \right\} \cup\)」を除去すると \(\text{(b)}\) の結果が成り立たないことが分かる例を示せ。

次に示す二項関係のそれぞれが「狭義半順序である」「弱半順序である」「いずれでもない」のどれかを答えよ。いずれでもない二項関係に対しては、どの公理が成り立たないか答えよ。

1. \(\operatorname{pow}(\left\{ 1,2,3,4,5 \right\})\) に関する上位集合関係 \(\supseteq\)

2. 任意の非負整数 \(a\), \(b\) に対して \(a \equiv b \ \ (\text{mod } 8)\) と同値な非負整数間の二項関係

3. 任意の命題論理式 \(G\), \(H\) に対して \(G \ \operatorname{\text{\footnotesize IMPLIES}}\ H\) の恒真性と同値な命題論理式間の二項関係

4. じゃんけんの手の間の「勝利する」関係 (じゃんけんを知らない読者へ: じゃんけんの手はグー・チョキ・パーの三種類であり、グーはチョキに、チョキはパーに、パーはグーに勝利する)

5. 実数全体の集合上の空関係

6. 整数全体の集合上の恒等関係

1. 非負整数全体の集合上の整除関係は弱半順序であることを確かめよ。

2. 整数全体の集合上の整除関係も弱半順序か？

「集合 \(A\) 上の二項関係 \(R\) が推移性と非反射性を持つなら非対称性を持つ」を定義から直接 (DAG を考えることなく) 示せ。

整除関係による半順序を持つ非負整数全体の集合が次の性質を持つことを示せ:

1. 最小要素を持つ。

2. 最大要素を持つ。

3. 無限個の要素を含む鎖を持つ。

4. 無限個の要素を含む反鎖を持つ。

5. \(1\) より大きい極小要素は存在するか？ 極大要素はどうか？

集合 \(\left\{ 0, 1 \right\}\) 上の二項関係はいくつあるか？ 推移性・非対称性・反射性・非反射性を持つもの、そして狭義半順序・弱半順序であるものはそれぞれいくつあるか？

ヒント: 二項関係を全て書き出し、それぞれの二項関係がどの性質を持つかを表にまとめるとよい。

\(R\) が半順序なら \(R^{-1}\) も半順序だと示せ。

1. 次の二項関係が同値関係・狭義半順序・弱半順序のどれであるか答えよ。半順序と答えた二項関係に対しては、それが線形順序かどうかを答えよ。いずれでもない場合は、推移性・対称性・非対称性のどれが成り立つかを答えよ。

   1. 整数 \(a\), \(b\) に対する \(a = b + 1\)

   2. 整数全体の集合の冪集合上の上位集合関係 \(\supseteq\)

   3. 有理数全体の集合上の空関係

   4. 非負整数全体の集合上の整除関係

   5. 整数全体の集合上の整除関係

   6. \(4\) の正冪全体の集合上の整除関係

   7. 非負整数全体の集合上の「互いに素」関係

   8. 整数上の「同じ素因数を持つ」関係

2. 関数 \(f\colon D \to \mathbb{R}\) の集合に次の規則で半順序を定義する:

   \[ f \leq g \ \ \overset{\text{def}}{\longleftrightarrow}\ \ \forall d \in D.\ \ f(d) \leq g(d) \]

   \(L\) を次の形をした関数 \(f\colon \mathbb{R} \to \mathbb{R}\) 全体の集合とする:

   \[ f(x) = ax + b \quad (a, b \in \mathbb{R}) \]

   無限個の要素を含む \(L\) の鎖と、無限個の要素を含む \(L\) の反鎖の例を示せ。

\(n\) 人の総当たり戦 (round-robin tournament) では、任意の異なる二人が一度だけ対戦する。全ての対戦で勝敗が決定し、引き分けは起こらないと仮定する。このとき総当たり戦の結果はトーナメント有向グラフ (tournament digraph) で表現できる。この有向グラフの頂点は選手を表し、辺 \(\langle x \to y \rangle\) は \(x\) が \(y\) に勝利したことを表す。

1. トーナメント有向グラフが長さ \(1\) または \(2\) の閉路を持たないことを示せ。

2. トーナメント有向グラフが表す「勝利する」の関係が次の性質を「常に持つ」「場合によっては持つ」「常に持たない」のいずれかを答えよ。

   • 非対称性

   • 反射性

   • 非反射性

   • 推移性

3. 長さ \(3\) の閉路を持たないトーナメント有向グラフは半順序だと示せ。

集合 \(A\) 上の二項関係 \(R\), \(S\) が両方とも推移性を持つとする。次に示す二項関係の中で必ず推移性を持つのはどれか？ 推移性を持つなら理由を簡単に説明し、持たないなら反例を示せ。

1. \(R^{-1}\)
2. \(R \cap S\)
3. \(R \circ R\)
4. \(R \circ S\)

有向グラフ \(G\) が一意路規則 (unique path property) を満たすとは、\(G\) の頂点の任意の非空有限集合に対して、それに属する頂点だけを含む有向路が一意に存在することを言う。

1. \(G\) が線形狭義半順序なら \(G\) は一意路規則を満たすと示せ。

2. 逆に、\(G\) が一意路規則を満たすなら \(G\) の正歩道関係が線形狭義半順序だと示せ。

\(32\) 個のタスク間の直接的な依存関係が \(\operatorname{pow}(\left\{ 1,2,3,4,5 \right\})\) 上の真の包含関係 \(\subsetneq\) と同型だとする。

例えば、集合 \(\left\{ 1, 2, 4 \right\}\) に対応するタスクを開始するには集合 \(\left\{ 2, 4 \right\}\) に対応するタスクを完了させる必要がある: なぜなら \(\left\{ 2, 4 \right\} \subsetneq \left\{ 1, 2, 4 \right\}\) が成り立つからである。また、空集合は任意の非空部分集合 \(S \subset \left\{ 1, 2, 3, 4, 5 \right\}\) の真部分集合なので、空集合に対応するタスクはどのタスクより先に完了させなければならない。

1. 全てのタスクを完了させるのにかかる最短並列時間を求めよ。

2. この半順序における要素数最大の反鎖を示せ。

3. 全てのタスクを最短並列時間で完了させるのに必要な最小のプロセッサ数が \(\text{(b)}\) で解答した反鎖の要素数に等しい理由を簡単に説明せよ。

\(R\) を集合 \(A\) 上の弱半順序とする。\(C\) を \(A\) の有限鎖⁵とする。

1. \(C\) が最大要素を持つと示せ。

   ヒント: \(C\) の要素数に関する数学的帰納法を使う。

2. \(C\) の全ての要素を並べた狭義増加な列が一意に存在すると示せ。

   ヒント: \(C\) の要素数に関する数学的帰納法と \((a)\) の結果を使う。

\(R_{1}\) と \(R_{2}\) の少なくとも一方が非反射性を持つなら、\(R_{1} \times R_{2}\) も非反射性を持つと示せ。

\(R_{1}\), \(R_{2}\) を集合 \(A\) 上の二項関係とする。二項関係の性質が直積の下で保存されるとは、\(R_{1}\) と \(R_{2}\) がその性質を持つとき \(R_{1} \times R_{2}\) も必ずその性質を持つことを言う。

1. 次の性質が直積の下で保存されることを確認せよ:

   • 反射性

   • 反対称性

   • 推移性

2. \(R_{1}\) と \(R_{2}\) が半順序で少なくとも一方が狭義半順序なら、\(R_{1} \times R_{2}\) は狭義半順序だと示せ。

集合 \(A\) 上の半順序が整礎 (well founded) とは、\(A\) の任意の非空部分集合が極小要素を持つことを言う。例えば、実数からなる整列集合上の「未満」関係 (第 2.4 節) は整礎な線形順序である。\(R\), \(S\) が整礎な半順序のとき、\(R \times S\) も同じ性質を持つと示せ。

\(n\) 個の異なる実数が並んだ列を \(S\) とする。\(S\) の部分列 (subsequence) とは、\(S\) から要素をいくつか除去して得られる列を言う。

例えば、次の列が \(S\) だとする:

このとき \(647\) と \(7253\) は \(S\) の部分列である。可読性のため、以降では前文のように列の括弧とコンマを省略する: \(647\) は \((6, 4, 7)\) の略記である。

\(S\) の増加部分列 (increasing subsequence) とは、要素が次第に大きくなる \(S\) の部分列を言う。例えば \(1238\) は \(S\) の増加部分列である。減少部分列 (decreasing subsequence) も同様に定義される。例えば \(641\) は \(S\) の減少部分列である。

1. \(S\) の最長増加部分列と最長減少部分列を全て示せ。

列 \(S\) に含まれる整数全体の集合を \(A\) とする (上述の \(S\) では \([1..9]\) が \(A\) となる)。\(A\) に対して容易に考えられる線形順序が二つある。一つは数値的大小 \(<\) による順序であり、もう一つは \(S\) における順序をそのまま利用する順序である。後者の順序を \(<_{S}\) と表記する。例えば、上述の \(S\) では次の関係が成り立つ:

二つの線形順序 \(<_{S}\) と \(<\) の直積関係を \(\prec\) とする。つまり、\(\prec\) を次の規則で定義する:

このとき \(\prec\) は \(A\) 上の半順序である (参照: 第 10.9 節)。

1. 上述の \(S\) に対する \(A\) 上の半順序 \(\prec\) を表す図を書け。極大要素と極小要素は何か？

2. 列 \(S\) の増加部分列と減少部分列、そして \(\prec\) の鎖と反鎖の間にある関係を説明せよ。

3. \(n\) 個の異なる実数が並んだ任意の列 \(S\) は長さが \(\sqrt{n}\) より大きい増加部分列、または長さが \(\sqrt{n}\) 以上の減少部分列を持つと示せ。

次の二項関係について、反射性・対称性・推移性を持つかどうか、そして同値関係かどうかを答えよ:

1. \(\left\{ (a,b) \; | \; \text{\(a\) と \(b\) は同い年} \right\}\)
2. \(\left\{ (a, b) \; | \; \text{\(a\) と \(b\) は同じ両親を持つ} \right\}\)
3. \(\left\{ (a, b) \; | \; \text{\(a\) と \(b\) は何らかの言語で会話できる} \right\}\)

次に示す二項関係のそれぞれについて「狭義半順序である」「弱半順序である」「同値関係である」「どれでもない」の中で正しいものを答えよ。半順序に対しては線形順序かどうかを答え、どれでもない二項関係に対しては半順序と同値関係の公理の中で満たさないものはどれかを答えよ。

1. 冪集合 \(\operatorname{pow}(\left\{ 1, 2, 3, 4, 5 \right\})\) 上の上位集合関係 \(\supseteq\)

2. 任意の非負整数 \(a\), \(b\) に対して \(a \equiv b \ \ (\text{mod } 8)\) と同値な非負整数間の二項関係

3. 任意の命題論理式 \(G\), \(H\) に対して \(G \ \operatorname{\text{\footnotesize IMPLIES}}\ H\) の恒真性と同値な命題論理式間の二項関係

4. 任意の命題論理式 \(G\), \(H\) に対して \(G \ \operatorname{\text{\footnotesize IFF}}\ H\) の恒真性と同値な命題論理式間の二項関係

5. じゃんけんの手の間の「勝利する」関係 (じゃんけんを知らない読者へ: じゃんけんの手はグー・チョキ・パーの三種類であり、グーはチョキに、チョキはパーに、パーはグーに勝利する)

6. 実数全体の集合上の空関係

7. 整数全体の集合上の恒等関係

8. 整数全体の集合上の整除関係

定理 10.10.4 を証明せよ: この定理は「同値類からなる集合族は始域 (かつ終域) の分割である」と主張する。

詳しく言えば次の通りである。\(R\) を集合 \(A\) 上の同値関係として、任意の要素 \(a \in A\) の同値類 \([a]_{R}\) を次のように定義する:

言い換えれば \([a]_{R} = R(a)\) と定める。

1. 空の同値類は存在せず、\(A\) の任意の要素は何らかの同値類に属すると示せ。

2. \([a]_{R} \cap [b]_{R} \neq \varnothing\) なら \(a \mathrel{R} b\) だと示せ。全ての \(a \in A\) に対する同値類 \([a]_{R}\) を集めた集合族は \(A\) の分割だと結論付けよ。

3. \(a \mathrel{R} b \ \ \longleftrightarrow \ \ [a]_{R} = [b]_{R}\) を示せ。

任意の全域関数 \(f\colon A \to B\) からは次の規則で二項関係 \(\equiv_{f}\) を定義できる:

1. \(\equiv_{f}\) が \(A\) 上の同値関係であることの証明の概略を示せ。

2. 集合 \(A\) 上の任意の同値関係 \(R\) は、次の規則で定義される関数 \(f\colon A \to \operatorname{pow}(A)\) に対する \(\equiv_{f}\) に等しいと示せ:

   \[ f(a) ::= \left\{ a^{\prime} \in A \; | \; a \mathrel{R} a^{\prime} \right\} \]

   言い換えれば \(f(a) = R(a)\) である。

\(R\) を集合 \(D\) 上の二項関係とする。次に示す論理式は \(R\) が反鎖性・非対称性・推移性といった性質を持つことを意味する。述語論理式は \(\text{i}\), \(\text{ii}\), \(\ldots\) で表され、二項関係に関する論理式 (等式および包含関係) は \(\text{(a)}\), \(\text{(b)}\), \(\ldots\) で表されている。

二項関係に関する論理式のそれぞれに対して、それと等しい述語論理式の番号を全て答えよ。論理式が表現する性質の名前を書く必要はないものの、書いた場合は部分点が与えられる。例えば \(\text{(a)}\) に等しいのは \(\text{(i)}\) であり、この性質は非反射性と呼ばれる。

述語論理式:

1. \(\forall d.\ \;\operatorname{\text{\footnotesize NOT}} (d \mathrel{R} d)\)
2. \(\forall d.\ \;d \mathrel{R} d\)
3. \(\forall c, d.\ \;c \mathrel{R} d \ \ \longleftrightarrow \ \ d \mathrel{R} c\)
4. \(\forall c, d.\ \;c \mathrel{R} d \ \ \longrightarrow \ \ d \mathrel{R} c\)
5. \(\forall c, d.\ \;c \mathrel{R} d \ \ \longrightarrow \ \ \operatorname{\text{\footnotesize NOT}} (d \mathrel{R} c)\)
6. \(\forall c \neq d.\ \;c \mathrel{R} d \ \ \longrightarrow \ \ \operatorname{\text{\footnotesize NOT}} (d \mathrel{R} c)\)
7. \(\forall c \neq d.\ \;c \mathrel{R} d \ \ \longleftrightarrow \ \ \operatorname{\text{\footnotesize NOT}} (d \mathrel{R} c)\)
8. \(\forall b, c, d.\ \;(b \mathrel{R} c \ \operatorname{\text{\footnotesize AND}} \ c \mathrel{R} d) \ \ \longrightarrow \ \ b \mathrel{R} d\)
9. \(\forall b, d.\ \; (\exists c.\ (b \mathrel{R}c \ \operatorname{\text{\footnotesize AND}} \ c \mathrel{R} d)) \ \ \longrightarrow \ \ b \mathrel{R} d\)
10. \(\forall b, d.\ \; b \mathrel{R} d \ \ \longrightarrow \ \ (\exists c.\ (b \mathrel{R} c \ \operatorname{\text{\footnotesize AND}} \ c \mathrel{R} d))\)

二項関係に関する論理式:

1. \(R \cap \text{Id}_{D} = \varnothing\)
2. \(R \subseteq R^{-1}\)
3. \(R = R^{-1}\)
4. \(\text{Id}_{D} \subseteq R\)
5. \(R \circ R \subseteq R\)
6. \(R \subseteq R \circ R\)
7. \(R \cap R^{-1} \subseteq \text{Id}_{R}\)
8. \(\overline{\mathstrut R} \subseteq R^{-1}\)
9. \(\overline{\mathstrut R} \cap \text{Id}_{R} = R^{-1} \cap \text{Id}_{R}\)
10. \(R \cap R^{-1} = \varnothing\)

\(R_{1}\), \(R_{2}\) を集合 \(A\) 上の同値関係とする。次の二項関係が同値関係かどうかを答え、証明または反例を与えよ:

1. \(R_{1} \cap R_{2}\)
2. \(R_{1} \cup R_{2}\)

\(G\) を有向グラフ、\(u\), \(v\) を \(G\) の二頂点とする。\(u\) から \(v\) への路と \(v\) から \(u\) への路が両方とも \(G\) に存在するとき、\(G\) で \(u\) と \(v\) は相互接続 (mutually connected) と言い、次のように表記する:

\(A\) を非空集合とする。

1. \(A\) 上の二項関係であって同値関係かつ弱半順序なものを示せ。

2. \(\text{(a)}\) の解答の他に同値関係かつ弱半順序な \(A\) 上の二項関係が存在しないと示せ。