Bước tới nội dung

Đồ thị chính quy

Bách khoa toàn thư mở Wikipedia

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 đủ là đồ thị chính quy mạnh với mọi .

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

Cho Ama trận kề của đồ thị. Đồ thị là đồ thị chính quy khi và chỉ khi 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ảosửa mã nguồn

🔥 Top keywords: Đài Truyền hình Kỹ thuật số VTCLương CườngTrang ChínhTrương Thị MaiLê Minh HưngBộ Chính trị Ban Chấp hành Trung ương Đảng Cộng sản Việt NamĐặc biệt:Tìm kiếmBùi Thị Minh HoàiTô LâmNguyễn Trọng NghĩaThường trực Ban Bí thư Trung ương Đảng Cộng sản Việt NamLương Tam QuangĐỗ Văn ChiếnLê Minh HươngBan Bí thư Trung ương Đảng Cộng sản Việt NamPhan Văn GiangTrần Quốc TỏChủ tịch nước Cộng hòa xã hội chủ nghĩa Việt NamNguyễn Phú TrọngNguyễn Duy NgọcSlovakiaPhan Đình TrạcTrần Thanh MẫnLê Thanh Hải (chính khách)Đài Truyền hình Việt NamTổng cục chính trị Quân đội nhân dân Việt NamViệt NamCleopatra VIITrần Cẩm TúBan Chấp hành Trung ương Đảng Cộng sản Việt NamHồ Chí MinhThích Chân QuangChủ nhiệm Tổng cục chính trị Quân đội nhân dân Việt NamLê Minh Hùng (Hà Tĩnh)Lễ Phật ĐảnChiến dịch Điện Biên PhủẤm lên toàn cầuTrưởng ban Tổ chức Trung ương Đảng Cộng sản Việt NamPhạm Minh Chính