喻 衛(wèi)

（安徽三聯(lián)學院基礎(chǔ)部，安徽，合肥 230601）

0 引言

關(guān)于優(yōu)美樹的討論是數(shù)學家 G.Ringel在 1963年和1966年A.Rosa的一篇論文中提出的，在之后很多數(shù)學家在這方面作了大量的工作；并且于1996年由A.Rosa提出了著名的優(yōu)美樹猜想（在文獻[1]的第十五個未解決的問題）；幾十年來國內(nèi)外許多學者從各方面研究此問題[2-11]。本文在前人基礎(chǔ)之上進行討論，擴大了優(yōu)美樹的種類。文中所討論的圖都是無向圖，分別表示圖G的頂點集和邊集。未給出的記號和定義見參考文獻[9]。

定義1一棵有n個頂點的樹T,若存在集合{0,1,2,3,4,… ,n-1}分配給它頂點的一個標號為θ，使得由(uv)=定義的邊誘導標號分配給各邊以不同的標號，則稱樹T是優(yōu)美的。

定義2兩棵樹在根點處用一條線相連，形成的圖稱之為樹的根積。n棵樹T的根積記為，另外定義中的子樹按逆時針標上，并記根點u的那棵樹為（見圖 1）。

定義3n棵樹T的根點(即對稱點)同時與一個頂點連接，形成的樹稱為n棵樹T的根和，記為nT。

定義4G是一個非空集合，優(yōu)美樹，且優(yōu)美樹T對于加法、乘法具有封閉性。單位元為空圖，逆元為，則稱G為一個優(yōu)美樹群。

乘法即在根點處用一條直線相連（見圖1）。加法即在任意多棵同構(gòu)樹之間添加一個原點然后分別與根點連接（見圖2）。

圖1 n棵樹T的根積記為Fig.1 The root product of n tree T is recorded as

圖2 n棵樹T的根和記為Fig.2 The root sum of n tree T is recorded as

定義5一棵樹存在一條割邊，能使割邊分開的兩部分完全一樣，則稱這樣的割邊為完全割邊。

定義6一棵樹存在一個這樣的一個割點，能使割點分開的左側(cè)和右側(cè)完全一樣，則稱這樣的割點為完全割點。

定義7一棵樹在某一頂點或者在某一邊進行一刀切，使得分成兩邊的樹完全重合在一起，則稱這樣的樹為完全對稱樹（見圖3，圖4）。

圖3 關(guān)于邊的完全對稱樹Fig.3 On the complete symmetric tree of edges

圖4 關(guān)于點的完全對稱樹Fig.4 On the complete symmetric tree of points

1 主要結(jié)果及其證明

定理1是優(yōu)美樹。

證明樹T的頂點數(shù)為m。樹T的優(yōu)美標號為f，邊集為E。的頂點標號為。

下面給出的標號：

對于中n為偶數(shù)時；

下面證明θ是優(yōu)美標號。

事實上，根據(jù)上述標號可知，樹的頂點標號滿足，，有。

為方便起見，記樹邊的誘導標號集合為根點組成的邊誘導標號集合為樹邊的誘導標號集合為，即

則

其中u滿足是奇數(shù)；v滿足是偶數(shù)。

其中u2滿足是奇數(shù)；v滿足是偶數(shù)；u1是T1的根點。

其中，u滿足是奇數(shù)；v滿2足是偶數(shù)；ui是Ti的根點。

其中，u滿足是奇數(shù)；v2滿足是偶數(shù)；是根點。

所以每條邊互不相同且

故θ是優(yōu)美標號，即是優(yōu)美樹。

對于中n為奇數(shù)時；下面給出優(yōu)美標號，證明同上。

所以是優(yōu)美樹。

定理2是優(yōu)美樹。

下面給出的標號：

那張狀子寫道：“列國紛爭，尚有移民移粟；天朝一統(tǒng)，何分江北江南。”對仗工整，說理透徹，令人拍案叫絕。由此可見，訟師們的智慧的確不容小覷。

,w是原點。

下面證明θ是優(yōu)美標號。

事實上，按上述標號給每個頂點標號，可得出：

同樣標記每條邊的誘導標號集=，有

下面證明每條邊是互不相同的。

證明同定理1。

對于nT中n為奇數(shù)時；

下面給出優(yōu)美標號，證明同上。

定理3 G是一個優(yōu)美樹群。

證明由定理1知一棵優(yōu)美樹T在群中的乘法具有封閉性。由定理2知在群中的加法也具有封閉性。群中的單位元是空白圖（即沒有點和邊的圖）用記號T0表示。群中的逆元是，故優(yōu)美樹對加法與乘法構(gòu)造的集合是一個優(yōu)美樹群。

定理4在優(yōu)美樹群中的元素合成是一棵新的優(yōu)美樹的充分必要條件是每個組成部分都是優(yōu)美的。

證明在代數(shù)中任意一個多項式都可以表示成

則在優(yōu)美樹群中任何一棵新的優(yōu)美樹都可以分解成

證明必要性：

因為，，…，是優(yōu)美的。

當,…中只有一個不為0時，由定理1和2知定理成立。

當,… ,中至少有兩個不為0時，不妨假設不等于0。

則證明構(gòu)成的是一棵優(yōu)美樹。

由定理1的優(yōu)美標號知，每棵子樹的根點分別為,,… ,，原點為。

