標題: 變動相對距離和的排列
Total relative displacement of permutation in graph
作者: 鄭凱鐘
Kai-Chung Cheng
傅恆霖
Hung-Lin Fu
應用數學系所
關鍵字: 變動相對距離和的排列;近似自同構;混沌映射;total relative displacement of permutation;near-automorphism;chaotic mapping
公開日期: 1999
摘要: 設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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT880507026
http://hdl.handle.net/11536/66177
顯示於類別:畢業論文