篇名 : 齒輪 之不能說的秘密 ~ 完美標號之 alpha 標號 harmonious 標號 作者 : 石朝俊 嘉義市私立興華高中 普通科二年四班薛偉呈 嘉義市私立興華高中 普通科二年四班陳俊儒 嘉義市私立興華高中 普通科二年四班 指導老師 : 李佩珊老師 1
壹 前言 韓國藝人李玖哲的一首歌 完美並不美 道盡了做任何事物時, 追求最完美的過程中往往也會流逝一些珍貴的東西, 難道完美真的絕非最好嗎? 於是探討 找尋完美的想法勃然而生, 與指導老師討論後決定探討 圖形之完美標號 此主題 此篇介紹較為特殊的 齒輪圖 之完美標號 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 後之 餘數皆不同, 則此標號稱為調和標號 ( 註五 )
三 齒輪圖的標號 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
() 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
() 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
也符合 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
(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
整的標號資料 而接著令我們有興趣的是 : 標號的方式不只這三種, 齒輪圖是否能找出另外的標號方式呢? 好奇的你們, 不妨利用 A Dynamic Survey of Graph Labeling 此篇論文介紹的標號種類嘗試找尋吧! 肆 引註資料 註一 圖之點 邊定義 ( 維基百科網站 ) http://zh.wikipedia.org/w/index.php?title=%e5%9b%be&variant=zh-tw#.e4.ba.8c.e5.8 5.83.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. 註四 二部圖定義 ( 維基百科網站 ) http://zh.wikipedia.org/w/index.php?title=%e4%ba%8c%e9%83%a8%e5%9c%96&var 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 網站 ) http://mathworld.wolfram.com/geargraph.html ( 檢所日期 :009/03/09) 註七 齒輪圖的完美標號 K.-J. Ma and C.-J. Fing. On the gracefulness of gear graphs. Math. Practice Theory,(1984), 7-73. 註八 齒輪圖的 alpha 標號 P.-S. Lee. On α -labelings of Prism Graphs and Gear Graphs. Master's Thesis, Chung Yuan Christian University. Taiwan, preprint. 8