Đồ thị chính quy

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Trong lý thuyết đồ thị, một đồ thị chính quy (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 đủ K_m là đồ thị chính quy mạnh với mọi m.

Các tính chất đại số[sửa | sửa mã nguồn]

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

Tham khảo[sửa | sửa mã nguồn]