Chu_trình trung_bình nhỏ nhất Trong lý_thuyết đồ_thị bài_toán chu_trình trung_bình nhỏ nhất yêu_cầu tìm trong một đồ_thị có hướng cho trước một chu_trình có trọng_số trung_bình nhỏ nhất Trọng_số trung_bình của một chu_trình là tỉ_số giữa tổng trọng_số các cung của chu_trình và số cung của nó Bài_toán này có nhiều ứng_dụng trong lý_thuyết đồ_thị và phân_tích hệ_thống sự_kiện rời_rạc Định_nghĩa Xét đồ_thị có hướng formula _ 1 và một hàm trọng_số formula _ 2 Trọng_số của một chu_trình formula _ 3 ký_hiệu là formula _ 4 là tổng trọng_số các cung của formula _ 3 Trọng_số trung_bình của formula _ 3 được định_nghĩa là tỉ_số formula _ 8 Thuật_toán Cho đơn_giản mở_rộng formula _ 9 bằng cách thêm vào một đỉnh gốc formula _ 10 có cung_độ dài 0 tới tất_cả các đỉnh khác Do formula _ 9 không có thêm chu_trình nào nên chu_trình trung_bình nhỏ nhất là không đổi Thuật_toán Karp_Có rất nhiều thuật_toán cho bài_toán tìm chu_trình trung_bình nhỏ nhất Thuật_toán đầu_tiên cho bài_toán này là của Karp_Định nghĩa formula _ 12 là độ dài đường đi ngắn nhất từ formula _ 10 tới formula _ 14 gồm đúng formula _ 15 cung Nếu không có đường đi nào gồm đúng formula _ 15 cung thì formula _ 17 Định_nghĩa Có_thể chứng_minh rằng formula _ 19 chính là trung_bình nhỏ nhất của các chu_trình trong formula _ 9 Để tính formula _ 19 thuật_toán tính tất_cả các giá_trị formula _ 22 theo công_thức sau Thời_gian_thực thi của thuật_toán là formula _ 24 Xem thêm BULLET Luồng cực_đại chi_phí cực_tiểu
Chu_trình trung_bình nhỏ nhất