練習問題

\(n\) 個の頂点を持つグラフでは、頂点の平均次数が頂点一つ当たりの辺の平均個数の二倍に等しい。その理由を説明せよ。

頂点の次数の和が \(20\) である連結グラフを考えるとき:

• 頂点数の最大値は何か？

• 頂点数の最小値は何か？

それぞれ理由を簡単に説明すること。

1. 全てのグラフにおいて、次数が奇数の頂点の個数は偶数だと示せ。

2. パーティの参加者が互いに握手をするとき、奇数回の握手をする参加者の人数は偶数だと結論付けよ。

3. パーティの参加者の列が握手列 (handshake sequence) とは、連続する任意の二人が握手をしていることを言う。

   Georgeジョージ が握手をした参加者の人数が奇数のとき、George から始まって奇数人と握手した他の人物で終わる参加者の列が存在する。その理由を説明せよ。

ある研究グループが \(m\) 人の男性と \(f\) 人の女性から構成されるグループ内の異性交遊関係に関するデータを解析したところ、男性一人当たりの女性パートナーの平均人数は女性一人当たりの男性パートナーの平均人数より \(10\%\) 大きいことが判明した。

1. 研究グループは「全てのカップルは一人の男性と一人の女性からなるのだから、異性パートナーの平均人数は男女で同じはずだ。よって男性がパートナーの人数を過剰申告している」と考察した。この考察についてどう思うか？

2. \(m = c \cdot f\) を満たす定数 \(c\) はどんな値か？

3. データによると性的経験を持たない女性は女性全体の約 \(20\%\) を占めるのに対して、男性では男性全体の約 \(5\%\) に過ぎない。性的関係を持つ人物だけを考えれば結果が変わるだろうかと研究グループは疑問を抱いた。もし彼らがグラフ理論を知っていれば、性的経験を持つ男性一人当たりの女性パートナーの平均人数は性的経験を持つ女性一人当たりの男性パートナーの平均人数の \(x (f / m)\) 倍になると分かったことだろう。この \(x\) を求めよ。

4. 次の研究では、グループに属するそれぞれの女性をグループに属する男性一人へと一意に対応付ける必要があるという。しかし、そのような対応付けの作成は不可能である。その理由を説明せよ。

グラフに関する性質を次にいくつか示す。同型写像によって保存されるものを全て答えよ。

1. 全ての頂点を含む閉路が存在する。

2. 頂点に \(1\) から \(7\) までの番号が付いている。

3. 頂点に \(1\) から \(7\) までの番号を付けることができる。

4. 次数が \(8\) の頂点が \(2\) 個ある。

5. 同じ長さの辺が二つある。

6. どの辺を除去したとしても、任意の二頂点間に路が存在する。

7. 頂点が集合である。

8. 全ての辺が同じ長さとなるように描画できる。

9. 全ての辺が交わらないように描画できる。

10. 同型写像で保存される二つの性質を \(\operatorname{\text{\footnotesize OR}}\) でつないだ命題が成り立つ。

11. 同型写像で保存される性質の否定が成り立つ。

次に示すグラフの組が同型かどうかを答え、同型なら同型写像を一つ示せ。辺は \(\langle a\>\text{---}\>b \rangle\) ではなく \(ab\) と表記されている。

1.  

   \[ \begin{aligned} G_{1} &= (\left\{ 1, 2, 3, 4, 5, 6 \right\},\ \left\{ 12, 23, 34, 14, 15, 35, 45 \right\}) \\ G_{2} &= (\left\{ 1, 2, 3, 4, 5, 6 \right\},\ \left\{ 12, 23, 34, 45, 51, 24, 25 \right\}) \end{aligned} \]

2.  

   \[ \begin{aligned} G_{3} &= (\left\{ 1, 2, 3, 4, 5, 6 \right\},\ \left\{ 12, 23, 34, 14, 45, 56, 26 \right\}) \\ G_{4} &= (\left\{ a, b, c, d, e, f \right\},\ \left\{ ab, bc, cd, de, ae, ef, cf \right\}) \end{aligned} \]

図 \(\text{12.23}\) に示す二つのグラフ間の同型写像を全て答えよ。それ以外に存在しない理由を説明すること。

図 \(\text{12.24}\) に示す四つのグラフの中で同型なのはどれか答えよ。同型なグラフの組それぞれについて、対応する同型写像を一つ示せ。同型でないグラフの組のそれぞれについて、同型写像で保存される性質であって二つのグラフのちょうど一方だけが持つものを示せ。解答した性質の中から一つ選び、それが同型写像で保存されることを示せ (他の性質は証明しなくてよい)。

1. グラフの任意の頂点 \(v\) に対して、\(N(v)\) で \(v\) の近傍 (neighbor) 全体の集合を表すと定める。つまり、\(N(v)\) を隣接頂点全体の集合として次のように定義する:

   \[ N(v) ::= \left\{ u \; | \; \text{辺 } \langle u\>\text{---}\>v \rangle \text{ がグラフに存在する} \right\} \]

   \(f\) をグラフ \(G\) からグラフ \(H\) への同型写像とする。\(G\) の任意の頂点 \(v\) に対して \(f(N(v)) = N(f(v))\) だと示せ。言い換えれば、\(f\) が頂点 \(v\) を頂点 \(w = f(v)\) に対応付けるとき、\(f\) による \(N(v)\) の像は \(w\) の近傍にちょうど等しいと示せ。

   証明は同型写像と \(N(v)\) の定義を使った単純な議論であるべきである ── 図を使ってはいけない。

   ヒント: 任意の \(h \in V(H)\) に対する次の関係を同値変形で示す:

   \[ h \in N(f(v)) \ \ \longleftrightarrow \ \ h \in f(N(v)) \]

   ある \(u \in V(G)\) で \(h = f(u)\) となる事実 (なぜ？) を使う。

次数が \(1\) の頂点を二つ持ち、他の全ての頂点の次数が \(2\) であるグラフを双頭グラフ (two-ended graph) と呼ぶことにしよう。双頭グラフの例を次に示す:

1. 線グラフ (line graph) とは頂点が一列に並び、その列で隣り合う二頂点の間にだけ辺が存在するようなグラフを言う。例えば上記の双頭グラフは長さ \(4\) の線グラフである。

   次の定理に対する反例を示せ:

   誤った定理

   全ての双頭グラフは線グラフである。

2. 上記の誤った定理に対する誤った証明を次に示す。この証明で最初に現れる正しくない文を指摘せよ。

   誤った証明 数学的帰納法を用いる。次の述語 \(P(n)\) を帰納法の仮定とする:

   \[ P(n) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ \text{\(n\) 本の辺を持つ全ての双頭グラフは線グラフである} \]

   ベースケース: \(1\) 本の辺を持つ唯一の双頭グラフは \(2\) 個の頂点が辺で結ばれた形をしている:

   

   明らかに、このグラフは線グラフである。よって \(P(1)\) は成り立つ。

   帰納ステップ: ある \(n \geq 1\) で帰納法の仮定 \(P(n)\) が成立すると仮定し、それを使って \(P(n + 1)\) を証明する。\(n\) 本の辺を持つ任意の双頭グラフを \(G_{n}\) とする。帰納法の仮定より \(G_{n}\) は線グラフである。\(G_{n}\) に頂点と辺を新しく \(1\) 個ずつ追加して双頭グラフ \(G_{n+1}\) を作ることを考える。\(G_{n+1}\) を作るには、次に示すように新しい頂点と \(G_{n}\) で端にある頂点を結ぶ辺を追加する以外に選択肢がない。これ以外の辺を追加すると双頭グラフが得られない:

   

   明らかに、この \(G_{n+1}\) も線グラフである。よって \(P(n+1)\) は成り立つ。以上で数学的帰納法による証明が完了した。 ■

\(G\) を任意のグラフとする。\(G\) から同じグラフ \(G\) への同型写像を、\(G\) の自己同型写像 (automorphism) と呼ぶ¹。簡単な例を示すと、恒等関数 \(\operatorname{id}\colon V(G) \to V(G)\) は必ず自己同型写像である。

1. 図 \(\text{12.25}\) に示す Dürerデューラー グラフ (Dürer graph) を \(D\) とする。\(D\) の自己同型写像であって恒等写像でないものを答えよ。

