部分立方体

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

歴史

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

例

頂点にハミングラベルが付けられた部分立方体の例。このグラフは中央値グラフでもあります。

すべての木は部分立方体です。木Tにm個の辺があり、これらの辺に（任意に）0からm – 1 までの番号が付けられているとします。木の根頂点r を任意に選択し、各頂点vに、辺iがTのrからvへのパス上にある場合、位置iに 1 が含まれるmビットの文字列のラベルを付けます。例えば、r自体にはすべて 0 ビットのラベルが付けられ、その近傍には 1 ビットが 1 個含まれるラベルが付けられます。任意の 2 つのラベル間のハミング距離は、木内の 2 つの頂点間の距離となるため、このラベル付けによってTは部分立方体であることがわかります。

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

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

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

ジョコビッチとウィンクラーの関係

部分立方体に関する定理の多くは、グラフの辺に定義される特定の二項関係に直接的または間接的に基づいています。この関係は、 Djoković (1973)によって初めて記述され、 Winkler (1984)によって距離に関する同等の定義が与えられており、 と表記されます 。2つの辺と は、のとき、 と と 表記される関係 にあると定義されます 。この関係は反射的で対称的ですが、一般に推移的ではありません。 ${\displaystyle \Theta}$ ${\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)}$

ウィンクラーは、連結グラフが部分立方体であるための必要十分条件は、それが二部グラフであり、かつその関係 が推移的であることを示した。^{[ 8 ]}この場合、同値関係が形成され、各同値類はグラフの連結された二つの部分グラフを互いに分離する。ハミングラベル付けは、各ラベルの1ビットをジョコビッチ-ウィンクラー関係の同値類のそれぞれに割り当てることによって得られる。すなわち、辺の同値類によって分離された二つの連結部分グラフの一方において、全ての頂点のラベルのその位置には0が入り、他の連結部分グラフにおいて、全ての頂点の同じ位置には1が入る。 ${\displaystyle \Theta}$

認識

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

寸法

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

あらゆる超立方体、ひいてはあらゆる部分立方体は、整数格子に等長的に埋め込むことができる。グラフの格子次元とは、グラフを等長的に埋め込むことができる整数格子の最小次元である。格子次元は等長次元よりも大幅に小さくなることがある。例えば、木の場合、格子次元は木の葉の数の半分（最も近い整数に切り上げ）である。任意のグラフの格子次元と最小次元の格子埋め込みは、補助グラフにおける最大マッチングに基づくアルゴリズムによって多項式時間で求めることができる。 ^{[ 11 ]}

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

化学グラフ理論への応用

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

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

注記

1. オフチニコフ (2011)、定義 5.1、p. 127.
2. オフチニコフ (2011)、p. 174.
3. Ovchinnikov (2011)、セクション5.11、「中央値グラフ」、pp. 163–165。
4. Ovchinnikov (2011)、第7章「超平面配置」、pp.207–235。
5. エップスタイン（2006年）。
6. Ovchinnikov (2011)、第5.7節「部分立方体の直積」、144～145ページ。
7. ボードゥ、グラヴィエ、メスレム (2008)。
8. Winkler (1984)、定理4。Ovchinnikov (2011)、定義2.13、p.29、および定理5.19、p.136も参照。
9. エップスタイン（2008年）。
10. Ovchinnikov (2011)、第5.6節「等尺性次元」、pp. 142–144、および第5.10節「等尺性埋め込みの一意性」、pp. 157–162。
11. Hadlock & Hoffman (1978) ; Eppstein (2005) ; Ovchinnikov (2011)、第6章「Lattice Embeddings」、pp. 183–205。
12. エップスタイン (2009) ;カベロ、エップスタイン、クラヴザール (2011)。
13. Klavžar、Gutman & Mohar (1995)、命題 2.1 および 3.1。イムリッヒ & クラヴザール (2000)、p. 60; Ovchinnikov (2011)、セクション 5.12、「平均長とウィナー指数」、165 ～ 168 ページ。
14. エップスタイン（2009年）。

参考文献

• 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。
• ジョコビッチ、ドラゴミール・Ž. (1973)、「超立方体の距離保存部分グラフ」、Journal of Combinatorial Theory、シリーズ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。
• エップスタイン、デイヴィッド（2006）、 「単純配置からの立方体部分立方体」、Electronic Journal of Combinatorics、13（1）R79、arXiv ： math.CO/0510263、doi ： 10.37236 /1105、S2CID  8608953。
• Eppstein, David (2008)、「二次時間での部分立方体の認識」、Proc. 19th ACM-SIAM Symposium on Discrete Algorithms、pp.  1258– 1266、arXiv : 0705.1025、Bibcode : 2007arXiv0705.1025E。
• Eppstein, David (2009)、「等尺性ダイヤモンドサブグラフ」、Proc. 16th International Symposium on Graph Drawing、Heraklion、クレタ島、2008年、Lecture Notes in Computer Science、vol. 5417、Springer-Verlag、pp.  384– 389、arXiv : 0807.2218、doi : 10.1007/978-3-642-00219-9_37、ISBN 978-3-642-00218-2、S2CID  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)、「グラフのブールキューブへの等尺埋め込みについて」、Cyber​​netics、1 : 112– 113、doi : 10.1007/bf01074705、S2CID  121572742。Ovchinnikov (2011)によって引用されたとおり。
• ハドロック、F.; ホフマン、F. (1978)、「マンハッタンの樹木」、ユーティリタス・マセマティカ、13 : 55–67。Ovchinnikov (2011)によって引用されたとおり。
• イムリッチ、ウィルフリード、クラヴジャー、サンディ（2000）、プロダクトグラフ：構造と認識、ワイリー・インターサイエンス・シリーズ・イン・ディスクリート・マスキュリティー・アンド・オプティマイゼーション、ニューヨーク：ジョン・ワイリー・アンド・サンズ、ISBN 978-0-471-37039-0、MR  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)によって引用されたとおり。
• Ovchinnikov, Sergei (2011), Graphs and Cubes , Universitext, Springer特に第5章「部分立方体」の127～181ページを参照してください。
• ウィンクラー、ピーター・M.（1984）「完全グラフの積における等長埋め込み」、離散応用数学、7（2）：221-225、doi：10.1016/0166-218X（84）90069-6、MR  0727925。