グラフを反転

数学において、フリップ グラフとは、頂点が組み合わせオブジェクトまたは幾何学的オブジェクトであり、フリップと呼ばれる基本操作によって相互に取得できる場合に、エッジがこれらのオブジェクトのうち 2 つをリンクするグラフです。フリップ グラフは、幾何学的グラフの特殊なケースです。

注目すべき反転グラフの中には、連想面体^[1]や円面体^[2]などの多面体の1次元スケルトンがあります。

典型的なフリップグラフは、凸-角形 のグラフです。このグラフの頂点はの三角形分割であり、2 つの三角形分割は、 1 つの内部辺が異なる場合は常にグラフ内で隣接しています。この場合、フリップ操作は凸四辺形の対角線を交換することです。これらの対角線は、フリップグラフで隣接する 2 つの三角形分割が異なる内部辺です。結果として得られるフリップグラフは、タマリ格子のハッセ図^[3]と- 次元アソシアヘドロンの1 スケルトンの両方です。^[1]${\displaystyle n}$${\displaystyle \pi}$${\displaystyle \pi}$${\displaystyle (n-3)}$

この基本的な構造は、いくつかの方法で一般化できます。

を有限の点集合の三角形分割とします。ある条件下では、反転によっての別の三角形分割に変換できます。この操作は、 が回路( の最小アフィン従属部分集合) を三角形分割する方法を変更することです。より正確には、回路の三角形分割が の部分集合であり、 のすべてのセル (最大次元の面) が内で同じリンクを持つ場合、を で置き換えることによって内で反転を実行できます。ここで ${\displaystyle T}$${\displaystyle {\mathcal {A}}\subset \mathbb {R} ^{d}}$${\displaystyle T}$${\displaystyle {\mathcal {A}}}$${\displaystyle T}$${\displaystyle {\mathcal {A}}}$${\displaystyle \tau^{-}}$${\displaystyle z\subset {\mathcal {A}}}$${\displaystyle T}$${\displaystyle \tau^{-}}$ ${\displaystyle \lambda}$${\displaystyle T}$${\displaystyle T}$${\displaystyle \lambda {\mathord {\star }}\tau ^{-}}$${\displaystyle \lambda {\mathord {\star }}\tau ^{+}}$

${\displaystyle X{\mathord {\star }}{Y}=\{x\cup {y}:(x,y)\in {X{\mathord {\times }}{Y}}\},}$

また、ラドンの分割定理により、 は の唯一の他の三角形分割です。 反転が可能な前述の条件により、この操作により の三角形分割が確実に得られます。^[4]対応する反転グラフは、頂点が の三角形分割であり、辺がそれらの間の反転に対応するものであり、 が凸多角形の頂点の集合であるときに 2 つの反転グラフが一致するため、凸多角形の反転グラフの自然な一般化です。 ${\displaystyle \tau^{+}}$${\displaystyle z}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle n}$

別の種類のフリップグラフは、位相面の三角形分割を考えることによって得られます。^[5]そのような面 を考え、その上に有限個の点を配置​​し、2 つの弧が決して交差しないように弧でそれらを接続します。この弧の集合が最大である場合、それは三角形に分解されます。さらに、複数の弧(同じ頂点のペアを持つ個別の弧) やループがない場合、この弧の集合はの三角形分割を定義します。 ${\displaystyle {\mathcal {S}}}$${\displaystyle n}$${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {S}}}$

この設定では、連続変換によって互いに取得できる 2 つの三角形分割は同一です。 ${\displaystyle {\mathcal {S}}}$

2 つの三角形分割は、それらを構成する弧のちょうど 1 つだけが異なる場合に、フリップによって関連付けられます。これらの 2 つの三角形分割は、必ず頂点の数が同じであることに注意してください。ユークリッドの場合と同様に、のフリップ グラフは、頂点がの三角形分割であり、その辺が頂点間のフリップに対応するグラフです。この定義は、境界のある位相面に直接拡張できます。 ${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle n}$

表面のフリップ グラフは-gon のフリップ グラフを一般化します。これは、表面が境界上に点が配置された位相ディスクである場合に、2 つが一致するためです。 ${\displaystyle n}$${\displaystyle n}$

三角形分割の別の定義を使用して、他の多くのフリップグラフを定義できます。たとえば、頂点が - 角形の中心対称三角形分割であり、辺が 2 つの中心対称フリップを実行する操作に対応するフリップグラフは、次元円盤の1 スケルトンです。^[2]また、この表面の三角形分割で複数の弧とループを許可することによって定義される、位相表面の別のフリップグラフを検討することもできます。 ${\displaystyle (2d+2)}$${\displaystyle d}$

フリップ グラフは、三角形分割以外の組み合わせオブジェクトを使用して定義することもできます。このような組み合わせオブジェクトの例としては、平面内の特定の領域のドミノ タイルが挙げられます。この場合、2 つの隣接するドミノが正方形を覆うときにフリップを実行できます。つまり、これらのドミノを正方形の中心を中心として 90 度回転させ、同じ領域の異なるドミノ タイルを作成します。

アソシアヘドラとサイクロヘドラ以外にも、1-スケルトンがフリップグラフであるという性質を持つ多面体がいくつかあります。たとえば、が内の点の有限集合である場合、の正規三角形分割は、次元多面体のいくつかの面をに投影することで得られるものです。 のフリップグラフでこれらの三角形分割によって誘導される部分グラフは、多面体の1-スケルトン、つまり の二次多面体です。^[6]${\displaystyle {\mathcal {A}}}$${\displaystyle \mathbb {R} ^{d}}$${\displaystyle {\mathcal {A}}}$${\displaystyle (d+1)}$${\displaystyle \mathbb {R} ^{d}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {A}}}$

この性質により、多面体フリップグラフは連結している。 1930年代にクラウス・ワグナーが示したように、位相球面のフリップグラフは連結している。 ^[7]連結フリップグラフの中には、任意の有限2次元点集合のフリップグラフも存在する。^[8]高次元ユークリッド空間では、状況ははるかに複雑である。が少なくとも5のときはいつでも、連結されていないフリップグラフを持つの有限点集合が見つかっている。^{[4] [9] [10]}${\displaystyle \mathbb {R} ^{d}}$${\displaystyle d}$

4次元超立方体の頂点集合のフリップグラフは連結していることが知られている。^[11]しかし、有限の3次元および4次元の点集合のフリップグラフが常に連結であるかどうかはまだわかっていない。^[4]

三角形分割を別の三角形分割に変換するために必要な反転の最大回数は、反転グラフの直径です。凸角形の反転グラフの直径は、が十分に大きい場合、ダニエル・スレイター、ロバート・タージャン、ウィリアム・サーストンによって得られました^[12 ]。また、すべての の場合、ライオネル・ポーニンによって得られました。この直径はの場合に に等しくなります。^[13]${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle 2n-10}$${\displaystyle n\geq 13}$

他のフリップグラフの直径も研究されている。例えば、クラウス・ワグナーは球面上のマークされていない点の集合のフリップグラフの直径の2次上限を示した。 ^[7]直径の現在の上限は、^[14]であり、最もよく知られている下限は である。^[15]境界を持つ任意の位相面のフリップグラフの直径も研究されており、いくつかのケースで正確にわかっている。^{[16] [17] [18]}${\displaystyle n}$${\displaystyle 5.2n-33.6}$${\displaystyle 7n/3+\シータ (1)}$

• 反転距離
• 回転距離