再建の推測

非公式には、グラフ理論における再構築予想は、グラフはそのサブグラフによって一意に決定されるというものである。これはケリー^[1]とウラム^{[2] [3]}によるものである。

グラフ が与えられたとき、の頂点削除サブグラフは、 から正確に 1 つの頂点を削除することによって形成されるサブグラフです。定義により、これはの誘導サブグラフです。 ${\displaystyle G=(V,E)}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$

グラフ に対して、と表記されるG のデッキは、のすべての頂点削除されたサブグラフの同型類の多重集合です。 の各グラフはカードと呼ばれます。 同じデッキを持つ 2 つのグラフは、ハイポモルフィックであると言われます。 ${\displaystyle G}$${\displaystyle D(G)}$${\displaystyle G}$${\displaystyle D(G)}$

これらの定義を用いると、推測は次のように述べることができます。

• 再構成予想:少なくとも 3 つの頂点を持つ任意の 2 つの低同型グラフは同型です。

(グラフに少なくとも 3 つの頂点があるという要件が必要なのは、2 つの頂点上の両方のグラフが同じデッキを持つためです。)

ハラリー^[4]は、この推測のより強力なバージョンを提案した。

• 集合再構成予想:少なくとも 4 つの頂点を持ち、頂点が削除されたサブグラフの集合が同じである 2 つのグラフは同型です。

グラフ が与えられた場合、の辺削除サブグラフは、 から正確に 1 つの辺を削除することによって形成されるサブグラフです。 ${\displaystyle G=(V,E)}$${\displaystyle G}$${\displaystyle G}$

グラフ に対して、G のエッジデッキ( と表記) は、のエッジ削除サブグラフのすべての同型類の多重集合です。 の各グラフはエッジカードと呼ばれます。 ${\displaystyle G}$${\displaystyle ED(G)}$${\displaystyle G}$${\displaystyle ED(G)}$

• エッジ再構築予想: (Harary, 1964) ^[4]少なくとも4つのエッジを持ち、同じエッジデッキを持つ2つのグラフは同型である。

再構築予想の文脈では、グラフのデッキからプロパティを決定できる場合、 グラフ プロパティは認識可能と呼ばれます。グラフの次のプロパティは認識可能です。

• グラフの順序– グラフの順序は、多重集合がの1つの頂点を削除することによって作成されたの各サブグラフを含むため、から認識できます。したがって^[5]${\displaystyle G}$${\displaystyle |V(G)|}$${\displaystyle D(G)}$${\displaystyle D(G)}$${\displaystyle G}$${\displaystyle G}$${\displaystyle |V(G)|=|D(G)|}$
• グラフの辺の数–頂点を持つグラフの辺の数は認識可能です。まず、 の各辺がのメンバーに出現することに注目してください。これは の定義によって真であり、 の定義により、各辺は、それが接続する各頂点が のメンバーに含まれるたびに必ず含まれることが保証されます。そのため、 の端点が削除される 2 つのメンバーを除くすべてのメンバーに辺が発生します。したがって、はのi番目のメンバーの辺の数です。^[5]${\displaystyle G}$${\displaystyle n}$${\displaystyle |E(G)|}$${\displaystyle G}$${\displaystyle n-2}$${\displaystyle D(G)}$${\displaystyle D(G)}$${\displaystyle D(G)}$${\displaystyle D(G)}$${\displaystyle |E(G)|=\sum {\frac {q_{i}}{n-2}}}$${\displaystyle q_{i}}$${\displaystyle D(G)}$
• 次数列– グラフの次数列は、各頂点の次数が認識可能なため認識可能です。のi番目の要素に存在しない頂点の次数を見つけるには、その頂点を削除して作成されたグラフ を調べます。このグラフには に接しないすべての辺が含まれているため、の辺の数が であれば となります。グラフ内のすべての頂点の次数がわかれば、グラフの次数列がわかります。^[5]${\displaystyle G}$${\displaystyle v_{i}}$${\displaystyle D(G)}$${\displaystyle G_{i}}$${\displaystyle v_{i}}$${\displaystyle q_{i}}$${\displaystyle G_{i}}$${\displaystyle |E(G)|-q_{i}=\deg(v_{i})}$
• (頂点)接続性– 定義により、任意の頂点を削除すると- 頂点接続グラフが作成される場合、グラフは - 頂点接続されています。したがって、すべてのカードが - 頂点接続グラフである場合、元のグラフは- 頂点接続であったことがわかります。また、元のグラフが接続されていたかどうかを判断することもできます。これは、任意の 2 つのカードが接続されていることと同じです。^[5]${\displaystyle n}$${\displaystyle n-1}$${\displaystyle n-1}$${\displaystyle n}$${\displaystyle G_{i}}$
• トゥッテ多項式
• 特性多項式
• 平面性
• グラフ内の全域木の種類
• 彩色多項式
• 完全グラフまたは区間グラフ、あるいは完全グラフの特定の他のサブクラスであること^[6]

