CayLey引自Wikipedia

rockylinux

               
v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}

  Normal
  0
  false
  
  
  7.8 磅
  0
  2
  
  false
  false
  false
  
  EN-US
  ZH-CN
  X-NONE
  
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
  
  MicrosoftInternetExplorer4
  
   
   
   
   
   
   
   
   
   
   
   
  

  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  

/* Style Definitions */
table.MsoNormalTable
        {mso-style-name:普通表格;
        mso-tstyle-rowband-size:0;
        mso-tstyle-colband-size:0;
        mso-style-noshow:yes;
        mso-style-priority:99;
        mso-style-qformat:yes;
        mso-style-parent:"";
        mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
        mso-para-margin:0cm;
        mso-para-margin-bottom:.0001pt;
        mso-pagination:widow-orphan;
        font-size:10.5pt;
        mso-bidi-font-size:11.0pt;
        font-family:"Calibri","sans-serif";
        mso-ascii-font-family:Calibri;
        mso-ascii-theme-font:minor-latin;
        mso-hansi-font-family:Calibri;
        mso-hansi-theme-font:minor-latin;
        mso-font-kerning:1.0pt;}
凯莱图
在数学中，凯莱图也叫做凯莱着色图是编码离散群的图。它的定义是凯莱定理(以阿瑟·凯莱命名)所暗含的，并使用这个群的特定的通常有限的生成元集合。它是组合群论与几何群论的中心工具。


在两个生成元 a 和 b 上的
自由群
的凯莱图




二面体群 D4 在两个生成元 α 和 β 上的凯莱图。
定义
假设 G \, 是群而 S \, 是生成集。凯莱图 \Gamma=\Gamma(G,S) \, 是如下构造的着色的有向图。
    *
G \, 每个元素 g \, 指派一个顶点: \Gamma \, 的顶点集合 V(\Gamma) \, 同一于 G \,。
    *
S \, 的每个生成元 s \, 指派一种颜色 c_s \,。
    *
对于任何 g\in G, s\in S，对应于元素 g \, 和 gs \, 的顶点用颜色 c_s \, 的有向边连接。因此边集合 E(\Gamma) \, 由形如 (g, gs) \, 的有序对构成，带着 s\in S 提供的颜色。
在几何群论中，集合 S \, 通常被假定为有限的、“对称的”也就是 S=S^{-1} \,，并且不包含这个群的单位元。在这种情况下，凯莱图是正常的图: 它的边没有方向并且不包含环路。
例子
    *
假设 G = Z 是无限循环群而集合 S 有标准生成元 1 和它的逆元(用加法符号为 −1)构成，则它的凯莱图是无穷链。
    *
类似的，如果 G = Zn 是 n 阶循环群而 S 由两个元素构成，G 的标准生成元和它的逆元，则凯莱图是环图 Cn。
    *
群的直积的凯莱图是对应的凯莱图的笛卡尔积。因此带有四个元素(±1, ±1)组成的生成集的阿贝尔群 Z2 的凯莱图是在平面 R2 上无穷网格，而带有类似的生成集的直积 Zn × Zm 的凯莱图是在环面上 n 乘 m 有限网格。
二面体群 D4 在两个生成元
α 和 β 上的凯莱图。
    *
二面体群 D4 在两个生成元
α 和 β 上的凯莱图列于右侧。红色箭头表示左乘元素 α。因此元素 β 是自我逆转的，表示左乘元素 β 蓝色线是无方向的。因此这个图是混合的: 它有 8 个顶点，8 个有向边，4 个边。群 D4 的凯莱表可以从群展示得出:
   
\langle \alpha, \beta | \alpha^4 = \beta^2 = e, \alpha \beta = \beta
\alpha^3 \rangle 。
    *
在对应于集合 S = {a, b, a−1, b−1} 的两个生成元 a, b 上的自由群的凯莱图列出在文章开头，这里的 e 表示单位元。沿着边向右走表示右乘 a，而沿着变向上走表示乘以 b。因为自由群没有关系，它的凯莱图中没有环。这个凯莱图是证明巴拿赫-塔斯基悖论的关键因素。
特征
群 G 通过左乘作用在自身上(参见凯莱定理)。这个作用可以看作 G 作用在它的凯莱图上。明显的，一个元素 h\in G 映射一个顶点 g\in V(\Gamma) 到顶点 hg\in V(\Gamma)。凯莱图的边集合被这个作用所保存: 边 (g,gs) 变换成边 (hg,hgs)。任何群在自身上的左乘作用是简单传递的，特别是凯莱图是顶点传递的。这导致了凯莱图的下列特征:
    图 Γ 是群 G 的凯莱图，当且仅当它通过图自同构许可 G 的简单传递作用(就是保存边的集合)。
要从一个凯莱图
Γ = Γ(G,S) 恢复群 G 和生成集 S，选择一个顶点 v_1\in V(\Gamma) 并标记上这个群的单位元。接着对每个
Γ 的顶点 v 标记上变换 v1 到 v 的 G 的唯一元素。产生 Γ 为凯莱图的 G 的生成元的集合 S 是毗连到选择的顶点的顶点的标记的集合。生成集合是有限(这是凯莱图的共同假定)当且仅当这个图是局部有限的(就是说每个顶点毗连与有限多个边)。
基本性质
    *
如果生成集合的成员 s 是自身的逆元，即 s = s − 1，则它一般被表示为无向边。
    *
凯莱图 Γ(G,S) 本质上依赖于生成元的集合
S 的选择方式。例如，如果生成集合 S 有 k 个元素，则凯莱图的每个顶点都有 k 个进入和 k 个外出的有向边。在有 r 个元素的对称生成集合 S 的情况下，凯莱图是 r 度的正则图。
    *
在凯莱图中的环(“闭合路径”)指示在 S 的两个元素之间的关系。在群的凯莱复形的更精细构造中，对应于关系的闭合路径被用多边形“填充”。
    *
如果 f: G'\to G 是满射群同态并且 G' 的生成集合 S' 的元素的像是不同的，则它引发一个图的覆盖
      
\bar{f}: \Gamma(G',S')\to \Gamma(G,S),\quad 这里的 S=f(S')
\,。
    特别是，如果群 G 有 k 个生成元，都有不是 2 的阶，并且这些生成元和它们的逆元构成集合 S，则凯莱图
Γ(G,S) 由对应于在相同生成集合的自由群的 2k 度无限正则树所覆盖。
    *
图 Γ(G,S) 可以被构造即使集合 S 不生成群 G。但是，它是连通的并不被认为是凯莱图。在这种情况下，这个图的每个连通部件表示一个 S 生成子群的陪集。
    *
对于被认为是无向的凯莱图，顶点连通性等于这个图的度。[1]
Schreier陪集图
如果转而把顶点作为固定子群 H 的右陪集，就得到了一个有关的构造Schreier陪集图，它是陪集枚举或Todd-Coxeter算法的基础。
与群论的关系
研究图的邻接矩阵特别是应用谱图理论的定理能洞察群的结构。
参见
    *
群的生成集合
    *
群的展示
注释
   1.
^ Babai, L.（1996）．Technical Report TR-94-10．University of
Chicago． [1]
               
               
               
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/3176/showart_1432723.html