巡回グラフ
(Cycle graph から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2026/03/10 05:41 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
閉路グラフ
(Cycle graph から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/03/05 14:20 UTC 版)
閉路グラフ（へいろグラフ、英: cycle graph）は、グラフ理論において1つの閉路から成るグラフをいう。言い換えれば、いくつかの辺が相互に連なって1つの輪・環を形成しているグラフである。n個の辺による閉路グラフを Cn と表記する。Cn においては、辺と頂点の数は等しく、各頂点の次数は2である。つまり、各頂点は2つの辺と接合している。
有向閉路グラフ (英: directed cycle graph) は辺に向きのある閉路グラフであり、全ての辺は同じ向きになっている。
有向グラフにおいて、それぞれの有向閉路から少なくとも1つの辺（枝）を含んでいる枝集合を帰還枝集合 (feedback arc set) と呼ぶ。同様に、それぞれの有向閉路から少なくとも1つの頂点を含んでいる頂点集合を帰還頂点集合 (feedback vertex set) と呼ぶ。
有向閉路グラフの各頂点は入次数が1で、出次数が1である。
有向閉路グラフは、巡回群におけるケイリーグラフである（外部リンクの Trevisan 参照）。
閉路のない有向グラフは有向非巡回グラフ (英: directed acyclic graph) という
関連項目
外部リンク
- Eric W. Weisstein, Cycle Graph at MathWorld（巡回グラフのことも同じ項目で扱っている）
- Luca Trevisan, Characters and Expansion.
「Cycle graph」の例文・使い方・用例・文例
- “Photo”は“Photograph”の略だ
- Cycle graphのページへのリンク
