3.3. 単純グラフから多重グラフへの一般化

練習問題 2.3, 2.4, 2.7, 2.14, 2.15, 2.5, 2.8 の中で「単純グラフ」を「多重グラフ」に置き換えても成り立つのはどれか？

[成り立たなくなる問題に対しては反例を示すこと。多重グラフでも成り立つ問題に対しては証明を示すか、単純グラフにおける議論がそのまま多重グラフにも適用できることを説明せよ。]

少なくとも一つの辺を持つ多重グラフを \(G\) とする。\(G\) の各頂点の次数が偶数なら \(G\) は閉路を持つと示せ。

[解答: これは 2017 年春学期に開講された講義で出した midterm #2 の Exercise 4 である。解答は講義ページに載っている。]

\(G\) を多重グラフ、\(d > 2\) を整数とする。\(G\) の全ての頂点 \(v\) で \(\deg v > 2\) が成り立つとき、\(d\) で割り切れない長さを持つ閉路が \(G\) に存在することを示せ。

\(G\) を多重グラフとする。奇数の次数を持つ \(G\) の頂点がちょうど二つ存在するとき、その二つの頂点は路連結だと示せ。

ループを持たない多重グラフを \(G=\left( V,E,\varphi\right) \) とする。

辺 \(e \in E\) と \(e\) に含まれる頂点 \(v \in V\) に対して、\(e/v\) で \(v\) でない \(e\) の端点を表す。\(e\) がループなら、\(e/v\) は \(v\) を表す。

それぞれの \(v \in V\) に対して、有理数 \(q_{v}\) を次のように定義する:

[右辺で足されている項の分母 \(\deg v\) は足される項が一つでもあるなら \(0\) でない点に注意してほしい。]

[この \(q_{v}\) は \(v\) の隣接頂点の次数の平均値である。ただし、隣接頂点の次数は \(v\) とその隣接頂点を結ぶ辺の個数で重み付けされる。例えば \(v\) が隣接頂点を持たないなら \(q_{v} = 0\) が成り立つ。]

次の不等式を示せ:

[言い換えれば、ソーシャルネットワークにおいて、あなたの友達は平均してあなたより多くの友達を持つ！]

[ヒント: 任意の実数 \(x\), \(y\) に対して \(\dfrac{x}{y}+\dfrac {y}{x}\geq2\) が成り立つ。この不等式はどうして、そしてどのように役に立つのだろうか？]

\(F\) を任意の体とする。 [例えば \(\mathbb{Q}\), \(\mathbb{R}\), \(\mathbb{C}\) などが \(F\) となれる。]

\(G = \left( V, E, \varphi\right) \) を多重グラフとする。ここで \(V = \left\{ 1, 2, \ldots, n \right\} \) (\(n \in \mathbb{N}\)) である。

各辺 \(e \in E\) に対して、ベクトル \(\chi_{e} \in F^{n}\) (\(n\) 個の要素からなる列ベクトル) を次のように構築する:

• \(e\) がループなら、零ベクトルを \(\chi_{e}\) とする。

• そうでないなら、\(e\) の端点を \(u\), \(v\) として、第 \(u\) 要素に \(1\) を、第 \(v\) 要素に \(-1\) を、それ以外の場所に \(0\) を持つ列ベクトルを \(\chi_{e}\) とする。 [\(u\) と \(v\) をどちらの端点とするかは好きに選んでよい。どのように選んだとしても命題は成り立つ。]

全ての \(e\in E\) に対する列ベクトル \(\chi_{e}\) を横に並べた \(F\) 上の \(n\times\left\vert E\right\vert \) 行列を \(M\) とする (列ベクトルを並べる順番は適当で構わない: 命題の真偽には影響しない)。\(G\) の成分の個数を \(\operatorname{conn} G\) と表すとき、次の等式を示せ:

[例: 次の多重グラフを \(G\) とする:

このとき \(n=5\) である。辺 \(b\) の端点に対して \(u = 2\), \(v = 5\) としたなら、\(\chi_{b}\) は次のようになる:

同じ辺で \(u = 5\), \(v=2\) としたなら、\(\chi_{b}\) は次のようになる:

\(\chi_{b}\) としてどちらを採用しても構わない。同様の列ベクトルを \(G\) の全ての辺に対して構築し、それらを横に並べれば \(M\) が得られる:

ここでは \(\chi_{a}\), \(\chi_{b}\), \(\chi_{c}\), \(\chi_{d}\), \(\chi_{e}\), \(\chi_{f}\), \(\chi_{g}\), \(\chi_{h}\) の順に列ベクトルを並べている。容易に分かるように \(\operatorname*{rank}M=4\) であり、これは \(\left\vert V\right\vert -\operatorname*{conn}G\) に等しい。]

[Remark: この練習問題で証明する命題は「全ての \(e \in E\) に対するベクトル \(\chi_{e}\) が張る空間は \(\left\vert V\right\vert -\operatorname*{conn}G\) の次元を持つ」と言い換えられる。

トポロジーの研究者は行列 \(M\) を「境界演算子 \(\partial\colon C_{1}\left( G\right) \rightarrow C_{0}\left( G\right) \) を表す行列」と捉えるだろう。このとき \(G\) は CW 複体 (CW-complex) となる。]

多重グラフ \(G\) に対して、\(G\) の成分の個数を \(\operatorname{conn} G\) と表す。 [例えば \(G\) が頂点を持たなければ \(\operatorname{conn} G = 0\) であり、\(G\) が連結なら \(\operatorname{conn} G = 1\) である。]

\(\left( V,H,\varphi\right) \) を多重グラフ、\(E\), \(F\) を \(H\) の部分集合とする。

1. 次の不等式を示せ:

   \[ \begin{aligned} & \operatorname{conn}\left( V,\ E,\ \varphi|_{E}\right) +\operatorname{conn}\left( V,\ F,\ \varphi|_{F}\right) \nonumber\\ & \quad \leq\operatorname{conn}\left( V,\ E\cup F,\ \varphi|_{E\cup F}\right) +\operatorname{conn}\left( V,\ E\cap F,\ \varphi|_{E\cap F}\right) \end{aligned} \]

   [ヒント: 単純グラフの場合を考えても構わない。つまり、単純グラフ \(G = \left(V, E\right)\) と \(V\) の部分集合 \(E\), \(F\) に対する次の不等式の証明を解答としてよい:

   \[ \begin{aligned} & \operatorname{conn}\left( V,\ E\right) +\operatorname{conn}\left( V,\ F\right) \\ &\quad \leq\operatorname{conn}\left( V,\ E\cup F\right) +\operatorname{conn}\left( V,\ E\cap F\right) \end{aligned} \]

   こうしたとしても多重グラフの場合と比べて問題が本質的に簡単になるわけではない。ただ、写像 \(\varphi\) を考える必要がなくなる。]

2. 前問の不等式が等式とならない例を示せ。

[解答: これは 2017 年春学期に開講された講義で出した homework set #3 の Exercise 3 である。解答は講義ページに載っている。]

\(2m\) 個の辺を持つ連結な多重グラフを \(G=\left( V,E,\varphi\right) \) とする (\(m \in \mathbb{N}\))。二つの異なる辺からなる集合 \(\left\{ e,f\right\} \) が友好組 (friendly couple) とは、\(e\) と \(f\) が共通の端点を少なくとも一つ持つことを言う。共通要素を持たない \(m\) 個の友好組に \(G\) の辺集合を分解できると示せ。言い換えれば、共通要素を持たない \(m\) 個の友好組 \(\left\{ e_{1},f_{1}\right\}\), \(\left\{ e_{2},f_{2}\right\}\), ..., \(\left\{ e_{m},f_{m}\right\} \) であって \(E=\left\{ e_{1},f_{1},e_{2},f_{2},\ldots,e_{m},f_{m}\right\} \) を満たすものが存在することを示せ。 [ここで「共通要素を持たない」は「辺の集合として共通要素を持たない」を意味する ── つまり共通の辺を持たない。]

[例: 偶数個の辺を持つ多重グラフの例を示す:

このグラフでは \(\left\{a,z\right\}\), \(\left\{b,x\right\}\), \(\left\{c,y\right\}\) が条件を満たす友好組の例である。]

[ヒント: \(\left\vert E\right\vert \) に関する数学的帰納法を使う。次数が \(1\) より大きい頂点を選び、\(G\setminus v\) の成分に注目する。]

\(n \geq 0\) を整数、和 \(d_{1}+d_{2}+\cdots+d_{n}\) が偶数となるような \(n\) 個の非負整数を \(d_{1},d_{2},\ldots,d_{n}\) とする。

1. 頂点集合が \(\left\{ 1,2,\ldots,n\right\} \) で、全ての \(i\in\left\{ 1,2,\ldots ,n\right\} \) が \(\deg i=d_{i}\) を満たす多重グラフ \(G\) が存在することを示せ。

2. 頂点集合が \(\left\{ 1,2,\ldots,n\right\} \) で、全ての \(i\in\left\{ 1,2,\ldots ,n\right\} \) が \(\deg i=d_{i}\) を満たすループを持たない多重グラフ \(G\) が存在するのは、全ての \(i\in\left\{ 1,2,\ldots,n\right\} \) が次の不等式を満たすとき、かつそのときに限ると示せ:

   \[ \begin{aligned} \sum_{\substack{j\in\left\{ 1,2,\ldots,n\right\} ;\\j\neq i}}d_{j}\geq d_{i} \end{aligned} \]

[Remark: 最後の不等式は \(n\) 角形不等式 (\(n\)-gon inequality) という名前で知られる。この不等式の成立は辺の長さが \(d_{1},d_{2},\ldots,d_{n}\) であるような \(n\) 角形の存在と等価である (長さ \(0\) の辺は退化すると解釈する)。]

ループを持たない多重グラフを \(G\) とする。辺が相異なる \(G\) の歩道を \(G\) の小道 (trail) と呼ぶ (小道の頂点は重複しても構わない)。\(u\), \(v\) を \(G\) の二頂点とする。歩道と同様に、「\(u\) から \(v\) への小道」とは「\(u\) で始まって \(v\) で終わる小道」を意味する。次の等式を示せ:

[ヒント: 路でない小道の組を作る方法を定義し、路でない小道の集合が共通要素を持たない組の和集合として表せると示す。組の定義が well-defined であること (任意の路でない小道 \(\mathbf{t}\) が自身でない相方を持ち、\(\mathbf{t}\) の相方の相方が \(\mathbf{t}\) であること) を忘れずに証明する。]

全ての頂点が偶数の次数を持つ多重グラフを \(G\)、\(u\), \(v\) を \(G\) の異なる二頂点とするとき、\(u\) から \(v\) への路の個数は偶数だと示せ。

[ヒント: \(u\) と \(v\) をつなぐ辺を \(G\) に加えると、頂点の中で \(u\) と \(v\) だけが奇数の次数を持つグラフが得られる。このグラフに対する「\(u\) から \(v\) への路の個数は奇数」という命題が示せれば証明が完了する [なぜ？]。この命題は元の命題よりずっと証明しやすい: 路には最初の辺が存在するから...。]

[練習問題 3.10 より、この命題は「路」を「小道」に置き換えても成り立つ。]

\(G=\left( V,E,\varphi\right) \) を \(\left\vert E\right\vert >\left\vert V\right\vert \) が成り立つ多重グラフ、\(n=\left\vert V\right\vert \) とする。長さが \(\dfrac{2n+2}{3}\) 以上の閉路を \(G\) が持つことを示せ。

[解答: これは 2017 年春学期に開講された講義で出した midterm #3 の Exercise 8 である。解答は講義ページに載っている。]