跳转到内容

正则图

本页使用了标题或全文手工转换
维基百科,自由的百科全书

正则图是每个顶点都有相同数目的相邻点的,即从每个顶点出发,所连接到的点的数目相同,这个数目用"度"来表示。若每个顶点的度均为,称为-正则图。

0-正则图是没有边的图。1-正则图由不相连的边组成。2-正则图由不相连的圈组成。3-正则图称为立方图或三次图。阶为-正则图是完全图

强正则图,每对相邻顶点都有相同数目 l 的共同邻居,每对非相邻顶点也有相同数目 m 节共同邻居。最小的正则而非强正则的图是6个顶点的环状图或圈。

性质

[编辑]
  1. 对于每个图及每个不小于的最大度整数,存在一个有作子图的-正则图。
  2. 若有阶为-正则图,k是偶数或n是偶数。

代数性质

[编辑]

为图邻接矩阵是正则图当且仅当是A的特征向量

是正则又连通的图当且仅当矩阵)在图的邻接代数内。