被覆グラフ

数学の分野であるグラフ理論では、グラフ Cの頂点集合からグラフGの頂点集合への被覆写像がある場合、グラフ C は別のグラフGの被覆グラフである。被覆写像fは全射であり局所同型である: Cの頂点vの近傍は、 Gの⁠ ⁠の近傍に全単射に写像される。 ${\displaystyle f(v)}$

リフトという用語は、連結グラフの被覆グラフの同義語としてよく使用されます。

誤解を招くかもしれませんが、被覆グラフと頂点被覆または辺被覆の間には（明らかな）関係はありません。

被覆グラフの組合せ論的定式化は、多重グラフの場合に直ちに一般化される。被覆グラフは被覆複体の特殊なケースである。^{[1]被覆複体と1次元セル複体を持つ多重グラフは、どちらも}位相空間の被覆空間の例にすぎないため、被覆変換群、普遍被覆、アーベル被覆、最大アーベル被覆など、被覆空間の理論の用語が使用可能である。^[2]

G = ( V ₁ , E ₁ ) とC = ( V ₂ , E ₂ ) を2つのグラフとし、f​​ : V ₂ → V ₁を全射とします。このとき、各v ∈ V ₂に対して、 f の v の近傍への制限が G における f ( v ) の近傍への全単射である場合、fはCからGへの被覆写像です。言い換えると、 fはvに接続する辺をf ( v )に接続する辺に1対1で写像します。

CからGへの被覆写像が存在する場合、C はGの被覆グラフ、またはリフトです。h-リフトは、被覆写像fが、 Gのすべての頂点vに対して、そのファイバーf ⁻¹ (v)がちょうどh個の要素を持つという特性を持つリフトです。

次の図では、グラフC はグラフHの被覆グラフです。

CからHへの被覆写像fは色で示されています。たとえば、Cの青い頂点は両方ともHの青い頂点に写像されます。写像fは全射です。つまり、 Hの各頂点はCに原像を持ちます。さらに、f はCの頂点vの各近傍をHの頂点f ( v )の近傍に全単射的に写像します。

たとえば、v をCの紫色の頂点の 1 つとします。 v はC内に 2 つの隣接頂点、緑の頂点uと青の頂点tを持ちます。同様に、v ′ をHの紫色の頂点とします。 v ′ はH内に 2 つの隣接頂点、緑の頂点u ′と青の頂点t ′ を持ちます。 { t , u , v }に制限されたマッピングf は、 { t ′ , u ′ , v ′ }への全単射です。これは次の図に示されています。

同様に、 Cの青い頂点の近傍がHの青い頂点の近傍に 1 対 1 でマッピングされていることを確認できます。

上記の例では、Hの各頂点はCにちょうど 2 つの原像を持ちます。したがって、C はHの2 重被覆または二重被覆です。

任意のグラフGに対して、 Gの二部二重被覆(これは二部グラフであり、 Gの二重被覆でもある)を構築することができる。Gの二部二重被覆は、グラフG × K ₂のテンソル積である。

Gがすでに二部グラフである場合、その二部二重被覆はGの互いに素な 2 つのコピーから構成されます。グラフには二部二重被覆以外にもさまざまな二重被覆が存在することがあります。

任意の連結グラフGに対して、その普遍被覆グラフ を構築することができる。^[3]これは、位相幾何学におけるより一般的な普遍被覆の概念の一例である。普遍被覆は単連結であるという位相的な要件は、グラフ理論の用語では、非巡回かつ連結であるという要件、つまり木に変換される。普遍被覆グラフは一意である（同型性を除いて）。G が木である場合、G自体はGの普遍被覆グラフである。その他の有限連結グラフGに対して、 Gの普遍被覆グラフは可算無限（ただし局所的に有限）木である。

