Chu trình (lý thuyết đồ thị)
dây chuyền đóng trong lý thuyết đồ thị
Trong lý thuyết đồ thị, chu trình trong đồ thị là một dây chuyền đóng.
Đồ thị chỉ gồm một chu trình với n đỉnh được gọi là đồ thị vòng, ký hiệu Cn,
Các loại chu trình:
- Chu trình chẵn: là chu trình có độ dài chẵn.
- Chu trình lẻ: là chu trình có độ dài lẻ.
- Chu trình có hướng: là một chu trình đơn mà mọi cung trong đó đều cùng hướng, nghĩa là mọi đỉnh đều có bậc trong và bậc ngoài bằng 1. Có thể gọi đơn giản là chu trình khi ngữ cảnh rõ ràng.
- Chu trình đơn: là chu trình không đi qua một cạnh nào quá một lần.
- Chu trình sơ cấp: là chu trình không chứa cùng một đỉnh quá một lần (trừ đỉnh đầu và đỉnh cuối). Trong đồ thị ở hình trên, (1, 5, 2, 1) là một chu trình sơ cấp. Chu trình sơ cấp thì là chu trình đơn.
- Chu trình Euler: là chu trình qua tất cả các cạnh, mỗi cạnh đúng một lần.
- Chu trình bao trùm: là cách gọi khác của chu trình Hamilton.
Tham khảo
🔥 Top keywords: Đài Truyền hình Kỹ thuật số VTCTrang ChínhGiỗ Tổ Hùng VươngTrương Mỹ LanĐặc biệt:Tìm kiếmHùng VươngVương Đình HuệUEFA Champions LeagueKuwaitChiến dịch Điện Biên PhủFacebookĐài Truyền hình Việt NamTrần Cẩm TúĐội tuyển bóng đá quốc gia KuwaitGoogle DịchViệt NamCúp bóng đá U-23 châu ÁCúp bóng đá U-23 châu Á 2024Real Madrid CFBảng xếp hạng bóng đá nam FIFACleopatra VIITô LâmTim CookNguyễn Phú TrọngHồ Chí MinhHai Bà TrưngManchester City F.C.VnExpressChủ tịch nước Cộng hòa xã hội chủ nghĩa Việt NamNguyễn Ngọc ThắngĐền HùngCúp bóng đá trong nhà châu Á 2024Võ Văn ThưởngOne PieceLịch sử Việt NamCuộc đua xe đạp toàn quốc tranh Cúp truyền hình Thành phố Hồ Chí Minh 2024Phạm Minh ChínhTikTokĐinh Tiên Hoàng