求蜂窩圖最大的蜂窩對稱性對稱性:以蜂窩22來看,其對稱數為14=max{5,11,14}(從三個軸來看)因此其最大對稱性為圖C12345678910121314151617182021222324212223249924228213314172134589101516172021222324圖A:5個蜂窩圖B:11個蜂窩圖C:14個蜂窩123456789101213141516182023本圖最大的蜂窩對稱性為不考慮中空的蜂窩圖12345678910121314151617182021222324點座標XYZ(1,0,0)(0,1,0)(0,0,1)(1,1,-1)(1,2,-1)演算法考量1.每一個cell能確實地被找出來2.蜂窩與蜂窩之間的相對位置12345678910121314151617182021222324Lemma1給定一個蜂窩圖,對於蜂窩圖上任何一個蜂窩C,若已知C任意兩個邊,則可在常數時間內找出C.Definition--distance12345678910121314151617182021222324distance(3,4)=1distance(3,9)=1distance(3,22)=2distance(3,24)=3Lemma2給定一個蜂窩圖,已知蜂窩圖上兩個蜂窩C與C’,且C與C’有邊相鄰,則C與C’的相對位置可以在常數時間內找出.CC’abcdefghijupdownC:abcdefupdownC’:ihgbajupdownC’:abghijAlgorithmC1.d=12.任意挑兩個相鄰的邊e1、e2,找出包含e1、e2這兩個邊的蜂窩C.3.找出所有與蜂窩C距離為d的蜂窩4.d=d+15.若存在蜂窩與C的距離為d,則回到step3.否則結束.Complexityoftransformation•Space–,C為蜂窩個數•Time–)()(nOCO)()(nOCO)log()(?2nnOnOnnlog
