サイクルグラフ（代数）

抽象代数学のサブフィールドである群論において、群のサイクル グラフは、群の生成元のセットが与えられた場合に、その群のさまざまなサイクルを示す無向グラフです。サイクル グラフは、小さな有限群の構造を視覚化する場合に役立ちます。

サイクルは、与えられた群の元 a の累乗の集合です。ここで、元 a の n乗であるa nは、a^をn回自身に乗じた積として定義されます。元a はサイクルを生成すると言われています。有限群では、aのゼロでない累乗が必ず 群の単位元で、これはeまたは 1 で表されます。そのような最小の累乗は元aの位数、つまりサイクル内で生成される異なる元の数です。サイクル グラフでは、サイクルは多角形として表され、その頂点は群の元を表し、辺はそれらがどのようにリンクされてサイクルを形成するかを示します。

各グループ要素はサイクル グラフ内のノードで表され、十分なサイクルがグラフ内のポリゴンとして表されるため、すべてのノードは少なくとも 1 つのサイクル上にあります。これらのポリゴンはすべて、アイデンティティを表すノードを通過し、他のノードも複数のサイクル上に存在する場合があります。

グループ要素a が位数 6 のサイクルを生成する (位数が 6 である) と仮定します。この場合、ノードa、a ²、a ³、a ⁴、a ⁵、およびa ⁶ = eはサイクル グラフ内の六角形の頂点になります。この場合、要素a ^{2 は}位数 3 になりますが、ノードa ²、a ⁴、およびe をグラフ内の三角形の頂点にしても、新しい情報は追加されません。したがって、別のサイクルのサブセットではないプリミティブサイクルのみを考慮する必要があります。また、位数 6 であるノードa ^5は、 a自体と同じサイクルを生成します。したがって、サイクルの生成に使用する要素について、少なくとも 2 つの選択肢があります (多くの場合、それ以上の選択肢があります)。

グループのサイクル グラフを構築するには、まず各グループ要素のノードを作成します。次に、各プリミティブ サイクルについて、そのサイクルを生成する要素a を選択し、 eのノードをaのノードに接続し、a をa ²に接続し、...、a ^{k −1を}a ^kに接続するなどして、 eに戻るまで続けます。その結果、グループのサイクル グラフが作成されます。

群の元a が位数 2 の場合（つまり、aによる乗算が反転となる場合）、上記の規則はe をaに2 つの辺で接続し、1 つは外に出て、もう 1 つは戻ってくることになります。このようなサイクルの 2 つの辺を強調する場合を除き、通常は2 つの元を結ぶ 1 本の線として 描かれます^{[1] 。}

グループとグラフの対応は、どちらの方向でも 1 対 1 ではないことに注意してください。2 つの異なるグループが同じサイクル グラフを持つことがあり、2 つの異なるグラフが 1 つのグループのサイクル グラフであることもあります。それぞれの例については、非一意性のセクションで示します。

群サイクルグラフの例として、二面体群Dih ₄を考えてみましょう。この群の乗算表が左側に示され、サイクルグラフが右側に示されます。e は単位元を指定します。

掛け算表のサイクル { e , a , a ² , a ^{3 } に注目してください。ここで、} a ⁴ = eです。逆数a ⁻¹ = a ³もこのサイクルの生成元です: ( a ³ ) ² = a ²、( a ³ ) ³ = a、( a ³ ) ⁴ = e。同様に、どのグループのどのサイクルにも少なくとも 2 つの生成元があり、どちらの方向にも横断できます。より一般的には、n個の要素を持つサイクルの生成元の数はnのオイラー φ 関数で与えられ、これらの生成元はいずれもサイクルの最初のノード (恒等関数eの隣) として記述できます。または、より一般的には、ノードはマークされません。2 つの異なるサイクルが生成元内で交差することはできません。

素数でない数の要素を含むサイクルには、グラフに示されていない巡回サブグループがあります。上記のグループ Dih ₄の場合、( a ² ) ² = eなので、 a ²とeの間に線を引くことができますが、a ^{2 は}より大きなサイクルの一部であるため、これはサイクル グラフのエッジではありません。

2 つのサイクルが非単位元を共有する場合、あいまいさが生じる可能性があります。たとえば、8 要素の四元数グループには、右に示すサイクル グラフがあります。中央の行の各要素をそれ自体で乗算すると、-1 になります (1 は単位元です)。この場合、サイクルを追跡するために異なる色を使用することがありますが、対称性を考慮することもできます。

前述のように、2 要素サイクルの 2 つのエッジは通常、1 本の線として表されます。

要素の逆は、同一性を固定する反射に関して、そのサイクル内でその要素と対称なノードです。

グループのサイクルグラフは、グラフ同型性を除いて一意に決定されません。また、グループ同型性を除いてグループを一意に決定しません。つまり、得られるグラフは選択された生成子セットに依存し、2つの異なるグループ（選択された生成子セットを持つ）が同じサイクルグラフを生成する可能性があります。^[2]

いくつかのグループでは、そのグループのさまざまな原始サイクルを生成するために異なる元を選択すると、異なるサイクルグラフにつながる可能性があります。この例として、位数が 20 であるアーベル群があります。 ^[2] そのグループの元を 3 つの数値 で表します。ここで、とのそれぞれは0 または 1 です。この 3 つ組は単位元です。下の図では、が と の上に示されています。 ${\displaystyle C_{5}\times C_{2}\times C_{2}}$${\displaystyle (i;j,k)}$${\displaystyle 0\leq i<5}$${\displaystyle j}$${\displaystyle k}$${\displaystyle (0;0,0)}$${\displaystyle i}$${\displaystyle j}$${\displaystyle k}$

