變動相對距離和的排列

Abstract

設G是一個連通圖，d_{G}(a,b)是指G中a,b兩點間的距離，令$\alpha$是V(G)的一個排列，定義$\delta_\alpha(G)$ to be $\displaystyle\sum_{a,b\in V(G)}|d_{G}(a,b)-d_{G}(\alpha(a),\alpha(b))|$，則稱$\delta_\alpha(G)$ 是圖中變動相對距離和的排列(Total relative displacement of permutation $\alpha$)，所以此排列$\alpha$稱為是G的一個自同構(Automorphism)若且唯若$\delta_\alpha(G)$=0。令$\pi(G)$ 是在所有排列$\alpha$中所得$\delta_\alpha(G)$ 的最小正數，此排列稱為G的近似自同構(Near-automorphism)。此外，令$\pi^{\ast}(G)$是在所有排列$\alpha$中所得$\delta_\alpha(G)$ 的最大數，則此排列$\alpha$稱為G的混沌映射(Chaotic Mapping)。本論文主要在研究當$\pi(G)=2$時，此圖G的結構，以及$\pi^{\ast}(C_n)$ 的值為何。

Let $\alpha$ be a permutation of the $n$ vertices of a connected graph $G$. Define $\delta_\alpha(G)$ to be $\displaystyle\sum_{a,b\in V(G)}|d_{G}(a,b)-d_{G}(\alpha(a),\alpha(b))|$, where the sum is over all the ${n \choose 2}$ unordered pairs of distinct vertices of $G$. The number $\delta_\alpha(G)$ is called the {\it total relative displacement} of $\alpha$ in $G$. So, permutation $\alpha$ is an automorphism of $G$ if and only if $\delta_\alpha(G)=0$. Let $\pi(G)$ denote the smallest positive value of $\delta_\alpha(G)$ among the n! permutations $\alpha$ of the vertices of $G$. A permutation $\alpha$ for which $\pi(G)=\delta_\alpha(G)$ has been called a {\it near-automorphism} of $G$. Let $\pi^{\ast}(G)$ be the maximum value of $\delta_\alpha(G)$ among all permutations of $V(G)$ and the permutation which realizes $\pi^{\ast}(G)$ is called a {\it chaotic mapping} of $G$. In this thesis, we study the structure of a connected graph $G$ for $\pi(G)=2$ and the bound of $\pi^{\ast}(G)$ when $G$ is a cycle with $n$ vertices.