2. \(V(G)\) 上の二項関係 \(R\) を次の規則で定義する:

   \[ v \mathrel{R} w \ \ \overset{\text{def}}{\longleftrightarrow}\ \ \text{\(f(v) = w\) を満たす \(G\) の自己同型写像 \(f\) が存在する} \]

   特殊ケースとして、図 \(\text{12.25}\) の Dürer グラフ \(D\) では \(1 \mathrel{R} 10\) だと示せ。

   ヒント: \(1\), \(2\), \(3\) をそれぞれ \(10\), \(11\), \(12\) に移す。他の頂点はどこに移すべきか？

3. 図 \(\text{12.25}\) の Dürer グラフ \(D\) では \(\operatorname{\text{\footnotesize NOT}} (1 \mathrel{R} 4)\) だと示せ。

   ヒント: 長さ \(3\) の閉路に注目する。

4. 一般のグラフ \(G\) に対する二項関係 \(R\) が同値関係であることを注意深く証明せよ。

5. \(R\) が同値関係なので、グラフの頂点集合は \(R\) に関する同値類に分割できる²。図 \(\text{12.25}\) の Dürer グラフ \(D\) の \(R\) に関する同値類はどんな集合か？ どうすれば分かるか？

   ヒント: 同値類は二つしか存在しない。

\(B\) を二部グラフとする。\(L(B)\) に属する頂点の次数の和と \(R(B)\) に属する頂点の次数の和が等しい理由を説明せよ。

とある工科大学には学生の所属する部活動が数多く存在する。部活動は生徒会が統括し、活動費が必要な部は代表者を一人選出して学部長と面談することになっている。ただし、同じ人物が複数の部の代表者となることは認められていない。幸いにも生徒会長は「情報科学のための数学」の講義を受講していたので、この状況がマッチング問題の一種である事実に気が付いた。

1. 部の代表者を選出する問題を二部マッチング問題としてモデル化せよ (これはモデル化の問題なので、二部マッチング問題を解くアルゴリズムを答える必要はない)。

2. 生徒会の記録によると、\(10\) 個以上の部に所属する生徒は存在しない。また、活動費を要求する部には少なくとも \(13\) 人の部員が要求される。この事実があれば、部の代表者を必ず選出できると分かる。その理由を説明せよ (生徒会長が「アルゴリズム」の講義も受講していれば、具体的な代表者の選出も簡単に行える)。

グラフが正則 (regular) とは、全ての頂点が同じ次数を持つことを言う。右頂点と左頂点の個数が等しい正則二部グラフを平衡 (balanced) と呼ぶことにする。

グラフ \(G\) が平衡なら、全てのブロックが完全マッチングとなるように \(G\) の辺集合を分割できると示せ。

例えば、もし \(G\) が \(2k\) 個の頂点を持つ平衡グラフで各頂点の次数が \(j\) なら、全てのブロックが完全マッチングとなるように \(G\) の辺集合を \(k\) 個の辺からなる \(j\) 個のブロックに分割できる。

Warvelワーベル 社は新作映画 Averagers: Epsilon War の試写会をランダムに選んだ MIT の学生に向けて \(4\) 回にわたって実施することを決定した。スケジュールを立てるために、Warvel 社は試写会に招待した学生に対して自身の予定と衝突しない日時を尋ねた。その回答によると、どの学生も \(4\) 回ある試写会の少なくとも \(2\) 回には出席可能だと判明した。それぞれの試写会に出席できるのは最大で \(20\) 人であり、席を全て埋める必要はない。こうして Warvel 社は複雑なスケジューリング問題に直面した: どうすれば毎回の試写会で学生が席を見つけられることを保証できるだろうか？ このジレンマを解決するのがあなたの仕事である。

1. この状況をマッチング問題としてモデル化せよ。グラフの頂点と辺が何に対応するか、そしてグラフのマッチングと学生の割り当てがどのように対応するかを述べること (これはモデル化の問題なので、マッチング問題を解くアルゴリズムを答える必要はない)。

2. 招待された学生が \(41\) 人のとき、マッチングの存在は保証されるか？ それとも、特定の試写会で \(41\) 人の学生に席を用意できない状況が存在するか？ 理由を簡単に説明せよ。

3. 招待された学生が \(40\) 人ならマッチングが必ず存在すると証明せよ。

   ヒント: Hall の定理または同様の結果を使う。グラフは次数制約を満たすか？

「情報科学のための数学」の講義が大人気になってしまったので、TA の Mikeマイク は通常のオフィスアワーを使って質問に答えることを諦めた。その代わり、学生を何らかの勉強グループに所属させ、質問できるのはグループの代表者一人だけと定めた。それぞれの学生は少なくとも一つのグループに所属し、一人の学生は複数のグループの代表者になれないとする。この規則に従うように各グループから代表者を選ぶ問題を考える。

1. この代表者の選出問題をマッチング問題としてモデル化せよ (これはモデル化の問題なので、マッチング問題を解くアルゴリズムを答える必要はない)。

2. 記録によると、一人の学生が所属するグループの個数は最大で \(4\) であり、各グループには少なくとも \(4\) 人が所属している。この事実は代表者の選択が可能であることを保証するか？ 理由を説明せよ。

\(\widehat{\vphantom{\scriptsize l} R}\) を命題論理式上の「含意」関係として次のように定義する:

例えば、命題論理式 \((P \ \operatorname{\text{\footnotesize AND}} \ Q) \ \operatorname{\text{\footnotesize IMPLIES}}\ P\) は恒真なので \((P \ \operatorname{\text{\footnotesize AND}} \ Q)\,\mathrel{\widehat{\vphantom{\scriptsize l} R}}\,P\) が成り立つ。また、\((P \ \operatorname{\text{\footnotesize OR}}\ Q) \ \operatorname{\text{\footnotesize IMPLIES}}\ P\) は恒真でないので \((P \ \operatorname{\text{\footnotesize OR}}\ Q)\,\mathrel{\widehat{\vphantom{\scriptsize l} R}}\,P\) は成り立たない。

1. \(A\), \(B\) を上図が示す命題論理式の集合とする。\(\widehat{\vphantom{\scriptsize l} R}\) が集合 \(A \cup B\) 上の弱半順序でない理由を説明せよ。

2. \(A\) の要素から \(B\) の要素に向かう \(\widehat{\vphantom{\scriptsize l} R}\) を表す矢印を書き入れよ。

3. \(\text{(b)}\) で完成した図が定義する二部グラフを \(G\) とする。\(G\) は \(L(G) = A\) と \(R(G) = B\) を満たし、辺 \(\langle F\>\text{---}\>G \rangle\) の存在は \(F \mathrel{\widehat{\vphantom{\scriptsize l} R}} G\) と同値である。\(A\) の部分集合 \(S\) であって、\(S\) と \(A - S\) の両方が非空集合であり、\(S\) の近傍全体の集合 \(N(S)\) が \(S\) と同じ要素数である (\(|N(S)| = |S|\) が成り立つ) ものを示せ。

4. \(G\) を一般の有限二部グラフとする。任意の集合 \(S \subseteq L(G)\) に対して \(\overline{\mathstrut S} ::= L(G) - S\) と定める。同様に任意の集合 \(M \subseteq R(G)\) に対して \(\overline{\mathstrut M} ::= R(G) - M\) と定める。ある \(S \subseteq L(G)\) で \(|N(S)| = |S|\) が成り立ち、\(S\) と \(\overline{\mathstrut S}\) がいずれも非空集合だとする。次の命題が正しくなるように空欄に入る数式を選択肢から選べ:

   \(L(G)\) から \(R(G)\) へのマッチングが存在するのは、\(S\) から \(S\) の近傍全体の集合 \(N(S)\) へのマッチング、そして \(\overline{\mathstrut S}\) から ( \(\cdots\) ) へのマッチングが両方とも存在するとき、かつそのときに限る。

   1. \(N(\overline{\mathstrut S})\)
   2. \(\overline{\mathstrut N(S)}\)
   3. \(N^{-1}(N(S))\)
   4. \(N^{-1}(N(\overline{\mathstrut S}))\)
   5. \(N(\overline{\mathstrut S}) - \overline{\mathstrut N(S)}\)
   6. \(N(S) - N(\overline{\mathstrut S})\)

   ヒント: Hall のボトルネック定理の証明を参考にする。

