李德財臺灣大學：資訊工程學研究所陳奕先Chen, Yi-xianYi-xianChen2007-11-262018-07-052007-11-262018-07-052006http://ntur.lib.ntu.edu.tw//handle/246246/53742優美標號(Graceful labeling)最早是由Rosa在1966年提出。一個graph G上的端點標號(vertex labeling)所指的是一個vertex的函數f對應到一些數值(即標號)，而G上的每一edge xy 被指定一個由f(x)和f(y)所決定的數值。如果這樣的一個f:V-->{0,1,...|E|}是單射，且指定 edge xy 的數值為|f(x)-f(y)|而所有的edge都被指定不同的數值，則f被稱為一個優美標號。 Rosa提出假說猜測所有的tree都有優美標號，這個問題懸宕了四十多年。而除了tree以外許多其他的graph上的優美標號也都有研究結果提出。 我的研究發現，在三維和四維的網格上，只要這個網格的三個邊長(三維)或四個邊長(四維)並非全為奇數也並非全為偶數，則這個網格上存在優美標號。Graceful labeling was first introduced by Rosa in 1966. A vertex labeling of a graph G is an assignment f of labels to the vertices of G that induces for each edge (xy) a label depending on the vertex labels f(x) and f(y). An assignment f is called a graceful labeling of a graph G if f is an injection from the vertices of G to the set{0, 1, ..., |E|}, such that, when each edge (xy) is assigned the label |f(x)-f(y)|, the edge labels are distinct. Rosa conjectured that all trees are graceful, which is an open question for more than 40 years. Besides the trees, many other graphs have been studied. My study shows that any grid in 3-dimension and 4-dimension with its lengths not all odd neither all even, is graceful. A formula to give an alpha-labeling on such grids is also given in thisIntroduction 4 2 2-Dimensional Grids 6 2.1 Labeling On A Path . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Labeling On Pn X Pm . . . . . . . . . . . . . . . . . . . . . . . . 8 3 3-Dimensional Grids 15 3.1 Labeling on Pn X Pm X P2 . . . . . . . . . . . . . . . . . . . . . . 15 3.2 Pn X Pm X P2k: stack k copies of Pn X Pm X P2 together . . . . . 24 3.3 P2n X P2m X P2k and P2n+1 X P2m+1 X P2k+1 . . . . . . . . . . . 30 4 4-Dimensional Grids 32 4.1 Labeling on Pn X P2m+1 X P2k X Pj . . . . . . . . . . . . . . . . 32 5 Conclusion 361304639 bytesapplication/pdfen-US優美標號網格alpha標號graceful labelinggridalpha labelingthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53742/1/ntu-95-R93922137-1.pdf