Thực đơn
Thuật_toán_Karger Phép hợp nhấtTrong 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 v e {\displaystyle v_{e}} 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ị G = ( V , E ) {\displaystyle G=\left(V,E\right)} và e = { x , y } ∈ E {\displaystyle e=\lbrace x,y\rbrace \in E} , kết quả phép hợp nhất hai đỉnh kề với cạnh e {\displaystyle e} (ký hiệu G / e = ( V ′ , E ′ ) {\displaystyle G/e=\left(V',E'\right)} ) là một đa đồ thị định nghĩa như sau:
V ′ = ( V ∖ { x , y } ) ∪ { v e } {\displaystyle V'=\left(V\setminus \lbrace x,y\rbrace \right)\cup \lbrace v_{e}\rbrace }và:
E ′ = { { v , w } ∈ E ∣ { v , w } ∩ { x , y } = ∅ } ∪ { { v e , w } ∣ { x , w } ∈ E ∖ { e } {\displaystyle 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 } hoặc { y , w } ∈ E ∖ { e } } {\displaystyle \lbrace y,w\rbrace \in E\setminus \lbrace e\rbrace \rbrace }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ực đơn
Thuật_toán_Karger Phép hợp nhấtLiên quan
Thuật ngữ giải phẫu cử động Thuật toán Thuật ngữ anime và manga Thuật ngữ thiên văn học Thuật ngữ lý thuyết đồ thị Thuật chiêu hồn Thuật toán Dijkstra Thuật ngữ tin học Thuật toán Kruskal Thuật ngữ ngữ âm họcTài liệu tham khảo
WikiPedia: Thuật_toán_Karger http://people.csail.mit.edu/karger/Papers/contract... http://people.csail.mit.edu/karger/Papers/mincut.p...