1. 図 \(\text{12.26}\) の二部グラフを \(G\) とする。\(L(G)\) を被覆する \(G\) のマッチングが存在しないことを示せ。

2. 図 \(\text{12.27}\) の二部グラフを \(H\) とする。\(L(H)\) を被覆する \(H\) のマッチングが存在することを簡単に確認できる性質が存在する。どんな性質か？

\(n\) を正整数とする。\(n \times n\) のラテン方陣 (Latin square) とは、\(1\) 以上 \(n\) 以下の整数を \(n \times n\) に並べたものであって、\(n\) 個ある行と \(n\) 個ある列のそれぞれに \(1\) 以上 \(n\) 以下の整数が全て含まれるものを言う。脚注³の小話が示す理由により、ラテン方陣は科学実験の設計で頻繁に利用される。

例えば、次に示すのは \(4 \times 4\) ラテン方陣である:

1. 最初の \(3\) 行が埋まった \(5 \times 5\) のラテン方陣を次に示す:

   \[ \def\arraystretch{1.2}\begin{array}{|c|c|c|c|c|c|} \hline 2 & 4 & 5 & 3 & 1 \\ \hline 4 & 1 & 3 & 2 & 5 \\ \hline 3 & 2 & 1 & 5 & 4 \\ \hline & & & & \\ \hline & & & & \\ \hline \end{array} \]

   この「ラテン長方形」の最後の \(2\) 行を埋めることでラテン方陣を完成させよ。

2. \(m \times n\) (\(m < n\)) のラテン長方形の次の行を求める問題は、ある \(2n\) 頂点の二部グラフのマッチングを求める問題に等しいと示せ。

3. \(\text{(b)}\) で登場した二部グラフが常にマッチングを持つこと、つまりラテン長方形は必ずラテン方陣に拡張できることを示せ。

\(52\) 枚のカードからなる通常のトランプ一式がある。それぞれのカードは絵柄と数字を持つ。絵柄はハート・ダイアモンド・クラブ・スペードのいずれか、数字は \(A\), \(2\), \(3\), \(\ldots\), \(10\), \(J\), \(Q\), \(K\) のいずれかである。カードは \(4 \times 13\) 通りある絵柄と数字の組み合わせごとに一枚ずつ存在する。

友人に頼んでトランプのカードを \(4\) 行 \(13\) 列の格子状に並べてもらったとする。カードが並ぶ順番はどんなものでも構わない。この問題では、各列から \(1\) 枚ずつ計 \(13\) 枚のカードを選ぶことで、\(13\) 個の数字が書かれたカードを集めることが常に可能である事実を証明する。

1. この事実を二部マッチング問題としてモデル化せよ。二部グラフは \(13\) 個の「列頂点」と \(13\) 個の「数字頂点」を持つはずである。このグラフは次数制約を常に満たすか？

2. 任意の \(n\) 個の列には少なくとも \(n\) 個の異なる値が含まれることを示し、マッチングの存在を証明せよ。

哲学者たちは長い年月をかけて \(12\) 個の人間の美徳を特定した: 正直であること、寛大であること、忠義を尽くすこと、慎重に振る舞うこと、読後エッセイreading-responseを毎週ちゃんと書くこと、などである。「情報科学のための数学」の講義を受講する全ての学生は、タームの最初にちょうど \(8\) 個の美徳を持っている。さらに、それぞれの学生が持つ美徳は異なる: 同じ \(8\) 個の美徳を持つ学生は存在しない。この講義では、それぞれの学生にタームの終わりまでに追加で習得すべき美徳が一つ指定される。それぞれの学生が持つ美徳がタームの終わった時点でも異なるように追加の美徳を選択できると示せ。

ヒント: 適切に構築された二部グラフに対するマッチングの存在を示す。二部グラフの (右および左) 頂点と辺が何かを明確に述べること。

\(n\) チームの総当たり戦を考える。各チームは一日に一度だけ他のチームと対戦し、\(n - 1\) 日間で全てのチームは自身以外の全てのチームとちょうど \(1\) 回ずつ対戦する。対戦に引き分けはなく、必ず勝敗が決まると仮定する。日ごとに勝利した \(1\) チームを選択していくとき、同じチームを \(2\) 回以上選択しないようにできると示せ⁴。

ヒント: \(L(G)\) が日付の集合、\(R(G)\) がチームの集合であるような二部グラフ \(G\) を考える。任意の日付の集合 \(D\) に対して、その全てで敗北したチームが存在することもあれば存在しないこともある。

次のグラフを \(G\) とする。\(\chi(G) = 4\) である理由を説明せよ⁵。

典型的なコンピュータープログラムには、結果が変数に格納される計算の列が含まれる。この例を次に示す:

マイクロプロセッサはレジスタ (register) と呼ばれる非常に高速なデータ保存領域を持ち、変数の値がレジスタに保存されているときコンピューターは最も高速に計算を実行できる。このため、プログラミング言語のコンパイラはプログラムで使用される全ての変数をレジスタに割り当てる問題を解くことになる。通常レジスタはコンピューターに少数しか存在しないので、賢く使って可能な場合は再利用しなければならない。この問題はレジスタ割り当て問題 (register allocation problem) と呼ばれる。

上記の例では、それぞれ異なる入力を保持する変数 \(a\), \(b\) は異なるレジスタに割り当てなければならない。さらに、変数 \(c\), \(d\) も同じレジスタに割り当てることはできない。なぜなら、もしそうするとステップ \(2\) で \(c\) の値が失われ、ステップ \(3\) で誤った \(c\) の値が使われるからである。一方で、変数 \(b\), \(d\) は同じレジスタに割り当てて構わない: ステップ \(2\) 以降で \(b\) の値が使われないので、レジスタが保持する \(b\) の値は上書きしても問題が起こらない。また、\(f\) と \(h\) にも同じレジスタを割り当てられる。なぜなら、ステップ \(6\) の \(f + 1\) が計算された時点で \(f\) の値は不必要になるからである。

1. レジスタ割り当ての問題をグラフ彩色の問題に言い換えたものを答えよ。何が頂点に対応するか？ どんな条件が成り立つとき二頂点の間に辺が存在するか？ 上記の例に対応するグラフを構築せよ。

2. \(\text{(a)}\) で解答したグラフを可能な限り少ない色を使って彩色せよ。コンピューターのレジスタを \(R1\), \(R2\), \(\ldots\) とするとき、その彩色が意味するレジスタ割り当てを具体的に示せ。いくつのレジスタが必要になるか？

3. 次に示すように、一つの変数に対する代入が何度も起きるプログラムも存在する:

   \[ \begin{aligned} &\cdots \\ t &= r + s \\ u &= t \ast 3 \\ t &= m - k \\ v &= t + u \\ &\cdots \end{aligned} \]

   この状況を扱うにはどうすればいいだろうか？

\(n\) 頂点の二部グラフがちょうど \(k\) 個の連結成分を持ち、それぞれの連結成分には \(2\) 個以上の頂点が含まれるとする。このグラフを \(2\) 種類の色を使って彩色する方法は何通り存在するか？

6.042 では復習用の少人数講義 (recitation) が開講されることがある。今年は \(8\) 回の少人数講義が開講され、毎回 \(2\) 人または \(3\) 人のスタッフが必要だとする。各回を担当するスタッフ (のコードネーム) は次の通りである:

• R1: Maverick, Goose, Iceman

• R2: Maverick, Stinger, Viper

• R3: Goose, Merlin

• R4: Slider, Stinger, Cougar

• R5: Slider, Jester, Viper

• R6: Jester, Merlin

• R7: Jester, Stinger

• R8: Goose, Merlin, Viper

同じ人物が担当する二つの少人数講義は同じ時間に実施できない。少人数講義が 90 分の時間枠でしか開講できないとき、全ての少人数講義を実施するのに最低でいくつの時間枠が必要になるだろうか？

1. この問題を特定のグラフに対する彩色問題に書き換えよ。そのグラフを図示し、頂点・辺・色がそれぞれ何を意味するか説明せよ。

2. \(\text{(a)}\) で解答したグラフに対する可能な限り少ない色数を使った彩色を示せ。それより少ない色数では彩色が不可能な理由を説明せよ。その彩色はどんなスケジュールを意味するか？

この問題では「最大次数が \(w\) のグラフは \((w + 1)\)-彩色可能である」という定理 12.6.3 を一般化する。

