部分立方体

グラフ理論において、部分立方体とは、ハイパーキューブの等長部分グラフであるグラフのことである。^{[ 1 ]}言い換えれば、部分立方体は、部分立方体内の任意の2つの頂点間の距離がハイパーキューブ内のそれらの頂点間の距離と同じになるように、ハイパーキューブの部分グラフと同一視することができる。同等に、部分立方体とは、グラフ内の2つの頂点間の距離がそれらのラベル間のハミング距離に等しくなるように、頂点に同じ長さのビット列でラベル付けできるグラフのことである。このようなラベル付けはハミングラベル付けと呼ばれ、部分立方体のハイパーキューブへの等長埋め込みを表す。

Firsov (1965)は、グラフのハイパーキューブへの等長埋め込みを最初に研究した。このような埋め込みを許容するグラフは、Djoković (1973)とWinkler (1984)によって特徴付けられ、後に部分キューブと呼ばれるようになった。グラフのハイパーキューブラベル付けではなく集合の族という用語で同じ構造に関する別の研究の流れは、Kuzmin & Ovchinnikov (1975)やFalmagne & Doignon (1997)などによって続けられた。^{[ 2 ]}

すべての木は部分立方体です。例えば、木Tにm本の辺があるとします。これらの辺に (任意に) 0からm – 1までの番号を付けます。木のルート頂点r を任意に選び、各頂点vにmビットの文字列をラベル付けします。この文字列では、辺i がT内のrからvへのパス上にある場合、位置iに 1 が含まれます。例えば、r自身にはすべてのビットがゼロのラベルが付き、その隣接頂点には 1 ビットのラベルが付きます。すると、任意の 2 つのラベル間のハミング距離は、木内の 2 つの頂点間の距離になります。したがって、このラベル付けによって、 Tが部分立方体であることが示されます。

すべてのハイパーキューブグラフはそれ自体が部分的なキューブであり、ハイパーキューブの次元に等しい長さのすべての異なるビット列でラベル付けすることができる。

より複雑な例としては、以下のようなものがあります。

• 頂点ラベルが、 n ビットまたはn + 1ビットの非ゼロビットを持つすべての可能な(2 n + 1)桁のビット列で構成されるグラフを考えます。2 つの頂点は、ラベルが 1 ビットだけ異なる場合に隣接します。このラベル付けにより、これらのグラフをハイパーキューブ (同じ隣接条件を持つ、与えられた長さのすべてのビット列のグラフ) に埋め込むことができ、この埋め込みは距離を保存することがわかります。結果として得られるグラフは二部グラフの Kneser グラフです。このようにしてn = 2で形成されたグラフは、 20 個の頂点と 30 個のエッジを持ち、 Desargues グラフと呼ばれます。
• すべてのメディアングラフは部分立方体です。^{[ 3 ]}木とハイパーキューブグラフはメディアングラフの例です。メディアングラフには、正方形グラフ、単体グラフ、フィボナッチ立方体、および有限分配束の被覆グラフが含まれるため、これらはすべて部分立方体です。
• ユークリッド平面上の直線の配置の平面双対グラフは部分立方体である。より一般的には、任意の次元のユークリッド空間における任意の超平面配置に対して、配置の各セルに頂点を持ち、隣接する2つのセルに辺を持つグラフは部分立方体である。^{[ 4 ]}
• すべての頂点がちょうど 3 つの隣接点を持つ部分立方体は、立方部分立方体として知られています。立方部分立方体の無限族がいくつか知られており、その他にも散発的な例が多数ありますが、平面グラフではない既知の立方部分立方体は、デザルググラフのみです。^{[ 5 ]}
• 反マトロイドの基となるグラフは、反マトロイド内の各集合に対応する頂点と、1つの要素だけ異なる2つの集合に対応する辺を持ち、常に部分立方体となる。
• 任意の有限個の部分立方体のデカルト積は、別の部分立方体である。^{[ 6 ]}
• 完全グラフの分割が部分立方体であるのは、完全グラフのすべての辺が2辺のパスに分割されている場合、または、接続する辺がすべて分割されておらず、接続しない辺がすべて偶数長のパスに分割されている完全グラフの頂点が1つ存在する場合に限る。^{[ 7 ]}

