Đồ_thị tăng luồng Đồ_thị tăng luồng BULLET Giả_sử f là một luồng trên mạng G V E Từ mạng G V E ta xây_dựng đồ_thị có trọng_số trên cung G V E với tập cung E và trọng_số trên các cung được xác_định theo quy_tắc sau BULLET 1 Nếu e u v E với f u v 0 thì u v E với trọng_số c u v BULLET 2 Nếu e u v E với f u v c u v thì v u E với trọng_số f u v BULLET 3 Nếu e u v E với 0 f u v c u v thì u v E với trọng_số c u v f u v và v u E với trọng_số f u v BULLET Các cung của G đồng_thời cũng là cung của G được gọi là cung thuận các cung còn lại được gọi là cung nghịch Đồ_thị G được gọi là đồ_thị tăng luồng Tăng luồng BULLET Giả_sử P s v v v v t là một đường đi từ s đến t trên đồ_thị tăng luồng G Gọi k là trọng_số cung nhỏ nhất trên đường đi P Xây_dựng luồng f theo quy_tắc sau BULLET 1 f u v f u v k nếu u v P là cung thuận BULLET 2 f u v f u v k nếu u v P là cung nghịch BULLET 3 f u v f u v nếu u v P BULLET Dễ_dàng kiểm_tra được rằng f xây_dựng như trên là luồng trong mạng và val f val f k BULLET Thủ_tục tăng luồng này gọi là tăng luồng dọc theo đường P Đường tăng luồng BULLET Đường tăng luồng f là mọi đường đi từ s đến t trên đồ_thị tăng luồng G BULLET Các mệnh_đề dưới đây là tương_đương BULLET 1 f là luồng cực_đại trong mạng BULLET 2 Không tìm được đường tăng luồng f BULLET 3 val f c X X với một lát cắt X X nào đó Chứng_minh BULLET CM 2 3 Ký_hiệu X là tập các đỉnh đến được từ s Đặt_X_V_X Lúc đó X X là lát cắt và f u v 0 với mọi u X và v X Do_đó BULLET với u X và v X do u v G nên f u v c u v Vậy Đọc thêm BULLET Lát cắt lý_thuyết đồ_thị BULLET Thuật_toán Ford Fulkerson_BULLET_Định lý luồng cực_đại lát cắt cực_tiểu BULLET Luồng trên mạng BULLET Luồng cực_đại Liên_kết ngoài BULLET Sách trực_tuyến về Lý_thuyết đồ_thị BULLET Hướng_dẫn về lý_thuyết đồ_thị BULLET Bài giảng của một môn_học về các thuật_toán đồ_thị BULLET Minh_hoạ hoạt_hình về các thuật_toán đồ_thị BULLET Lần bước thuật_toán để tìm_hiểu BULLET Tóm_tắt các trang minh_hoạ thuật_toán BULLET Dữ_liệu test chuẩn cho các bài_toán đồ_thị con đầy_đủ lớn nhất Maximum_Clique tập con độc_lập lớn nhất Maximum_Independent_Set phủ đỉnh nhỏ nhất Minimum_Vertex_Cover và tô màu đỉnh Vertex_Coloring_BULLET_Sưu tập ảnh số 1 một_số mạng_lưới thực BULLET Sưu_tập ảnh số 1 một_số mạng_lưới thực BULLET Sưu_tập các liên_kết về đồ_thị BULLET Các tạp_chí lý_thuyết đồ_thị BULLET Sách về lý_thuyết đồ_thị
Đồ_thị tăng luồng