2020.01.22
# 離散数学 # 群論 # ガロア

「ガロア理論」を本気で学ぶための、1時間でわかる離散数学の基礎

一歩ずつ進めば必ず理解できます!
芳沢 光雄 プロフィール

順序の入れ替えができるのが「可換群」

前頁で示した①~④を満たす集合\(G\)と演算\(*\)があって、さらに下記の⑤を満たすとき、「\(G\)は\(*\)に関して可換群である」という。

⑤ \(G\)の任意の元(要素)\(x ,y\)に対し、 \[ x*y=y*x \]  が成り立つ(交換法則が成立)。

上の例で述べると、\(G\)の部分集合 \[ H=\{e, a_1 ,a_2 ,a_3 ,a_4\} \]や\[K=\{e, a_5\}\] などは可換群である。しかし、 \[ a_2*a_5=a_6, \\ a_5*a_2=a_9\] なので、\(G\)は可換群ではない。

また、上の\(H\)や\(K\)のように、群\(G\)の部分集合で(同じ演算に関して)群になるものを、一般に群\(G\)の部分群という。

ところで、正五角形に対する合同変換全体の集合から成る群\[ G=\{e, a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8, a_9\} \] を、正五角形の自己同型群という。

離散数学における「グラフ」とは何か?

離散数学で扱うグラフは、小学生から習う棒グラフ、折れ線グラフ、帯グラフ、円グラフなどのグラフとは異なって、頂点と頂点どうしを結ぶ辺のみからなる構造のことである。

辺に関しては「結ぶ」か「結ばない」か、それだけを問うのであって、長さや向きなどはいっさい問わないものである。

一例として、A、B、C、D、E、F、Gの7人がいて、それらに関しては「知り合い」か「知り合いでない」か、のどちらかが成り立つとする。そして、すべての知り合いの関係を以下の6個とする。

AとD、BとD、CとD、DとE、EとF、EとG

このとき、「知り合い」を辺とするグラフを示すと下図になる。

参考までに、前回の記事『「あみだくじの仕組み」から学ぶ いまや必須の「離散数学」』では次のことを述べて証明したが、これもグラフに関係する問題のひとつである。

ここにA〜Iの9人がいて、どの2人をとっても、「知り合い」か「知り合いでない」かの関係があるとする。A、B、C、Dの4人は「自分はちょうど4人と知り合いの関係がある」と言い、E、F、G、H、Iの5人は「自分はちょうど3人と知り合いの関係がある」と言う。

このとき、誰かが嘘を言っていることが証明できる。

一般に、集合\(\Omega\)から\(\Omega\)への写像\( f \)で、次の2つの条件を満たすものを\(\Omega\)上の置換という。

(ア) \( \{f(x)\)全体\(|x\)は\(\Omega\)の元\(\}=\Omega \)
(イ) \(\Omega\)の相異なる任意の元\( x ,y\)に対し、\( f(x)≠f(y)\)

直観的に述べると、\(\Omega\)上の置換とは\(\Omega\)の元全体の取り替えになっているものである。もちろん、\(\Omega\)の各元をそれ自身に移す写像も\(\Omega\)上の置換である。

グラフの自己同型写像とは、グラフの頂点集合上の置換で、グラフとしての構造を変えないものである。また、グラフの自己同型群とは、グラフの自己同型写像全体がつくる群のことである(演算は写像の合成)。

上の図で示したグラフの自己同型写像は、以下の12個である。

\[ \left( \begin{array}{cc} A & B & C & D & E & F & G \\ A & B & C & D & E & F & G \end{array} \right) \ \ \ \left( \begin{array}{cc} A & B & C & D & E & F & G \\ A & B & C & D & E & G & F \end{array} \right) \\ \left( \begin{array}{cc} A & B & C & D & E & F & G \\ B & A & C & D & E & F & G \end{array} \right) \ \ \ \left( \begin{array}{cc} A & B & C & D & E & F & G \\ B & A & C & D & E & G & F \end{array} \right) \\ \left( \begin{array}{cc} A & B & C & D & E & F & G \\ C & B & A & D & E & F & G \end{array} \right) \ \ \ \left( \begin{array}{cc} A & B & C & D & E & F & G \\ C & B & A & D & E & G & F \end{array} \right) \\ \left( \begin{array}{cc} A & B & C & D & E & F & G \\ A & C & B & D & E & F & G \end{array} \right) \ \ \ \left( \begin{array}{cc} A & B & C & D & E & F & G \\ A & C & B & D & E & G & F \end{array} \right) \\ \left( \begin{array}{cc} A & B & C & D & E & F & G \\ B & C & A & D & E & F & G \end{array} \right) \ \ \ \left( \begin{array}{cc} A & B & C & D & E & F & G \\ B & C & A & D & E & G & F \end{array} \right) \\ \left( \begin{array}{cc} A & B & C & D & E & F & G \\ C & A & B & D & E & F & G \end{array} \right) \ \ \ \left( \begin{array}{cc} A & B & C & D & E & F & G \\ C & A & B & D & E & G & F \end{array} \right) \\ \]

関連記事