正則圖

维基百科,自由的百科全书
跳转至: 导航搜索

正則圖是每個頂點都有相同數目的鄰居的,即每個頂點的度相同。若每個頂點的度均為k,稱為k-正則圖。

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

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

性質[编辑]

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

代數性質[编辑]

A為圖G鄰接矩陣G是正則圖若且唯若\begin{bmatrix}1\\ \vdots \\1 \end{bmatrix}是A的特徵向量

G是正則又連通的圖若且唯若矩陣JJ_{ij}=1)在圖的鄰接代數內。