Chương V: Một Số Bài Toán Tối ưu Trên đồ Thị.pdf (Toán Rời Rạc)

Trang chủ Tìm kiếm Trang chủ Tìm kiếm Toán rời rạc - Chương V: Một số bài toán tối ưu trên đồ thị pdf 20 284 KB 1 67 4.3 ( 6 lượt) Xem tài liệu Nhấn vào bên dưới để tải tài liệu Tải về Đang chuẩn bị: 60 Bắt đầu tải xuống Đang xem trước 10 trên tổng 20 trang, để tải xuống xem đầy đủ hãy nhấn vào bên trên Chủ đề liên quan Toán rời rạc dạng toán rời rạc Bài tập toán rời rạc tài liệu toán rời rạc toán rời rạc trên đồ thị

Nội dung

http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập CHƯƠNG V MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ðỒ THỊ 5.1. ðỒ THỊ CÓ TRỌNG SỐ VÀ BÀI TOÁN ðƯỜNG ðI NGẮN NHẤT. 5.1.1. Mở ñầu: Trong ñời sống, chúng ta thường gặp những tình huống như sau: ñể ñi từ ñịa ñiểm A ñến ñịa ñiểm B trong thành phố, có nhiều ñường ñi, nhiều cách ñi; có lúc ta chọn ñường ñi ngắn nhất (theo nghĩa cự ly), có lúc lại cần chọn ñường ñi nhanh nhất (theo nghĩa thời gian) và có lúc phải cân nhắc ñể chọn ñường ñi rẻ tiền nhất (theo nghĩa chi phí), v.v... Có thể coi sơ ñồ của ñường ñi từ A ñến B trong thành phố là một ñồ thị, với ñỉnh là các giao lộ (A và B coi như giao lộ), cạnh là ñoạn ñường nối hai giao lộ. Trên mỗi cạnh của ñồ thị này, ta gán một số dương, ứng với chiều dài của ñoạn ñường, thời gian ñi ñoạn ñường hoặc cước phí vận chuyển trên ñoạn ñường ñó, ... ðồ thị có trọng số là ñồ thị G=(V,E) mà mỗi cạnh (hoặc cung) e∈E ñược gán bởi một số thực m(e), gọi là trọng số của cạnh (hoặc cung) e. Trong phần này, trọng số của mỗi cạnh ñược xét là một số dương và còn gọi là chiều dài của cạnh ñó. Mỗi ñường ñi từ ñỉnh u ñến ñỉnh v, có chiều dài là m(u,v), bằng tổng chiều dài các cạnh mà nó ñi qua. Khoảng cách d(u,v) giữa hai ñỉnh u và v là chiều dài ñường ñi ngắn nhất (theo nghĩa m(u,v) nhỏ nhất) trong các ñường ñi từ u ñến v. Có thể xem một ñồ thị G bất kỳ là một ñồ thị có trọng số mà mọi cạnh ñều có chiều dài 1. Khi ñó, khoảng cách d(u,v) giữa hai ñỉnh u và v là chiều dài của ñường ñi từ u ñến v ngắn nhất, tức là ñường ñi qua ít cạnh nhất. 5.1.2. Bài toán tìm ñường ñi ngắn nhất: Cho ñơn ñồ thị liên thông, có trọng số G=(V,E). Tìm khoảng cách d(u0,v) từ một ñỉnh u0 cho trước ñến một ñỉnh v bất kỳ của G và tìm ñường ñi ngắn nhất từ u0 ñến v. Có một số thuật toán tìm ñường ñi ngắn nhất; ở ñây, ta có thuật toán do E. Dijkstra, nhà toán học người Hà Lan, ñề xuất năm 1959. Trong phiên bản mà ta sẽ trình bày, người ta giả sử ñồ thị là vô hướng, các trọng số là dương. Chỉ cần thay ñổi ñôi chút là có thể giải ñược bài toán tìm ñường ñi ngắn nhất trong ñồ thị có hướng. Phương pháp của thuật toán Dijkstra là: xác ñịnh tuần tự ñỉnh có khoảng cách ñến u0 từ nhỏ ñến lớn. Trước tiên, ñỉnh có khoảng cách ñến a nhỏ nhất chính là a, với d(u0,u0)=0. Trong các ñỉnh v ≠ u0, tìm ñỉnh có khoảng cách k1 ñến u0 là nhỏ nhất. ðỉnh này phải là một trong các ñỉnh kề với u0. Giả sử ñó là u1. Ta có: d(u0,u1) = k1. 67 http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập Trong các ñỉnh v ≠ u0 và v ≠ u1, tìm ñỉnh có khoảng cách k2 ñến u0 là nhỏ nhất. ðỉnh này phải là một trong các ñỉnh kề với u0 hoặc với u1. Giả sử ñó là u2. Ta có: d(u0,u2) = k2. Tiếp tục như trên, cho ñến bao giờ tìm ñược khoảng cách từ u0 ñến mọi ñỉnh v của G. Nếu V={u0, u1, ..., un} thì: 0 = d(u0,u0) < d(u0,u1) < d(u0,u2) < ... < d(u0,un). 5.1.3. Thuật toán Dijkstra: procedure Dijkstra (G=(V,E) là ñơn ñồ thị liên thông, có trọng số với trọng số dương) {G có các ñỉnh a=u0, u1, ..., un=z và trọng số m(ui,uj), với m(ui,uj) = ∞ nếu (ui,uj) không là một cạnh trong G} for i := 1 to n L(ui) := ∞ L(a) := 0 S := V \ {a} u := a while S ≠ ∅ begin for tất cả các ñỉnh v thuộc S if L(u) +m(u,v) < L(v) then L(v) := L(u)+m(u,v) u := ñỉnh thuộc S có nhãn L(u) nhỏ nhất {L(u): ñộ dài ñường ñi ngắn nhất từ a ñến u} S := S \ {u} end Thí dụ 1: Tìm khoảng cách d(a,v) từ a ñến mọi ñỉnh v và tìm ñường ñi ngắn nhất từ a ñến v cho trong ñồ thị G sau. 4 b 1 1 3 a 2 2 2 4 e 5 3 n 6 c 6 d 2 g 2 3 1 5 m 68 h 3 k 3 http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập L(a) L(b) L(c) L(d) L(e) L(g) L(h) L(k) L(m) L(n) 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ − 1 ∞ ∞ 3 ∞ ∞ ∞ 3 2 − − 5 ∞ 2 ∞ ∞ ∞ 3 2 − − 5 ∞ 2 ∞ ∞ ∞ 3 − − − 4 ∞ − 6 ∞ ∞ 3 − − − 4 ∞ − 6 ∞ 6 − − − − − 10 − 6 ∞ 6 − − − − − 8 − − 9 6 − − − − − 8 − − 7 − − − − − − 8 − − − − − − 5.1.4. ðịnh lý: Thuật toán Dijkstra tìm ñược ñường ñi ngắn nhất từ một ñỉnh cho trước ñến một ñỉnh tuỳ ý trong ñơn ñồ thị vô hướng liên thông có trọng số. Chứng minh: ðịnh lý ñược chứng minh bằng quy nạp. Tại bước k ta có giả thiết quy nạp là: (i) Nhãn của ñỉnh v không thuộc S là ñộ dài của ñường ñi ngắn nhất từ ñỉnh a tới ñỉnh này; (ii) Nhãn của ñỉnh v trong S là ñộ dài của ñường ñi ngắn nhất từ ñỉnh a tới ñỉnh này và ñường ñi này chỉ chứa các ñỉnh (ngoài chính ñỉnh này) không thuộc S. Khi k=0, tức là khi chưa có bước lặp nào ñược thực hiện, S=V \ {a}, vì thế ñộ dài của ñường ñi ngắn nhất từ a tới các ñỉnh khác a là ∞ và ñộ dài của ñường ñi ngắn nhất từ a tới chính nó bằng 0 (ở ñây, chúng ta cho phép ñường ñi không có cạnh). Do ñó bước cơ sở là ñúng. Giả sử giả thiết quy nạp là ñúng với bước k. Gọi v là ñỉnh lấy ra khỏi S ở bước lặp k+1, vì vậy v là ñỉnh thuộc S ở cuối bước k có nhãn nhỏ nhất (nếu có nhiều ñỉnh có nhãn nhỏ nhất thì có thể chọn một ñỉnh nào ñó làm v). Từ giả thiết quy nạp ta thấy rằng 69 http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập trước khi vào vòng lặp thứ k+1, các ñỉnh không thuộc S ñã ñược gán nhãn bằng ñộ dài của ñường ñi ngắn nhất từ a. ðỉnh v cũng vậy phải ñược gán nhãn bằng ñộ dài của ñường ñi ngắn nhất từ a. Nếu ñiều này không xảy ra thì ở cuối bước lặp thứ k sẽ có ñường ñi với ñộ dài nhỏ hơn Lk(v) chứa cả ñỉnh thuộc S (vì Lk(v) là ñộ dài của ñường ñi ngắn nhất từ a tới v chứa chỉ các ñỉnh không thuộc S sau bước lặp thứ k). Gọi u là ñỉnh ñầu tiên của ñường ñi này thuộc S. ðó là ñường ñi với ñộ dài nhỏ hơn Lk(v) từ a tới u chứa chỉ các ñỉnh không thuộc S. ðiều này trái với cách chọn v. Do ñó (i) vẫn còn ñúng ở cuối bước lặp k+1. Gọi u là ñỉnh thuộc S sau bước k+1. ðường ñi ngắn nhất từ a tới u chứa chỉ các ñỉnh không thuộc S sẽ hoặc là chứa v hoặc là không. Nếu nó không chứa v thì theo giả thiết quy nạp ñộ dài của nó là Lk(v). Nếu nó chứa v thì nó sẽ tạo thành ñường ñi từ a tới v với ñộ dài có thể ngắn nhất và chứa chỉ các ñỉnh không thuộc S khác v, kết thúc bằng cạnh từ v tới u. Khi ñó ñộ dài của nó sẽ là Lk(v)+m(v,u). ðiều ñó chứng tỏ (ii) là ñúng vì Lk+1(u)=min(Lk(u), Lk(v)+m(v,u)). 5.1.5. Mệnh ñề: Thuật toán Dijkstra tìm ñường ñi ngắn nhất từ một ñỉnh cho trước ñến một ñỉnh tuỳ ý trong ñơn ñồ thị vô hướng liên thông có trọng số có ñộ phức tạp là O(n2). Chứng minh: Thuật toán dùng không quá n−1 bước lặp. Trong mỗi bước lặp, dùng không hơn 2(n−1) phép cộng và phép so sánh ñể sửa ñổi nhãn của các ñỉnh. Ngoài ra, một ñỉnh thuộc Sk có nhãn nhỏ nhất nhờ không quá n−1 phép so sánh. Do ñó thuật toán có ñộ phức tạp O(n2). 5.1.6. Thuật toán Floyd: Cho G=(V,E) là một ñồ thị có hướng, có trọng số. ðể tìm ñường ñi ngắn nhất giữa mọi cặp ñỉnh của G, ta có thể áp dụng thuật toán Dijkstra nhiều lần hoặc áp dụng thuật toán Floyd ñược trình bày dưới ñây. Giả sử V={v1, v2, ..., vn} và có ma trận trọng số là W ≡ W0. Thuật toán Floyd xây dựng dãy các ma trận vuông cấp n là Wk (0 ≤ k ≤ n) như sau: procedure Xác ñịnh Wn for i := 1 to n for j := 1 to n W[i,j] := m(vi,vj) {W[i,j] là phần tử dòng i cột j của ma trận W0} for k := 1 to n if W[i,k] +W[k,j] < W[i,j] then W[i,j] := W[i,k] +W[k,j] {W[i,j] là phần tử dòng i cột j của ma trận Wk} 5.1.7. ðịnh lý: Thuật toán Floyd cho ta ma trận W*=Wn là ma trận khoảng cách nhỏ nhất của ñồ thị G. 70 http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập Chứng minh: Ta chứng minh bằng quy nạp theo k mệnh ñề sau: Wk[i,j] là chiều dài ñường ñi ngắn nhất trong những ñường ñi nối ñỉnh vi với ñỉnh vj ñi qua các ñỉnh trung gian trong {v1, v2, ..., vk}. Trước hết mệnh ñề hiển nhiên ñúng với k=0. Giả sử mệnh ñề ñúng với k-1. Xét Wk[i,j]. Có hai trường hợp: 1) Trong các ñường ñi chiều dài ngắn nhất nối vi với vj và ñi qua các ñỉnh trung gian trong {v1, v2, ..., vk}, có một ñường ñi γ sao cho vk ∉ γ. Khi ñó γ cũng là ñường ñi ngắn nhất nối vi với vj ñi qua các ñỉnh trung gian trong {v1, v2, ..., vk-1}, nên theo giả thiết quy nạp, Wk-1[i,j] = chiều dài γ ≤ Wk-1[i,k]+Wk-1[k,j]. Do ñó theo ñịnh nghĩa của Wk thì Wk[i,j]=Wk-1[i,j]. 2) Mọi ñường ñi chiều dài ngắn nhất nối vi với vj và ñi qua các ñỉnh trung gian trong {v1, v2, ..., vk}, ñều chứa vk. Gọi γ = vi ... vk ... vj là một ñường ñi ngắn nhất như thế thì v1 ... vk và vk ... vj cũng là những ñường ñi ngắn nhất ñi qua các ñỉnh trung gian trong {v1, v2, ..., vk-1} và Wk-1[i,k]+Wk-1[k,j] = chiều dài(v1 ... vk) + chiều dài(vk ... vj) = chiều dài γ < Wk-1[i,j]. Do ñó theo ñịnh nghĩa của Wk thì ta có: Wk[i,j] = Wk-1[i,k]+Wk-1[k,j] . Thí dụ 2: Xét ñồ thị G sau: 7 v1 1 3 2 4 v4 v3 1 2 2 4 v2 v5 v6 Áp dụng thuật toán Floyd, ta tìm ñược (các ô trống là ∞) 2  7    4 1    3  W = W0 =   4  2  2    1    71 http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập     W1 =   2      4 1  3  , W2 = 4   9 2 4   1        2    1 5     W3 =   2    7 11 2 8 14   4 1 7 3  , W4 = 4 8 5 11  9 2 4 10 5  1 5 2 8        2    6 10 2 7 13   4 1 7  3   4 8 5 11  8 2 4 9 5  1 5 2 8  7 2 7 11 2 8 4 1 4 8 5 9 2 4 10 2    3        9 6 9 2 7 12   9 6 9 2 7 12      3 9 3 5 1 6  3 7 3 5 1 6   7 4 7 9 5 3  3  , W* = W6 =  . W5 =   7 4 7 9 5 10   7 4 7 9 5 10  2 8 2 4 9 5  2 6 2 4 7 5      4 1 4 6 2 7  4 1 4 6 2 7      Thuật toán Floyd có thể áp dụng cho ñồ thị vô hướng cũng như ñồ thị có hướng. Ta chỉ cần thay mỗi cạnh vô hướng (u,v) bằng một cặp cạnh có hướng (u,v) và (v,u) với m(u,v)=m(v,u). Tuy nhiên, trong trường hợp này, các phần tử trên ñường chéo của ma trận W cần ñặt bằng 0. ðồ thị có hướng G là liên thông mạnh khi và chỉ khi mọi phần tử nằm trên ñường chéo trong ma trận trọng số ngắn nhất W* ñều hữu hạn. 5.2. BÀI TOÁN LUỒNG CỰC ðẠI. 5.2.1. Luồng vận tải: 5.2.1.1. ðịnh nghĩa: Mạng vận tải là một ñồ thị có hướng, không có khuyên và có trọng số G=(V,E) với V={v0, v1, ..., vn} thoả mãn: 1) Mỗi cung e ∈ E có trọng số m(e) là một số nguyên không âm và ñược gọi là khả năng thông qua của cung e. 2) Có một và chỉ một ñỉnh v0 không có cung ñi vào, tức là degt(v0)=0. ðỉnh v0 ñược gọi là lối vào hay ñỉnh phát của mạng. 3) Có một và chỉ một ñỉnh vn không có cung ñi ra, tức là dego(vn)=0. ðỉnh vn ñược gọi là lối ra hay ñỉnh thu của mạng. 72 http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập 5.2.1.2. ðịnh nghĩa: ðể ñịnh lượng khai thác, tức là xác ñịnh lượng vật chất chuyển qua mạng vận tải G=(V,E), người ta ñưa ra khái niệm luồng vận tải và nó ñược ñịnh nghĩa như sau. Hàm ϕ xác ñịnh trên tập cung E và nhận giá trị nguyên ñược gọi là luồng vận tải của mạng vận tải G nếu ϕ thoả mãn: 1) ϕ(e) ≥ 0, ∀e ∈ E. 2) ∑ ϕ (e) = ∑ ϕ (e) , ∀v ∈V, v≠v0, v≠vn. Ở ñây, Γ − (v)={e∈E | e có ñỉnh cuối là v}, e∈Γ − ( v ) e∈Γ + ( v ) Γ + (v)={e∈E | e có ñỉnh ñầu là v}. 3) ϕ(e) ≤ m(e), ∀e ∈ E. Ta xem ϕ(e) như là lượng hàng chuyển trên cung e=(u,v) từ ñỉnh u ñến ñỉnh v và không vượt quá khả năng thông qua của cung này. Ngoài ra, từ ñiều kiện 2) ta thấy rằng nếu v không phải là lối vào v0 hay lối ra vn, thì lượng hàng chuyển tới v bằng lượng hàng chuyển khỏi v. Từ quan hệ 2) suy ra: 4) ∑ ϕ (e) = ∑ ϕ (e) =: ϕ vn . e∈Γ + (v0 ) e∈Γ − ( vn ) ðại lượng ϕ vn (ta còn ký hiệu là ϕ n ) ñược gọi là luồng qua mạng, hay cường ñộ luồng tại ñiểm vn hay giá trị của luồng ϕ. Bài toán ñặt ra ở ñây là tìm ϕ ñể ϕ vn ñạt giá trị lớn nhất, tức là tìm giá trị lớn nhất của luồng. 5.2.1.3. ðịnh nghĩa: Cho mạng vận tải G=(V,E) và A ⊂ V. Ký hiệu Γ − (A)={(u,v)∈E | v∈A, u∉A}, Γ + (A)={(u,v)∈E | u∈A, v∉A}. ðối với tập cung M tuỳ ý, ñại lượng ϕ(M)= ∑ ϕ (e) ñược gọi là luồng của tập e∈M cung M. Từ ñiều kiện 2) dễ dàng suy ra hệ quả sau. 5.2.1.4. Hệ quả: Cho ϕ là luồng của mạng vận tải G=(V,E) và A ⊂ V \{v0,vn}. Khi ñó: ϕ( Γ − (A))=ϕ( Γ + (A)). 5.2.2. Bài toán luồng cực ñại: Cho mạng vận tải G=(V,E). Hãy tìm luồng ϕ ñể ñạt ϕ vn max trên mạng G. Nguyên lý của các thuật toán giải bài toán tìm luồng cực ñại là như sau. 5.2.2.1. ðịnh nghĩa: Cho A ⊂ V là tập con tuỳ ý không chứa lối vào v0 và chứa lối ra vn. Tập Γ − (A) ñược gọi là một thiết diện của mạng vận tải G. ðại lượng m( Γ − (A))= ∑ m( e) ñược gọi là khả năng thông qua của thiết diện − e∈Γ ( A) Γ − (A). 73 http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập Từ ñịnh nghĩa thiết diện và khả năng thông qua của nó ta nhận thấy rằng: mỗi ñơn vị hàng hoá ñược chuyển từ v0 ñến vn ít nhất cũng phải một lần qua một cung nào ñó của thiết diện Γ − (A). Vì vậy, dù luồng ϕ và thiết diện Γ − (A) như thế nào ñi nữa cũng vẫn thoả mãn quan hệ: ϕn ≤ m( Γ − (A)). Do ñó, nếu ñối với luồng ϕ và thiết diện W mà có: ϕn = m(W) thì chắc chắn rằng luồng ϕ ñạt giá trị lớn nhất và thiết diện W có khả năng thông qua nhỏ nhất. 5.2.2.2. ðịnh nghĩa: Cung e trong mạng vận tải G với luồng vận tải ϕ ñược goi là cung bão hoà nếu ϕ(e)=m(e). Luồng ϕ của mạng vận tải G ñược gọi là luồng ñầy nếu mỗi ñường ñi từ v0 ñến vn ñều chứa ít nhất một cung bão hoà. Từ ñịnh nghĩa trên ta thấy rằng, nếu luồng ϕ trong mạng vận tải G chưa ñầy thì nhất ñịnh tìm ñược ñường ñi α từ lối vào v0 ñến lối ra vn không chứa cung bão hoà. Khi ñó ta nâng luồng ϕ thành ϕ’ như sau: ϕ (e) + 1 khi e∈α , ϕ ' ( e) =  khi e∉α . ϕ (e) Khi ñó ϕ’ cũng là một luồng, mà giá trị của nó là: ϕ’n = ϕn +1 > ϕn. Như vậy, ñối với mỗi luồng không ñầy ta có thể nâng giá trị của nó và nâng cho tới khi nhận ñược một luồng ñầy. Tuy vậy, thực tế cho thấy rằng có thể có một luồng ñầy, nhưng vẫn chưa ñạt tới giá trị cực ñại. Bởi vậy, cần phải dùng thuật toán Ford-Fulkerson ñể tìm giá trị cực ñại của luồng. 5.2.2.3. Thuật toán Ford-Fulkerson: ðể tìm luồng cực ñại của mạng vận tải G, ta xuất phát từ luồng tuỳ ý ϕ của G, rồi nâng luồng lên ñầy, sau ñó áp dụng thuật toán Ford-Fulkerson hoặc ta có thể áp dụng thuật toán Ford-Fulkerson trực tiếp ñối với luồng ϕ. Thuật toán gồm 3 bước: Bước 1 (ñánh dấu ở ñỉnh của mạng): Lối vào v0 ñược ñánh dấu bằng 0. 1) Nếu ñỉnh vi ñã ñược ñánh dấu thì ta dùng chỉ số +i ñể ñánh dấu cho mọi ñỉnh y chưa ñược ñánh dấu mà (vi,y)∈E và cung này chưa bão hoà (ϕ(vi,y)0). 74 http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập Nếu với phương pháp này ta ñánh dấu ñược tới lối ra vn thì trong G tồn tại giữa v0 và vn một xích α, mọi ñỉnh ñều khác nhau và ñược ñánh dấu theo chỉ số của ñỉnh liền trước nó (chỉ sai khác nhau về dấu). Khi ñó chắc chắn ta nâng ñược giá trị của luồng. Bước 2 (nâng giá trị của luồng): ðể nâng giá trị của luồng ϕ, ta ñặt: ϕ’(e) = ϕ(e), nếu e∉α, ϕ’(e) = ϕ(e)+1, nếu e∈α ñược ñịnh hướng theo chiều của xích α ñi từ vo ñến vn, ϕ’(e) = ϕ(e)−1, nếu e∈α ñược ñịnh hướng ngược với chiều của xích α ñi từ vo ñến vn. +i e y vj z vi 0 -j v0 vn ϕ’ thoả mãn các ñiều kiện về luồng, nên ϕ’ là một luồng và ta có: ϕ’n = ϕn+1. Như vậy, ta ñã nâng ñược luồng lên một ñơn vị. Sau ñó lặp lại một vòng mới. Vì khả năng thông qua của các cung ñều hữu hạn, nên quá trình phải dừng lại sau một số hữu hạn bước. Bước 3: Nếu với luồng ϕ0 bằng phương pháp trên ta không thể nâng giá trị của luồng lên nữa, nghĩa là ta không thể ñánh dấu ñược ñỉnh vn, thì ta nói rằng quá trình nâng luồng kết thúc và ϕ0 ñã ñạt giá trị cực ñại, ñồng thời gọi ϕ0 là luồng kết thúc. Khi mạng vận tải G=(V,E) ñạt tới luồng ϕ0, thì bước tiếp theo ta không thể ñánh dấu ñược tới lối ra vn. Trên cơ sở hiện trạng ñược ñánh dấu tại bước này, ta sẽ chứng minh rằng luồng ϕ0 ñã ñạt ñược giá trị cực ñại. 5.2.2.4. Bổ ñề: Cho luồng ϕ của mạng vận tải G=(V,E) và A ⊂ V, chứa lối ra vn và không chứa lối vào v0. Khi ñó: ϕ vn = ϕ (Γ − ( A)) − ϕ (Γ + ( A)) . Chứng minh: ðặt A1=A \{vn}. Theo Hệ quả 5.2.1.4, ta có: ϕ (Γ − ( A1 )) = ϕ (Γ + ( A1 )) (1). ðặt C1={(a,vn)∈E | a∉A}. Khi ñó Γ − ( A) = Γ − ( A1 ) ∪ C1 và Γ − ( A1 ) ∩ C1 = ∅, nên ϕ (Γ − ( A)) = ϕ (Γ − ( A1 )) + ϕ (C1) (2). ðặt C2={(b,vn)∈E | b∈A1}. Khi ñó C2={(b,vn)∈E | b∈A}, Γ + ( A1 ) = Γ + ( A) ∪ C2 và Γ + ( A) ∩ C2 = ∅, nên ϕ (Γ + ( A)) = ϕ (Γ + ( A1 )) − ϕ (C2) (3). 75 http://ebook.here.vn Tải miễn phí ðề thi, eBook, Tài liệu học tập Ngoài ra, Γ − (v n ) = C1∪C2 và C1∩C2 = ∅, nên ϕ vn = ϕ (Γ − (v n )) = ϕ (C1)+ ϕ (C2) (4). Từ (1), (2), (3) và (4), ta có: ϕ vn = ϕ (Γ − ( A)) − ϕ (Γ + ( A)) . 5.2.2.5. ðịnh lý (Ford-Fulkerson): Trong mạng vận tải G=(V,E), giá trị lớn nhất của luồng bằng khả năng thông qua nhỏ nhất của thiết diện, nghĩa là max ϕ vn = ϕ min A⊂V ,v0∉A,vn∈A m(Γ − ( A)) . Chứng minh: Giả sử trong mạng vận tải G, ϕ0 là luồng cuối cùng, mà sau ñó bằng phương pháp ñánh dấu của thuật toán Ford-Fulkerson không ñạt tới lối ra vn. Trên cơ sở hiện trạng ñược ñánh dấu lần cuối cùng này, ta dùng B ñể ký hiệu tập gồm các ñỉnh của G không ñược ñánh dấu. Khi ñó v0∉B, vn∈B. Do ñó Γ − (B) là một thiết diện của mạng vận tải G và theo Bổ ñề 5.2.2.4, ta có: ϕ v0 = ϕ 0 (Γ − ( B)) − ϕ 0 (Γ + ( B )) (1). n ðối với mỗi cung e=(u,v)∈ Γ − (B) thì u∉B và v∈B, tức là u ñược ñánh dấu và v không ñược ñánh dấu, nên theo nguyên tắc ñánh dấu thứ nhất, e ñã là cung bão hoà: ϕ0(e) = m(e). ϕ 0 (Γ − ( B)) = Do ñó, ∑ ϕ 0 (e) = ∑ m(e) = m(Γ − ( B)) − (2). − e∈Γ ( B ) + e∈Γ ( B ) ðối với mỗi cung e=(s,t)∈ Γ (B) thì s∈B và t∉B, tức là s không ñược ñánh dấu và t ñược ñánh dấu, nên theo nguyên tắc ñánh dấu thứ hai: ϕ0(e) = 0. ϕ 0 (Γ + ( B )) = Do ñó, ∑ ϕ 0 (e) = 0 (3). + e∈Γ ( B ) Từ (1), (2) và (3) ta suy ra: ϕ v0 = m(Γ − ( B )) . n Vì vậy, ϕ v0 n là giá trị lớn nhất của luồng ñạt ñược, còn m( Γ − (B)) là giá trị nhỏ nhất trong các khả năng thông qua của các thiết diện thuộc mạng vận tải G. Thí dụ 3: Cho mạng vận tải như hình dưới ñây với khả năng thông qua ñược ñặt trong khuyên tròn, luồng ñược ghi trên các cung. Tìm luồng cực ñại của mạng này. Luồng ϕ có ñường ñi (v0,v4), (v4,v6), (v6,v8) gồm các cung chưa bão hoà nên nó chưa ñầy. Do ñó có thể nâng luồng của các cung này lên một ñơn vị, ñể ñược ϕ1. Do mỗi ñường xuất phát từ v0 ñến v8 ñều chứa ít nhất một cung bão hoà, nên luồng ϕ1 là luồng ñầy. Song nó chưa phải là luồng cực ñại. Áp dụng thuật toán Ford-Fulkerson ñể nâng luồng ϕ1. 76 This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

Tìm kiếm

Chủ đề

Atlat Địa lí Việt Nam Tài chính hành vi Lý thuyết Dow Hóa học 11 Đề thi mẫu TOEIC Thực hành Excel Đơn xin việc Bài tiểu luận mẫu Đồ án tốt nghiệp Mẫu sơ yếu lý lịch Giải phẫu sinh lý Trắc nghiệm Sinh 12 adblock ​ Bạn đang sử dụng trình chặn quảng cáo?

Nếu không có thu nhập từ quảng cáo, chúng tôi không thể tiếp tục tài trợ cho việc tạo nội dung cho bạn.

Tôi hiểu và đã tắt chặn quảng cáo cho trang web này