グラフの全ての頂点を並べた列の幅 (width) が \(w\) とは、任意の頂点に対して「自身より前にある自身の隣接頂点が \(w\) 個以下」が成り立つことを言う。グラフ \(G\) の幅が \(w\) とは、\(G\) の全ての頂点を並べた列であって幅が \(w\) であるものが存在することを言う。最大次数が \(w\) 以下のグラフは明らかに幅が \(w\) 以下である: 任意の順序で頂点を並べればよい。

1. 幅が \(w\) 以下の全てのグラフは \((w + 1)\)-彩色可能だと示せ。

2. 最小の幅が \(n\) の \(2\)-彩色可能グラフを説明せよ。

3. 幅 \(w\) のグラフの平均次数は \(2w\) 以下だと示せ。

4. \(100\) 個の頂点を持つ幅が \(3\) のグラフであって平均次数が \(5\) より大きいものを説明せよ。

グラフの全ての頂点を並べた列の幅が \(w\) とは、任意の頂点に対して「自身より前にある自身の隣接頂点が \(w\) 個以下」が成り立つことを言う。グラフ \(G\) の幅が \(w\) とは、\(G\) の全ての頂点を並べた列であって幅が \(w\) であるものが存在することを言う。

1. グラフの幅が頂点の次数の最小値以上である理由を説明せよ。

2. 有限グラフの幅が \(w\) なら、全ての頂点を並べた幅 \(w\) の列であって次数が最小の頂点を末尾に持つものが存在すると示せ。

3. グラフの幅の最小値を計算する簡単なアルゴリズムを説明せよ。

全ての頂点の次数が \(k\) 以下であるグラフを \(G\) とする。頂点の個数に関する数学的帰納法を使って、もし \(G\) の全ての連結成分に次数が \(k\) 未満の頂点が存在するなら \(G\) は \(k\)-彩色可能だと示せ。

彩色数が \(n\) であるグラフの例として \(n\) 頂点の完全グラフがある: \(\chi(K_{n}) = n\) が成り立つ。ここから、部分グラフとして \(K_{n}\) を含むグラフの彩色数は \(n\) 以上だと分かる。この逆が成り立つと考えてしまうのはよくある間違いである: 大きな彩色数を持つグラフが部分グラフとして完全グラフを持つとは限らない。この問題では、この間違いが明らかになる反例を示す。具体的には、彩色数が \(4\) であるにもかかわらず三角形 (長さ \(3\) の閉路) を含まないグラフを見る。三角形を含まないグラフには \(K_{n}\) (\(n \geq 3\)) と同型な部分グラフも存在しない。

図 \(\text{12.28}\) のグラフを \(G\) とする。\(G\) が三角形を含まないことは簡単に確かめられる。

1. \(G\) が \(4\)-彩色可能だと示せ。

2. \(G\) が \(3\)-彩色可能でないと示せ。

この問題では、グラフの \(3\)-彩色が命題論理式の充足と同程度に難しいことを証明する。これから考えるグラフには、色頂点 (color-vertex) と呼ばれる互いに辺で結ばれた \(3\) 個の頂点が存在する。これらの色頂点は三角形を構成するために異なる色を持ち、グラフの他の頂点の色に制約を加える役割を果たす。\(3\) 個の色頂点に割り当てられる色をそれぞれ \(\textbf{T}\), \(\textbf{F}\), \(\textbf{N}\) と呼ぶ。

\(f\) を \(n\) 引数の真理値関数とする:

グラフ \(G\) が \(3\)-彩色 \(f\)-ゲート (\(3\)-color \(f\)-gate) とは、\(G\) が \(n\) 個の入力頂点 (input vertex) と \(1\) 個の出力頂点 (output vertex) を持ち、次の条件を満たすことを言う:

• \(G\) は入力頂点に \(\textbf{T}\) または \(\textbf{F}\) の色を塗るときに限って \(3\)-彩色可能となる。

• 全ての \(b_{1}, b_{2}, \ldots, b_{n} \in \left\{ \textbf{T}, \textbf{F} \right\}\) に対して、入力頂点 \(v_{1}, v_{2}, \ldots, v_{n} \in V(G)\) にそれぞれ色 \(b_{1}, b_{2}, \ldots, b_{n} \in \left\{ \textbf{T}, \textbf{F} \right\}\) を割り当てる \(3\)-彩色が存在する。

• \(G\) の任意の \(3\)-彩色において、入力頂点 \(v_{1}, v_{2}, \ldots, v_{n} \in V(G)\) に割り当てられた色が \(b_{1}, b_{2}, \ldots, b_{n} \in \left\{ \textbf{T}, \textbf{F} \right\}\) なら出力頂点の色は \(f(b_{1}, b_{2}, \ldots, b_{n})\) である。

例えば、\(3\)-彩色 \(\operatorname{\text{\footnotesize NOT}}\)-ゲートを図 \(\text{12.29}\) に示す。\(P\) と書かれた頂点が (唯一の) 入力頂点であり、\(\operatorname{\text{\footnotesize NOT}} (P)\) と書かれた頂点が出力頂点である。両方とも \(\textbf{N}\) が塗られた色頂点と辺でつながれているので、これらの頂点には任意の \(3\)-彩色で \(\textbf{T}\) または \(\textbf{F}\) の色だけが塗られる。また、両者は辺で結ばれているので、任意の \(3\)-彩色で頂点 \(P\) の色が \(\textbf{T}\) のとき頂点 \(\operatorname{\text{\footnotesize NOT}} (P)\) の色は \(\textbf{F}\) となり、頂点 \(P\) の色が \(\textbf{F}\) のとき頂点 \(\operatorname{\text{\footnotesize NOT}} (P)\) の色は \(\textbf{T}\) となる。

1. 図 \(\text{12.30}\) に示すグラフが \(3\)-彩色 \(\operatorname{\text{\footnotesize OR}}\)-ゲートであることを確かめよ。図中の破線は色頂点 \(\textbf{N}\) との辺を表す。つまり頂点 \(P\), \(Q\), \(P \ \operatorname{\text{\footnotesize OR}}\ Q\) は色頂点 \(\textbf{N}\) と隣接するので、任意の \(3\)-彩色において \(\textbf{T}\) または \(\textbf{F}\) の色しか持てない。

2. \(n\) 変数の命題論理式 \(E\) によって真理値関数 \(f\colon \left\{ \textbf{T}, \textbf{F} \right\}^{n} \to \left\{ \textbf{T}, \textbf{F} \right\}\) が定義されると仮定する。\(3\)-彩色 \(f\)-ゲートであるグラフを構築する簡単な方法を説明せよ。

3. グラフの \(3\)-彩色可能性を判定する効率的な手続きが存在するなら、命題論理式の充足可能性問題 (SAT) を解く効率的な手続きが存在すると言える理由を説明せよ。

平面グラフに対する \(3\)-彩色可能性の判定問題は一般のグラフに対する同じ問題と同程度に難しいことが分かっている。この主張は \(3\)-彩色歩道橋ガジェット (\(3\)-color cross-over gadget) の存在から直ちに示せる。このガジェットは平面グラフであり、外側の頂点をたどると四頂点 \(u\), \(v\), \(w\), \(x\) を時計回りに含む閉路となっている。さらに、このガジェットは次の性質を持つ:

1. \(u\) と \(v\) にどんな色を割り当てたとしても、それをガジェット全体の \(3\)-彩色に拡張できる。

2. ガジェットの全ての \(3\)-彩色において、\(u\) と \(w\) の色、そして \(v\) と \(x\) の色は同じである。

\(3\)-彩色歩道橋ガジェットを図 \(\text{12.31}\) に示す⁶。

任意のグラフ \(G\) の \(3\)-彩色可能性問題を平面グラフの \(3\)-彩色可能性問題に帰着させるには、\(G\) を平面に (必要なら辺を交差させて) 描画し、そこに含まれる全ての辺の交差を図 \(\text{12.32}\) に示すように \(3\)-彩色歩道橋ガジェットで置き換えればよい。こうして得られる平面グラフの \(3\)-彩色可能性は元のグラフの \(3\)-彩色可能性と同値である。

1. 実際に彩色を示すことで、図 \(\text{12.31}\) のグラフが条件 \(\text{(i)}\) を満たすと示せ。

   ヒント: 必要となる彩色は二つしかない: 「\(u\) と \(v\) が同じ色を持つ場合」と「\(u\) と \(v\) が異なる色を持つ場合」の両方で彩色を示せば十分となる。

