圖轉置的相對變量

Abstract

令f是V(G)上的一個排列。圖G經由 f 的轉置後所產生的相對變量(total relative displacement of the permutation f in G)為 ，其中總和中的 (x,y) 為G中不同點有 個無序對。當排列f為G的一個自同構(automorphism) 若且為若 □f(G) = 0。令 □(G) 表示在 n! 個排列中所得到了最小的正整數。當排列f滿足 □f(G) = □(G)時，則稱f是G的一個近似同構(near automorphism)。此外，令 □*(G)為所有排列中所得到的 □f(G) 最大值，且稱對應的排列f為G的混沌映射(chaotic mapping)。 在本論文中，在第1章，我們給了一些圖轉置的基本介紹和一些之前別人做的結果。第2章，我們刻劃了一些圖G它們的□(G) = 2和一些樹圖T其□(T) = 4若且為若的條件。在第3章，我們致力於找圈圖Cn的近似同構和證明 □(Cn) = 4 - 4對於所有n □ 4 都對。而第4章，則探討哪些點數n □ 3的樹圖T他的近似同構值會是2n - 4。而在要做結束前，在第5章，我們找到一個的□*(Pn)的下界改進值。最後第6章，則是對本文的一個總結並且提出幾個尚未解決的問題。

Let f be a permutation of V(G). Define □f (x,y)=|dG(x,y)-dG(f(x),f(y))| and the total relative displacements of permutation f in G, □f (G)=□□f (x,y), over all the unordered pairs {x,y} of distinct vertices of G. The smallest positive value of □f (G) among all the permutations f of V(G) is denoted by □(G) and the maximum value of □f (G) among all the permutations f of V(G) is denoted by □*(G). The permutation f with □f (G) = □(G) is called a near automorphism of G and the permutation g with □g(G) = □*(G) is called a chaotic mapping of G. This thesis is devoted to investigate the permutations which are near automorphisms and chaotic mappings respectively. In Chapter 1, we start with an introduction of the total relative displacement and present a short survey of the existing literature. Then, in Chapter 2, we study the graphs with small near automorphism values, and we mainly characterize certain graphs G with □(G) = 2 and trees T with □(T) = 4. In Chapter 3, our focus will be on the near automorphisms of the cycles Cn and we prove that □(Cn) = 4□n/2□-4 for n □ 4. We then study the trees T of order n with □(T) = 2n-4, n □ 3, in Chapter 4. (2n-4 is the maximum total relative displacement of a near automorphism of an order n graph.) Before the end of this thesis, we also study the lower bound of □*(G) for some graph G. We obtain a better lower bound of paths Pn than the currently known one. Finally, we conclude this thesis with several remarks which include the direction of further study and open problems.