本帖最后由 aoe1981 于 2018-1-18 13:49 编辑
发几个小工具_完全展开图论中环形顶点染色问题
内容繁多，思绪凌乱，捋了半天，就先从给定的正方形（以至于正1、2、3、……、n边形及至圆，同理可得）的顶点的标注开始吧。如下图：
对于正方形顶点染色的问题，我们要标注的事实上有两种：一是顶点的名称，一是顶点的颜色。其中：顶点我们假定位置、次序不变，变化的是其颜色，也即下文所说的“置换”我们可以理解为顶点不变而置换其颜色。这时就有不同的习惯，为不至于造成不必要的混乱，此处声明。我们可以用数字序号表示顶点，也可以表示颜色，字母符号则表示颜色或顶点，此处我选择用数字序号表示顶点，方便确定顶点位置、次序的不变，用字母表示颜色。当然，这只是习惯而已，我的做法不具代表性。于是，给定一种染色方案，可以完整地如下表示： 1 2 3 4 a b c d 当然，这时您会发现用了4种不同的颜色，事实上可以选用任意种颜色，比如：2种颜色，甚至5种颜色。所以用和顶点数相同的颜色数举例，是为了方便展现下文置换的效果，这只是理解上的需要。
一、什么是置换？
一个4元置换f可以用符号可以表示为（一般情况为n元置换，此处以正方形为例）：
从左到右的次序表示顶点1、2、3、4的着色，经过f置换，顶点1的着色由a变为d，顶点2的着色由b变为a，顶点3的着色由c变为b，顶点4的着色由d变为c。 这样的4元置换一共有4!=24（个），这是根据乘法原理可以得到的易理解的。
二、什么是置换群？ 我们重点要考察的是由以上置换所组成的集合。显然，对于上面的例子，最大的集合包含所有24个置换。这个最大的集合作成一个群，可以称为置换群，表示为： S4={f|f是4元置换} 既然有集合的概念，为什么又要创造一个“群”的概念呢？简单回答，是因为群不是一般的集合，而是满足特定条件的集合。换个角度理解，就是对于以上4元置换组成的集合，有许许多多，比如：0个4元置换组成的空集φ、1个4元置换组成的集合、2个4元置换组成的集合、……、直到24个4元置换组成的最大集合。总数应当是2^24个，够多，这还只是4元置换的，n元置换所有的集合总数为：2^(n!)个。这些集合并不都是具有好的性质，借用一个概念，众多集合往往是平凡的，只有特定的集合才是不平凡的。群就是一些不平凡的集合。 一个集合G怎样才能做成一个群？要满足3个条件： 1.合成运算封闭。我们习惯的运算是加、减、乘、除，运算对象是数。现在，运算对象变了，是置换，运算也要重新定义，叫做合成运算，用圈ο表示。比如： f∈G，g∈G，定义在G上的圈运算写为：fοg 怎样理解这个运算呢？类似于复合函数。fοg的意思是先进行g置换，再将结果进行f置换。顺序是从右到左。这个运算的实质就是置换可以施加多次。 定义好运算以后，关键的一点就是：封闭。如果一个由置换组成的集合G，其元素进行圈运算后，结果仍在集合G当中，我们称这个集合G对圈运算封闭。表示为： ∀ f∈G，∀ g∈G，fοg∈G 这时，集合G已经比很多集合“好”多了。但是要成为“群”，还不够。 2.有单位元。记作L（这个符号读作：yi ao ta，不是字母L，只是找了个最像的），基本性质如下： L∈G ∀ f∈G， Lοf= fοL=f
单位元L是这样的一个置换：
也就是说啥也不动，也叫恒等置换。其作用类比于加法运算中的0，乘法运算中的1。通俗点讲就是，单位元与其他任何元素作定义其上的运算时，结果还是那个元素本身。 3.有逆元。表示为： ∀ f∈G，有：f^-1∈G，且：fοf^-1= f^-1οf=L 逆元可类比于对于加法的正负数，对于乘法的倒数。 到此，如果一个由置换作为元素组成的集合G满足以上3个条件后，G便作成一个群，叫做置换群。置换群是极好的集合。
三、置换群的“好”与“坏” 显然，所有4元置换集合S4作成一个最大的置换群，因为： 1.对其间任意元素做任意次的迭加置换（即圈运算），其结果仍是一个置换，且在S4中，因为S4就包括所有的4元置换，结果无出其右。 2.恒等置换包含其中。 3.任一置换都有逆元存在。单位元的逆元是其本身，其他的比如：
二者显然互为逆元。有些置换其逆元是其他的置换，有些置换的逆元则是其本身。总之，S4满足这一条。 同样显然，单独一个{L}，即恒等置换作成一个最小的群。 空集φ是最赖皮的，可以说拥有所有性质，也可以说啥性质都没有。他的存在，往往是为了理论的自我完善，实际意义不大。就好像写代码时，经常要考虑等于0、1时会不会出错。 总之，上面谈到的两个群，S4最大，元素太多了，{L}最小，元素只有一个，都是不太好的群，称呼为平凡的群。在那些比{L}大的S4的真子群中，往往存在性质更好的群，在许多问题中能化腐朽为神奇。我们称这些群为不平凡的群。
四、如何找到不平凡的群 其实不平凡的群据我理解是和解决问题息息相关的。以上例：从R、B两色中对正方形顶点进行不同着色的问题入手谈谈。
首先是全染色方案，这个很简单：4个顶点，2种颜色，每个顶点都有2种颜色选择，共有2^4=16（种）染色方案。形如： RRRR,RRRB,RRBR,RRBB,RBRR,RBRB,RBBR,RBBB, BRRR,BRRB,BRBR,BRBB,BBRR,BBRB,BBBR,BBBB, 请注意：此时顶点的次序是不变的，每种染色方案从左至右都为顶点1、顶点2、顶点3、顶点4的对应染色。 如果问题止于此，则省去了许多折腾。但事实是，以上全染色方案中的许多方案都被认为是相同的，或是重复的。这是因为，我们不是以静止的角度看问题，而是让正方形动了起来。怎么动？从这个实际问题中来，影响我们对其是否为不同染色方案判断的图形运动是旋转变换和对称变换。
其次是旋转变换。 对于正方形而言，旋转变换有4个，记为：L,ρ4,ρ4^2,ρ4^3，其中：L=ρ4^0，ρ4=ρ4^1（ρ读作：rou，不是字母p、P）。什么意思？4个顶点将圆周角分为4个直角，上述4个旋转变换分别为将正方形旋转（逆时针考虑，其实顺逆无所谓，都能转回去）0°、90°、180°、270°。360°和0°自然效果是一样的，都是原地不动，也即所谓恒等变换。为了便于考虑顶点的染色问题，我们假定顶点不动，而只对顶点上的颜色进行旋转变换，于是就有：
列表为： 1 2 3 4 a b c d d a b c c d a b b c d a 当然，此处我又用了4种颜色，如果只用RB，则对于一种染色方案RRBB，会变换为： RRBB，BRRB，BBRR，RBBR 是不是不太直观了？呵呵
再次是对称变换。 对于正方形而言，对称变换也有4个，记为：τ1,τ2,τ3,τ4，τ读作：tao，不是字母t、T。这又是什么意思？如下图：
此时，列表为： 1 2 3 4 τ1 a d c b τ2 b a d c τ3 c b a d τ4 d c b a 对称轴有4条，其中2条是对应顶点连线，2条是对边中点连线。 如果颜色只用RB，则对于一种染色方案RRBB，会变换为： RBBR，RRBB，BRRB，BBRR
最后是考察上述8个变换（与“置换”的说法个人感觉在于运算规则和表达符号上的不同，对于此问题二者实质相同）的集合： G={L,ρ4,ρ4^2,ρ4^3,τ1,τ2,τ3,τ4} 很幸运，这个集合作成一个群，他果然是S4的真子群！！！这是因为： 1.对圈运算封闭。其间任意个置换迭加后的结果仍是这8个置换之一，且有一些有趣的现象： ρορ→ρ，τοτ→ρ，所有ροτ1→τ的全体 什么意思？即：两个旋转变换效果的迭加还是一个旋转变换；两个对称变换效果的迭加也是一个旋转变换；先进行对称变换τ1，再逐一进行所有旋转变化，可以得到全体对称变换（但请注意标号并不是简单对应的，比如：τ3=ρ4^0οτ1）。这说明G可以进一步简化： G={ρ4^0,ρ4^1,ρ4^2,ρ4^3, ρ4^0οτ1,ρ4^2οτ1, ρ4^1οτ1, ρ4^3οτ1} 即： G={L,ρ4,ρ4^2,ρ4^3,τ1, ρ4^2οτ1,ρ4οτ1, ρ4^3οτ1} 这说明，集合G中的8个变换中有3个变换是核心变换：恒等变换L、旋转变换ρ4、对称变换τ1。这个特点在我做自定义函数小工具时起到了莫大的帮助。 2.存在单位元即恒等变换L。 3.每个变换都有逆元。值得注意的是：一个对称变换的逆元是其本身。可以直观想到，同一对称变换施加两次，又回到了初始的状态。用符号表示为： (ρ4^i)^-1=ρ4^(4-i)，i取值：0、1、2、3 (τi)^-1=τi，i取值：1、2、3、４
这个群G就是一个不平凡的群，原因与计算并寻找正方形顶点的不同染色方案的问题有关。现在，可以给出一个概括结论（这也是我的折腾心得）： 如果对于一个染色方案，在经历上述8种变换后都能保持不变或稳定，我们将其计数为1，从计算的角度出发，计数为：8/8。这样的方案很容易找，有两种：RRRR，BBBB（联系实际很简单，颜色都一样嘛，自然是很稳定，嘻嘻）。 如果一个染色方案经历以上8种变换后，不变（稳定）的有i种，我们将其计数为i/8。 对全染色方案进行上述计数的求和即为不同染色方案数。至于具体方案从我做的VBA附件结论中可以看出，需在每一种不同方案的8个不同表示中随便选一种作为代表即可，大抵为群论中的“互异代表”是也。
| 
沪公网安备 31011702000001号 沪ICP备11019229号-2
发表于 2018-1-17 12:06
楼主