2. 図 \(\text{12.31}\) のグラフが条件 \(\text{(ii)}\) を満たすと示せ。

   ヒント: \(\text{(a)}\) で解答した彩色は \(u\) と \(v\) に割り当てられた色からほぼ完全に決定する。

1. 上記の誤った主張の \(k = 2\) のケースに対する反例を答えよ。

2. 上記の誤った主張に対する誤った証明を次に示す。正当化されていない最初の文 (または文の一部) に下線を引け。

   誤った証明 グラフの頂点数 \(n\) に関する数学的帰納法で示す。次の述語 \(P(n)\) を帰納法の仮定とする:

   \[ \begin{aligned} P(n) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ & \text{全ての頂点の次数が \(k\) 以下の \(n\) 頂点グラフ \(G\) が} \\ & \text{次数 \(k\) 未満の頂点を持つなら、\(G\) は \(k\)-彩色可能である} \end{aligned} \]

   ベースケース: \(n = 1\) のとき \(G\) は次数が \(0\) の頂点を一つだけ持つ。この \(G\) は \(1\)-彩色可能なので \(P(1)\) は成り立つ。

   帰納ステップ: ある \(n\) で \(P(n)\) が成り立つと仮定する。\(P(n+1)\) を証明するために、全ての頂点の次数が \(k\) 以下である \(n + 1\) 頂点グラフを \(G_{n+1}\) として、\(G_{n+1}\) が次数 \(k\) 未満の頂点 \(v\) を持つと仮定する。この上で \(G_{n+1}\) が \(k\)-彩色可能だと示せばよい。

   \(G_{n+1}\) から頂点 \(v\) を除去して得られる \(n\) 頂点グラフを \(G_{n}\) とする。\(G_{n+1}\) で \(v\) に隣接する任意の頂点を \(u\) とすれば、\(v\) を除去すると \(u\) の次数は \(1\) だけ減少するので、\(G_{n}\) で頂点 \(u\) の次数は \(k\) より小さい。辺は追加されないから、\(G_{n}\) の全ての頂点の次数は \(k\) 以下である。よって \(G_{n}\) は帰納法の仮定 \(P(n)\) の前提条件を満たすので、\(k\)-彩色可能と分かる。

   \(G_{n}\) の \(k\)-彩色からは \(G_{n+1}\) の \(v\) 以外の頂点に対する彩色が得られる。\(v\) の次数は \(k\) 未満なので、\(v\) に隣接する頂点に割り当てられる色の種類は \(k\) 未満である。よって \(k\) 種類の色があれば、\(v\) に隣接頂点と異なる色を割り当てることができる。こうして \(G_{n+1}\) の \(k\)-彩色が得られた。 ■

3. 上記の誤った主張の前提条件を少しだけ強めると、\(\text{(b)}\) と同様の証明で示せる正しい主張となる。

   主張

   \(G\) の全ての頂点の次数が \(k\) 以下だと仮定する。もし ( \(\cdots\) ) 次数 \(k\) 未満の頂点を持つなら、\(G\) は \(k\)-彩色可能である。

   この主張に含まれる空欄を埋める文章として正しいものを次の中から全て選べ:

   • \(G\) が連結で

   • \(G\) が次数 \(0\) の頂点を持たず、

   • \(G\) が完全グラフ \(K_{k}\) を部分グラフに持たず、

   • \(G\) の全ての連結成分が

   • \(G\) のある連結成分が

図 \(\text{12.33}\) に示すグラフの左側にある三角形に属する三つの頂点を色頂点 (color-vertex) と呼ぶ。このグラフの任意の彩色において、これらの三つの色頂点には必ず異なる色が割り当てられる。三つの色頂点に割り当てられる色をそれぞれ \(\textbf{T}\), \(\textbf{F}\), \(\textbf{N}\) と呼ぶ。図中の破線は \(\textbf{N}\) が割り当てられる色頂点を端点とする辺を表す。

1. \(P\) と \(Q\) のラベルが付いた二頂点に異なる真理値色を割り当てるとき、グラフ全体の \(3\)-彩色が一意に定まると示せ。

2. このグラフの任意の \(3\)-彩色において、\(P \ \operatorname{\text{\footnotesize XOR}}\ Q\) のラベルが付いた頂点の色は \(P\), \(Q\) のラベルが付いた二頂点の色の \(\operatorname{\text{\footnotesize XOR}}\) だと示せ。

頂点 \(u\), \(v\) の間に二つの異なる路があるものの、\(u\) と \(v\) はいずれも閉路に含まれないようなグラフを示せ。\(u\) と \(v\) がどの頂点か示すこと。

ヒント: 条件を満たす \(5\) 頂点のグラフが存在する。

単純グラフでは辺を往復できるので、次数が \(0\) でない任意の頂点は偶数長閉歩道に含まれる。そのため偶数長閉歩道の存在は偶数長閉路の存在に関する情報をあまりもたらさない。一方で、奇数長の閉歩道の存在からは興味深い事実が分かる。

1. 全ての頂点が何らかの奇数長閉路と何らかの偶数長閉路に含まれる単純グラフの例を示せ。

   ヒント: 条件を満たす \(4\) 頂点のグラフが存在する。

2. 全ての頂点がただ一つの奇数長閉路に含まれ、どの頂点も偶数長閉路に含まれない単純グラフの例を示せ。

3. 単純グラフでは長さが最小の奇数長閉歩道は閉路だと示せ。なお、長さが最小の奇数長閉歩道より短い偶数長閉歩道は常に数多く存在する。

   ヒント: 長さが最小の奇数長閉歩道を \(\textbf{e}\) として、\(\textbf{e}\) の始点を \(a\) とする。もし \(\textbf{e}\) が閉路でないなら、重複する頂点 \(b \neq a\) が存在する。つまり \(\textbf{e}\) は \(a\) から \(b\) への歩道 \(\textbf{f}\) から始まり、その次に \(b\) から \(b\) への歩道 \(\textbf{g}\) があり、末尾に \(b\) から \(a\) への閉歩道 \(\textbf{h}\) がある⁷。

グラフ \(G\) が \(2\)-除去可能 (\(2\)-removable) とは、\(G - v\) と \(G - w\) が両方とも連結となるような \(G\) の二頂点 \(v\), \(w\) が存在することを言う。\(2\) 個以上の頂点を持つ任意の連結なグラフは \(2\)-除去可能だと示せ。

ヒント: 最長の路を考える。

次のように定義されるグラフ \(H_{n}\) を \(n\) 次元超立方体 (\(n\)-dimensional hypercube) と呼ぶ: \(H_{n}\) の頂点集合は長さ \(n\) のビット列全体の集合である。\(H_{n}\) の二頂点間に辺が存在するのは、両者が \(1\) ビットだけ異なるとき、かつそのときに限る。例えば \(\texttt{111}\) と \(\texttt{011}\) は \(1\) ビットだけ異なるので、\(H_{3}\) は頂点 \(\texttt{111}\) と頂点 \(\texttt{011}\) を結ぶ辺を持つ。これに対して \(\texttt{101}\) と \(\texttt{011}\) の違いは \(2\) ビットなので、\(H_{3}\) は頂点 \(\texttt{101}\) と頂点 \(\texttt{011}\) を結ぶ辺を持たない。

1. \(H_{3}\) には辺を共有しない異なる二つの全域木が存在しないと示せ。

2. \(H_{3}\) の任意の異なる頂点を \(x\), \(y\) とするとき、\(x\) と \(y\) 以外に頂点を共有しない \(x\) から \(y\) への三つの路が存在すると示せ。

3. \(H_{3}\) の連結度⁸が \(3\) だと結論付けよ。

4. 同じ議論で \(H_{4}\) の連結度を求めよ (一般に全ての正整数 \(n\) に対して \(H_{n}\) の連結度は \(n\) である)。

グラフの頂点の集合 \(M\) が極大接続 (maximal connected) とは、\(M\) に属する任意の二頂点が接続であり、\(M\) を部分集合に持つ \(M\) でない任意の集合が接続でない二頂点を含むことを言う。

1. 次の (連結でない) グラフの極大接続な頂点の集合を全て答えよ。

   

2. 極大接続な頂点の集合と連結成分の関係を述べ、証明せよ。

