标题： 论图的自同构群 显示英文标题

标题： On the Automorphism Group of a Graph

摘要： An automorphism of a graph $G$ with $n$ vertices is a bijective map $\phi$ from $V(G)$ to itself such that $\phi(v_i)\phi(v_j)\in E(G)$ $\Leftrightarrow$ $v_i v_j\in E(G)$ for any two vertices $v_i$ and $v_j$ of $G$. 表示由$\mathfrak{G}$组成的群，该群包含$G$的所有自同构。 众所周知，$\mathfrak{G}$在$V(G)$上的作用结构由其块系统明确表示。 另一方面，对于每个排列$\sigma$在$[n]$上，存在一个在任意向量$\pmb{v}=(v_1,v_2,\ldots,v_n)^t\in \mathbb{R}^n$上的自然作用，使得$\sigma\pmb{v}=(v_{\sigma^{-1}1},v_{\sigma^{-1}2},\ldots,v_{\sigma^{-1} n})^t$。因此，我们实际上在$\mathbb{R}^n$中拥有$\mathfrak{G}$的排列表示。 在本文中，我们建立了$\mathfrak{G}$的块系统与其不可约表示之间的一些联系，并通过这一点，我们最终设计了一个算法，在时间$n^{C \log n}$内输出$\mathfrak{G}$的生成集和所有块系统，其中 $C$是某个常数。 显示英文摘要

摘要： An automorphism of a graph $G$ with $n$ vertices is a bijective map $\phi$ from $V(G)$ to itself such that $\phi(v_i)\phi(v_j)\in E(G)$ $\Leftrightarrow$ $v_i v_j\in E(G)$ for any two vertices $v_i$ and $v_j$ of $G$. Denote by $\mathfrak{G}$ the group consisting of all automorphisms of $G$. As well-known, the structure of the action of $\mathfrak{G}$ on $V(G)$ is represented definitely by its block systems. On the other hand for each permutation $\sigma$ on $[n]$, there is a natural action on any vector $\pmb{v}=(v_1,v_2,\ldots,v_n)^t\in \mathbb{R}^n$ such that $\sigma\pmb{v}=(v_{\sigma^{-1}1},v_{\sigma^{-1}2},\ldots,v_{\sigma^{-1} n})^t$. Accordingly, we actually have a permutation representation of $\mathfrak{G}$ in $\mathbb{R}^n$. In this paper, we establish the some connections between block systems of $\mathfrak{G}$ and its irreducible representations, and by virtue of that we finally devise an algorithm outputting a generating set and all block systems of $\mathfrak{G}$ within time $n^{C \log n}$ for some constant $C$.