電圧グラフ

グラフ理論において、電圧グラフとは、その辺が群の要素によって可逆的にラベル付けされた有向グラフである。形式的にはゲイングラフと同一であるが、位相グラフ理論においては、電圧グラフの 導出グラフと呼ばれる別のグラフを簡潔に指定する手段として一般的に用いられる。

電圧グラフに使用されるグループの一般的な選択肢には、2要素グループ（グラフの二部二重被覆を定義するため）、自由グループ（グラフの普遍被覆を定義するため）、 d次元整数格子（ベクトル加算の下でのグループとして見られ、d次元ユークリッド空間内の周期構造を定義するため）、^{[ 1 ]} 、およびn  > 2の有限巡回グループがあります。Πが巡回グループの場合、電圧グラフは巡回電圧グラフと呼ばれることがあります。 ${\displaystyle \mathbb {Z} _{2}}$ ${\displaystyle \mathbb {Z} ^{d}}$ ${\displaystyle \mathbb {Z_{n}} }$

意味

与えられた群Πに対するΠ電圧グラフの正式な定義:

• 有向グラフGから始めます。(方向は表記上の便宜上のためだけのものです。)
• Gの弧上の Π 電圧は、その弧の元 によるラベルです。例えば の場合、ラベルはi  (mod  n ) という数になります。${\displaystyle x\in \Pi }$ ${\displaystyle \Pi =\mathbb {Z} _{n}}$
• Π電圧割り当ては、 Gの各弧に Π 電圧のラベルを付ける関数です。${\displaystyle \alpha :E(G)\rightarrow \Pi }$
• Π電圧グラフは、Gが有向グラフで、α が電圧割り当てであるペアです。${\displaystyle (G,\alpha :E(G)\rightarrow \Pi )}$
• 電圧グラフの電圧グループは、電圧が割り当てられるグループΠです。${\displaystyle (G,\alpha :E(G)\rightarrow \Pi )}$

電圧グラフの電圧は、キルヒホッフの電圧法則（閉経路の周りの電圧の和は0（群の単位元））を満たす必要はないことに注意してください。ただし、この法則は、後述する導出グラフには当てはまります。したがって、この名称は多少誤解を招く可能性があります。これは、電圧グラフが位相グラフ理論の電流グラフの双対であるという起源に由来しています。

導出されたグラフ

電圧グラフの導出グラフは、頂点集合が、辺集合が であるグラフです。ここで、 e の末尾がvで先頭がwであるような辺 ( e、k )の端点は、です。 ${\displaystyle (G,\alpha :E(G)\rightarrow \mathbb {Z} _{n})}$ ${\displaystyle {\tilde {G}}}$ ${\displaystyle {\チルダ {V}}=V\times \mathbb {Z} _{n}}$ ${\displaystyle {\tilde {E}}=E\times \mathbb {Z} _{n}}$ ${\displaystyle (v,\ k)}$ ${\displaystyle (w,\ k+\alpha (e))}$

電圧グラフは有向グラフに対して定義されていますが、無向辺を逆向きの有向辺のペアに置き換え、これらの辺がグループ構造において互いに逆向きのラベルを持つようにすることで、無向グラフにも拡張できます。この場合、導出グラフも有向辺が逆向きの辺のペアを形成するという性質を持つため、導出グラフ自体が無向グラフとして解釈される可能性があります。

導出グラフは、与えられた電圧グラフの被覆グラフです。電圧グラフの辺ラベルが単位元でない場合、導出グラフの頂点に関連付けられた群元は、群位数に等しい色数で導出グラフを彩色します。重要な特殊なケースとして、二部二重被覆があります。これは、すべての辺が2元群の非単位元でラベル付けされている電圧グラフの導出グラフです。群の位数は2であるため、この場合の導出グラフは二部であることが保証されます。

多項式時間アルゴリズムは、-電圧グラフの導出グラフに有向サイクルが含まれているかどうかを判断するために知られている。^{[ 1 ]}${\displaystyle \mathbb {Z} ^{d}}$

例

Π群の任意のケイリーグラフは、与えられた生成元集合Γとともに、 1つの頂点とΓ 個の自己ループを持つΠ -電圧グラフの導出グラフとして定義することができる。各ループにはΓ内の生成元のいずれかがラベル付けされている。^{[ 2 ]}

ピーターセングラフは、2つの頂点と3つの辺を持つダンベル型の -電圧グラフの派生グラフである。2つの頂点を結ぶ辺が1つ、各頂点に1つの自己ループがある。一方の自己ループには1のラベルが、もう一方の自己ループには2のラベルが付けられ、2つの頂点を結ぶ辺には0のラベルが付けられる。より一般的には、同じ構成により、任意の一般化ピーターセングラフGP( n , k )を、グループ内のラベル1、0、 kを持つ同じダンベルグラフの派生グラフとして構築することができる。^{[ 3 ]}${\displaystyle \mathbb {Z} _{5}}$ ${\displaystyle \mathbb {Z} _{n}}$

平面の任意の周期的モザイクの頂点と辺は、電圧が の有限グラフの派生グラフとして形成できます。 ${\displaystyle \mathbb {Z} ^{2}}$

注記

1. 岩野＆シュタイグリッツ (1987) ;コサラジュとサリバン (1988) ;コーエンとメギド (1989)。
2. Gross & Tucker (1987)、定理2.2.3、p.69。
3. Gross & Tucker (1987)、例2.1.2、p.58。

参考文献

• コーエン、エディス、メギド、ニムロッド(1989)、「動的グラフにおける閉路検出のための強力多項式時間およびNCアルゴリズム」、第21回ACM計算理論シンポジウム (STOC '89) 論文集、pp.  523– 534、doi : 10.1145/73007.73057、ISBN 0-89791-307-8。
• グロス、ジョナサン L. (1974)、「電圧グラフ」、離散数学、9 (3): 239– 246、doi : 10.1016/0012-365X(74)90006-5。
• グロス、ジョナサン・L.;タッカー、トーマス・W. (1977)、「順列電圧割り当てによる全グラフ被覆の生成」、離散数学、18 (3): 273– 283、doi : 10.1016/0012-365X(77)90131-5。
• グロス、ジョナサン L.; タッカー、トーマス W. (1987)、トポロジカルグラフ理論、ニューヨーク：ワイリー。
• 岩野 健; シュタイグリッツ 健 (1987)、「周期構造を持つ無限グラフのサイクルのテスト」、第19回ACM計算理論シンポジウム (STOC '87) 論文集、pp.  46– 55、doi : 10.1145/28395.28401、ISBN 0-89791-221-7、S2CID  37934099。
• Kosaraju, S. Rao ; Sullivan, Gregory (1988)、「多項式時間による動的グラフのサイクル検出」、Proc. 20th Annual ACM Symposium on Theory of Computing (STOC '88)、pp.  398– 406、doi : 10.1145/62212.62251、ISBN 0-89791-264-0、S2CID  14290312。