このグループには、それぞれ次数が 10 の 3 つの基本サイクルがあります。最初のサイクル グラフでは、3 つのサイクルの生成元として、ノード、、およびを選択します。2 番目では、 ではなく から始めて、3 番目のサイクル (青いサイクル) を生成します。 ${\displaystyle (1;1,0)}$${\displaystyle (1;0,1)}$${\displaystyle (1;1,1)}$${\displaystyle (2;1,1)}$

結果として得られる 2 つのグラフは、それぞれ直径が5 と 4 であるため、同型ではありません。

2 つの異なる (非同型) グループが同型のサイクル グラフを持つ場合があります。後者の同型性はグラフのノードのラベルを無視します。したがって、グループの構造はサイクル グラフによって一意に決定されるわけではありません。

この例は、位数 16 の群、つまりとの 2 つの群に対して既に存在します。アーベル群は、位数 8 と 2 の巡回群の直積です。非アーベル群は、の非単位元が の5倍の自己同型に写像される、との半直積です。 ${\displaystyle C_{8}\times C_{2}}$${\displaystyle C_{8}\rtimes _{5}C_{2}}$${\displaystyle C_{8}\times C_{2}}$${\displaystyle C_{8}\rtimes _{5}C_{2}}$${\displaystyle C_{8}}$${\displaystyle C_{2}}$${\displaystyle C_{2}}$${\displaystyle C_{8}}$

これら2つのグループのサイクルグラフを描く際には、要素sとtによって生成されるものとし、 ${\displaystyle C_{8}\times C_{2}}$

${\displaystyle s^{8}=t^{2}=1\quad {\text{and}}\quad ts=st,}$

ここで後者の関係はアーベル的である。そして、を元𝜎と𝜏によって生成されるものと し、${\displaystyle C_{8}\times C_{2}}$${\displaystyle C_{8}\rtimes _{5}C_{2}}$

${\displaystyle \sigma ^{8}=\tau ^{2}=1\quad {\text{and}}\quad \tau \sigma =\sigma ^{5}\tau .}$

以下は、これら 2 つのグループのサイクル グラフです。左側に緑のサイクルを生成し、右側にそのサイクルを生成することを 選択しました。${\displaystyle st}$${\displaystyle \sigma \tau}$

右側のグラフでは、緑色のサイクルは1から に移動した後、 の横に移動します。 ${\displaystyle \sigma \tau}$${\displaystyle \sigma ^{6},}$

${\displaystyle (\sigma \tau )(\sigma \tau )=\sigma (\tau \sigma )\tau =\sigma (\sigma ^{5}\tau )\tau =\sigma ^{6}.}$

サイクルグラフは、1950年代初頭に 数論学者ダニエル・シャンクスによって、剰余類の乗法群を研究するためのツールとして研究されました。^[3]シャンクスは、1962年に出版された著書『数論における解決済みおよび未解決の問題』の初版で初めてこのアイデアを発表しました。^[4]この本で、シャンクスはどの群が同型サイクルグラフを持つか、またサイクルグラフが平面グラフになるのはいつかを調査しています。^{[5] 1978年の第2版で、シャンクスは}類群に関する研究とベイビーステップ・ジャイアントステップ法の開発について振り返っています。^[6]

サイクルグラフは有限アーベル群を扱うときに有用であることが証明されており、私は複雑な構造を理解するのに[77, p. 852]、必要な乗法関係を得るのに[78, p. 426]、必要なサブグループを分離するのに[79]、サイクルグラフを頻繁に使用してきました。

サイクルグラフは、ネイサン・カーターの2009年の入門教科書「Visual Group Theory」で教育ツールとして使用されています。^[7]

特定のグループ タイプでは、典型的なグラフが生成されます。

巡回群Z _n、位数nは、頂点に要素を持つ n辺の多角形として単純にグラフ化された単一の巡回群です。

nが素数のとき、形式(Z _n ) ^mの群は単位元を共有 する( n ^m − 1)/( n − 1) n元循環を持つ。

二面体群Dih _n、位数 2 n はn要素サイクルとn 2 要素サイクル で構成されます。

二環式群、Dic _n = Q _{4 n}、位数4 n :

その他の直接製品:

対称群– 対称群 S _{n に}は、位数nの任意の群に対して、その群と同型な部分群が含まれます。したがって、位数nのあらゆる群のサイクル グラフは、 S _nのサイクル グラフに含まれます。
例: S4 の部分群を参照してください。

完全八面体群は対称群 S ₄と巡回群 Z _2の直積で ある。 その位数は 48 であり、48 を割り切るすべての位数のサブグループを持つ。 ${\displaystyle S_{4}\times Z_{2}}$

以下の例では、相互に関連するノードが隣り合って配置されている
ため、これらのグループにとって最も単純なサイクル グラフではありません (右側のグラフなど)。

すべてのグラフと同様に、サイクル グラフはさまざまな方法で表現して、さまざまな特性を強調することができます。S ₄のサイクル グラフの 2 つの表現はその一例です。

ウィキメディア・コモンズには、グループサイクルグラフに関連するメディアがあります。

• 小グループのリスト
• ケーリーグラフ

• Skiena, S. (1990)。サイクル、スター、ホイール。離散数学の実装: Mathematica による組合せ論とグラフ理論(pp. 144-147)。
• シャンクス、ダニエル（1978）[1962]、数論における解決済みおよび未解決の問題（第2版）、ニューヨーク：チェルシー出版社、ISBN 0-8284-0297-3
• Pemmaraju, S., & Skiena, S. (2003). Cycles, Stars, and Wheels.計算離散数学: Mathematica による組合せ論とグラフ理論(pp. 248-249). Cambridge University Press.

• Weisstein、Eric W.「グループサイクルグラフ」。MathWorld。