imported>NhacNy2412Bot: sửa tham số CS1

2023-01-01T07:45:05Z

sửa tham số CS1

Trang mới

Trong [[khoa học máy tính]] và [[lý thuyết đồ thị]], '''thuật toán Karger''' là một [[thuật toán Monte Carlo]] để tìm [[lát cắt nhỏ nhất]] của một [[đồ thị (lý thuyết đồ thị)|đồ thị]] vô hướng. Bài toán lát cắt nhỏ nhất yêu cầu tìm cách chia đồ thị làm hai phần sao cho số cạnh nối các đỉnh ở hai phần khác nhau là nhỏ nhất. Thuật toán được tìm ra bởi [[David Karger]].

==Thuật toán==
Ý tưởng chính của thuật toán là sử dụng phép hợp nhất hai đầu của một cạnh <math>e</math> trong đồ thị <math>G = (V, E)</math>. Sau mỗi lần hợp nhất, số đỉnh của đồ thị giảm đi 1. Thuật toán sử dụng một chuỗi các phép hợp nhất các cạnh ngẫu nhiên của đồ thị. Xác suất chọn mỗi cạnh tỉ lệ với trọng số của nó. Thuật toán này là một thuật toán đệ quy. Trong mỗi tầng đệ quy, thuật toán hoạt động như sau. Thử hai lần độc lập nhau việc lặp đi lặp lại phép hợp nhất để giảm số đỉnh của <math>G</math> xuống <math> \left\lceil n / \sqrt{2} + 1 \right\rceil </math> và gọi đệ quy để tính lát cắt nhỏ nhất trong đồ thị thu được. Sau đó, chọn kết quả tốt hơn trong hai lần gọi đệ quy và trả về giá trị đó.

==Phép hợp nhất==
Trong mỗi lần thực hiện, phép toán này hợp nhất hai đỉnh ''x'' và ''y'' của một cung ''e'' thành một đỉnh mới <math>v_e</math> kề với tất cả các đỉnh kề của ''x'' và ''y''. Định nghĩa cụ thể là như sau.

Cho một đồ thị <math>G = \left (V, E \right)</math> và <math>e = \lbrace x, y \rbrace \in E</math>, kết quả phép hợp nhất hai đỉnh kề với cạnh <math>e</math> (ký hiệu <math>G/e = \left (V', E'\right)</math>) là một [[đa đồ thị]] định nghĩa như sau:

:<math>V' = \left(V \setminus \lbrace x, y \rbrace \right) \cup \lbrace v_e \rbrace</math>

và:

:<math>E' = \lbrace \lbrace v, w \rbrace \in E \mid \lbrace v,w \rbrace \cap \lbrace x,y \rbrace = \emptyset \rbrace \cup \lbrace \lbrace v_e,w \rbrace \mid
\lbrace x,w \rbrace \in E \setminus \lbrace e \rbrace </math> hoặc <math> \lbrace y,w \rbrace \in E \setminus \lbrace e \rbrace \rbrace</math>

Có thể chứng minh phép toán này không làm giảm nhưng có thể làm tăng giá trị lát cắt nhỏ nhất.

==Thời gian thực hiện==
Thuật toán Karger là thuật toán ngẫu nhiên nhanh nhất hiện nay cho việc tìm lát cắt nhỏ nhất, với thời gian chạy ''O''(|''V''|2 log3|''V''|). Để chứng minh điều này, tác giả chỉ ra cách thực hiện chuỗi các phép hợp nhất để giảm kích thước <math>G</math> xuống <math> \left\lceil n / \sqrt{2} + 1 \right\rceil </math> đỉnh trong thời gian <math>O(n^2)</math>. Do đó thời gian chạy của thuật toán là <math> T(n) = 2 \left(n^2 + T\left(\left\lceil n / \sqrt{2} + 1 \right\rceil \right) \right) </math>. Phương trình này cho kết quả <math>T(n)= O(n^2 log(n)) </math>. Sau mỗi lần thực hiện thuật toán, xác suất tìm ra lát cắt nhỏ nhất là <math>\Omega(1/ log(n))</math>. Nếu thực hiện thuật toán <math>O(log^2(n))</math> lần thì xác suất không tìm ra lát cắt nhỏ nhất giảm xuống {{math|O(1/''n''2)}}.

==Tham khảo==
{{Tham khảo}}
{{refbegin}}
# {{cite conference|author=David R. Karger|url=http://people.csail.mit.edu/karger/Papers/mincut.ps|title=Global Min-cuts in RNC and Other Ramifications of a Simple Mincut Algorithm|book-title=Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms|year=1993}}
# {{chú thích|first1=David R.|last1=Karger|first2=Clifford|last2=Stein|url=http://people.csail.mit.edu/karger/Papers/contract.ps|title=A New Approach to the Minimum Cut Problem|journal=Journal of the ACM |volume=43|issue=4|pages=601–640|year=1996}}
{{refend}}

{{DEFAULTSORT:Karger, Thuật toán}}
[[Thể loại:Giải thuật lý thuyết đồ thị]]

Thuật toán Karger - Lịch sử thay đổi

imported>NhacNy2412Bot: sửa tham số CS1