練習問題

次に示す二つのグラフの離散面は何か？

それぞれの離散面 (閉歩道) を頂点の列として答えよ。列には空白を入れずに、アルファベット順で最も先頭にある文字を始点かつ終点として時計回りに (例えば \(adbfa\) のように) 頂点を並べること。また、異なる閉歩道の区切りは空白とせよ。

1.  

   

2.  

   

下図の通りにグラフ \(G_{1}\), \(G_{2}\), \(G_{3}\) を定める:

1. \(G_{1}\) から \(G_{2}\) への同型写像、そして \(G_{2}\) から \(G_{3}\) への同型写像を示せ。

2. \(\text{(a)}\) の結果が \(G_{1}\) から \(G_{3}\) への同型写像の存在を意味する理由を説明せよ。

\(G\), \(H\) を平面グラフとする。\(G\) の平面埋め込み \(E_{G}\) が \(H\) の平面埋め込み \(E_{H}\) と同型 (isomorphic) とは、\(G\) から \(H\) への同型写像であって \(E_{G}\) の離散面を \(E_{H}\) の離散面に移すものが存在することを言う。

3. 上に示した平面埋め込みの一つは他の二つと同型でない。どれか？ 理由を簡単に説明せよ。

4. 二つの同型な平面グラフの平面埋め込みが同じ個数の離散面を持つことを示せ。

1. 次の条件を満たす二つの平面埋め込みを持つ平面グラフの例を答えよ:

   一つ目の平面埋め込みに、二つ目の埋め込みの離散面のいずれとも長さが異なる離散面が存在する。

   条件の成立が分かる二つの平面埋め込みを示すこと。

2. 平面埋め込み \(\mathcal{E}\) の長さ (length) を \(\mathcal{E}\) に属する離散面の長さの和と定義する。同じ平面グラフの全ての平面埋め込みは同じ長さを持つと示せ。

平面埋め込みの定義 (定義 13.2.2 ) は連結グラフを仮定していた。この定義を連結でない平面グラフに拡張するには、次の構築ケースを追加する必要がある:

• 構築ケース: [和集合] \(\mathcal{E}_{1}\) と \(\mathcal{E}_{2}\) が共通の頂点を持たない平面埋め込みのとき、\(\mathcal{E}_{1} \cup \mathcal{E}_{2}\) は平面埋め込みである。

Euler の公式も連結でないグラフに拡張できる。\(v\) 個の頂点と \(e\) 個の辺と \(c\) 個の連結成分を持つグラフの平面埋め込みが \(f\) 個の離散面を持つなら、次の等式が成り立つ:

この事実は平面埋め込みの定義に関する構造的帰納法で証明できる。

1. 構造的帰納法のベースケースを述べ、証明せよ。

2. 「和集合」の構築ケースにおいて、平面埋め込み \(\mathcal{E}_{i}\) を持つグラフの頂点、辺、連結成分の個数を \(v_{i}\), \(e_{i}\), \(c_{i}\) として、\(\mathcal{E}_{i}\) に含まれる離散面の個数を \(f_{i}\) とする (\(i = 1, 2\))。同様に、平面埋め込み \(\mathcal{E} ::= \mathcal{E_{1}} \cup \mathcal{E_{2}}\) を持つグラフの頂点、辺、連結成分の個数を \(v\), \(e\), \(c\) として、\(\mathcal{E}\) に含まれる離散面の個数を \(f\) とする。\(v\), \(e\), \(c\), \(f\) を \(v_{i}\), \(e_{i}\), \(c_{i}\), \(f_{i}\) を使って表せ。

3. 構造的帰納法の「和集合」の構築ケースを証明せよ。

1. グラフが \(8\) 個の頂点と \(24\) 個の辺を持つという。頂点の平均次数を求めよ。

2. 連結な平面グラフの辺の個数が頂点の個数より \(5\) だけ大きいという。このグラフの平面埋め込みは何個の面を持つか？

