組み合わせマップ

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

組合せ写像は、画像表現・処理、そして幾何学モデリングにおいて効率的なデータ構造として用いられます。このモデルは単体複体および組合せ位相幾何学と関連しています。組合せ写像は境界表現モデルであり、物体をその境界によって表現します。

歴史

組合せ写像の概念は、平面グラフである多面体曲面^{[ 2 ]}に対して、J. エドモンズによって非公式に導入されました。この概念は、A. ジャック^{[ 3 ] [ 4 ]}によって「星座」という名前で初めて明確に公式表現されましたが、この概念は既に「回転」という名前で、ゲルハルト・リンゲル^{[ 5 ]}と JWT ヤングスによって、ヒーウッドの写像彩色問題の有名な解法において広く用いられていました。「星座」という用語はそのまま残されず、「組合せ写像」という用語が好まれました^{[ 6 ] 。}

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

モチベーション

多くのアプリケーションでは、オブジェクトの細分化を表現するためのデータ構造が必要です。例えば、2次元オブジェクトは頂点（0次元セル）、辺（1次元セル）、面（2次元セル）に分解できます。より一般的には、n次元オブジェクトは0次元からn次元までのセルで構成されます。さらに、これらのセル間の隣接関係を表現する必要が生じることも少なくありません。

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

意味

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

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

直感的に言えば、組合せ写像は、各辺が2本のダーツ（ハーフエッジとも呼ばれる）に分割されたグラフに対応します。σ の順列は、各ダーツに対して、頂点を正の方向に回転させて次のダーツを与えます。αの順列は、各ダーツに対して、同じ辺のもう一方のダーツを与えます。

α は辺（フランス語でa rête の代わりにa lpha）を、 σ は頂点（フランス語でs ommet の代わりにs igma ）をそれぞれ取得することを可能にします。φ = σ ∘ α と 定義すると、これは各ダーツに対して、同じ面の次のダーツ（フランス語でf ace の代わりにp hi）を与えます。

したがって、順列がσかφかによって、組み合わせ写像を表現する方法は2つあります（下の例を参照）。これらの2つの表現は互いに双対であり、頂点と面が交換されます。

組み合わせマップの例: 平面グラフと、表記法( D ,  σ ,  α )または( D ,  φ ,  α )を使用するかどうかに応じた 2 つの組み合わせマップ。

平面グラフ

対応する組み合わせマップ（D、  σ ​​、  α）。ダーツは番号付きの線分で表され、σは灰色の矢印で表されます（例：σ（1）= 7）。αでつながれた2本のダーツは連続して描かれ、小さなバーで区切られます（例：α（1）= 2）。

対応する組み合わせマップ（D、  φ、  α）。ダーツは番号付きの矢印で表され、φでつながれた2本のダーツは連続して描かれ（例：φ（1）＝3 ）、 αでつながれた2本のダーツは平行かつ逆向きに描かれる（例：α（1）＝2）。

高次元一般化

