Graph Automorphism.md

グラフの自己同型写像とは何か

1. はじめに

グラフ理論は、頂点と辺の関係を記述する数学の分野であり、多くの応用を持つ。その中でも、**グラフの自己同型写像（graph automorphism）**は、グラフの構造を保持する写像として重要な概念である。本記事では、自己同型写像の定義、性質、および具体例を通してその重要性を解説する。

2. 自己同型写像の定義

定義: グラフ ( G = (V, E) ) に対して、自己同型写像とは、頂点集合 ( V ) 上の全単射（bijection） ( \phi: V \to V ) であって、

[ (u, v) \in E \quad \text{ならば} \quad (\phi(u), \phi(v)) \in E ]

を満たすものである。つまり、元のグラフで隣接している頂点の対は、写像後も隣接したままである必要がある。

3. 自己同型写像の特徴

1. グラフの対称性を記述する

   • 自己同型写像は、グラフの対称性を反映する。対称性が高いグラフほど、自己同型写像の数が多い。

2. 自己同型群を形成する

   • すべての自己同型写像の集合は、写像の合成を演算とする群（group）を形成する。この群を 自己同型群（automorphism group） と呼ぶ。

3. 非対称グラフ（asymmetric graph）

   • 恒等写像（どの頂点もそのまま移す写像）以外に自己同型写像を持たないグラフを非対称グラフという。非対称グラフは、すべての頂点が異なる役割を持つような構造をしている。

4. 自己同型写像の具体例

例1: 完全グラフ ( K_n )

完全グラフ ( K_n ) は、すべての頂点が互いに接続されているため、頂点の並べ替え（置換）全体が自己同型写像になる。したがって、自己同型群は対称群 ( S_n ) となる。

例2: サイクルグラフ ( C_n )

サイクルグラフ ( C_n ) は ( n ) 個の頂点が円状に接続されている。自己同型写像としては、頂点を回転させる操作と、鏡映（反転）操作が存在し、群としては 二面体群 ( D_n ) になる。

例3: 星グラフ ( S_n )

中心頂点と ( n-1 ) 個の端点からなる星グラフでは、端点の入れ替えが可能であるため、自己同型群は ( S_{n-1} ) となる。

例4: 非対称グラフ

上記のような対称性を持たないグラフでは、自己同型写像は恒等写像のみである。このようなグラフを**極小非対称グラフ（minimal asymmetric graph）**とも呼ぶ。

5. 応用

自己同型写像の概念は、以下のような分野で応用される。

• ネットワーク理論: 通信ネットワークやソーシャルネットワークの対称性解析
• 化学グラフ理論: 分子の対称性解析（例: 化学構造の同一性判定）
• アルゴリズム設計: グラフ同型判定問題やデータ構造の圧縮

6. まとめ

グラフの自己同型写像は、グラフの対称性を表す基本的な概念であり、数学的な研究だけでなく、さまざまな分野で応用される。特に、自己同型群の構造を理解することで、グラフの性質を深く解析できる。