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 G = ( V , E ) {\displaystyle G=(V,E)} và một hàm trọng số w : E → R {\displaystyle w:E\rightarrow \mathbb {R} } . Trọng số của một chu trình C {\displaystyle C} , ký hiệu là w ( C ) {\displaystyle w(C)} , là tổng trọng số các cung của C {\displaystyle C} , w ( C ) = ∑ e ∈ C w ( e ) {\displaystyle w(C)=\sum _{e\in C}w(e)} Trọng số trung bình của C {\displaystyle C} được định nghĩa là tỉ số w ( C ) | C | {\displaystyle {\frac {w(C)}{|C|}}} . Cho đơn giản, mở rộng G {\displaystyle G} bằng cách thêm vào một đỉnh gốc s {\displaystyle s} có cung độ dài 0 tới tất cả các đỉnh khác. Do G {\displaystyle 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. 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 ) {\displaystyle d_{t}(s,u)} là độ dài đường đi ngắn nhất từ s {\displaystyle s} tới u {\displaystyle u} gồm đúng t {\displaystyle t} cung. Nếu không có đường đi nào gồm đúng t {\displaystyle t} cung thì d t ( s , u ) = ∞ {\displaystyle d_{t}(s,u)=\infty } . Định nghĩa, μ ∗ = min v ∈ V max 0 ≤ k ≤ n − 1 d n ( s , v ) − d k ( s , v ) n − k {\displaystyle \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 μ ∗ {\displaystyle \mu ^{*}} chính là trung bình nhỏ nhất của các chu trình trong G {\displaystyle G} . Để tính μ ∗ {\displaystyle \mu ^{*}} , thuật toán tính tất cả các giá trị d t ( s , u )   ∀ u ∈ V , 0 ≤ t ≤ n {\displaystyle 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 ∈ V d t ( s , u ) + w ( u , v ) {\displaystyle 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 ( V E ) {\displaystyle O(VE)} . ^ Dasdan (2004) ^ Georgiadis và đồng nghiệp (2009) ^ Karp (1978) Luồng cực đại chi phí cực tiểu 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