(3.237.97.64) 您好!臺灣時間:2021/03/09 10:05
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:楊德風
研究生(外文):Yang, De-Feng
論文名稱:從演算法觀點看樹的L(d,1)標號問題
論文名稱(外文):Algorithmic Aspeect of the L(d,1)-labelling on Trees:Revisited
指導教授:葉光清
指導教授(外文):Roger K. Yeh
學位類別:碩士
校院名稱:逢甲大學
系所名稱:應用數學研究所
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:1998
畢業學年度:86
語文別:中文
論文頁數:50
中文關鍵詞:"樹標號問題最大匹配演算法L(d1)標號"應用數學數學
外文關鍵詞:"treelabellingSDRMaximum matchAlgorithmL(d1)-labelling"APPLIED-MATHEMATICSMATHEMATICS
相關次數:
  • 被引用被引用:0
  • 點閱點閱:100
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
令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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊
 
系統版面圖檔 系統版面圖檔