Đồ thị chính quy là gì? Chi tiết về Đồ thị chính quy mới nhất 2023

Bài viết này cần thêm chú thích nguồn gốc để kiểm chứng thông tin. Mời bạn giúp hoàn thiện bài viết này bằng cách bổ sung chú thích tới các nguồn đáng tin cậy. Các nội dung không có nguồn có thể bị nghi ngờ và xóa bỏ.

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ố[sửa | sửa mã nguồn]

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 \1end{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[sửa | sửa mã nguồn]

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

Wikimedia Commons có thêm hình ảnh và phương tiện truyền tải về Đồ thị chính quy.