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.0219 seconds