(35.175.212.130) 您好!臺灣時間:2021/05/17 20:59
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:謝宏政
研究生(外文):Hsieh,Hung Cheng
論文名稱:一個新的距離二上附加條件之圖形著色法
論文名稱(外文):The Far Side of the L(2,1)-labelling
指導教授:葉光清
指導教授(外文):Yeh,Roger K.
學位類別:碩士
校院名稱:逢甲大學
系所名稱:應用數學研究所
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:1995
畢業學年度:83
語文別:中文
外文關鍵詞:L(21)圖形著色法L(12)圖形著色法著色數L(21)-labellingL(12)-labellingLabelling number
相關次數:
  • 被引用被引用:0
  • 點閱點閱:78
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
Griggs 與Yeh 在一九九0年首先對簡單圖形(simple graphs)提出L(2
,1)-labelling 的問題。若我們給定一個正數d,令G=(V,E)為一個簡單圖
形,L(2d,d)-labelling為一個非負實值函數f:v→[0,∞]使得在圖形中相
鄰的兩點x,y,其函數值差不小於 2d即|f(x)-f(y)|不小於2d,而若是x,y
距離為2時,則其函數值差不小於d|f(x)-f(y)|不小於d。他們並且已証明
了對任何L(2d,d)-labelling問題能被縮減到僅考慮非負整數值函數之
L(2, 1)-labelling。此著色數L(2,1)-labellingnumber(或L(2,1)-
number)稱為λ(G)為最小整數k,使得G上有一L(2,1)-labelling f,使得
當v屬於V時 f(v)有最大值k。  在本文中,我們把原先在距離一與距離
二上的條件稍做修改,考慮一個新的著色稱為L(1,2)-labelling。
L(1,2)-labelling為一個非負整數值函數f:v →[0,∞]使得若圖形中相
鄰的兩點x,y則|f(x)-f(y)|不小於1,若是x,y在圖形中距離為2則|f(x)-
f(y)|不小於2。我們將它的著色數L(1, 2)-labelling number定義為■(
G)最小整數m,使得圖形G上有一L(1,2)- labelling f使得當v屬於V時f(
v)有最大值m。這樣的修改有些類似補集的概念,然而並非如此。首先我
們考慮許多基本圖形的■值,然後找出含最大度數(Maximum degree)圖形
之■值的上界,並舉出二種■值接近此上界的圖形,同時也考慮直徑為二
之圖形(Diameter Two Graphs)的■值,並將■與λ在path,cycle,
wheel,tree等基本圖形及直徑為二之圖形與Inci- dent Graph,
Polarity Graph 上作一比較。

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top