再構成予想と集合再構成予想は、ブレンダン・マッケイによって、最大13頂点を持つすべてのグラフに対して検証されている。^{[7] [8]}

確率論的な意味では、ほぼすべてのグラフが再構築可能であることがBéla Bollobásによって示されています。 ^[9]これは、頂点上のランダムに選択されたグラフが再構築不可能で ある確率が、無限大に近づくにつれて 0 に近づくことを意味します。実際、ほぼすべてのグラフが再構築可能であるだけでなく、再構築にデッキ全体は必要ないことが示されています。ほぼすべてのグラフには、デッキ内にグラフを一意に決定する 3 枚のカードが存在するという特性があります。 ${\displaystyle n}$${\displaystyle n}$

この予想は、多数の無限のグラフクラス（および、当然のことながら、それらの補グラフ）に対して検証されています。

• 正則グラフ^[10] - 正則グラフは、グラフのデッキから認識できるいくつかの事実を直接適用することで再構築できます。 -正則グラフとそのデッキが与えられている場合、次数シーケンスを認識することでデッキが正則グラフであることを認識できます。ここで、デッキの 1 つのメンバー を調べてみましょう。このグラフには、次数が の頂点と次数が の頂点がいくつか含まれています。このグラフに頂点を追加し、それを次数の頂点に接続して、開始時のグラフと同型の -正則グラフを作成できます。したがって、すべての正則グラフはデッキから再構築できます。興味深い正則グラフの特定のタイプは、完全グラフです。^[5]${\displaystyle n}$${\displaystyle G}$${\displaystyle D(G)}$${\displaystyle D(G)}$${\displaystyle G_{i}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n-1}$${\displaystyle n}$${\displaystyle n-1}$${\displaystyle n}$
• 木^[10]
• 切断されたグラフ^[10]
• 単位間隔グラフ ^[6]
• 端点のない分離可能なグラフ^[11]
• 最大平面グラフ
• 最大外平面グラフ
• 外平面グラフ
• 重要なブロック

再構成予想は、すべての2連結グラフが再構成可能である場合に成立する。^[12]

頂点再構成予想は、 がその頂点デッキ から再構成できる場合、その補集合 は次のようにから再構成できるという双対性に従います。 から始めて、 内のすべてのカードの補集合を取って を取得し、これを使用して を再構成し、次に再び補集合を取って を取得します。 ${\displaystyle G}$${\displaystyle D(G)}$${\displaystyle G'}$${\displaystyle D(G')}$${\displaystyle D(G')}$${\displaystyle D(G)}$${\displaystyle G}$${\displaystyle G'}$

エッジ再構築はそのような双対性に従いません。実際、エッジ再構築可能なグラフのいくつかのクラスでは、その補グラフがエッジ再構築可能かどうかは不明です。

以下のものは一般に再構築できないことが示されています。

• 有向グラフ: 再構築不可能な有向グラフの無限族が知られており、これにはトーナメント(Stockmeyer ^[13] )と非トーナメント(Stockmeyer ^[14] )が含まれる。トーナメントは、強く連結されていない場合に再構築可能である。^{[15]再構築予想のより弱いバージョンが有向グラフに対して予想されている。}新しい有向グラフ再構築予想を参照のこと。
• ハイパーグラフ（Kocay ^[16]）。
• 無限グラフ。T がすべての頂点が可算無限次数を持つ木である場合、 Tの2つの互いに素なコピーの和はTに同型ではないが、同型ではない。^[17]
• 局所有限グラフは、すべての頂点が有限次数を持つグラフです。局所有限無限木の再構築可能性の問題（1972年のハラリー・シュウェンク・スコット予想）は、2017年にボウラーらによって最大次数3の再構築不可能な木が発見されるまで、長年未解決の問題でした。^[18]

• 新しい有向グラフ再構築予想
• 部分的な対称性

このテーマに関する詳しい情報は、ナッシュ・ウィリアムズの調査を参照のこと。^[19]