3. 連結なグラフの頂点の個数が辺の個数より \(1\) だけ大きいという。このグラフが平面グラフだと示せ。

4. \(\text{(c)}\) のグラフの平面埋め込みは何個の面を持つか？

5. 図 \(\text{13.17}\) のグラフを \(G\) とする。\(G\) から \(G\) への異なる同型写像 (恒等写像を含む) はいくつあるか？

図 \(\text{13.18}\) に四つの平面グラフを示す。

1. 図が表す四つの平面埋め込みに含まれる離散面 (面の境界を定義する閉歩道) をそれぞれ示せ。

2. 同型なグラフはどれか？ 同じ (離散面が同一の) 平面埋め込みを表すのはどれか？

3. 図 \(\text{13.18}\) \(\text{(d)}\) が表す平面埋め込みを、平面埋め込みの再帰的定義 (定義 13.2.2) を繰り返し適用することで構築してみせよ。構築ケースの適用ごとに、適用の対象となる離散面と新しく作成される閉歩道を示すこと。

平面埋め込みの定義 (定義 13.2.2) に関する構造的帰納法を使って次の命題を示せ。

1. 任意のグラフの平面埋め込みでは、全ての辺が離散面にちょうど \(2\) 度含まれる。

2. \(3\) 個以上の頂点を持つ連結グラフの平面埋め込みでは、任意の離散面の長さが \(3\) 以上である。

グラフが三角形欠落 (triangle-free) とは、長さ \(3\) の閉路を持たないことを言う。

1. 三角形欠落かつ連結な平面グラフが \(v > 2\) 個の頂点と \(e\) 個の辺を持つなら次の不等式が成り立つと示せ:

   \[ e \leq 2v - 4 \tag{13.9}\]

2. 任意の三角形欠落かつ連結な平面グラフは次数 \(3\) 以下の頂点を持つと示せ。

3. 任意の三角形欠落かつ連結な平面グラフは \(4\)-彩色可能だと示せ。

1. 次の補題を示せ:

   補題[辺の順序の交換]

   頂点集合が共通部分を持たない平面グラフの集合がそれぞれ平面埋め込みを持ち、それらに平面埋め込みの定義 (定義 13.2.2) の構築ケースを適用して辺 \(e\) と辺 \(f\) をこの順番で追加したところ、平面埋め込み \(\mathcal{F}\) が得られたとする。このとき、同じ平面埋め込みの集合に対して辺 \(f\) と辺 \(e\) をこの順番で追加可能であり、その結果として得られる平面埋め込みは \(\mathcal{F}\) である。

   ヒント: \(e\) と \(f\) の追加が二つある構築ケースのいずれを利用したかに応じて、四通りの場合を議論する。構造的帰納法は必要ない。

2. 次の系を示せ:

   系[辺の順序の置換]

   頂点集合が共通部分を持たない平面グラフの集合がそれぞれ平面埋め込みを持ち、それらに平面埋め込みの定義 (定義 13.2.2) の構築ケースを適用して辺 \(e_{0}\), \(e_{1}\), \(\ldots\), \(e_{n}\) をこの順番で追加したところ、平面埋め込み \(\mathcal{F}\) が得られたとする。このとき、同じ平面埋め込みの集合に対して辺 \(e_{0}\), \(e_{1}\), \(\ldots\), \(e_{n}\) の任意の置換¹をその順番で追加可能であり、その結果として得られる平面埋め込みは \(\mathcal{F}\) である。

   ヒント: 列 \(0\), \(1\), \(\ldots\), \(n\) を置換 \(\pi(0)\), \(\pi(1)\), \(\ldots\), \(\pi(n)\) に変形するのに必要な隣接要素の交換の回数に関する数学的帰納法を用いる。

3. 次の系を示せ:

   系[辺の除去]

   平面グラフから辺を除去して得られるグラフは平面グラフである。

4. 平面グラフの部分グラフは平面グラフだと結論付けよ。