凯莱图

✍ dations ◷ 2025-07-11 17:49:54 #群论,置换群,图

凯莱图(Cayley graph)也叫做凯莱着色图是编码离散群的图。它的定义是凯莱定理(以阿瑟·凯莱命名)所暗含的,并使用这个群的特定的通常有限的生成元集合。它是组合群论与几何群论的中心工具。

假设 G {\displaystyle G} 是群,而 S {\displaystyle S} 是G的生成集。凯莱图 Γ = Γ ( G , S ) {\displaystyle \Gamma =\Gamma (G,S)} ,是如下构造的着色的有向图。

在几何群论中,集合 S {\displaystyle S} ,通常被假定为有限的、“对称的”也就是 S = S 1 {\displaystyle S=S^{-1}} ,并且不包含这个群的单位元。在这种情况下,凯莱图是正常的图:它的边没有方向并且不包含环路。

G {\displaystyle G} 通过左乘作用在自身上(参见凯莱定理)。这个作用可以看作 G {\displaystyle G} 作用在它的凯莱图上。明显的,一个元素 h G {\displaystyle h\in G} 映射一个顶点 g V ( Γ ) {\displaystyle g\in V(\Gamma )} 到顶点 h g V ( Γ ) {\displaystyle hg\in V(\Gamma )} 。凯莱图的边集合被这个作用所保存:边 ( g , g s ) {\displaystyle (g,gs)} 变换成边 ( h g , h g s ) {\displaystyle (hg,hgs)} 。任何群在自身上的左乘作用是简单传递的,特别是凯莱图是顶点传递的。这导致了凯莱图的下列特征:

要从一个凯莱图 Γ = Γ ( G , S ) {\displaystyle \Gamma =\Gamma (G,S)} 恢复群 G {\displaystyle G} 和生成集 S {\displaystyle S} ,选择一个顶点 v 1 V ( Γ ) {\displaystyle v_{1}\in V(\Gamma )} 并标记上这个群的单位元。接着对每个 Γ {\displaystyle \Gamma } 的顶点 v {\displaystyle v} 标记上变换 v 1 {\displaystyle v_{1}} v {\displaystyle v} G {\displaystyle G} 的唯一元素。产生 Γ {\displaystyle \Gamma } 为凯莱图的 G {\displaystyle G} 的生成元的集合 S {\displaystyle S} 是毗连到选择的顶点的顶点的标记的集合。生成集合是有限(这是凯莱图的共同假定)当且仅当这个图是局部有限的(就是说每个顶点毗连与有限多个边)。

如果转而把顶点作为固定子群 H {\displaystyle H} 的右陪集,就得到了一个有关的构造Schreier陪集图,它是陪集枚举或Todd-Coxeter算法的基础。

研究图的邻接矩阵特别是应用谱图理论的定理能洞察群的结构。

相关

  • 唐纳德·戴维森唐纳德·赫伯特·戴维森(英语:Donald Davidson,1917年3月6日-2003年8月30日)20世纪下半叶美国最为著名和活跃的哲学家之一。戴维森1917年3月6日生于美国麻省斯普林菲尔德。在早期
  • 漂白水漂白剂是一些化学物品,可透过氧化还原反应将有色分子反应成无色分子,来将颜色去除或变淡以达至漂白物品的功用。漂白剂依据其在漂白过程发生的氧化还原反应所担任的角色来区分
  • Léri-Weill软骨骨生成障碍综合症Léri-Weill软骨骨生成障碍综合征(英语:Léri-Weill dyschondrosteosis,LWD),是一种罕见的基因疾病,肇因于性染色体上拟常染色体区的“SHOX(英语:SHOX)基因”突变。此病将造成患者身
  • 中川胜彦中川 胜彦(1962年7月20日-1994年9月17日)是日本东京都出生的演员及歌手,他是女艺人中川翔子的父亲。在演出活动中,他的代表作为单元剧《穿越时空的少女》的“一夫”、连续剧《白
  • 甲二氯胂MDA MDCA二氯甲基胂,亦可简写为MD,是一种有机化合物,化学式为CH3AsCl2。它是一种无色、易挥发的液体,具有很强的毒性,是一种糜烂性毒剂,可作为化学武器使用。德国化学家于1917-191
  • 圣玛丽大教堂圣马利亚座堂(英语:St Mary's Cathedral)是英国苏格兰格拉斯哥的一座苏格兰圣公会教堂,位于格拉斯哥西部。现在的建筑于1871年11月9日开始使用,在1893年竣工。这座教堂是英国的A
  • 自愈力自愈力属于自然疗法,认为人类体内本自具有最好的医生,跟西医之父希波克拉底所提倡的“自我疗能”(vis medicatrix naturae)是一样的,主张身体有自动修复的机制。若要启动自愈力的
  • 鲍勃·凯恩鲍勃·凯恩(英语:Bob Kane,原名:罗伯特·卡恩 Robert Kahn,1915年10月24日-1998年11月3日),是一名美国的著名漫画家、编剧,是著名漫画《蝙蝠侠》的原始作者,即“蝙蝠侠之父”。他出生
  • 嘉玛道理会士盎博罗削嘉玛道理会士盎博罗削(Ambrogio Camaldolese,原名 Ambrogio Traversari,1386年-1439年10月20日),嘉玛道理会神学家,意大利文艺复兴时期人文主义者,天主教圣人,瞻礼11月20日。盎博罗削
  • Machinima公司Machinima公司是一个专注于游戏的全球YouTube频道。Machinima跨YouTube、Twitter、Facebook、Android和iOS多平台。公司于2000年1月由Hugh Hancock成立,总部位于加利福尼亚州