Article View/Open
(123)
Publication Export
| Citation Infomation |
| No doi shows Citation Infomation |
| 社群 sharing |
Related Publications in TAIR
- > Simple Record
- > Full Record
| Field | Value |
|---|---|
| Title: | 樹形圖具有對稱相似性 Symmetric Similarity of Trees |
| Authors: | 龔英一 |
| Contributors: | 李陽明 龔英一 |
| Date: | 1989 1989 |
| Issue Date: | 2016-05-03 14:17:45 (UTC+8) |
| Description.abstract: | 論文提要:
圖論上，談到兩點相似(similar)，是這樣定義的:若a，b是圖G上的兩點，且存在一箇定義於V (G)的某排列ϕ，滿足:(1)ϕ∈Aut (0) 及(2) ϕ(a) =b. 則稱G 之a. b兩點相似。由定義吾人固然知必有一ϕ∈Aut(O). 滿足ϕ(a) =b. 如果G之a. b兩點相似的話。然而，有人不禁會問:若G上任二點a. b相似，則是否存在一ϕ∈Aut (G) .同時滿足ϕ (a)=b 且ϕ (b) =a 呢7?(本文稱G為對稱相似(symmetrically similar). 若答案為真時。) 作者在研究GRAPH RECONSTRUCTION CONJECTURE時，亦產生相同的疑問。本文乃作者試就此一問題，將樹型圖(Tree)加以研究，發現：凡是具有有限點的樹形圖(finite tree) 皆具備此特性。 首先，吾人知: 任意樹形圖乃一不具環路的聯結圖( acyclic cconnected graph ).且任二不同點，a. b僅可決定出唯一的(a-b)路逕(path)。 本文先針對此路徑觀察出二項特性(1)當(a-b)為偶路徑，c為其中點，且ϕ (a) = b.ϕ∈Aut (G) 時，ϕ作用在c之後不變。(2)當(a-b)為奇路徑，y. z為其二中點，且ϕ (a) = b，ϕ∈Aut(G)時，ϕ作用在y. z 之後對調(即ϕ (y)=z 且φ(z)=y) 。其證明包含在定理2. 1. 7 及定理2. 1. 10 立中。 其次，以定理2. 1. 7 及定理2. 1. 10 為基礎，本文將證明出確實存在一ϕ∈Aut (G) .同時滿足ϕ (a) = b 且ϕ (b) = a. 此處G為一樹形圖。 由於找不到反例，本文將給一箇Conjecture 作為總結，即任一有限simple圖皆具對稱相似性。 [Introduction] [Introduction] It's well known in graph theory that if u and v are two vertices of a graph G and for some automophism ϕ of G. ϕ (u)=v then u and v are said to be similar. A graph G is said to be vertex-symmetric (edge-symmetric) if every pair of its vertices (edges) are similar.(see [5]. pp. 171-175) Several properties concerning these similarities have been dealt with in some papers. For example, (1) If u and v are similar, then G-u≅G-v. (see [6]) (2) Not every regular edge-symmetric graph is vertex-symmetric. (see [4]) Especially, (1) is frequently occurred in the articles about the famous problem--graph reconstruction conjecture. e.g. [2]. [7] and [8]. And probably, the research of these similarities of graphs is a key to solve this reconstruction conjecture. In this paper, we will investigate a special kind of similarity of trees. That is, we'll assert that if u and v are two similar vertices of a finite tree T. then there is an automorphism ¢ of T satisfying: ¢(u) = v and ¢(v) = u. ( In such case. we say that T is symmetrically similar (Definition 2.1.2) or T preserves symmetric similarity . ) In Part I. we only give the fundamental definitions and concepts about graph theory as the preliminaries for our main subject. And in general, we follow the terminology and notations of [1]. [3] and [5]. In Part II, we'll present some lemmas. e.g. Lemma 2.1.4. Lemma 2.1.5. Lemma 2.1.6. Lemma 2.1.8. Lemma 2.1.9 and Lemma 2.2.1 and we will prove: Theorem 2.1.7 Let T be a tree. aT ̃b and (a-b): a=X_0, X_1,…, X_(d-1), X_d=c, X_(d+1),…, X_(ad-1), X_ad, X_(ad+1)=b be an odd path of T where d<0. If ϕ(a)=b, ϕ∈Aut(T), then ϕ∈(X_1)= X_(d-1),, i=0, 1,…, d. Theorem 2.1.10 Let T be a tree. AT ̃b and (a-b): a=X_0, X_1,…, X_(d-1), X_d=y, X_(d+1)=z,…, X_(ad-1), X_ad, X_(ad+1)=b be an odd path of T where d>0. If ϕ(a)=b, ϕ∈Aut(T), then ϕ∈(X_1)= X_(d-1), i=0, 1,…, d. Theorem 2.2.2 Let T be a tree. AT ̃b and (a-b): a=X_0, X_1,…, X_(d-1), X_d=c, X_(d+1),…, X_(ad-1), X_ad=b is an even path of T where d>1, then ∃ψ∈Aut(T) s.t. (1) ψ(a)=b, ψ(b)=a and (2) ψ(x)=x, ∀x∈{w∈V(T)│Tc<w>≠Tc<a>}, Tc<w>≠Tc<b>. Theorem 2.2.3 Let T be a tree. AT ̃b and (a-b): a=X_0, X_1,…, X_(d-1), X_d=y, X_(d+1)=z,…, X_ad, X_(ad+1)=b be an odd path of T where d>0. then ∃ψ∈Aut(T) s.t. (1) ψ(a)=b, ψ(b)=a Since the length of any (a-b) path of the tree T is either even or odd, imploying Theorem 2.2.2-(1) 2.2.3. we immediately have: Theorem 2.2.4 Every Tree is symmetrically similar At last, we give a conjecture as a conclusion for this paper, i.e. Conjecture: Every simple graph is symmetrically similar. |
| Reference: | REFERENCES
[1] Berge. C .. The Theory of Graphs and its Applications. Wiley. New York (1962). [2] Bondy. J.A. and Hemminger. R.L.. Graph reconstruction－a survey. J. Graph Theory 1 (1977) 227-268. [3] Chartrand. G. and Lesniak, L., Graphs and Digraphs. Wadsworth. Inc., Belmont (1986) [4] FoIkman. J. (1967). Regular line-symmetric graphs. [5]J. Comb. Theory 3. 215-232.Harary. F., Graph Theory. Company. Inc., Mas. (1972) Addison-Wesley Publishing [6] Harary. F.and Palmer. E. (1966). The smallest graph whose group is cyclic. Czech. Math. J. 16. 70-71. [7] Nash--Williams. C. St. J. A., The reconstruction problem. [8]Selected Topics in Graph Theory. Academic Press. New York (1978) 205-236.Yang. Y.Z.,The Reconstruction Conjecture is True if All 2-Connected Graphs are Reconstructible. Theory 12 (1988) 237-243. |
| Description: | 碩士 國立政治大學 應用數學系 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#B2002005456 |
| Data Type: | thesis |
| DCField | Value | Language |
|---|---|---|
| dc.contributor.advisor | 李陽明 | zh_TW |
| dc.contributor.author | 龔英一 | zh_TW |
| dc.creator (Authors) | 龔英一 | zh_TW |
| dc.date (Date) | 1989 | en_US |
| dc.date (Date) | 1989 | en_US |
| dc.date.accessioned | 2016-05-03 14:17:45 (UTC+8) | - |
| dc.date.available | 2016-05-03 14:17:45 (UTC+8) | - |
| dc.date.issued (Issue Date) | 2016-05-03 14:17:45 (UTC+8) | - |
| dc.identifier (Other Identifiers) | B2002005456 | en_US |
| dc.identifier.uri (URI) | http://nccur.lib.nccu.edu.tw/handle/140.119/90191 | - |
| dc.description (Description) | 碩士 | zh_TW |
| dc.description (Description) | 國立政治大學 | zh_TW |
| dc.description (Description) | 應用數學系 | zh_TW |
| dc.description.abstract (Abstract) | 論文提要:
圖論上，談到兩點相似(similar)，是這樣定義的:若a，b是圖G上的兩點，且存在一箇定義於V (G)的某排列ϕ，滿足:(1)ϕ∈Aut (0) 及(2) ϕ(a) =b. 則稱G 之a. b兩點相似。由定義吾人固然知必有一ϕ∈Aut(O). 滿足ϕ(a) =b. 如果G之a. b兩點相似的話。然而，有人不禁會問:若G上任二點a. b相似，則是否存在一ϕ∈Aut (G) .同時滿足ϕ (a)=b 且ϕ (b) =a 呢7?(本文稱G為對稱相似(symmetrically similar). 若答案為真時。) 作者在研究GRAPH RECONSTRUCTION CONJECTURE時，亦產生相同的疑問。本文乃作者試就此一問題，將樹型圖(Tree)加以研究，發現：凡是具有有限點的樹形圖(finite tree) 皆具備此特性。 首先，吾人知: 任意樹形圖乃一不具環路的聯結圖( acyclic cconnected graph ).且任二不同點，a. b僅可決定出唯一的(a-b)路逕(path)。 本文先針對此路徑觀察出二項特性(1)當(a-b)為偶路徑，c為其中點，且ϕ (a) = b.ϕ∈Aut (G) 時，ϕ作用在c之後不變。(2)當(a-b)為奇路徑，y. z為其二中點，且ϕ (a) = b，ϕ∈Aut(G)時，ϕ作用在y. z 之後對調(即ϕ (y)=z 且φ(z)=y) 。其證明包含在定理2. 1. 7 及定理2. 1. 10 立中。 其次，以定理2. 1. 7 及定理2. 1. 10 為基礎，本文將證明出確實存在一ϕ∈Aut (G) .同時滿足ϕ (a) = b 且ϕ (b) = a. 此處G為一樹形圖。 由於找不到反例，本文將給一箇Conjecture 作為總結，即任一有限simple圖皆具對稱相似性。 | zh_TW |
| dc.description.abstract (Abstract) | [Introduction]
[Introduction] It's well known in graph theory that if u and v are two vertices of a graph G and for some automophism ϕ of G. ϕ (u)=v then u and v are said to be similar. A graph G is said to be vertex-symmetric (edge-symmetric) if every pair of its vertices (edges) are similar.(see [5]. pp. 171-175) Several properties concerning these similarities have been dealt with in some papers. For example, (1) If u and v are similar, then G-u≅G-v. (see [6]) (2) Not every regular edge-symmetric graph is vertex-symmetric. (see [4]) Especially, (1) is frequently occurred in the articles about the famous problem--graph reconstruction conjecture. e.g. [2]. [7] and [8]. And probably, the research of these similarities of graphs is a key to solve this reconstruction conjecture. In this paper, we will investigate a special kind of similarity of trees. That is, we'll assert that if u and v are two similar vertices of a finite tree T. then there is an automorphism ¢ of T satisfying: ¢(u) = v and ¢(v) = u. ( In such case. we say that T is symmetrically similar (Definition 2.1.2) or T preserves symmetric similarity . ) In Part I. we only give the fundamental definitions and concepts about graph theory as the preliminaries for our main subject. And in general, we follow the terminology and notations of [1]. [3] and [5]. In Part II, we'll present some lemmas. e.g. Lemma 2.1.4. Lemma 2.1.5. Lemma 2.1.6. Lemma 2.1.8. Lemma 2.1.9 and Lemma 2.2.1 and we will prove: Theorem 2.1.7 Let T be a tree. aT ̃b and (a-b): a=X_0, X_1,…, X_(d-1), X_d=c, X_(d+1),…, X_(ad-1), X_ad, X_(ad+1)=b be an odd path of T where d<0. If ϕ(a)=b, ϕ∈Aut(T), then ϕ∈(X_1)= X_(d-1),, i=0, 1,…, d. Theorem 2.1.10 Let T be a tree. AT ̃b and (a-b): a=X_0, X_1,…, X_(d-1), X_d=y, X_(d+1)=z,…, X_(ad-1), X_ad, X_(ad+1)=b be an odd path of T where d>0. If ϕ(a)=b, ϕ∈Aut(T), then ϕ∈(X_1)= X_(d-1), i=0, 1,…, d. Theorem 2.2.2 Let T be a tree. AT ̃b and (a-b): a=X_0, X_1,…, X_(d-1), X_d=c, X_(d+1),…, X_(ad-1), X_ad=b is an even path of T where d>1, then ∃ψ∈Aut(T) s.t. (1) ψ(a)=b, ψ(b)=a and (2) ψ(x)=x, ∀x∈{w∈V(T)│Tc<w>≠Tc<a>}, Tc<w>≠Tc<b>. Theorem 2.2.3 Let T be a tree. AT ̃b and (a-b): a=X_0, X_1,…, X_(d-1), X_d=y, X_(d+1)=z,…, X_ad, X_(ad+1)=b be an odd path of T where d>0. then ∃ψ∈Aut(T) s.t. (1) ψ(a)=b, ψ(b)=a Since the length of any (a-b) path of the tree T is either even or odd, imploying Theorem 2.2.2-(1) 2.2.3. we immediately have: Theorem 2.2.4 Every Tree is symmetrically similar At last, we give a conjecture as a conclusion for this paper, i.e. Conjecture: Every simple graph is symmetrically similar. | en_US |
| dc.description.tableofcontents | Table of Contents
Acknowledgements………i Abstract………ii Table of Contents………iii Introduction………1 Part I Background 1.1 Graphs………4 1.2 Isomorphisms……… 8 Part II Trees are symmetrically similar 2.1 Mapping on the path………10 2.2 The desired ϕ……… 27 Conclusion………31 References………32 | zh_TW |
| dc.source.uri (Source URI) | http://thesis.lib.nccu.edu.tw/record/#B2002005456 | en_US |
| dc.title (Title) | 樹形圖具有對稱相似性 | zh_TW |
| dc.title (Title) | Symmetric Similarity of Trees | en_US |
| dc.type (Data Type) | thesis | en_US |
| dc.relation.reference (Reference) | REFERENCES
[1] Berge. C .. The Theory of Graphs and its Applications. Wiley. New York (1962). [2] Bondy. J.A. and Hemminger. R.L.. Graph reconstruction－a survey. J. Graph Theory 1 (1977) 227-268. [3] Chartrand. G. and Lesniak, L., Graphs and Digraphs. Wadsworth. Inc., Belmont (1986) [4] FoIkman. J. (1967). Regular line-symmetric graphs. [5]J. Comb. Theory 3. 215-232.Harary. F., Graph Theory. Company. Inc., Mas. (1972) Addison-Wesley Publishing [6] Harary. F.and Palmer. E. (1966). The smallest graph whose group is cyclic. Czech. Math. J. 16. 70-71. [7] Nash--Williams. C. St. J. A., The reconstruction problem. [8]Selected Topics in Graph Theory. Academic Press. New York (1978) 205-236.Yang. Y.Z.,The Reconstruction Conjecture is True if All 2-Connected Graphs are Reconstructible. Theory 12 (1988) 237-243. | zh_TW |
NO.64,Sec.2,ZhiNan Rd.,Wenshan District,Taipei City 11605,Taiwan (R.O.C.)
11605 臺北市文山區指南路二段64號 Tel：+886-2-2939-3091
© 2016 National ChengChi University All Rights Reserved.
DSpace Software Copyright © 2002-2004 MIT & Hewlett-Packard / Enhanced by NTU Library IR team Copyright © 2006-2017 - 問題回報 Problem return