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 $G=(V,E)$ và một hàm trọng số $w:E\rightarrow \mathbb {R}$. Trọng số của một chu trình $C$, ký hiệu là $w(C)$, là tổng trọng số các cung của $C$,

$w(C)=\sum _{e\in C}w(e)$

Trọng số trung bình của $C$ được định nghĩa là tỉ số ${\frac {w(C)}{|C|}}$.

Thuật toán

Cho đơn giản, mở rộng $G$ bằng cách thêm vào một đỉnh gốc $s$ có cung độ dài 0 tới tất cả các đỉnh khác. Do $G$ 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 $d_{t}(s,u)$ là độ dài đường đi ngắn nhất từ $s$ tới $u$ gồm đúng $t$ cung. Nếu không có đường đi nào gồm đúng $t$ cung thì $d_{t}(s,u)=\infty$. Định nghĩa,

$\mu ^{*}=\min _{v\in V}\max _{0\leq k\leq n-1}{\frac {d_{n}(s,v)-d_{k}(s,v)}{n-k}}$

Có thể chứng minh rằng $\mu ^{*}$ chính là trung bình nhỏ nhất của các chu trình trong $G$. Để tính $\mu ^{*}$, thuật toán tính tất cả các giá trị $d_{t}(s,u)~\forall u\in V,0\leq t\leq n$ theo công thức sau:

$d_{t+1}(s,v)=\min _{u\in V}d_{t}(s,u)+w(u,v)$

Thời gian thực thi của thuật toán là $O(VE)$.

Xem thêm

• Luồng cực đại chi phí cực tiểu

Tham khảo

• Dasdan, Ali (2004), “Experimental analysis of the fastest optimum cycle ratio and mean algorithms”, ACM Trans. Des. Autom. Electron. Syst., ACM, 9 (4): 385–418, doi:10.1145/1027084.1027085, ISSN 1084-4309
• Georgiadis, Loukas; Goldberg, Andrew V.; Tarjan, Robert E.; Werneck, Renato F. (2009), “An Experimental Study of Minimum Mean Cycle Algorithms”, ALENEX (PDF), tr. 1–13, Bản gốc (PDF) lưu trữ ngày 18 tháng 10 năm 2012, truy cập ngày 11 tháng 9 năm 2012
• Karp, R. M. (1978), “A characterization of the minimum cycle mean in a digraph”, Disc. Math., 23: 309–311