対称グラフ
数学のグラフ理論の分野において、あるグラフ G が対称グラフ(たいしょうぐらふ、英: symmetric graph)あるいは弧推移グラフであるとは、G に含まれる任意の与えられた隣接する頂点同士からなるペア u1—v1 および u2—v2 に対して、
f(u1) = u2 and f(v1) = v2
であるような自己同型(英語版)
f : V(G) → V(G)
が存在することを言う。言い換えると、グラフが対称的であるとは、その自己同型群が、向き付けられた隣接する頂点同士のペアの上(すなわち、方向を持つと考えられる辺の上)で推移的に作用することを言う。 そのようなグラフはしばしば1-弧推移的(1-arc-transitive)あるいは旗推移的(flag-transitive)とも呼ばれる。
定義に従い(u1 と u2 を無視することで)、孤立頂点を含まない対称グラフは必ず頂点推移的でなければならないことが分かる。また、上述の定義では、一つの辺を別のものへと写しているため、対称グラフは辺推移的でなければならないことも分かる。しかしながら、辺推移グラフは必ずしも対称グラフではない。なぜならば、a—b が d—c ではなく c—d へと写されることも考えられるからである。また、例えば、半対称グラフは辺推移的かつ正則であるが、頂点推移的ではない。
したがって、全ての連結対称グラフは頂点推移的かつ辺推移的であり、次数が奇数であるようなグラフに対してはその逆も成立する。