Luồng cực_đại Luồng cực_đại là một trong những bài_toán tối_ưu trên đồ_thị tìm được những ứng_dụng rất rộng_rãi trong cả thực_tế cũng như trong lý_thuyết tổ_hợp Bài_toán được đề_xuất vào đầu những năm 1950 và gắn liền với tên_tuổi của 2 nhà toán_học Mỹ Lester_Randolph_Ford và Delbert_Ray_Fulkerson_Mạng BULLET Mạng network là một đồ_thị có hướng G V E trong đó BULLET Có duy_nhất một đỉnh s không có cung đi vào được gọi là đỉnh phát source BULLET Có duy_nhất một đỉnh t không có cung đi ra được gọi là đỉnh thu sink Mỗi cạnh e u v E được gán một_số nguyên không âm c e c u v và gọi là khả_năng thông_qua của cung đó capacity BULLET Ta quy_ước nếu mạng không có cung u v thì ta thêm vào cung u v với khả_năng thông_qua c u v bằng 0 BULLET Với một mạng G V E c ta ký_hiệu W x u v E u V tập các cung đi vào đỉnh v Luồng trên mạng BULLET Giả_sử cho mạng G V E Ta gọi luồng f trong mạng là ánh xạ f E R gán cho mỗi cung e u v E một_số thực không âm f e f u v thoả_mãn các điều_kiện sau BULLET 1 ĐK 1 Capacity_Constraint_Luồng trên mỗi cung e E không vượt quá khả_năng thông_qua của nó 0 f e c e BULLET 2 ĐK 2 Flow_Conversion Điều_kiện cân_bằng luồng trên mỗi đỉnh của mạng Tổng luồng trên các cung vào đỉnh v bằng tổng luồng trên các cung đi ra khỏi đỉnh v nếu v s t t W x t W x x s t Tính_chất của luồng Với tập B V ký_hiệu W B a b E a B b B tập cạnh từ ngoài B đi vào B W B a b E a B b B tập cạnh từ B đi ra khỏi B Khi đó nếu tập con các đỉnh B không chứa x0 và z thì t W B t W B Theo tính_chất b của luồng t W x t W x Cạnh kề với đỉnh x nếu có đỉnh đầu và đỉnh cuối đều nằm trong tập B thì nó sẽ có_mặt ở cả hai vế củađẳng thức đúng một lần do_đó có_thể giản_ước Giá_trị của luồng BULLET Giá_trị của một luồng được tính bằng tổng giá_trị trên các cung đi ra từ đỉnh nguồn s hoặc tổng giá_trị trên các cung đi vào đỉnh thứ t Ứng_dụng thực_tế Ví_dụ BULLET Xét đồ_thị tương_ứng hệ_thống ống dẫn dầu Trong đó các ống tương_ứng với các cung điểm phát là tàu chở dầu điểm thu là bể chứa các điểm nối của ống là các nút của đồ_thị Khả_năng thông_qua của các cung tương_ứng là tiết_diện các ống Cần phải tìm luồng dầu lớn nhất có_thể bơm từ tàu chở dầu vào bể chứa BULLET Xác_định cường_độ lớn nhất của dòng vận_tải giữa 2 nút của một bản_đồ giao_thông BULLET Bài_toán cặp ghép có m chàng trai và n cô gái Mỗi chàng trai ưa_thích một_số cô gái Hãy tìm cách ghép cặp sao cho số cặp ghép được là nhiều nhất Một_số thuật_toán về luồng cực_đại Bài_toán luồng cực_đại trên mạng Lát cắt Đường tăng luồng Định_nghĩa Ta gọi lát cắt X X là một_cách phân hoạch tập đỉnh V của mạng ra thành hai tập X và X V X trong đó s X và t X Khả_năng thông_qua của lát cắt X X là số Lát cắt với khả_năng thông_qua nhỏ nhất được gọi là lát cắt hẹp nhất Bổ_đề 1 giá_trị của mọi luồng f trong mạng luôn nhỏ hơn bằng khả_năng thông_qua lát cắt X X bất_kỳ trong nó val f c X X Hệ_quả 1 Giá_trị luồng cực_đại trong mạng không vượt quá khả_năng thông_qua của lát cắt hẹp nhất trong mạng Giả_sử f là một luồng trong mạng G V E Từ mạng G V E ta xây_dựng đồ_thị có trọng_số trên cung Gf_V_Ef với tập cung Ef và trọng_số trên các cung được xác_định theo quy_tắc sau Các cung của Gf đồng_thời cũng là cung của G được gọi là cung thuận các cung còn lại gọi là cung nghịch Đồ_thị Gf được gọi là đồ_thị tăng luồng Ví_dụ Các số viết cạnh các cung của G ở hình 1 theo thứ_tự là luồng trên cung và khả_năng thông_qua Đường tăng luồng Giả_sử P s v0 v1 v2 vk t là một đường đi từ s đến t trên đồ_thị tăng luồng Gf_Gọi d là giá_trị nhỏ nhất của các trọng_số của các cung trên đường đi P Xây_dựng luồng f trên mạng G theo quy_tắc sau Dễ_dàng kiểm_tra được rằng f được xây_dựng như trên là luồng trong mạng và val f val f d Ta sẽ gọi thủ_tục biến_đổi luồng vừa nêu là tăng luồng dọc theo đường P Sau biến_đổi ta có luồng mới mang giá_trị 9 val f 4 3 3 2 3 9 Thuật_toán Ford Fulkerson_Đến_Thuật toán Luồng cực_đại với khả_năng thông_qua các cung và các đỉnh Giả_sử trong đồ_thị G V E ngoài khả_năng thông_qua của các cung c u v ở mỗi đỉnh còn có khả_năng thông_qua của đỉnh là d v và đòi_hỏi tổng luồng đi vào đỉnh v không còn vượt quá d v tức_là f w v d v với w V Cần phải tìm luồng cực_đại giữa s và t trong mạng như_vậy Xây_dựng một mạng G sao cho mỗi đỉnh v của G tương_ứng với hai đỉnh v v trong G mỗi cung u v trong G ứng với cung u v trong G mỗi cung v w trong G ứng với cung v w trong G Ngoài_ra mỗi cung v v trong G có khả_năng thông_qua là d v tức_là bằng khả_năng thông_qua của đỉnh v trong G Giải_quyết bài_toán Từ mạng G V E khả_năng thông_qua các cung và các đỉnh Ta sẽ giải_quyết theo hai bước sau Ma_trận biểu_diễn đồ_thị của bài_toán luồng cực_đại 1 Biểu_diễn mạng G với khả_năng thông_qua các cung và đỉnh Giả_sử mạng G V E V n Ta có_thể biểu_diễn bởi ma_trận trọng_số A cấp n x n như sau Trong đó di là khả_năng thông_qua đỉnh i C i j khả_năng thông_qua cung i j 2 Biểu_diễn mạng G tương_ứng với mạng G Mạng tương_ứng với G V E V n là mạng G V E V 2 V E 2 E 1 Được biểu_diễn thông_qua ma_trận A cấp 2n x 2n như sau Như thí_dụ trên có mạng G như sau Tương_tự mạng G Áp_dụng Thuật_toán Ford Fulkerson tìm luồng cực_đại cho mạng G ta được mạng cực_đại và ma_trận biểu_diễn nó như sau Đọc thêm BULLET Thuật_toán Ford Fulkerson_BULLET_Luồng trên mạng Liên_kết ngoài BULLET Bài_toán luồng cực_đại trên mạng Các thuật_toán đa_thức BULLET Animation of Ford Fulkerson algorithm 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ị
Luồng cực_đại