Microsoft Word - 完美標號.doc

Size: px

Start display at page:

Download "Microsoft Word - 完美標號.doc"

冥哉别
5 years ago
Views:

1 篇名 : 齒輪之不能說的秘密 ~ 完美標號之 alpha 標號 harmonious 標號作者 : 石朝俊嘉義市私立興華高中普通科二年四班薛偉呈嘉義市私立興華高中普通科二年四班陳俊儒嘉義市私立興華高中普通科二年四班指導老師 : 李佩珊老師 1

2 壹前言韓國藝人李玖哲的一首歌完美並不美道盡了做任何事物時, 追求最完美的過程中往往也會流逝一些珍貴的東西, 難道完美真的絕非最好嗎? 於是探討找尋完美的想法勃然而生, 與指導老師討論後決定探討圖形之完美標號此主題此篇介紹較為特殊的齒輪圖之完美標號 alpha 標號及 harmonious 標號, 如何讓這圖形變成最完美的圖呢? 想知道其中的奧秘, 就請您跟隨我們進入完美圖形世界裡貳正文一圖形標號的由來與應用在 1967 年, 數學家 Rosa 最先展開圖形標號的方法研究而在 1980 年,Graham 和 Sloane 追隨研究圖形標號的可應用於辨識系統實驗設計電腦網路等科學領域裡在數學領域中, 標號是圖形分割有用的工具二名詞介紹 1. 圖 graph: 圖 G 是一個有序二元組 (V,E), 其中 V( 或 VG) ( ) 稱為頂點集,E( 或 EG) ( ) 稱為邊集 ( 註一 ) 點標號 vertices-labeling: 一個函數 f 將圖的頂點集合對應到整數集合, 且定義兩頂點間之和或差值為其邊值 ( 註二 ) 3 完美標號 graceful-labeling or β -labeling: 一圖有 q 條邊, 若有一函數 f 將頂點 x, y 對應至集合 {0,1,,..., q }, 且定義 f ( x) f( y) 為其邊值, 滿足每邊值介在 0~q 皆不同, 則此標號稱為完美標號 ( 註三 ) 4 alpha 標號 alpha-labeling: 一圖具有完美標號, 存在有一臨界值 λ, 對每一邊的二端點值 f ( x), f( y ), 皆滿足 f ( x) λ < f( y) 或 f ( x) < λ f( y), 則此標號稱為 alpha-labeling 由定義可知若圖形有 alpha 標號就必須為二部圖 ( 註三 ) 5 二部圖 bipartite: 又稱雙分圖二分圖, 指頂點可以分成兩個不相交的集使得在同一個集內的頂點不相鄰 ( 沒有共同邊 ) 的圖 ( 註四 ) 6 調和標號 harmonious labeling: 一圖有 q 條邊, 一個函數 f 將頂點 x, y 集合對應至集合 {0,1,,..., q 1}, 定義 f ( x) + f( y) 為其邊值, 滿足邊值除以 q 後之餘數皆不同, 則此標號稱為調和標號 ( 註五 )

3 三齒輪圖的標號 1. 齒輪圖的定義齒輪圖 ( 註六 ), 以代號 G 表示, 是在車輪圖 (Wheel graph) 外圍上每個相鄰頂點間 n 再加入一點所形成因此, 齒輪圖就具有 n + 1個頂點及 3n 條邊其圖形展示如圖 (A) 將其頂點分成三部份 : 中心點與圓心連接的點及外圍插入的點, 並以 C Ai(1 i n) Bi(1 i n) 為三類頂點代號在 K. J. Ma and C. J. Feng 所做的論文 ( 註七 ) 研究裡, 已經找到一組優美標號, 而在此篇小論文中, 主要介紹 alpha labeling 及 harmonious labeling. 齒輪圖的 alpha 標號從眾多文獻中得知, 若一圖形有 alpha 標號, 其必要條件需為二部圖, 因此可將齒輪圖 ( 以 G 為例 ) 依照連接關係畫成二部圖如圖 (B): A1 C B1 B B1 C B A A1 A 圖 (B) 在碩博士論文 ( 註八 ) 中, 找到一 alpha 標號 f : V( x) {0,1,,...,3 n} 定義如下 : (1) n 為偶數時 f( Ai) = i 1 ; f( C) = 3 n ; f( B1) = n ; n n+ f ( Bi) = n -i + 1, 如果 i ; f ( Bi) = n - i, 如果 i n 3

4 () n 為奇數時齒輪之不能說的秘密 ~ 完美標號之 alpha 標號 harmonious 標號 f( A1) = 0 ; f( Ai) = i, 如果 i n ; f( C) = 3n-1 ; f( B1) = 3 n ; n-1 n-1 f ( Bi) = n -i +, 如果 i ; f ( Bi) = n -i + 1, 如果 + 1 i n 這是經過補邊值的方式, 使其邊值為 1~3n 之連續正整數, 再從點值找規律性所得結果, 而且此 alpha 標號的臨界值為 n 補邊值的方法以 G 為例做為解說如下 : 在下排的白點上由左向右從 0 至 n 標示, 即 A 1= 0 A = 1, 固定下排的點標號後, 依照所需的邊值填入適當的點值, 如果要產生邊值為 1, 則要在 B B 1 C 挑一點標示為, 三種情況做以下討論 : (1) B = 則產生 AB 的邊值為 1 AB 1 的邊值為, 接著要產生邊值為 3, 則可於 B 1 C 填入點值 4, 同樣地, a. 若 B 1= 4, 則可產生 AB 1的邊值為 3 且 AB 1 1的邊值為 4, 如要產生邊值為 5, 則 C 一定要標示點值為 6, 如此就能產生 AC 的邊值為 5 A1C 的邊值為 6 符合 alpha 標號定義, 則可說 G 圖可找到一組 alpha 標號 [0,1,,4,6], 如圖 (C) b. 若 C = 4, 則可產生 AC 的邊值為 3 且 A1C 的邊值為 4, 如果要產生邊值為 5, 則 B 1一定要標示點值為 6, 如此就能產生 AB 1的邊值為 5 AB 1 1的邊值為 6 也符合 alpha 標號定義, 則 G 圖可找到另一組 alpha 標號 [0,1,,6,4], 如圖 (D) 4

