Loading article…
数学の一分野である位相グラフ理論において、無向グラフのリンクレス埋め込みとは、グラフのどの 2 つのサイクルもリンクしないような方法で、グラフを 3 次元ユークリッド空間に埋め込むことである。フラット埋め込みとは、すべてのサイクルが、内部がグラフと分離している位相ディスクの境界であるという性質を持つ埋め込みである。リンクレス埋め込み可能グラフとは、リンクレス埋め込みまたはフラット埋め込みを持つグラフであり、これらのグラフは平面グラフの 3 次元版を形成する。[ 1 ]対照的に、本質的にリンクされたグラフとは、リンクレス埋め込みを持たないグラフである。
フラット埋め込みは自動的にリンクレスになりますが、その逆は成り立ちません。[ 2 ]完全グラフK6、ピーターセン グラフ、およびピーターセン ファミリーの他の 5 つのグラフには、リンクレス埋め込みがありません。[ 1 ]リンクレス埋め込み可能なグラフのすべてのグラフ マイナーは、再びリンクレス埋め込み可能になります。 [ 3 ]また、リンクレス埋め込み可能なグラフからYΔ 変換および ΔY 変換によって到達できるすべてのグラフも同様です。[ 2 ]リンクレス埋め込み可能なグラフは、ピーターセン ファミリーグラフを禁止マイナーとして持ち、[ 4 ]平面グラフと頂点グラフを含みます。[ 2 ]これらは認識でき、 O ( n2 )でフラット埋め込みを構築できます。[ 5 ]
円を単射関数（円の異なる 2 つの点を空間の同じ点に写像しない連続関数）によって3 次元ユークリッド空間に写像すると、その像は閉曲線になります。 同じ平面上にある 2 つの互いに素な閉曲線はリンクされていないと言われ、より一般的には、互いに素な閉曲線のペアは、空間の連続的な変形によって両方の曲線が同じ平面上に移動され、どちらの曲線も他方の曲線や自身を通過することがない場合に、リンクされていないと言われます。そのような連続的な動きがない場合、2 つの曲線はリンクしていると言われます。たとえば、ホップリンクは、それぞれが他方の円盤を通過する 2 つの円によって形成されます。これはリンクされた曲線のペアの最も単純な例ですが、曲線は他のより複雑な方法でリンクされる可能性があります。 2 つの曲線がリンクされていない場合、最初の曲線を境界とし、2 番目の曲線とは互いに素な位相円盤を空間内に見つけることが可能です。逆に、そのような円盤が存在する場合、曲線は必然的に互いに関連しない。
3 次元空間における 2 つの閉曲線の連結数は、曲線の位相不変量です。これは、曲線からいくつかの同等な方法で定義される数であり、曲線が互いに交差することなく連続的に移動しても変化しません。グラフのリンクなし埋め込みを定義するために使用される連結数のバージョンは、埋め込みを平面に投影し、投影された埋め込みで最初の曲線が 2 番目の曲線を越える回数を2で割った余りを数えることによって求められます。 [ 2 ]投影は「正則」でなければなりません。つまり、どの 2 つの頂点も同じ点に投影されず、どの頂点も辺の内部に投影されず、2 つの辺の投影が交差する投影のすべての点で、それらは横断的に交差します。この制約により、任意の 2 つの投影は同じ連結数になります。リンクされていないものの連結数はゼロであるため、曲線のペアの連結数がゼロでない場合、2 つの曲線はリンクされている必要があります。しかし、ホワイトヘッドリンクのように、リンク数はゼロであるがリンクしている曲線の例もある。
グラフを3次元空間に埋め込むとは、グラフの頂点から空間内の点へ、そしてグラフの辺から空間内の曲線へと写像することを意味します。各辺の端点は対応する曲線の端点に写像され、異なる2つの辺の曲線は、辺の共通の端点以外では交差しません。任意の有限グラフは有限個（ただし指数関数的である場合もある）の異なる単純サイクルを持ち、グラフが3次元空間に埋め込まれると、これらのサイクルはそれぞれ単純閉曲線を形成します。このようにして形成された互いに素な曲線のペアごとに連結数を計算することができます。すべてのサイクルのペアの連結数がゼロである場合、その埋め込みは連結がないと言われます。[ 6 ]
場合によっては、グラフを空間に埋め込むことで、グラフ内の各サイクルに対して、そのサイクルによって囲まれ、グラフの他の特徴と交差しないディスクを見つけることができます。この場合、そのサイクルは、グラフ内でそれと互いに素な他のすべてのサイクルからリンクされていない必要があります。すべてのサイクルがこのようにディスクを囲む場合、埋め込みはフラットであると言われます。[ 7 ]フラットな埋め込みは必然的にリンクレスですが、フラットではないリンクレスの埋め込みが存在する場合があります。たとえば、G が互いに素な 2 つのサイクルによって形成されるグラフであり、ホワイトヘッド リンクを形成するように埋め込まれている場合、埋め込みはリンクレスですがフラットではありません。
グラフは、埋め込み方に関係なく、埋め込みが常にリンクされている場合、本質的にリンクされていると言われます。リンクのない埋め込みとフラットな埋め込みは同じではありませんが、リンクのない埋め込みを持つグラフは、フラットな埋め込みを持つグラフと同じです。[ 8 ]
Sachs (1983)が示したように、Petersen ファミリーの 7 つのグラフはそれぞれ本質的にリンクされています。これらのグラフが空間にどのように埋め込まれていても、互いにリンクされた 2 つのサイクルがあります。これらのグラフには、完全グラフK 6、Petersen グラフ、完全二部グラフK 4,4からエッジを削除して形成されるグラフ、および完全三部グラフK 3,3,1 が含まれます。
すべての平面グラフには、平坦でリンクのない埋め込みが存在します。グラフを平面に埋め込み、その平面を空間に埋め込むだけです。グラフが平面である場合、これがグラフを平坦かつリンクなしで空間に埋め込む唯一の方法です。すべての平坦な埋め込みは、連続的に変形して平面上に配置できます。逆に、すべての非平面リンクレスグラフには、複数のリンクレス埋め込みが存在します。[ 2 ]
平面グラフに単一の頂点を追加して形成される頂点グラフも、平坦でリンクのない埋め込みを持ちます。グラフの平面部分を平面に埋め込み、頂点を平面の上に配置し、頂点から隣接する頂点へのエッジを線分として描画します。平面内の任意の閉曲線は、他のグラフの特徴を通過しない平面の下の円盤を囲み、頂点を通る任意の閉曲線は、他のグラフの特徴を通過しない平面上の円盤を囲みます。[ 2 ]
グラフがリンクレスまたはフラットな埋め込みを持つ場合、エッジを細分化または非細分化したり、同じ点のペア間に複数のエッジを追加または削除したり、次数 3 の頂点をその 3 つの隣接点を結ぶ三角形に置き換えるYΔ 変換および ΔY 変換を実行したり、その逆を行ったりすることでグラフを変更しても、フラット性とリンクレス性は維持されます。 [ 2 ]特に、立方体平面グラフ (すべての頂点がちょうど 3 つの隣接点を持つグラフ、例えば立方体)では、YΔ 変換を実行し、結果として得られる三角形のエッジの複数のコピーを追加し、次に逆の ΔY 変換を実行することで、任意の独立した頂点セットの複製を作成することが可能です。
グラフG がリンクレスまたはフラットな埋め込みを持つ場合、Gのすべてのマイナー(辺の縮約と辺および頂点の削除によって形成されるグラフ) もリンクレスまたはフラットな埋め込みを持ちます。削除によって埋め込みのフラット性を破壊することはできず、縮約は縮約された辺の一方の端点をそのままにして、もう一方の端点に接続するすべての辺を縮約された辺の経路に沿って再ルーティングすることによって実行できます。したがって、ロバートソン-シーモアの定理により、リンクレス埋め込み可能なグラフは、有限個のマイナーを一切含まないグラフとして禁止されたグラフ特性を持ちます。 [ 3 ]
リンクレス埋め込み可能グラフの禁止マイナーの集合は、 Sachs (1983)によって特定されました。Petersenファミリーの 7 つのグラフはすべて、マイナー最小の本質的にリンクされたグラフです。しかし、Sachs はこれらが唯一の最小リンクされたグラフであることを証明できず、これは最終的にRobertson、Seymour 、 Thomas (1995)によって達成されました。
リンクレスグラフの禁止マイナー特性は、その認識のための多項式時間アルゴリズムにつながるが、実際に埋め込みを構築するためのアルゴリズムにはつながらない。Kawarabayashi、Kreutzer 、 Mohar (2010)は、グラフがリンクレス埋め込み可能かどうかをテストし、可能であればグラフのフラット埋め込みを構築する線形時間アルゴリズムを記述した。彼らのアルゴリズムは、リンクレス埋め込みが存在する場合、その埋め込みが部分グラフの平面埋め込みを尊重するような、与えられたグラフ内の大きな平面部分グラフを見つける。そのような部分グラフが見つかるたびにグラフを繰り返し単純化することで、残りのグラフの木幅が制限される問題に問題を縮小し、その時点で動的計画法で解くことができる。
与えられた埋め込みが平坦であるかリンクレスであるかを効率的にテストする問題は、Robertson、Seymour 、 Thomas (1993a)によって提起されました。これは未解決のままであり、空間内の単一の曲線が結び目がないかどうかをテストする問題である結び目解除問題と複雑さが同等です。 [ 5 ]結び目がないことをテストすること (したがって、埋め込みのリンクレス性もテストすること) はNPに属することが知られていますが、 NP 完全であることが知られていません。[ 9 ]
コリン・ド・ヴェルディエール・グラフ不変量は、代数的グラフ理論を用いて任意のグラフに対して定義される整数です。任意の固定定数μに対して、コリン・ド・ヴェルディエール・グラフ不変量がμ以下のグラフは、マイナー閉族を形成し、そのうち最初の数個はよく知られています。μ ≤ 1のグラフは線形フォレスト（パスの非交和）、μ ≤ 2のグラフは外平面グラフ、μ ≤ 3のグラフは平面グラフです。Robertson 、Seymour 、 Thomas（1993a）が予想し、Lovász 、 Schrijver（1998）が証明したように、μ ≤ 4のグラフはまさにリンクレス埋め込み可能グラフです。
平面グラフと頂点グラフは、これらのグラフからYΔ 変換と ΔY 変換によって得られるグラフと同様に、リンクレス埋め込み可能である。 [ 2 ] YΔY還元可能グラフは、YΔ 変換と ΔY 変換、孤立頂点と次数 1 の頂点の除去、次数 2 の頂点の圧縮によって単一の頂点に還元できるグラフであり、マイナー閉じており、すべての平面グラフを含む。ただし、菱形十二面体のすべての次数 3 の頂点に頂点を接続することによって形成される頂点グラフなど、YΔY 還元可能ではないリンクレスグラフも存在する。[ 10 ] YΔ変換やΔY変換、孤立頂点や次数1の頂点の除去、次数2の頂点の圧縮によって頂点グラフに変換できないリンクレスグラフも存在する。例えば、10頂点のクラウングラフはリンクレス埋め込みを持つが、この方法では頂点グラフに変換できない。[ 2 ]
リンクレス埋め込みの概念に関連して、ノットレス埋め込みの概念があります。これは、グラフの単純サイクルが非自明な結び目を形成しないようにグラフを埋め込むものです。ノットレス埋め込みを持たないグラフ（つまり、本質的に結び目を持つグラフ）には、K 7とK 3,3,1,1が含まれます。[ 11 ]ただし、本質的にリンクされたグラフに 1 つの頂点を追加することによって形成されるものではない (これらの 2 つのグラフのように) ノットレス埋め込みの最小禁止マイナーも存在しますが、それらのリストは不明です。[ 12 ]
グラフ族は、埋め込みに複雑な結び目やリンクが存在するか存在しないかによって定義することもでき、[ 13 ]あるいはユークリッド空間以外の3次元多様体へのリンクなし埋め込みによって定義することもできます。 [ 14 ] Flapan、Naimi 、 Pommersheim（2001）は、3つのサイクルがあり、そのうちの1つが他の2つから分離できない場合、グラフ埋め込みを三重リンクであると定義しています。彼らは、K 9は本質的に三重リンクではないが、K 10は三重リンクであることを示しています。[ 15 ]より一般的には、任意のnに対してnリンク埋め込みを、位相球によって2つの分離された部分に分離できないn成分リンクを含む埋め込みとして定義できます。本質的にnリンクであるマイナー最小グラフは、すべてのnについて知られています。[ 16 ]
有向グラフは、すべての空間埋め込みにおいて、一貫して方向付けられた一対の有向サイクルからなる非自明なリンクを含む場合、本質的にリンクされていると言われます。無向グラフとは対照的に、エッジの縮約と∆−Y操作は、必ずしもリンクのない埋め込み可能性を保持するとは限りません。[ 17 ]
K 6がリンクレス埋め込みまたはフラット埋め込みを持つかどうかという問題は、1970 年代初頭にBothe (1973)によってトポロジー研究コミュニティ内で提起されました。リンクレス埋め込みはHorst Sachs ( 1983 )によってグラフ理論コミュニティの注目を集め、リンクレス埋め込みとフラット埋め込みを持つグラフの禁止グラフ特性を見つける問題など、いくつかの関連する問題を提起しました。Sachs は、 Petersen ファミリーの 7 つのグラフ ( K 6を含む) にはそのような埋め込みがないことを示しました。NešetřilとThomas (1985)が指摘したように、リンクレス埋め込み可能なグラフはグラフマイナーの下で閉じられており、 Robertson–Seymour の定理から禁止グラフ特性が存在することがわかります。有限個の障害グラフの存在証明は、この禁止マイナーの集合の明示的な記述にはつながりませんが、Sachs の結果から、Petersen ファミリーの 7 つのグラフがこの集合に属することがわかります。これらの問題は、Robertson、Seymour 、 Thomas (1995) [ 18 ]によって最終的に解決され、Petersen ファミリーの 7 つのグラフがこれらのグラフの唯一の最小禁止マイナーであることが示されました。したがって、リンクレス埋め込み可能グラフとフラット埋め込み可能グラフはどちらも同じグラフの集合であり、どちらも Petersen ファミリーマイナーを持たないグラフと同じです。
Sachs (1983)は、リンクレス埋め込み可能グラフのエッジ数と彩色数の上限も求めました。n頂点リンクレスグラフのエッジ数は最大で 4n − 10 です。n > 4の最大頂点グラフはまさにこの数のエッジを持ちます [ 1 ]。Mader (1968) は、より一般的なK 6マイナーフリーグラフのクラスに対して、一致する上限を証明しました。NešetřilとThomas (1985)は、彩色数に関する Sachs の疑問は、任意のk彩色グラフがk頂点完全グラフをマイナーとして持つというHadwiger の予想の証明によって解決されるだろうと指摘しました。ロバートソン、シーモア、トーマス (1993c)によるハドウィガー予想のk = 6 の場合の証明は、ザックスの疑問を解決するのに十分である。すなわち、リンクレス グラフは最大で 5 色で彩色できる。なぜなら、任意の 6 彩色グラフはK 6マイナーを含み、リンクレスではないからであり、5 色を必要とするK 5のようなリンクレス グラフが存在するからである。スナーク定理は、すべての3次リンクレス埋め込み可能グラフが3 エッジ彩色可能であることを示唆している。
リンクレス埋め込みは、1980年代後半にFellows & Langston (1988)とMotwani、Raghunathan & Saran (1988)の研究を通じてアルゴリズム研究コミュニティ内で研究され始めました。アルゴリズム的には、禁止マイナーの特徴が証明されると、リンクレスでフラットな埋め込み可能なグラフを認識する問題は解決されました。Robertson & Seymour (1995)のアルゴリズムを使用すると、与えられたグラフが7つの禁止マイナーのいずれかを含むかどうかを多項式時間でテストできます。 [ 19 ]この方法は、リンクレスまたはフラットな埋め込みが存在する場合でもそれらを構築しませんが、埋め込みを構築するアルゴリズムがvan der Holst (2009)によって開発され、より効率的な線形時間アルゴリズムがKawarabayashi、Kreutzer & Mohar (2010)によって発見されました。
Sachs (1983)が提起した、リンクのないグラフに対するFáry の定理の類似の可能性に関する最後の疑問は、未解決のままであるように思われる。すなわち、曲線または区分的に線形なエッジを持つリンクのないまたは平坦な埋め込みの存在は、エッジが直線セグメントであるリンクのないまたは平坦な埋め込みの存在をいつ意味するのか、という疑問である。