• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

樹形圖具有對稱相似性 / Symmetric Similarity of Trees

龔英一, GONG,YING-YI Unknown Date (has links)
論文提要內容: 圖論上,定義兩點相似(similar ):若a ,b 是圖G 上的兩點,且存在一個定義於 V (G )的某排列φ,滿足:(1)φAut(G)及(2)φ(a)=b,則稱G 之a,b 兩點相似。由定義吾人固然知必有一φ Aut(G),滿足φ(a)=b,如果G 之a,b 兩點相似的話。然而,有人不禁會問:若G 上任二點a,b相似 ,則是否存在一φ Aut(G),同時滿足φ(a)=b且φ(b)=a呢?( 本文稱G 為 對稱相似(symmet-rically similar),若答案為真時。) 作者在研究GRAPH RECONSTRUCTION CONJECTURE 時,亦產生相同的疑問。本文乃作者 試就此一問題,將樹形圖(Tree)加以研究,發現:凡是具有有限點的樹形圖(fin- ite tree)皆具備此特性。 本文共分二章四節。首先,吾人知:任意樹形圖乃一不具環路的聯結圖(acyclic c- onnected graph),且任二不同點a ,b 僅可決定出唯一的(a-b)路徑( path ) 。 本文先針對此路徑觀察出二項特性:(1)當(a-b)為偶路徑,m 為其中點,且φ (a)=b,φ Aut(G)時,φ作用在m,n之後對調(即φ(m)=n且φ(n )= m 。其證明包含在定理2.1.7及定理2.1.9之中。 其次,以定理2.1.7及定理2.1.9為基礎,本文將證明出:確實存在-φ Aut(G),同時滿足φ(a)=b且φ(b)=a,此處G 為一樹形圖。 由於找不到反例,本文將給一個Conjecture作為總結,即:任一有限simple圖皆具對 稱相似性。

Page generated in 0.0186 seconds