組み合わせマップ

組合せマップは、有向面上のグラフの組合せ表現です。組合せマップは、組合せ埋め込み、回転システム、有向リボングラフ、ファットグラフ、巡回グラフとも呼ばれます。^[1]より一般的には、次元組合せマップは、次元有向多様体上のグラフの組合せ表現です。 $n$ $n$

組み合わせマップは、画像の表現と処理、幾何学的モデリングにおける効率的なデータ構造として使用されます。このモデルは、単体複合体と組み合わせトポロジーに関連しています。組み合わせマップは境界表現モデルであり、オブジェクトをその境界によって表現します。

歴史

組合せマップの概念は、平面グラフである多面体表面^[2]に対してJ. Edmondsによって非公式に導入されました。これは A. Jacques ^[3]^[4]によって「星座」という名前で初めて明確に公式に表現されましたが、この概念は、 Heawood のマップ彩色問題の有名な解決法において、 Gerhard Ringel ^[5]と JWT Youngs によって「回転」という名前ですでに広く使用されていました。「星座」という用語は保持されず、代わりに「組合せマップ」が好まれました。^[6]

組み合わせマップは後に、より高次元の方向付け可能な細分化されたオブジェクトを表すために一般化されました。

モチベーション

いくつかのアプリケーションでは、オブジェクトの細分化を表すデータ構造が必要です。たとえば、2D オブジェクトは、頂点 (0 セル)、エッジ (1 セル)、面 (2 セル) に分解できます。より一般的には、n 次元オブジェクトは 0 から n 次元のセルで構成されます。さらに、これらのセル間の隣接関係を表すことも必要になることがよくあります。

したがって、細分内のすべてのセルと、これらのセル間のすべての接続関係および隣接関係を記述する必要があります。表現されるすべてのセルが単体である場合は単体複合体を使用できますが、任意のタイプのセルを表現する場合は、組み合わせマップや一般化マップなどのセル位相モデルを使用する必要があります。

意味

組合せ写像とは、次の三つ組 $M = (D, σ, α)である。$

$D は$ ダーツの有限集合です。
$σ は$ $D$ 上の順列である。
$α は$ 不動点を持たない $D$ 上の反転です

直感的には、組み合わせマップは、各エッジが 2 つのダーツ (ハーフエッジとも呼ばれる) に分割されたグラフに対応します。順列 $σ$ は、各ダーツに対して、頂点を正の方向に回転させることによって次のダーツを与えます。もう 1 つの順列 $α は$ 、各ダーツに対して、同じエッジの別のダーツを与えます。

$α$ は辺を取得でき (フランス語でa rête のa lpha)、 $σ は$ 頂点を取得できます (フランス語でs ommet のs igma $)。 φ$ $=$ $σ$ $\circ$ $α$ と定義すると、各ダーツに対して、同じ面の次のダーツが示されます (フランス語でf ace のp hi)。

$したがって、順列がσ$ か $φ$ かに応じて、組み合わせマップを表現する方法が 2 つあります(以下の例を参照)。これらの 2 つの表現は互いに双対であり、頂点と面が交換されます。

高次元一般化

n次元組合せマップ（またはnマップ）は、（n + 1）組 $M$ $=（$ $D$ $、$ $β1$ $、$ $...、$ $βn$ $）であり、次の式が$ $成り立つ$ ：^[7][ ^8]

$D は$ ダーツの有限集合です。
$β 1 は$ $D$ 上の順列である。
$β 2, ..., β n は$ $D$ の積分です。
$i + 2 \leq j (i, j \in { 1, ,..., n})ならば、$ $β$ $i$ $\circ$ $β$ $j は$ 反転である。

n次元の組合せマップ $は、閉じた向き付け可能な$ n次元空間の分割を表します。β i ∘ β j の制約は、 $マップの準多様$ 体分割としての位相的な妥当性を保証します。2 次元の組合せマップは、 $n = 2$ を固定し、 $σ を$ $β 1$ に、 $α を$ $β 2$ に名前変更することで取得できます。

必ずしも閉じているわけではない、または向きが付けられない空間は、( n次元の)一般化マップを使用して表現できます。

参照

参考文献

^ Bollobás, Béla; Riordan, Oliver (2001). 「有向面上のグラフの多項式不変量」.ロンドン数学会紀要. 83 (3). Wiley: 513–531. doi :10.1112/plms/83.3.513. ISSN 0024-6115. S2CID 15895860.
^ Edmonds , J. (1960). 「多面体表面の組み合わせ表現」. Notices Amer. Math. Soc . 7. hdl :1903/24820.
^ ジャック、A. (1969)。星座とトポロジグラフの専門家 (PhD)。パリ大学。
^ ジャック、A. (1970)。「星座とグラフのトポロジー」。コロク数学。社会ヤノス・ボリャイ: 657–672。
^ リンゲル、G. (2012) [1974]。マップカラー定理。スプリンガー。ISBN 978-3-642-65759-7。
^ コリ、R. (1975)。「グラフや平面図などのアプリケーションをコードで作成します。」アステリスク。２７．MR 0404045。Zbl 0313.05115 。
^ Lienhardt, P. (1991). 「境界表現のための位相モデル：n次元一般化マップとの比較」.コンピュータ支援設計. 23 (1): 59–82. doi :10.1016/0010-4485(91)90082-8.
^ Lienhardt, P. (1994). 「N次元一般化組み合わせマップとセルラー準多様体」.国際計算幾何学および応用ジャーナル. 4 (3): 275–324. doi :10.1142/S0218195994000173.

外部リンク

計算幾何学アルゴリズムライブラリ CGALの組み合わせマップ:
- Damiand, Guillaume. 「組み合わせマップ」 . 2021年2月6日閲覧。

CGoGNにおける組み合わせマップ、汎用N次元マップによる組み合わせおよび幾何モデリング
n ラボの組み合わせマップ

[br01-1] Bollobás, Béla; Riordan, Oliver (2001). 「有向面上のグラフの多項式不変量」.ロンドン数学会紀要. 83 (3). Wiley: 513–531. doi :10.1112/plms/83.3.513. ISSN 0024-6115. S2CID 15895860.

[2] ^ Edmonds , J. (1960). 「多面体表面の組み合わせ表現」. Notices Amer. Math. Soc . 7. hdl :1903/24820.

[3] ジャック、A. (1969)。星座とトポロジグラフの専門家 (PhD)。パリ大学。

[4] ジャック、A. (1970)。「星座とグラフのトポロジー」。コロク数学。社会ヤノス・ボリャイ: 657–672。

[5] リンゲル、G. (2012) [1974]。マップカラー定理。スプリンガー。ISBN 978-3-642-65759-7。

[6] コリ、R. (1975)。「グラフや平面図などのアプリケーションをコードで作成します。」アステリスク。２７．MR 0404045。Zbl 0313.05115 。

[7] Lienhardt, P. (1991). 「境界表現のための位相モデル：n次元一般化マップとの比較」.コンピュータ支援設計. 23 (1): 59–82. doi :10.1016/0010-4485(91)90082-8.

[8] Lienhardt, P. (1994). 「N次元一般化組み合わせマップとセルラー準多様体」.国際計算幾何学および応用ジャーナル. 4 (3): 275–324. doi :10.1142/S0218195994000173.