1. \(n > 1\) に対して \(K_{n}\) は \((n - 1)\)-辺接続だと示せ。

グラフ \(M_{n}\) を次のように定義する: 頂点集合が共通部分を持たない \(n\) 個の \((n - 1)\)-辺接続なグラフを取る (例えば、頂点を適切に変更した \(n\) 個の \(K_{n}\) を取る)。これらは \(M_{n}\) の部分グラフとなる。\(n\) 個のグラフから一つずつ計 \(n\) 個の頂点を選び、それらの頂点からなる部分グラフも \((n - 1)\)-辺接続になるまで二頂点間に辺を加える。

2. \(M_{3}\) を図示せよ。

3. \(M_{n}\) が \((n - 1)\)-辺接続である理由を説明せよ。

1. この主張に対する反例を示せ。

2. この主張は偽なので、次の「証明」は正しくない。証明に含まれる最初の誤り (正当化されないステップ) を指摘せよ。

   誤った証明 グラフの頂点数に関する数学的帰納法で示す。次の述語 \(P(n)\) を帰納法の仮定とする:

   \[ \begin{aligned} P(n) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ & \text{\(n\) 個の頂点を持ち、全ての頂点が} \\ & \text{正の次数を持つグラフは連結である} \end{aligned} \]

   ベースケース: グラフが \(1\) 個しか頂点を持たないとき、唯一の頂点は正の次数を持つことができない。よって \(P(1)\) は空虚に成り立つ。

   \(2\) 個の頂点を持ち全ての頂点が正の次数を持つグラフは一つしか存在しない。それは \(2\) 個の頂点の間に辺を持つグラフであり、明らかに連結である。よって \(P(2)\) は成り立つ。

   帰納ステップ: \(n \geq 2\) のとき \(P(n)\) から \(P(n+1)\) が導けることを示す必要がある。全ての頂点が正の次数を持つ \(n\) 頂点グラフを \(G\) とする。帰納法の仮定 \(P(n)\) より、このグラフは連結である。言い換えれば、\(G\) の任意の二頂点を結ぶ路が存在する。\(G\) に次数が正の新しい頂点 \(x\) を追加して \(n + 1\) 頂点グラフを作ることを考える:

   

   後は \(x\) から \(G\) の任意の頂点 \(z\) への路が存在すると示せばよい。\(x\) の次数は正なので、\(x\) から \(G\) の何らかの頂点 \(y\) への辺が存在する。よって \(x\) から \(y\) に移動して \(y\) から \(z\) に進むことで \(x\) から \(z\) に到達できる。よって \(P(n + 1)\) は成り立つ。

   数学的帰納法の原理より、全ての \(n \geq 0\) で \(P(n)\) は成り立つ。よって主張は正しい。 ■

グラフの辺が頂点の集合を離れる (leave) とは、その頂点の集合に辺の端点の一方が含まれ、もう一方が含まれないことを言う。

1. \(n\) 頂点グラフが乱雑 (mangled) とは、要素数が \(\lfloor n/2 \rfloor\) 以下の任意の頂点集合を離れる辺が存在することを言う。次の主張を証明せよ:

   主張

   全ての乱雑なグラフは連結である。

2. \(n\) 頂点グラフが乱脈 (tangled) とは、要素数が \(\lceil n/3 \rceil\) 以下の任意の頂点集合を離れる辺が存在することを言う。

   連結でない乱脈なグラフを一つ示せ。

3. 次の誤った証明に含まれる間違いを指摘せよ。

   誤った証明

   全ての乱脈なグラフは連結である。

   誤った証明 グラフの頂点数に関する強い数学的帰納法で示す。述語「乱脈な \(n\) 頂点グラフは連結である」を \(P(n)\) として、これを帰納法の仮定とする。

   ベースケース: 頂点を \(1\) 個だけ持つグラフは明らかに常に連結なので \(P(1)\) は成り立つ。

   帰納ステップ: ある \(n \geq 1\) で \(P(1)\), \(\ldots\), \(P(n)\) が全て成り立つと仮定する。これから \(P(n + 1)\) を示す。つまり、\(n + 1\) 個の頂点を持つグラフが乱脈なら連結だと示す。

   \(n + 1\) 個の頂点を持つ乱脈なグラフを \(G\) とする。\(\lceil n/3 \rceil\) 個の \(G\) の頂点を選び、その頂点からなる乱脈な部分グラフを \(G_{1}\) として、それ以外の頂点からなる乱脈な部分グラフを \(G_{2}\) とする。\(n \geq 1\) より \(G\) は \(2\) 個以上の頂点を持つので、\(G_{1}\) と \(G_{2}\) はどちらも少なくとも一つの頂点を持つ。\(G_{1}\) と \(G_{2}\) は乱脈なので、強い数学的機能の仮定より両方とも連結である。また、\(G\) は乱脈より \(G_{1}\) を離れる辺 \(e\) が存在し、この \(e\) は \(G_{2}\) に属する頂点をもう一方の端点に持つ。これは \(G\) の任意の二頂点間に路が存在することを意味する: 二頂点が同じ部分グラフに含まれるなら \(G_{1}\), \(G_{2}\) の連結性より路が存在し、そうでないなら \(e\) を経由することで二頂点間を移動できる。よって全体のグラフ \(G\) も連結である。

   以上で帰納ステップが完了したので、強い数学的帰納法の原理より主張は成り立つ。 ■

長さ \(2n\) の閉路グラフ \(C_{2n}\) において、閉路の反対側に位置する二頂点を反対組 (opposite) と呼ぶことにする。つまり \(C_{2n}\) で距離が \(n\) だけ離れた二頂点が反対組である。\(C_{2n}\) に全ての反対組を結ぶ辺を加えたグラフを \(G\) とする (全部で \(n\) 本の辺が追加される)。

1. \(G\) の任意の二頂点間の最短路を説明せよ。

   ヒント: 任意の最短路は反対組を結ぶ辺を最大で \(1\) 回しか使用しないと示す。

2. \(G\) の直径 (diameter) を求めよ。つまり、\(G\) の二頂点間の距離の最大値を求めよ。

3. \(G\) が \(4\)-連結でないと示せ。

4. \(G\) が \(3\)-連結だと示せ。

グラフ \(G\) の Eulerオイラー 周遊 (Euler tour) とは、\(G\) の全ての辺をちょうど一度ずつ含む閉歩道を言う⁹。この問題では次の定理を示す:

1. グラフが Euler 周遊を持つとき、全ての頂点の次数が偶数だと示せ。

以降では \(\text{(a)}\) の逆「連結な有限グラフの全ての頂点の次数が偶数なら、そのグラフは Euler 周遊を持つ」を証明する。このために、全ての辺を高々 \(1\) 回含む歩道を Euler 歩道 (Euler walk) と定義する。

2. 連結グラフの Euler 歩道 \(\textbf{v}\) が全ての辺を含まないと仮定する。このとき、\(\textbf{v}\) に含まれる頂点に隣接し、かつ \(\textbf{v}\) に含まれない辺が存在すると示せ。

連結な有限グラフの最長の Euler 歩道を \(\textbf{w}\) とする。

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

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

4. \(\text{w}\) の終点に隣接する辺は全て \(\text{w}\) に含まれる理由を説明せよ。

5. \(\text{w}\) の始点と終点が等しくないとき、\(\text{w}\) の終点の次数は奇数だと示せ。

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

6. 連結な有限グラフの全ての頂点の次数が偶数なら、そのグラフは Euler 周遊を持つと結論付けよ。

グラフ \(G\) に対する次の操作を考える: 異なる二頂点 \(u\), \(v\) を取る。そして:

• \(G\) が辺 \(\langle u\>\text{---}\>v \rangle\) を持ち、かつ辺 \(\langle u\>\text{---}\>v \rangle\) を含まない \(u\) から \(v\) への路を持つなら、\(\langle u\>\text{---}\>v \rangle\) を除去する。

• \(G\) に \(u\) から \(v\) への路が存在しないなら、辺 \(\langle u\>\text{---}\>v \rangle\) を追加する。

この操作を適用可能な異なる二頂点 \(u\), \(v\) が無くなるまで繰り返す手続きを考える。

