求蜂窝图最大的蜂窝对称性.ppt
( 4.5 )《求蜂窝图最大的蜂窝对称性.ppt》由会员分享，可在线阅读，更多相关《求蜂窝图最大的蜂窝对称性.ppt（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、求蜂窩圖最大的蜂窩對稱性求蜂窩圖最大的蜂窩對稱性對稱性:以蜂窩22來看,其對稱數為 14=max5,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、,2,-1)演算法考量演算法考量1.每一個每一個cell能確實地被找出來能確實地被找出來2.蜂窩與蜂窩之間的相對位置蜂窩與蜂窩之間的相對位置12345678910121314151617182021222324Lemma 1給定一個蜂窩圖給定一個蜂窩圖,對於蜂窩圖上任何一個蜂窩對於蜂窩圖上任何一個蜂窩C,若已知若已知C任意兩個邊任意兩個邊,則可在常數時間內找出則可在常數時間內找出C.Definition-distance12345678910121314151617182021222324distance(3,4)=1distance(3,9)=1distance(3,22)=2distanc
3、e(3,24)=3Lemma 2給定一個蜂窩圖給定一個蜂窩圖,已知蜂窩圖上兩個蜂窩已知蜂窩圖上兩個蜂窩C與與C,且且C與與C有邊相鄰有邊相鄰,則則C與與C的相對位置可以在常數時間內找出的相對位置可以在常數時間內找出.CCabcdefghijupdownC:a b c d e fupdownC:i h g b a jupdownC:a b g h i jAlgorithmC1.d=12.任意挑兩個相鄰的邊任意挑兩個相鄰的邊e1、e2,找出包找出包含含e1、e2這兩個邊的蜂窩這兩個邊的蜂窩C.3.找出所有與蜂窩找出所有與蜂窩C距離為距離為 d 的蜂窩的蜂窩4.d=d+15.若存在蜂窩與若存在蜂窩與C的距離為的距離為d,則則回到回到step 3.否則結束否則結束.Complexity of transformationSpace ,C為蜂窩個數Time n
- 配套讲稿：
如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制：
部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词：
- 蜂窝 最大 对称性
淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
限制150内