图的群作用与对称性 1. 基本概念引入 图的自同构群是刻画图对称性的核心工具。设图G=(V,E)，其自同构群Aut(G)由所有保持边关系的顶点置换组成。群作用理论将这一概念推广：任意群Γ通过置换顶点（且保持邻接关系）的方式作用于图G时，称Γ为G的自同构子群。例如，循环群可作用于环状图，二面体群可作用于多边形图。 2. 顶点轨道与边轨道 在群Γ作用下，顶点集V被划分为轨道（等价类）：若存在γ∈Γ使得γ(u)=v，则顶点u和v属于同一轨道。边集E同理可划分为边轨道。轨道结构反映了图的对称程度——若所有顶点处于同一轨道（顶点传递图），则图具有高度对称性；若边也处于同一轨道（弧传递图），对称性更强。 3. 商图构造与对称性分析 通过群作用可定义商图G/Γ：其顶点集为顶点轨道集合，边集为边轨道集合。商图保留了原图的拓扑特征但简化了结构。例如，若Γ作用自由（无不动点），则G可视为商图的覆盖空间。通过分析商图的连通性、度分布等性质，可反推原图的对称性特征。 4. 对称性度量的数学工具 引入轨道-稳定子定理：顶点v所在轨道的大小等于群Γ的阶除以其稳定子群Γ_ v的阶。结合Burnside引理，可精确计算轨道数量。对于高度对称图（如Petersen图），其自同构群阶数可达|V| !量级，而平凡图的自同构群为对称群，这体现了对称性与群规模的关联。 5. 对称性对图性质的影响 对称性会约束图的组合参数：顶点传递图的顶点度必须相同；边传递图的所有边需连接相同度数的顶点。在代数图论中，对称性导致邻接矩阵的特征值具有重数，谱分解与群表示理论密切相关。例如，强正则图的高度对称性使其特征值仅有三类。 6. 无限图的对称性扩展 将概念推广至无限图：若存在群作用使得图的每个有限子图都能通过群元素映射到任意位置，则称图具有齐次性。可数随机图具有惊人的对称性——其自同构群作用齐次，且任意部分同构可扩展为全图自同构（Fraïssé极限的典型例子）。 7. 应用与前沿问题 对称性分析在化学图论（分子对称性）、网络科学（互联网拓扑对称性）及编码理论中均有应用。未解决难题包括：确定特定群能否作为某图的自同构群、构造具有给定对称性但禁用子图的极值图等。这些问题的研究需要融合群论、组合优化与几何方法。