16-置换群的应用.ppt
《16-置换群的应用.ppt》由会员分享,可在线阅读,更多相关《16-置换群的应用.ppt(17页珍藏版)》请在三一文库上搜索。
1、置换群的应用,离散数学 第16讲,上一讲内容的回顾,变换和变换群 置换及其表示 置换群 任意群与变换群同构 置换群的应用,置换群的应用,置换群诱导的等价关系 轨道 轨道的大小 轨道的个数-Burnside定理 Burnside定理的应用,相同?不同?,f(x,y,z,t),4个变量, 可能的输入值有24个; 因此, 可以定义216(65,536)个不同的函数。,但是,真的需要这么多种电路吗?,f(x,y,z,t),由于对称性,只要调整接入线,同样的电路可以实现不同的函数。,等价类计数,如果定义上述函数的集合上的关系R:函数f1, f2满足关系关系R当且仅当它们可以用同一个电路实现(只需调整接入
2、方式,也可以用外部转相器)。 显然,上述关系R是等价关系。 可以用同一电路实现的所有函数包含在同一个等价类中。 因此,计算需要多少种不同电路才能实现所有可能的函数问题就转化为等价类计数问题。,对称在计数中的作用,用6种不同颜色给正方体的六个面着色,每个面有6中选择,假如给定每个面的编号,不同的着色序列有6!(=720)个,但哪些是“真正”不同的?,因此:不同的着色有6!/(6+3+6+8+1)=30种,更一般的情况,如果不是每个面的着色都不同, 比如有两个面是红的,如何判断两种着色是“真正”不同? 设着色对象的集合是S,允许使用的颜色的集合是C(我们只考虑有限集)。一种着色方案就是一个函数f:
3、SC。f与f2被认为“实际上”是一样的,当且仅当在所允许的变换(即前面例子中的对称旋转)下, f1能转变为f2或相反。 而对称旋转即置换群的元素。我们称“(置换)群作用于S,也作用于C。”,比立方体简单一点的例子,3个黑珍珠和6个白珍珠能做出多少样式不同的项链?,置换群诱导的等价关系,假设G是集合X上的置换群。定义X上的关系“”如下: x,yX, xy gG, 使得g(x)=y “”是等价关系 自反性:置换群中的单位元素一定是恒等映射。 对称性:由群的逆元素性保证。 传递性:由群的封闭性保证。 将关系“所决定的等价类记为Gx: Gx=y|yX, 且gG, 使得g(x)=y 这样的等价类称为X上
4、G的轨道。,保持x不变的置换构成子群,G中所有“将x变为y”的置换构成的集合: G(xy) = g|gG, 且g(x)=y G中所有“保持x不变”的置换的集合: Gx=g|gG, 且g(x)=x 注意:Gx构成子群(只需证明封闭性)。 G(xy)是Gx的右陪集:hG(xy), G(xy)=Gxh 若Gxh, 令=h(Gx), 则xX, (x) = h(x) = h(x) =y, G(xy) 若 G(xy), 则xX, h-1(x)=h-1(y)=x, 即h-1Gx, Gxh,轨道的大小,子群与相应的陪集等势,因此:若yGx, |G(xy)|=|Gx|, 否则|G(xy)|=0。 对任意xX,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 16 置换 应用
链接地址:https://www.31doc.com/p-3404457.html