部分立方体に関する定理の多くは、グラフのエッジ上で定義されたある二項関係に直接的または間接的に基づいている。この関係は、ジョコビッチ（1973）によって最初に記述され、ウィンクラー（1984）によって距離の観点から同等の定義が与えられ、次のように表される。 ${\displaystyle \Theta }$2つのエッジ${\displaystyle e=\{x,y\}}$そして${\displaystyle f=\{u,v\}}$関係にあると定義される ${\displaystyle \Theta }$書かれた${\displaystyle e{\mathrel {\Theta }}f}$、 もし ${\displaystyle d(x,u)+d(y,v)\not =d(x,v)+d(y,u)}$この関係は反射的かつ対称的ですが、一般に推移的ではありません。

ウィンクラーは、連結グラフが部分立方体であるのは、 それが二部グラフであり、かつ関係が成り立つ場合に限ることを示した。 ${\displaystyle \Theta }$推移的である。^{[ 8 ]}この場合、同値関係が形成され、各同値類はグラフの 2 つの連結部分グラフを互いに分離する。各ラベルの 1 ビットを Djoković–Winkler 関係の各同値類に割り当てることで、ハミング ラベリングが得られる。エッジの同値類によって分離された 2 つの連結部分グラフのうちの 1 つでは、すべての頂点のラベルのその位置に 0 があり、もう 1 つの連結部分グラフでは、すべての頂点の同じ位置に 1 がある。

部分立方体は認識でき、ハミングラベルが構築され、${\displaystyle O(n^{2})}$ 時間、${\displaystyle n}$ はグラフの頂点の数です。^{[ 9 ]}部分立方体が与えられた場合、各頂点から幅優先探索を行うことで、ジョコビッチ・ウィンクラー関係の同値類を簡単に構築できます。合計時間は${\displaystyle O(nm)}$; その${\displaystyle O(n^{2})}$-time 認識アルゴリズムは、ビットレベルの並列処理を使用してグラフを 1 回通過する際に複数の幅優先探索を実行することで処理を高速化し、その後、この計算結果が有効な部分立方体ラベル付けであることを検証する別のアルゴリズムを適用します。

部分立方体の等長次元は、それが等長的に埋め込まれることができる超立方体の最小次元であり、ジョコビッチ・ウィンクラー関係の同値類の数に等しい。例えば、${\displaystyle n}$-頂点木はエッジの数です。${\displaystyle n-1}$この次元の超立方体への部分立方体の埋め込みは、超立方体の対称性を除いて一意である。^{[ 10 ]}

すべてのハイパーキューブ、したがってすべての部分キューブは、整数格子に等長的に埋め込むことができます。グラフの格子次元は、グラフを等長的に埋め込むことができる整数格子の最小次元です。格子次元は等長次元よりもかなり小さい場合があります。たとえば、木の場合、格子次元は木の葉の数の半分（最も近い整数に切り上げ）です。任意のグラフの格子次元、および最小次元の格子埋め込みは、補助グラフでの最大マッチングに基づくアルゴリズムによって多項式時間で見つけることができます。 ^{[ 11 ]}

部分立方体の他の次元も、より特殊な構造への埋め込みに基づいて定義されている。^{[ 12 ]}

グラフのハイパーキューブへの等長埋め込みは、化学グラフ理論において重要な応用がある。ベンゼノイドグラフは、六角格子内のサイクル上および内部にあるすべての頂点と辺からなるグラフである。このようなグラフは、有機分子の大きなクラスであるベンゼノイド炭化水素の分子グラフである。このようなグラフはすべて部分立方体である。このようなグラフのハミングラベル付けを使用して、対応する分子のウィーナー指数を計算することができ、それによって特定の化学的性質を予測することができる。^{[ 13 ]}

