再構成問題 - 忘れても大丈夫

グラフ理論の有名な未解決問題である再構成予想について紹介します．

ここから先で考えるグラフはすべて，ラベルなし単純無向グラフです．すなわち，単純無向グラフの同型類について考えます．今後，ラベルなし単純無向グラフを単にグラフと呼ぶことにします．同型類について詳しく知りたい方は参考文献の3番を参照してください．

再構成問題（reconstruction problem）

グラフ $G = (V, E)$ に対して，多重集合 $[G - v \mid v \in V]$ を デッキ（deck） と呼び， $\mathcal{D}(G)$ と表します．ただし， $G - v$ は $G$ から頂点 $v$ を削除したグラフを表し，多重集合は同型なグラフも重複して含むものとします．また，デッキの要素を カード（card） と呼びます．

Q. 次のデッキの元のグラフは何でしょう？
　＊ 3番目と5番目のグラフは同型ですがデッキは多重集合なので両方含みます
f:id:tatanaideyo:20190111173404p:plain

答え（ここをクリック）

上の例ではデッキが与えられたときに元のグラフを一意に復元できましたが，どんなグラフに対してもデッキから一意に復元ができるでしょうか．

再構成問題（reconstruction problem）
　入力：グラフ $G$ のデッキ $\mathcal{D} (G)$ （ $G$ は分からない）
　出力： $G$ （の同型類）を一意に再構成できるか

グラフがデッキから一意に再構成できるとき，そのグラフは再構成可能（reconstructible）であると言います．

再構成予想（reconstruction conjecture）

再構成問題に関して Kelly と Ulam が1942年に次の予想を立てました．

再構成予想（reconstruction conjecture）
　頂点数が3以上のグラフは一意に再構成可能である

この予想はグラフ理論の未解決問題として知られています．この予想が成り立つと，非同型なグラフ $G$ と $H$ に対して， $\mathcal{D}(G) \neq \mathcal{D}(H)$ ということが分かります．

ここでの再構成問題は頂点に対して定義しましたが，辺を削除してデッキを作ったときに元のグラフが再構成可能かどうかを答える問題もあります．この問題は，辺再構成問題（edge reconstruction problem）と呼ばれ，それに対応する辺再構成予想（Haray, 1964）も未解決問題です．これらの予想の関係として，再構成予想が成り立つならば辺再構成予想が成り立つということが知られています．
一般グラフに対してはこれらの予想は未だに解かれていませんが，いくつかのサブクラスに対しては再構成予想が成り立つことが知られています．以降では，すべての頂点の次数が等しい正則グラフ（regular graph）が再構成可能であることを示します．

認識可能な性質

正則グラフが再構成可能であることを証明するために，いくつかの準備を行います．

定義．認識可能
　グラフの性質が 認識可能（recognizable） であるとは，デッキからその性質が求まることである

上の認識可能という言葉の定義は再構成問題での定義なので注意してください．認識可能なグラフの性質としていくつかあるので，その一部を紹介します．

認識可能な性質1：グラフの位数

頂点集合 $V$ のサイズ $|V|$ を $G$ の位数（order）と呼びます．デッキは多重集合なので， $|V| = |\mathcal{D}(G)|$ が成り立ちます．よって，デッキから $G$ の位数が分かるので位数は認識可能です．

認識可能な性質2：グラフの辺数

辺数 $|E|$ も認識可能です．頂点 $v \in V$ の次数を $\delta(v)$ ， $G - v$ のカードを $G_v = (V_v, E_v) \in \mathcal{D}(G)$ とします．このとき， $|E| = |E_v| + \delta(v)$ が成り立ちます．したがって， $|\mathcal{D}(G)| |E| = \sum_{v \in V} |E_v| + \delta(v)$ となり，握手補題 $2|E| = \sum_{v \in V} \delta(v)$ と $|V| = |\mathcal{D}(G)|$ から，

　　 $|E| = \frac{1}{n - 2} \sum_{v \in V} |E_v|$

となります．右辺の $|E_v|$ はデッキから分かるので辺数は認識可能です．

認識可能な性質3：次数列

グラフの次数列（degree sequence）とは $G$ の頂点の次数を非減少で並べた列のことを言います．上からグラフの辺数は認識可能なので， $\delta(v) = |E| - |E_v|$ からカード $G_v$ を与える頂点 $v$ の次数が分かります．他のカードに対して次数を求めて，それを非減少に並べれば $G$ の次数列と一致します．よって，次数列は認識可能です．
同型なグラフは同じ次数列を持ちますが，同じ次数列を持つ非同型なグラフは存在します．残念なことに，次数列は認識可能なのですが再構成予想を示すのに直接的には使えなさそうです．

下の図は上の3つの認識可能な性質の例です．
f:id:tatanaideyo:20190111195933p:plain

正則グラフは再構成可能（Kelly, 1957）

$k$ -正則グラフ $G$ のデッキ $\mathcal{D} (G)$ が与えられたとします．このとき， $\mathcal{D}(G)$ の次数列から $G$ が $k$ -正則グラフかどうかが分かります（次数列の要素がすべて $k$ ）． $k$ -正則グラフと分かったときに，任意にカード $G_v \in \mathcal{D}(G)$ を選びます． $G_v$ には次数が $k - 1$ の頂点がちょうど $k$ 個存在します．それ以外の頂点の次数はすべて $k$ です．このとき， $G$ が $k$ -正則グラフであることから， $v$ はその次数 $k - 1$ の頂点との間に辺があり，それ以外の頂点との間には辺がないことが分かります．これによって， $G$ が一意に構成可能であることが示せました．