巡回グラフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/04/19 14:43 UTC 版)
抽象代数学の一分野である群論において、群の巡回グラフ（じゅんかいグラフ、英：cycle graph）は、群の様々な巡回を図示し、特に小さな有限群の構造を視覚化するのに有効である。 位数が 16 未満の群において、巡回グラフは群を（同型の意味で）決定する。
巡回とは、ある群の元 a の冪の集合のことで、ここで 要素 a の n 乗 an は、a に自分自身を n − 1 回掛け算した積として定義される。 このとき、a は巡回を生成すると言う。 有限群の場合、a のある冪乗は、群の単位元に等しくなければならない。 この様な最小の冪を巡回の位数と言う。 巡回グラフでは、巡回は多角形の列で表現され、頂点は群の要素を表現し、そして連結する辺は多角形中の全要素が同一の巡回に含まれることを示す。
巡回
2つ以上の巡回は重なりを持つ場合があり、あるいは、単位元以外に共通の元を有しない場合もある。 巡回グラフは、個々の興味深い巡回を多角形で表示する。
a が位数 6 の巡回を生成する（または、a が位数 6 を有する）場合には、a6 = e である。 このとき、a2 の冪の集合 {a2, a4, e} は、巡回であるが、この場合には実際の所、何ら新しい情報を生み出さない。 同様に、a5 は a 自身と同じ巡回を生成する。
そこで、原始的巡回、つまり他の巡回の部分集合になっていない様な巡回についてのみ検討すれば良い。 これらはそれぞれ、ある原始的元 a によって生成される。 元の群の各元に対し、1つの点を取る。 各原始的元に関して、e から a、a から a2、…、an−1 から an、と、e に戻るまで繋いで行く。 その結果として、1つの巡回グラフが得られる。
（技術的に言うと、上記の説明によれば、a2 = e、つまり a が位数 2 を有する（対合である）場合は、e と 2辺で結ばれるのだが、慣用上 1辺のみを使用する[1]。）
特徴
群の巡回グラフの例として、位数 8 の正二面体群 Dih4 を考える。 e を単位元として、この群の乗積表を左側に、またその巡回グラフを右に示した。
| o | e | b | a | a2 | a3 | ab | a2b | a3b |
|---|---|---|---|---|---|---|---|---|
| e | e | b | a | a2 | a3 | ab | a2b | a3b |
| b | b | e | a3b | a2b | ab | a3 | a2 | a |
| a | a | ab | a2 | a3 | e | a2b | a3b | b |
| a2 | a2 | a2b | a3 | e | a | a3b | b | ab |
| a3 | a3 | a3b | e | a | a2 | b | ab | a2b |
| ab | ab | a | b | a3b | a2b | e | a3 | a2 |
| a2b | a2b | a2 | ab | b | a3b | a | e | a3 |
| a3b | a3b | a3 | a2b | ab | b | a2 | a | e |
e、a、a2、a3 の巡回について付言する。 乗積表から、a の冪の連続する列が、実際にこの様に振る舞うことを見て取れる。 この逆も成り立つ。 つまり、(a3)2=a2、(a3)3=a、(a3)4=e である。 この振る舞いは、あらゆる群のあらゆる巡回で成り立つ、つまり、巡回はどちらの方向にも回ることが可能である。
素数でない個数の元を含む巡回は、グラフ内で連結していない巡回を黙示的に有する。 上記の群 Dih4 において、 (a2)2=e であることから、 a2 と e の間に、線を引きたいと感じる。 しかし、a2 は、これより大きな巡回の一部であることから、そうしないのである。
2つの巡回が単位元でない元を共有する場合には、曖昧性が生じ得る。 例えば、単純四元群を考える。その巡回グラフを右に示す。 中央の行に示す各要素は、自分自身を掛けると −1 になる（1 を単位元とする）。 この場合、巡回の跡を辿るため、異なる色を用いよう。 ただし、対称の位置を有するようにもしておく。
上記の通り、2 要素の巡回は 2 本の線で結ばれる筈だが、通常は、1 本の線で略記する。
2つの相異なる群が同一の構造を有する巡回グラフを持つことがあり得、この場合には乗積表、または群の基本要素に関してグラフの要素をラベル付けすることによってのみ、区別可能である。 この問題が生じ得る最低位数は位数 16 であり、Z2 x Z8 および下に示すモジュラー群 の場合である。 （注意：これらグラフの中で、共通の元を有する巡回は、対称性により区別する。）
巡回グラフから得られるその他の情報
- 任意の要素の逆元を、巡回グラフの上で特定することができる。
- ある元の逆元は、単純に、同一巡回中の反対側の元である。
- 巡回が偶数個の元を有する場合には、自分自身が反対の位置にあり、従って、自分自身の逆元である元が、1つ存在する。
- 例えば、上の Dih4 のグラフにおいて、a の逆元はその反対の a3 であり、a2 は自分自身の逆元である。
特別な群の集団のグラフ的特性
ある群の型は、典型的なグラフを示す：
- 巡回群 Zn の場合は、要素を頂点に持つ n 角形のみによってグラフ化される単一の巡回である。
|
|
|
|
|
|
|
|
| Z1 | Z2 | Z3 | Z4 | Z5 | Z6 | Z7 | Z8 |
- (Zn)m の形の群の場合は、nが素数のとき共通の単位元を共有する n 個の要素を有する (nm − 1)/(n − 1) 個の巡回である。
|
|
|
|
|
| Z22 | Z23 | Z24 | Z32 | Z42 |
- 正二面体群 Dihn は、n 個の要素を有する1つの巡回と、2 個の要素を有する n 個の巡回から成り立つ。
|
|
|
|
|
|
|
|
| Dih1 | Dih2 | Dih3 | Dih4 | Dih5 | Dih6 | Dih7 |
- 対称群 ─ 対称群 Sn は、位数 n の任意の群と同型な部分群を有する。 従って、位数 n のあらゆる群の巡回グラフは、Sn の巡回グラフの部分グラフとして見つかる。
脚注
- ^ Perkins, Sarah (2006-01). “Commuting Involution Graphs for Ãn” (英語). Archiv der Mathematik (Springer) 86 (1): 16-25. doi:10.1007/s00013-005-1485-9.Section 2.2
関連文献
- Carter, Nathan (2009). Visual Group Theory. Classroom Resource Materials. The Mathematical Association of America. ISBN 978-0-88385-757-1
- Skiena, Steven (1990). “Cycles, Stars, and Wheels.”. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Addison-Wesley. pp. 144-147. ISBN 0-201-50943-1
- Shanks, Daniel (1978). Solved and Unsolved Problems in Number Theory (2nd ed.). New York: Chelsea Publishing Company. ISBN 0-8284-0297-3
- Pemmaraju, Sriram; Skiena, Steven (2003). “Cycles, Stars, and Wheels.”. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge University Press. pp. 248-249. ISBN 9781139164849
巡回グラフと同じ種類の言葉
- 巡回グラフのページへのリンク