炭素から形成される別の分子構造であるダイヤモンド立方体も部分的な立方体グラフを形成する。^{[ 14 ]}

• Beaudou, Laurent; Gravier, Sylvain; Meslem, Kahina (2008)、「ハイパーキューブにおける細分化された完全グラフの等長埋め込み」(PDF)、SIAM Journal on Discrete Mathematics、22 (3): 1226–1238、doi : 10.1137/070681909、MR 2424849、S2CID 6332951  
• カベロ、S.エップスタイン、Ｄ． Klavžar, S. (2011)、「グラフのフィボナッチ次元」、組み合わせ論電子ジャーナル、18 (1)、P55、arXiv : 0903.2507、Bibcode : 2009arXiv0903.2507C、doi : 10.37236/542、S2CID 9363180 。
• Djoković, Dragomir  Ž. (1973), "ハイパーキューブの距離保存部分グラフ", Journal of Combinatorial Theory , Series  B, 14 (3): 263–267 , doi : 10.1016/0095-8956(73)90010-5 , MR 0314669 。
• Eppstein、David (2005)、「グラフの格子次元」、European Journal of Combinatorics、26 (6): 585–592、arXiv : cs.DS/0402028、doi : 10.1016/j.ejc.2004.05.001、S2CID 7482443 。
• Eppstein, David (2006)、 「単体配置からの立方体部分立方体」、Electronic Journal of Combinatorics、13 (1) R79、arXiv : math.CO/0510263、doi : 10.37236 /1105、S2CID 8608953 。
• Eppstein, David (2008)、「部分立方体の認識を2次時間で行う」、第19回ACM-SIAM離散アルゴリズムシンポジウム論文集、pp. 1258–1266、arXiv : 0705.1025、Bibcode : 2007arXiv0705.1025E 。
• Eppstein, David (2009)、「等長ダイヤモンドサブグラフ」、第16回国際グラフ描画シンポジウム議事録、クレタ島ヘラクリオン、2008年、Lecture Notes in Computer Science、第 5417巻、Springer-Verlag、pp. 384–389、arXiv : 0807.2218、doi : 10.1007/978-3-642-00219-9_37、ISBN  978-3-642-00218-2S2CID 14066610​ 。
• Falmagne, J.-C. ; Doignon, J.-P. (1997)、「合理性の確率的進化」（PDF）、Theory and Decision、43（2）：107–138、doi：10.1023/A:1004981430688、hdl：2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/303273、S2CID 117983644 。
• Firsov, VV (1965)、「グラフのブールキューブへの等長埋め込みについて」、サイバネティクス、1 : 112–113、doi : 10.1007/bf01074705、S2CID 121572742 。Ovchinnikov (2011)によって引用されたとおり。
• Hadlock, F.; Hoffman, F. (1978)、「マンハッタン木」、Utilitas Mathematica、13 : 55–67。Ovchinnikov (2011)によって引用されたとおり。
• Imrich, Wilfried; Klavžar, Sandi (2000), Product Graphs: Structure and Recognition , Wiley-Interscience Series in Discrete Mathematics and Optimization, New York: John Wiley & Sons, ISBN 978-0-471-37039-0MR 1788124​ 。
• Klavžar, Sandi; Gutman, Ivan; Mohar, Bojan (1995)、「頂点距離関係を反映したベンゼノイド系のラベリング」(PDF)、Journal of Chemical Information and Computer Sciences、35 (3): 590–593、doi : 10.1021/ci00025a030。
• クズミン、V.、オフチンニコフ、S. ( 1975)、「選好空間の幾何学 I」、オートメーションとリモートコントロール、36 : 2059–2063。Ovchinnikov (2011)によって引用されたとおり。
• オフチンニコフ、セルゲイ（2011）、『グラフとキューブ』、Universitext、Springer特に第5章「部分立方体」（127～181ページ）を参照のこと。
• Winkler, Peter  M. (1984)、「完全グラフの積における等長埋め込み」、Discrete Applied Mathematics、7 (2): 221–225、doi : 10.1016/0166-218X(84)90069-6、MR 0727925 。