凯莱图

凯莱图（Cayley graph），理学-数学-图论-无限图，一种由代数结构——群转换而得的图。由某个给定的群和它的一个子集所定义。给定群，是的一个不包含单位元的子集。通常用表示由群和所确定的凯莱图，式中，且中包含有向弧当且仅当。因此，由群和它的子集确定的凯莱图是一个有向图，称之为有向凯莱图。更进一步，如果要求群的子集是封闭的，即若中的元属于，则的逆元也属于，那么，由此定义的凯莱图是简单无向图，此时简称为凯莱图。此外，凯莱图是一类重要的点传递图，比如超立方体就是凯莱图。但是，并非每个点传递图都是凯莱图，比如彼得森图（见特殊图）是点传递的，但它不是凯莱图。凯莱图是连通的当且仅当是的生成元集。此外，凯莱图是-正则的。