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.

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.
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.
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.