結(jié)合定理1，定理2的標號知，所要證明的問題轉(zhuǎn)化成(… ,,w)的標號是m優(yōu)美標號序列，

又因為這些點構(gòu)造而成的直徑是為5的樹，直徑為5的樹是優(yōu)美的[3]，故這些根點標號構(gòu)成了一個m優(yōu)美標號。所以在由加法的標號知，形成新的樹是優(yōu)美的，其中根點必然與原點連接。

下面證明：

由群中的加法知：在圖中添加一些直徑為2的子樹與根點鄰接，整個圖就構(gòu)造成直徑為5的樹。由直徑為5的樹是優(yōu)美樹知，是優(yōu)美樹，必要性證畢。

證明充分性：

由定理1知道任意直徑為或者5的樹經(jīng)過加法和乘法法則形成的樹是優(yōu)美的?，F(xiàn)在在優(yōu)美樹群中把這樣構(gòu)造而成的樹進行分解，看分解而成的每一部分的子樹是否是優(yōu)美的。定義是空白樹（沒有點和邊的圖）。對以下兩點進行討論：

(1) 如果這棵樹在優(yōu)美樹群中不可以分解的（即在加法和乘法下它不能拆分），那么的組成就是它本身。那么以其本身形成的

故每一部分是優(yōu)美的。

(2) 如果這棵樹在優(yōu)美樹群中在加法和乘法下可以分解，因為是一棵優(yōu)美樹，則可以把按照優(yōu)美群中的加法和乘法進行分解必然可以得到

由分解方法知每個部分顯然是優(yōu)美的。故定理成立。

定理5如果一棵樹能被“一刀切”，那么這棵樹是優(yōu)美的。

證明如果一棵樹存在完全割邊或者完全割點，對其邊進行切割或者對其割點進行切割，就會形成兩個部分，每個部分的直徑都是一樣的且每一部分的直徑比切割之前樹的直徑要小。如果這樣的樹能夠一直切割下去最終得到每一部分的直徑小于等于 5，則稱原始的樹（即未切割之前的樹）是優(yōu)美的。現(xiàn)分四種情況給出其證明。

情況⑴原始樹T僅存在完全割邊。在這里我們規(guī)定每切割一次形成的子樹（兩部分是完全一樣的）記為1T，切割k次，形成的子樹記為。當進行k次切割過后，形成子樹為且其直徑小于等于5，則稱樹T是優(yōu)美的。因為進行次切割過后，樹T被分成了個完全相同的部分，因為是優(yōu)美的[3]，由定理1知是優(yōu)美的，又，則是優(yōu)美的。則依次類推出是優(yōu)美的，又，則T是優(yōu)美的。

情況⑵原始樹T僅存在完全割點。原始樹T進行k次切割過后，樹T被分成了個完全相同的部分Tk，若Tk的直徑小于等于 5[3]，則稱樹T是優(yōu)美的。由定理2知是優(yōu)美的，又，則是優(yōu)美的。則依次類推出優(yōu)美的，又，則T是優(yōu)美的。

情況⑶原始樹T不可能同時存在完全割邊和完全割點。因為樹的頂點數(shù)與邊數(shù)的關(guān)系為n=m+1，其中n為樹的頂點數(shù)，m為樹的邊數(shù)。n,m互為奇偶的，故不可能同時存在完全割點和完全割邊。

情況⑷原始樹T第一次切割時存在完全割邊（完全割點），切割依次過后存在完全割點（完全割邊），進行k次切割過后，形成子樹為Tk且其直徑小于等于5，則稱樹T是優(yōu)美的。由定理1和定理2及以上情況⑴，情況⑵知這種情況是成立的。

綜上所述，為判斷一些樹是優(yōu)美樹給出了判斷方法。

[1]Burzio M, Ferrarese G. The subdivision graph of a graceful tree is a graceful tree[J]. Discrete mathematics,1998, 181(1-3): 275-281.

[2]Aldred R E L, McKay B D. Graceful and harmonious labellings of trees[J]. Bull. Inst. Combin. Appl, 1998, 23:69-72.

[3]Hrn?iar P, Haviar A. All trees of diameter five are graceful[J]. Discrete Mathematics, 2001, 233(1-3):133-150.

[4]ZHAO S H I L I N. All trees of diameter four are graceful[J]. Annals of the New York Academy of Sciences, 1989, 576(1): 700-706.

[5]Huang C, Rosa A. Decomposition of complete graphs into trees[J].Ars Combinatoria,1978（5）:23-63

[6]Bloom G S. A Chronology of the Ringel-kotzig Conjecture and the Continuing Quest to Call All Trees Graceful[J].Annals of the New York Academy of Sciences, 1979, 328(1): 32-51.

[7]Body J A , Murty u. Graph Theory with Application[M].New York:Elsevier,1976.

[8]Huang C. Further results on trees labellings[J].Utilitas Math.,1982;21C:31-48

[9]張先迪 ,李正良.圖論及其應用[M]. 北京:高等教育出版社,2005.

[10]喻衛(wèi),劉二根. 一類樹 Tk1⊕k3的優(yōu)美性[J].宜春學院學報,2013,35(6）:10-11,67.

[11]丁宗鵬, 喻衛(wèi), 徐保根. 關(guān)于圖的符號路 (點) 控制[J].宜春學院學報, 2012, 34(4): 4-6.