正則圖

各顶点的度相同的图

正則圖是每個頂點都有相同數目的相邻点的,即从每個頂點出发,所连接到的点的数目相同,这个数目用"度"来表示。若每個頂點的度均為,稱為-正則圖。

0-正則圖是沒有邊的圖。1-正則圖由不相連的邊組成。2-正則圖由不相連的圈組成。3-正則圖稱為立方圖或三次圖。階為-正則圖是完全圖

強正則圖,每對相鄰頂點都有相同數目 l 的共同鄰居,每對非相鄰頂點也有相同數目 m 節共同鄰居。最小的正則而非強正則的圖是6個頂點的環狀圖或圈。

性質

编辑
  1. 對於每個圖 及每個不小於 的最大度整數 ,存在一個有 作子圖的 -正則圖。
  2. 若有階為  -正則圖,k是偶數或n是偶數。

代數性質

编辑

 為圖 鄰接矩陣 是正則圖若且唯若 是A的特徵向量

 是正則又連通的圖若且唯若矩陣  )在圖的鄰接代數內。