n次元の組み合わせ写像（またはn写像）は、( _n +  1)組M  = ( D ,  β1 ,...,  βn ₎であって、次の式を満たすものである。^{[ 7 ] [ 8 ]}

• Dはダーツの有限集合です。
• β _1はD上の順列である。
• β ₂ , ...,  β _nはDの積分です。
• i  + 2 ≤  j ( i ,  j ∈ { 1, ,...,  n  })の場合、 β _i  ∘  β _jは反転です。

n次元の組合せ写像は、向き付け可能なn次元閉空間の分割を表す。β i _∘ β _j の 制約は、この写像が準多様体分割として位相的に妥当であることを保証する。2次元の組合せ写像は、 n  = 2を固定し、σをβ ₁、αをβ ₂と改名することで得られる。

必ずしも閉じた空間や向きが定まらない空間は、（ n次元の）一般化写像を使って表現できる。

ローテーションシステム

組合せ数学において、回転システム（組合せ埋め込みまたは組合せ写像とも呼ばれる）は、グラフの各頂点の周りの辺の循環的な順序付けを記述することにより、グラフの有向面への埋め込みを符号化する。回転システムのより正式な定義は、順列のペアを含む。このようなペアは、多重グラフ、面、および多重グラフの面への2セル埋め込みを決定するのに十分である 。

あらゆる回転スキームは、有向閉面上への連結多重グラフの一意の2セル埋め込みを定義します（向きを保存する位相同値性を除きます）。逆に、有向閉面上への連結多重グラフGの任意の埋め込みは、 Gを基礎多重グラフとする一意の回転システムを定義します。回転システムと2セル埋め込みのこの基本的な同値性は、1890年代にLothar Heffterによって双対形式で初めて解決され^{[ 9 ]} 、 1950年代にはRingelによって広く利用されました^{[ 10 ]} 。Edmondsは独立して定理の原型を与え^{[ 11 ]}、彼の研究の詳細はYoungsによって普及されました^{[ 12 ]} 。 多重グラフへの一般化はGrossとAlpertによって提示されました^{[ 13 ]}

回転システムは、Reingoldら (2002) がグラフのジグザグ積を定義するために用いた回転マップと関連しているが、同じではない。回転システムは各頂点の周りの辺の循環的な順序付けを指定するのに対し、回転マップは各頂点における辺の（非循環的な）順列を指定する。さらに、回転システムは任意のグラフに対して定義できるが、Reingoldらが定義する回転マップは正則グラフに限定される。

埋め込み表面の特性評価

オイラーの公式によれば、回転系によって定義される閉有向面（つまり、その上に基礎となる多重グラフが2セル埋め込まれている面）の種数gを導くことができる。 ^{[ 14 ]}、およびであることに注意する。 ${\displaystyle (\sigma ,\theta )}$ ${\displaystyle V=|Z(\sigma )|}$ ${\displaystyle E=|Z(\theta )|}$ ${\displaystyle F=|Z(\sigma \theta )|}$

${\displaystyle g=1-{\frac {1}{2}}(V-E+F)=1-{\frac {1}{2}}(|Z(\sigma )|-|Z(\theta )|+|Z(\sigma \theta )|)}$

ここで、 は順列 の軌道の集合を表します。 ${\displaystyle Z(\phi )}$ ${\displaystyle \phi }$

参照

• ボロバス・リオルダン多項式
• 境界表現
• 一般化された地図
• 二重接続エッジリスト
• 四辺形データ構造
• ローテーションシステム
• 単体複体
• 翼のあるエッジ

参考文献

1. Bollobás, Béla; Riordan, Oliver (2001). 「有向面上のグラフの多項式不変量」. Proceedings of the London Mathematical Society . 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 .
9. ヘフター (1891)、ヘフター (1898)
10. リンゲル（1965）
11. エドモンズ (1960a)、エドモンズ (1960b)
12. ヤングス（1963）
13. グロス＆アルパート（1974）
14. Lando & Zvonkin (2004)、式 1.3、p. 38.

参考文献

• コリ、R.マチ、A. (1992)。 「マップ、ハイパーマップ、およびそれらの自己同型性: 調査」。数学の解説。10 : 403–467。MR 1190182 。 ​​
• エドモンズ, J. (1960a). 「多面体表面の組合せ的表現」アメリカ数学会報7 :646 .
• エドモンズ, ジョン・ロバート (1960b).有向多面体曲面の組合せ表現(PDF) (修士論文). メリーランド大学. hdl : 1903/24820 .
• Gross, JL; Alpert, SR (1974). 「カレントグラフの位相理論」 . Journal of Combinatorial Theory, Series B. 17 ( 3): 218– 233. doi : 10.1016/0095-8956(74)90028-8 . MR  0363971 .
• ヘフター、L. (1891)。「Uber das 問題 der Nachbargebiete」。数学アンナレン。38 (4): 477–508。土井: 10.1007/BF01203357。S2CID  121206491。
• ヘフター、L. (1898)。「ユーバーメタシークリッシェグルッペンとナッハバルコンティギュレーション」。数学アンナレン。50 ( 2–3 ): 261–268 .土井: 10.1007/BF01448067。S2CID  120691296。
• Lando, Sergei K.; Zvonkin, Alexander K. (2004).曲面上のグラフとその応用. 数学百科事典：低次元位相幾何学 II. 第141巻. Springer-Verlag . ISBN 978-3-540-00203-1。。
• モハール、ボヤン、トーマスセン、カーステン(2001). 『曲面上のグラフ』 ジョンズ・ホプキンス大学出版局. ISBN 0-8018-6689-8。
• Reingold, O.; Vadhan, S.; Wigderson, A. (2002). 「エントロピー波、ジグザググラフ積、そして新しい定数次数展開子」Annals of Mathematics . 155 (1): 157– 187. arXiv : math/0406038 . doi : 10.2307/3062153 . JSTOR  3062153 . MR  1888797 . S2CID  120739405 .
• リンゲル、G. (1965)。 「Das Geschlecht des vollständigen paaren Graphen」。ハンブルク大学アブハンドルゲン数学セミナー。28 ( 3–4 ): 139–150 .土井: 10.1007/BF02993245。MR  0189012。S2CID  120414651。
• ヤングス, JWT (1963). 「最小埋め込みとグラフの種数」 .数学と力学ジャーナル. 12 (2): 303– 315. doi : 10.1512/iumj.1963.12.12021 . MR  0145512 .

外部リンク

• 計算幾何学アルゴリズムライブラリ CGALの組み合わせマップ:
  • ダミアン、ギヨーム. 「組み合わせ地図」 . 2021年2月6日閲覧。

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