\(G\) の頂点が \(1\), \(2\), \(\ldots\), \(n\) (\(n \geq 2\)) だと仮定すれば、この手続きは頂点が \(1\), \(2\), \(\ldots\), \(n\) のグラフを状態とする状態機械でモデル化できる。\(G\) が初期状態であり、操作が適用不可能なグラフが終了状態となる。

1. 頂点集合が \(\left( 1, 2, 3, 4 \right)\) で辺集合が \(\left\{ \left\{ 1, 2 \right\}, \left\{ 3, 4 \right\} \right\}\) のグラフを \(G\) とする。初期状態 \(G\) から到達可能な終了状態はいくつあるか？

2. 次に示す誘導変数 \(\text{(i)}\)-\(\text{(iv)}\) のそれぞれについて、初期状態 \(G\) がどんなグラフでも保たれることが保証される最も強い性質を次の選択肢から選べ。

   • 定数

   • 増加

   • 減少

   • 非減少

   • 非増加

   • どれでもない

   任意の状態に対して、\(e\) は辺の個数、\(c\) は連結成分の個数を表すと定める。例えば \(e\) は操作で増加することもあれば減少することもあるので、どの性質も持たない。

   1. \(c\)
   2. \(c + e\)
   3. \(2c + e\)
   4. \(c + \dfrac{e}{e + 1}\)

3. どんなグラフが初期状態 \(G\) だったとしても手続きは必ず停止する理由を説明せよ。\(\text{(b)}\) の結果を使う場合は証明してから使うこと。

4. 終了状態が頂点集合の順序無し木、つまり全域木であると示せ。

この主張を辺の個数 \(e\) に関する数学的帰納法で示せ。

1. 木の頂点の平均次数は \(2\) より小さいと示せ。

2. グラフの全ての頂点が \(k\) 以上の次数を持つとき、そのグラフには長さ \(k\) の路が存在すると示せ。

   ヒント: 最長の路を考える。

1. 図 \(\text{12.34}\) に示すグラフ \(G\) の全域木はいくつ存在するか？

2. \(G\) から頂点 \(e\) を除去したグラフを \(G - e\) とする。\(G - e\) の辺を共有しない二つの全域木を示せ。

3. \(G - e\) から辺 \(\langle a\>\text{---}\>d \rangle\) を除去したグラフには辺を共有しない二つの全域木が存在しない理由を説明せよ。

   ヒント: 頂点と辺の個数を数える。

図 \(\text{12.35}\) のグラフを \(H_{3}\) とする。\(H_{3}\) には辺を共有しない二つの全域木が存在しない理由を説明せよ。

連結なグラフの直径 (diameter) とは、二頂点間の距離の最大値と定義される。

1. \(n\) 頂点グラフの直径の最大値を求めよ。その直径を持つグラフを説明せよ。

2. \(n > 2\) のとき、\(n\) 個の頂点を持つ木の直径の最小値を求めよ。その直径を持つグラフを説明せよ。

1. グラフの同型写像で保存される性質を次から全て選べ:

   • 全ての頂点を含む閉路が存在する。

   • 同じ長さの辺が存在する。

   • どの二辺を除去したとしてもグラフの連結性は失われない。

   • 全ての全域木に含まれる辺が存在する。

   • 同型写像で保存される性質の否定が成り立つ。

2. 次に示す有限木に関する性質が正しいかどうかを答えよ。正しくないと解答した性質に対しては反例を示せ。

   • 任意の連結な部分グラフは木である。

   • 隣接しない任意の二頂点間に辺を加えると閉路が生じる。

   • 頂点の個数は葉の個数の \(2\) 倍から \(1\) を引いた値に等しい。

   • 頂点の個数は辺の個数から \(1\) を引いた値に等しい。

   • 任意の (木とは限らない) 有限グラフには全域木が存在する。

有限グラフ \(G\) に関する次の命題が正しいかどうか答えよ。

1. \(G\) は全域木を持つ。

2. \(G\) が連結なら \(|V(G)| = O(|E(G)|)\) である。

3. \(|E(G)| = O(|V(G)|)\)
4. \(\chi(G) \leq \max \left\{ \text{deg}(v) \; | \; v \in V(G) \right\}\)
5. \(|V(G)| = O(\chi(G))\)

[訳注: 漸近記法は第 14.7 節で説明される。]

Mark と呼ばれる手続きは、辺に印の付いていないグラフを最初に受け取り、辺に印を付けていく。手続きの任意の時点で、印の付いた辺だけからなる路を完全に印の付いた (fully marked) 路と呼び、完全に印の付いた路が存在しない二頂点間を結ぶ辺を適格 (eligible) と呼ぶことにする。

手続き Mark は適格な辺に印を付ける操作を適格な辺が存在しなくなるまで繰り返す。Mark が停止すること、そして停止した時点で印の付いた辺は元のグラフの全域木を構成することを示せ。

一般の (連結とは限らない) グラフの辺を変更して木を作る手続きを考えよう。この手続きはグラフを状態とする状態機械でモデル化される。この状態機械の遷移は次の規則で定義される:

• もし辺 \(\langle u\>\text{---}\>v \rangle\) を含む閉路が存在するなら、\(\langle u\>\text{---}\>v \rangle\) を除去する。

• もし \(u\) と \(v\) が接続でないなら、辺 \(\langle u\>\text{---}\>v \rangle\) を追加する。

遷移が不可能になる状態を終了状態 (final state) と呼ぶ。

1. 頂点集合が \(\left\{ 1, 2, 3, 4 \right\}\) で辺集合が \(\left\{ \langle 1\>\text{---}\>2 \rangle, \langle 3\>\text{---}\>4 \rangle \right\}\) のグラフが初期状態のとき、到達可能な終了状態を全て描画せよ。

2. この状態機械が最終状態に到達したとき、その最終状態は初期状態と同じ頂点集合を持つ木だと示せ。

3. 任意のグラフ \(G\) に対して、\(e\) で \(G\) の辺の個数、\(c\) で \(G\) の連結成分の個数、\(s\) で \(G\) が持つ閉路の個数を表すことにする。次に示す誘導変数 \(\text{(i)}\)-\(\text{(vi)}\) のそれぞれについて、初期状態がどんなグラフでも保たれることが保証される最も強い性質を次の選択肢から選べ。

   性質:

   • 定数

   • 増加

   • 減少

   • 非減少

   • 非増加

   • どれでもない

   誘導変数:

   1. \(e\)

   2. c

   3. \(s\)
   4. \(e - s\)
   5. \(c + e\)
   6. \(3c + 2e\)

4. \(\text{(c)}\) で示した誘導変数の一つが遷移ごとに狭義減少すると示し、全ての初期状態に対して状態機械は必ず終了状態に到達すると結論付けよ。

重み付きグラフ \(G\) では重みが最小の辺が一意に定まるという。つまり、ある辺 \(e \in E(G)\) が存在して、他の全ての辺 \(f \in E(G) - \left\{ e \right\}\) に対して \(w(e) < w(f)\) が成り立つ。このとき \(G\) の任意の最小全域木は \(e\) を含むと示せ。

頂点が \(4 \times 4\) の格子状に配置され、縦横に隣り合う頂点が辺で結ばれるグラフを \(G\) とする。\(G\) の辺に付いた重みは図 \(\text{12.36}\) の通りである。

次に \(G\) の最小重み全域木を構築する方法をいくつか示す。それぞれの構築方法について、設問に答えた上で、グラフに追加されるのと同じ順序で辺の重みを並べよ。

1. [Kruskal のアルゴリズム] 最初に最も重みの小さい辺を選択し、以降は「追加したとき閉路が生まれない辺の中で重みが最小のものを追加する」操作を \(G\) の全域木が得られるまで繰り返す。

   この構築方法の各ステップで追加される辺は、どんな白黒彩色の最小重み灰色辺 (補題 12.11.10) に対応するか？

2. [Prim のアルゴリズム] 頂点 \(u\) だけからなるグラフから始めて、「端点のちょうど一方が現在のグラフに含まれる辺の中で重みが最小のものを追加する」操作を \(G\) の全域木が得られるまで繰り返す。

   この構築方法の各ステップで追加される辺は、どんな白黒彩色の最小重み灰色辺 (補題 12.11.10) に対応するか？

