求蜂窝图最大的蜂窝对称性

《求蜂窝图最大的蜂窝对称性》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、求蜂窩圖最大的蜂窩對稱性對稱性:以蜂窩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)(

2、1,1,-1)(1,2,-1)演算法考量每一個cell能確實地被找出來蜂窩與蜂窩之間的相對位置12345678910121314151617182021222324Lemma1給定一個蜂窩圖,對於蜂窩圖上任何一個蜂窩C,若已知C任意兩個邊,則可在常數時間內找出C.Definition--distance12345678910121314151617182021222324distance(3,4)=1distance(3,9)=1distance(3,22)=2distance(3,24)=3Lemma2給定一個蜂窩圖,已知蜂窩圖上兩個蜂窩C與C’,且

3、C與C’有邊相鄰,則C與C’的相對位置可以在常數時間內找出.CC’abcdefghijupdownC:abcdefupdownC’:ihgbajupdownC’:abghijAlgorithmCd=1任意挑兩個相鄰的邊e1、e2,找出包含e1、e2這兩個邊的蜂窩C.找出所有與蜂窩C距離為d的蜂窩d=d+1若存在蜂窩與C的距離為d,則回到step3.否則結束.ComplexityoftransformationSpace,C為蜂窩個數Timen