5 () B 1= 則產生 AB 1的邊值為 1 AB 1 1的邊值為, 接著要產生邊值為 3, 則可於 B C 填入點值 4, 同樣地, a. 若 B = 4, 則可產生 AB 的邊值為 3 且 AB 1 的邊值為 4, 如要產生邊值為 5, 則 C 一定要標示點值為 6, 如此就能產生 AC 的邊值為 5 A1C 的邊值為 6 符合 alpha 標號定義, 則可說 G 圖可找到一組 alpha 標號 [0,1,4,,6], 如圖 (E) b. 若 C = 4, 則可產生 AC 的邊值為 3 且 A1C 的邊值為 4, 如果要產生邊值為 5, 則 B 一定要標示點值為 6, 如此就能產生 AB 的邊值為 5 AB 1 的邊值為 6 也符合 alpha 標號定義, 則 G 圖可找到另一組 alpha 標號 [0,1,6,,4], 如圖 (F) (3) C = 則產生 AC 的邊值為 1 A1C 的邊值為, 接著要產生邊值為 3, 則可於 B 1 B 填入點值 4, 同樣地, a. 若 B 1= 4, 則可產生 AB 1的邊值為 3 且 AB 1 1的邊值為 4, 如果要產生邊值為 5, 則 B 一定要標示點值為 6, 如此就能產生 AB 的邊值為 5 AB 1 的邊值為 6 符合 alpha 標號定義, 則可說 G 圖可找到一組 alpha 標號 [0,1,6,4,], 如圖 (G) b. 若 B = 4, 則可產生 AB 的邊值為 3 且 AB 1 的邊值為 4, 如要產生邊值為 5, 則 B 1一定要標示點值為 6, 如此就能產生 AB 1的邊值為 5 AB 1 1的邊值為 6 5

6 也符合 alpha 標號定義, 則 G 圖可找到另一組 alpha 標號 [0,1,4,6,], 如圖 (H) 由上述所言, 圖形具有 alpha 標號不具唯一性, 而我們把補邊的方式延伸至 G 3 G G, 然後找出其規律性 4 n 3. alpha 標號圖形依照標號規則, 列出 G 5 G 6 的 alpha 標號如圖 (I) 圖(J): 4. harmonious 標號在另一篇由陳麗娟所做之碩博士論文 ( 註五 ) 中, 找到一 harmonious 標號 f : V( x) {0,1,,...,3n 1} 定義如下 : 6

7 (1) n 為偶數時齒輪之不能說的秘密 ~ 完美標號之 alpha 標號 harmonious 標號 f( A1) = 3 ; f( Ai) = n i+, 如果 i n ; f( C) = 0 ; f( B1) = 1 ; n+ n+ 4 f( Bi) = n-i+ 3, 如果 i ; f( Bi) = 3n-i+, 如果 i n 1; f( Bi) = 3n 1, 如果 i = n () n 為奇數時 f( A1) = ; f( Ai) = n+ i 如果 i n; f( C) = 0 ; f( B1) = 1 ; n+ 1 n+ 3 f( Bi) = n-i+, 如果 i ; f( Bi) = 3n-i+ 1, 如果 i n 1; f( Bi) = 3n 1, 如果 i= n 同樣地,harmonious 標號之方法同 alpha 標號的補邊值方式, 在此不再多贅述 5. harmonious 標號圖形依照標號規則, 列出 G 5 G 6 的 harmonious 標號如圖 (K) 圖(L): 叁結論齒輪圖形的完美標號 alpha 標號及 harmonious 標號皆已分別在三篇碩博士論文中均找到點邊對應方式, 且可無限延伸的標號函數, 讓齒輪圖形有完 7

8 整的標號資料而接著令我們有興趣的是 : 標號的方式不只這三種, 齒輪圖是否能找出另外的標號方式呢? 好奇的你們, 不妨利用 A Dynamic Survey of Graph Labeling 此篇論文介紹的標號種類嘗試找尋吧! 肆引註資料註一圖之點邊定義 ( 維基百科網站 ) E7.B5.84.E7.9A.84.E5.AE.9A.E7.BE.A9 ( 檢索日期 :009/03/03) 註二點標號定義 Joseph A. Gallian. A Dynamic Survey of Graph Labeling. The Electronic Journal of Combinatorics, 5(005). 註三完美標號 alpha 標號定義 C.-M. Lu. On α -labeling graphs. Master's Thesis. Chung Yuan Christian University. Taiwan, preprint. 註四二部圖定義 ( 維基百科網站 ) iant=zh-tw ( 檢所日期 :009/03/08) 註五調和標號定義齒輪圖的 harmonious 標號 L.-C. Chen. On harmonious labelings of the amalgamation of wheels. Master's Thesis, Chung Yuan Christian University. Taiwan, preprint. 註六齒輪圖定義 (Mathworld 網站 ) ( 檢所日期 :009/03/09) 註七齒輪圖的完美標號 K.-J. Ma and C.-J. Fing. On the gracefulness of gear graphs. Math. Practice Theory,(1984), 註八齒輪圖的 alpha 標號 P.-S. Lee. On α -labelings of Prism Graphs and Gear Graphs. Master's Thesis, Chung Yuan Christian University. Taiwan, preprint. 8