非平面埋め込み

ウィキペディア小見出し辞書

非平面埋め込み

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/11 14:38 UTC 版)

「双対グラフ」の記事における「非平面埋め込み」の解説

K7 はトーラス上のヒーウッドグラフの双対である。 K6 はprojective plane上のピーターセングラフの双対である。 双対性の概念は、平面以外の二次元多様体上の埋め込みに拡張することができる。ほとんどの場合、埋め込みは各面が位相円板であるという性質を持つ場合に制限されている。この制約は、グラフが接続されているという平面グラフの要件を一般化したものである。この制約により、任意の埋め込みグラフは、同じ曲面に自然に埋め込まれることができる。例えば、完全グラフK7の双対グラフはヒーウッドグラフである。 平面グラフも非平面埋め込みを持つことがあり、その場合の双対は平面双対とは異なる。たとえば、立方体の4つのペトリー多角形（立方体の2つの対向する頂点を削除することによって形成された六角形）は、トーラスに立方体を埋め込むときの六角形の面を形成する。この埋め込みの双対グラフは、二重エッジを持つ完全なグラフK4を形成する4つの頂点を持つ。この双対グラフのトーラス埋め込みでは、各頂点が持つ6つの辺は、その頂点の周囲を巡回する順序で、他の3つの頂点を2回巡回する。平面内の状況とは対照的に、この立方体とその双対の埋め込みは一意ではない。立方体グラフの双対は、他のいくつかのトーラス埋め込みを持つ。 平面グラフの主グラフと双対グラフの性質の間の等価性の多くは、非平面埋め込みの場合に一般化できないか、追加の注意を必要とする。 表面埋め込みグラフに対するもう1つの操作はPetrie双対である 。これは、埋め込みのPetrieポリゴンを新しい埋め込みの面として使用する。このグラフは通常の双対グラフとは異なり、元のグラフと同じ頂点を持つが、一般に異なる面に属する。面双対性とPetrie双対性は6つのウィルソン演算のうちの2つであり、これらの演算による群を生成する。