連結グラフGの普遍被覆グラフTは次のように構築できます。開始点としてGの任意の頂点r を選択します。T の各頂点はrから始まる非バックトラックウォーク、つまりGの頂点のシーケンスw = ( r , v ₁ , v ₂ , ..., v _n ) であり、

• v _iとv _{i +1 は}Gにおいてすべてのiに対して隣接している、つまりwはウォークである
• すべてのiについてv _{i -1} ≠ v _{i +1}です。つまり、 w はバックトラックしません。

このとき、Tの 2 つの頂点は、一方が他方の単純な拡張である場合に隣接しています。つまり、頂点 ( r、v ₁、v ₂、 ...、v _n ) は頂点 ( r、v ₁、v ₂、 ...、v _{n -1 ) に隣接しています。同型性まで、開始点}rの選択に関係なく、同じツリーTが構築されます。

被覆写像f は、 Tの頂点 ( r ) をGの頂点rに写像し、 Tの頂点 ( r , v ₁ , v ₂ , ..., v _n ) をGの頂点v _nに写像します。

次の図はグラフHの普遍被覆グラフTを示しています。色は被覆マップを示しています。

任意のkに対して、すべてのk正則グラフは同じ普遍被覆、つまり無限k正則木を持ちます。

有限（多重）グラフの無限倍アーベル被覆グラフは、結晶構造の抽象化である位相結晶と呼ばれます。たとえば、グラフとしてのダイヤモンド結晶は、4辺双極子グラフの最大アーベル被覆グラフです。この見方は、「標準実現」の考え方と組み合わせると、（仮想）結晶の体系的な設計に役立つことがわかります。^[2]

グラフの平面被覆は有限被覆グラフであり、それ自体が平面グラフである。平面被覆を持つという性質は禁制のマイナーによって特徴付けられるかもしれないが、この形式の正確な特徴付けは未だに不明である。射影平面への埋め込みを持つすべてのグラフは、射影平面の向き付け可能な二重被覆から生じる平面被覆を持つ。1988年に永見誠也はこれらが平面被覆を持つ唯一のグラフであると予想したが、これは未だ証明されていない。^[4]

被覆グラフを形成する一般的な方法は、電圧グラフを使用するもので、与えられたグラフGのダーツ（つまり、Gの無向辺に対応する有向辺のペア）に、あるグループからの逆の要素のペアがラベル付けされます。電圧グラフの導出グラフは、その頂点としてペア（v、x）を持ちます。ここで、vはGの頂点、x はグループ要素です。Gのグループ要素yでラベル付けされたvから wへのダーツは、導出グラフの（v、x）から（w、xy）への辺に対応します。

このように、普遍被覆は、グラフの全域木の辺が群の単位元でラベル付けされ、残りの各ダーツのペアが自由群の別個の生成元でラベル付けされた電圧グラフの導出グラフとして見ることができます。 二部二重は、このように、各ダーツが位数 2 の群の非ゼロ元でラベル付けされた電圧グラフの導出グラフとして見ることができます。

• Godsil, Chris ; Royle, Gordon F. (2001). 「§6.8 折り畳みとカバー」. 代数グラフ理論. 大学院数学テキスト. 第 207 巻. Springer. pp. 114–6. ISBN 978-0-387-95220-8。
• Amit, Alon; Linial, Nathan ; Matoušek, Jiří ; Rozenman, Eyal (2001)。「グラフのランダムリフト」。第 12 回 ACM-SIAM 離散アルゴリズムに関するシンポジウム (SODA '01) の議事録。応用数学協会。pp. 883–894。CiteSeerX 10.1.1.719.3508。ISBN  978-0-89871-490-6。
• Angluin, Dana (1980)。「プロセッサ ネットワークのローカル プロパティとグローバル プロパティ (拡張要約)」。第 12 回 ACM コンピューティング理論シンポジウム (STOC '80) の議事録。Association for Computing Machinery。pp. 82–93。doi : 10.1145 /800141.804655。ISBN 978-0-89791-017-0。