臺灣博碩士論文加值系統

令G=(V,E)為一圖形，G之L(d,1)-標號為一函數f:V->{0,1,2,..}使得|f(
x)-f(y)|>=1 當d(x,y)=1；且|f(x)-f(y)|>=1，當d(x,y)=1。令f為G
之L(d,1)-標號為一函數， 定義||f(G)||=max{f(v):v屬於V(G)}，
且min||f(G)||為G之L(d,1)-標號數。 在本文主要介紹樹的L(
d,1)標號的演算法。在這個演算法中將會使用SDR，而 SDR的
問題事實上是和最大匹配的問題是等價的。因此在本文中也將介紹SDR及
最大匹配的演算法。在本文中，我們將利用Maple V撰寫程式，並將三個
程式 的執行結果分別列於第二章第三、五節及第三章第四節
。而關於實際的程式部 份我們收錄在本文最後的附錄中。

The L(d,1)-labeling of a graph G is a function f from V(G) to
the set of all nonnegative integers such that |f(x)-f(y)|>=d if
d(x,y)=1 and |f(x)-f(y)|>=1 if d(x,y)=2. A k-L(d,1)-labeling is
an L(d,1)-labeling such that no label is greater then k. The L(
d,1)-labeling number is the smallest number k such G has a k-L(
d,1)-labeling. The content introduces mainly the algorithmic
of the L(d,1)-labeling on trees. SDR will be served in this
algorithmic; in fact, the problem of SDR is equivalent to the
problem of

maximum matching . As a result, SDR and maximum matching will
be also discussed in this content. In addition, the conclusion
executived of three programs made by Maple V will be pressed
separately in the 3rd and 5th periods of the 2nd article and the
4th period of the 3rd article. Referring to practical programs,
that are enclosed in the appendices at the end of the content.