3. [6.042 特製の「並列」MST アルゴリズム] 左上の頂点および \(v\), \(w\) のラベルが付いた頂点から始める。これら \(3\) 個の頂点を単一頂点の木と考える。それぞれの木に対して、「端点のちょうど一方がそれに含まれる辺の中で重みが最小のもの」を加える操作を同時に実行する。他の木とつながったら、一方の木は消滅したものとして扱う。木が一つになるまで操作を繰り返し、木が一つになったら灰色辺を使う通常の方法で \(G\) の全域木を作成する。

4. \(3\) 種類の構築方法が作成する MST が系 12.11.13 の示す通り同一であることを確かめよ。

この問題では次の定理を証明する:

同値関係の証明でよくあるように、この定理の証明は二つの部分からなる: \(\text{(a)}\) は右方向の含意を示し、\(\text{(b)}\) 以降は左方向の含意を示す。

1. 右方向の含意を示せ。\(3\)-\(5\) 行の議論で十分なはずである。

2. 続いて左方向の含意を示す。最初のステップとして、\(G\) の連結成分 \(H\) にだけ注目すれば十分な理由を説明せよ。

3. 次のステップとして、任意の木を \(2\)-彩色する方法を説明せよ。

4. \(H\) の全域木 \(T\) の \(2\)-彩色を任意に選ぶ。\(T\) に属さない任意の \(H\) の辺の端点にはその彩色で異なる色が塗られると示すことで、\(H\) が \(2\)-彩色可能だと示せ。

MIT Information Services & Technology (IS&T) は \(n\) 台のコンピューターからなるクラスターをケーブルとハブで構築する計画を立てている。それぞれのコンピューターには \(1\) 本のケーブルを接続でき、それぞれのハブには最大で \(5\) 本のケーブルを接続できる。クラスターに属する任意の二台のコンピューターの間にはケーブルからなる路が存在する必要がある。

1. 数学的帰納法を使って、\(n\) 台のコンピューターから構成されるクラスターを構築するには \(\lfloor (n - 2) / 3 \rfloor\) 個のハブがあれば十分だと示せ。

IS&T は \(m\) 個のハブを保有していると仮定する。

2. どこにもつながっていないデバイスが存在しないようにハブとコンピューターを接続するとき、必要になるケーブルの本数の上界となる \(m\) と \(n\) を使った簡単な式を示せ。

3. 一つのハブに接続できるケーブルの本数に制限がない場合を考えることで、どこにもつながっていないデバイスが存在しないようにハブとコンピューターを接続するとき、必要になるケーブルの本数の下界となる \(m\) と \(n\) を使った簡単な式を示せ。

4. IS&T はクラスターの構築で必要になるハブの個数を最小化したいと考えている。ここまでの結果を使って、クラスターを構築するには \(\lfloor (n - 2) / 3 \rfloor\) 個のハブが必要十分だと示せ。

この問題の \(\text{(a)}\) と \(\text{(b)}\) は独立している。

1. 連結なグラフ \(G\) の任意の全域木は \(G\) のカット辺を全て含むと示せ。

2. 連結な重み付きグラフ \(G\) の重みが最大の辺 \(e\) が一意に定まると仮定する。\(G\) の最小重み全域木で \(e\) を含むものが存在するなら \(e\) はカット辺だと示せ。

有限グラフ \(G\) がちょうど \(|V(G)| - |E(G)|\) 個の連結成分を持つとき \(G\) は森だと示せ。頂点の個数に関する数学的帰納法を使うこと。

\(G\) を連結なグラフ、\(T\) を \(G\) の全域木、\(e\) を \(G\) の辺とする。

1. \(e\) を含む閉路が \(G\) に存在しないなら、\(e\) は \(T\) の辺だと示せ。

2. \(e\) を含む閉路が \(G\) に存在し、\(T\) が \(e\) を含むなら、\(T - e + f\) が全域木となる辺 \(f \neq e\) が存在すると示せ。

3. \(G\) の辺が重みを持ち、辺 \(e\) の重みが他の全ての辺の重みより大きいとする。\(e\) を含む閉路が \(G\) に存在し、\(T\) が \(e\) を含むなら、\(T\) は \(G\) の最小重み全域木でないと示せ。

以上の結果から、重みが最大の辺が最小重み全域木に含まれるのはそれがカット辺のとき、かつそのときに限ると結論できる。

1. \(T\) を木、\(e\) を \(T\) で隣接しない二頂点を結ぶ「新しい」辺とする。グラフ \(T + e\) が閉路を必ず持つ理由を説明せよ。

2. \(T + e\) が少なくとも \(3\) 個の全域木を持つと結論付けよ。

\(5\) 個の頂点を持つ同型でない木は何種類あるか？ 解答が正しい理由を説明せよ。

グラフの全ての頂点を並べた列の幅 (width) が \(w\) とは、任意の頂点に対して「自身より前にある自身の隣接頂点が \(w\) 個以下」が成り立つことを言う。グラフ \(G\) の幅 が \(w\) とは、\(G\) の全ての頂点を並べた列であって幅が \(w\) であるものが存在することを言う。

1. 幅が \(1\) の有限グラフは森だと示せ。

   ヒント: 数学的帰納法を用いる。末尾の頂点を取り除く。

2. 全ての有限木の幅が \(1\) だと示せ。「グラフ \(G\) が森」と「\(G\) の幅が \(1\)」が同値だと結論付けよ。

\(n > 1\) 個の色が固定されたとき、\(m\) 個の頂点を持つ任意の木を彩色する方法は

通り存在すると示せ。数学的帰納法を使うこと。

\(G\) を重み付き連結グラフ、\(v\) を \(G\) の頂点とする。\(e ::= \langle u\>\text{---}\>w \rangle\) が \(G\) の辺であり、その重みは \(v\) に接続する他の辺より真に小さいと仮定する。

\(G\) の任意の最小重み全域木が \(e\) を含むと直接 (「灰色辺」の議論を使わずに) 示せ。

\(G\) をグラフ、\(e\) を \(G\) で隣接しない二頂点を結ぶ「新しい」辺とする (形式的に言えば \(e \in V(G)^{2} - E(G)\) とする)。\(G\) の辺集合 \(E(G)\) に新しい辺 \(e\) を加えたグラフを \(G + e\) と表記する。グラフを引数に取る実数値関数 \(f\) に関する用語を次のように定める:

• \(f\) が狭義辺増加 (strictly edge-increasing) \(\ \ \overset{\text{def}}{\longleftrightarrow}\ \ \) \(f(G + e) > f(G)\)

• \(f\) が定数 (constant) \(\ \ \overset{\text{def}}{\longleftrightarrow}\ \ \) \(f(G + e) = f(G)\)

• \(f\) が広義辺増加 (weakly edge-increasing) \(\ \ \overset{\text{def}}{\longleftrightarrow}\ \ \) \(f(G + e) \geq f(G)\)

• \(f\) が狭義辺減少 (strictly edge-decreasing) \(\ \ \overset{\text{def}}{\longleftrightarrow}\ \ \) \(f(G + e) < f(G)\)

• \(f\) が広義辺減少 (weakly edge-decreasing) \(\ \ \overset{\text{def}}{\longleftrightarrow}\ \ \) \(f(G + e) \leq f(G)\)

ただし右辺の条件は全ての有限グラフ \(G\) と全ての新しい辺 \(e\) に関して量化される。

例えば \(f(G) = |E(G)|\) なら \(f(G + e) = 1 + f(G) > f(G)\) が成り立つので、この \(f\) は狭義辺増加である。また、新しい辺を追加しても頂点は増えないので \(f(G) = |V(G)|\) なら \(f(G + e) = F(G)\) であり、この \(f\) は定数である。

次に示す関数が持つ上記の性質はどれか答えよ。どれも持たない可能性もある。

1. \(\chi(G)\) (\(G\) の彩色数)

2. \(G\) の接続度: \(\max \left\{ k \; | \; \text{\(G\) は \(k\)-接続} \right\}\)

3. \(G\) が持つ最長の路の長さ

4. \(G\) の二頂点間の距離の最大値¹⁰

5. \(G\) の内周 (girth): \(G\) が持つ閉路の長さの最小値

6. \(G\) の連結成分の個数

7. \(G\) に含まれる完全部分グラフのサイズの最大値: \(\max \left\{ n \; | \; \text{\(K_{n}\) は \(G\) の部分グラフ} \right\}\)

8. \(G\) の頂点の次数の和

9. \(G\) の全域木の個数

10. \(G\) のカット辺の個数