Đồ thị chính quy

Trong lý thuyết đồ thị, một đồ thị chính quy, còn gọi là đồ thị đều (tiếng Anh: regular graph) là một đồ thị trong đó mỗi đỉnh có số láng giềng bằng nhau, nghĩa là các đỉnh có bậc bằng nhau. Một đồ thị chính quy với các đỉnh có bậc bằng k được gọi là đồ thị chính quy bậc k.

Các đồ thị chính quy có bậc không lớn hơn 2 rất dễ nhận: đồ thị chính quy bậc 0 bao gồm các đỉnh cô lập, đồ thị chính quy bậc 1 bao gồm các cạnh không nối với nhau, và đồ thị chính quy bậc 2 bao gồm các chu trình không nối với nhau.

Đồ thị chính quy bậc 3 còn được gọi là đồ thị bậc ba (cubic graph).

Đồ thị chính quy mạnh là đồ thị chính quy mà mọi cặp đỉnh kề nhau đều có số láng giềng chung bằng nhau và mọi cặp đỉnh không kề đều có số láng giềng chung bằng nhau. Các đồ thị nhỏ nhất là đồ thị chính quy nhưng không chính quy mạnh là các đồ thị vòng (cycle graph) và đồ thị tròn (circulant graph) 6 đỉnh.

Đồ thị đầy đủ ${\displaystyle K_{m}}$ là đồ thị chính quy mạnh với mọi ${\displaystyle m}$.

Các tính chất đại số

Cho A là ma trận kề của đồ thị. Đồ thị là đồ thị chính quy khi và chỉ khi ${\displaystyle {\begin{bmatrix}1\\\vdots \\1\end{bmatrix}}}$ là vectơ riêng của A. Khi nó là một vectơ riêng, giá trị riêng sẽ là hằng bậc của đồ thị.

Tham khảo

• Eric W. Weisstein, Regular Graph tại MathWorld
• Eric W. Weisstein, Strongly Regular Graph tại MathWorld