Luận văn Một số bài toán tối ưu trên đồ thị và ứng dụng

đi từ một đỉnh đầu tới một đỉnh cuối. Nếu với hai đỉnh u, v bất kỳ, có nhiều nhất một cạnh đi từ u tới v thì G được gọi là một đồ thị đơn có hướng. Nếu (a, b) ∈ E thì (a, b) được gọi là cạnh (cung) của G với đỉnh đầu là a, đỉnh cuối là b và có hướng đi từ a tới b. Ví dụ 1.1.1. a. Đồ thị vô hướng G = (V,E) trong đó: V = {a, b, c, d, e, f}, E = {(a, b), (a, e), (b, e), (c, d)} (Hình 1.1.a) b. Đồ thị có hướng G = (V,E) trong đó: V = {a, b, c, d, e, f}, E = {(a, b), (b, e), (c, d), (d, c), (e, a), (f, f)} (Hình 1.1b) Đồ thị G = (V,E) được gọi là đồ thị có trọng số (hay trọng đồ), nếu mỗi cạnh có một trọng số kết hợp, thường được cung cấp bởi một hàm trọng số w : E → R. Ví dụ 1.1.2. a. Đồ thị vô hướng G = (V,E) trong đó: V = {a, b, c, d, e, f}, E = {(a, b), (a, e), (b, e), (c, d)} 9(a) Đơn đồ thị vô hướng (b) Đơn đồ thị có hướng Hình 1.1: Đơn đồ thị vô hướng(a) và có hướng(b) và w(a, b) = 3, w(a, e) = 4, w(b, e) = 4.5, w(c, d) = 6 (Hình 1.2a) b. Đồ thị có hướng G = (V,E) trong đó: V = {a, b, c, d, e, f}, E = {(a, b), (b, e), (c, d), (d, c), (e, a), (f, f)} w(a, b) = 1.5, w(b, e) = 2, w(c, d) = 5,w(d, c) = 3.2, w(e, a) = 4, w(f, f) = 8 (Hình 1.2b) (a) (b) Hình 1.2: Đơn đồ thị vô hướng có trọng số(a) và có hướng có trọng số (b) Định nghĩa 1.1.3. Một đồ thị con của đồ thị G là một đồ thị H = (W,F ) sao choW ⊂ V, F ⊂ E. Tiếp sau đây là một số thuật ngữ cơ bản của lý thuyết đồ thị. 10 Trước tiên, ta xét các thuật ngữ mô tả các đỉnh và các cạnh của đồ thị vô hướng. Nếu (u, v) là một cạnh nằm trong đồ thị G = (V,E) ta nói đỉnh v kề với đỉnh u. Trong đồ thị vô hướng, quan hệ kề là đối xứng. Nếu e = (u, v) là cạnh của đồ thị ta nói cạnh này là liên thuộc với hai đỉnh u và v, hoặc cũng nói là nối đỉnh u và đỉnh v, đồng thời các đỉnh u và v sẽ được gọi là các đỉnh đầu của cạnh (u, v). Để biết có bao nhiêu cạnh liên thuộc với một đỉnh, ta dựa vào định nghĩa sau: Định nghĩa 1.1.4. Bậc của một đỉnh trong một đồ thị vô hướng là số lượng các cạnh liên thuộc trên nó. Ký hiệu: deg(v). Đỉnh v được gọi là đỉnh cô lập nếu deg(v) = 0. Đỉnh v được gọi là đỉnh treo nếu deg(v) = 1. Ta xét các thuật ngữ tương tự cho đồ thị có hướng Tương tự với đồ thị vô hướng, ta có khái niệm về quan hệ kề đối với đồ thị có hướng. Và trong một đồ thị có hướng, quan hệ kề không nhất thiết đối xứng. Nếu v kề với u trong một đồ thị có hướng, đôi lúc ta viết u→ v. Nếu (u, v) là một cạnh trong một đồ thị G = (V,E) , ta nói rằng (u, v) liên thuộc từ (incident from) đỉnh u và liên thuộc đến (incident to) đỉnh v. Định nghĩa 1.1.5. Trong một đồ thị có hướng, bậc đi ra của một đỉnh là số lượng cạnh rời khỏi nó, bậc đi vào của một đỉnh là số lượng cạnh nhập vào nó. Bậc của một đỉnh trong đồ thị có hướng là bậc đi ra cộng bậc đi vào của nó. Hay ta còn có thể viết dưới dạng sau: Giả sử G = (V,E) là một đồ thị có hướng và v ∈ V . Kí hiệu: 11 d+(v) = {x ∈ V |(v, x) ∈ E} d−(v) = {y ∈ V |(y, v) ∈ E} Khi đó |d+(v)| được gọi là bậc đi ra, |d−(v)| được gọi là bậc đi vào của v. d(v) = d+(v) + d−(v) Đỉnh v được gọi là đỉnh cô lập nếu d+(v) + d−(v) = 0. Đỉnh v được gọi là đỉnh treo nếu d+(v) + d−(v) = 1. 1.1.2 Biểu diễn đồ thị Biểu diễn đồ thị trên mặt phẳng là một biểu diễn cho ta phép nhìn nhận đối tượng này một cách khá trực quan. Tuy nhiên, ta vẫn cần tới các biểu diễn khác của đồ thị để đáp ứng các đòi hỏi khác nhau của các ứng dụng. Và có hai cách thường dùng để biểu diễn một đồ thị G = (V,E) : sử dụng một danh sách kề hoặc sử dụng một ma trận kề. Phép biểu diễn danh sách kề cung cấp một cách gắn gọn để biểu diễn các đồ thị thưa - là những đồ thị mà |E| nhỏ hơn nhiều so với |V |2. Phép biểu diễn ma trận kề được ưa dùng khi đồ thị là trù mật -|E| sát với |V |2 hoặc khi ta cần nhanh chóng biết một cạnh nối hai đỉnh đã cho hay không. Biểu diễn đồ thị bằng danh sách kề Trong khoa học máy tính, danh sách kề là một cấu trúc dữ liệu gắn bó chặt chẽ với việc biểu diễn đồ thị. Phép biểu diễn danh sách kề của một đồ thị G = (V,E) gồm một mảng Adj có độ lớn là |V |, ứng với các đỉnh của V . Với mỗi đỉnh u của đồ thị, ta cho tương ứng với nó một danh sách các đỉnh kề với u, nghĩa là sao cho có cạnh 12 (u, v) ∈ E. Nếu G là một đồ thị có hướng thì tổng các chiều dài của tất cả các danh sách kề là |E|, bởi mỗi cạnh (u, v) thể hiện v xuất hiện trong Adj[u]. Nếu G là một đồ thị vô hướng thì tổng các chiều dài của tất danh sách kề là 2|E|, vì nếu (u, v) là một cạnh vô hướng thì u xuất hiện trong danh sách kề của v và ngược lại. Danh sách kề có thể thay đổi để biểu diễn đồ thị có trọng số. Khi đó, trọng số w(u, v) của cạnh (u, v) được lưu trữ với đỉnh v trong danh sách kề của u. Một nhược điểm của phép biểu diễn danh sách kề đó là để xác định xem một cạnh đã cho (u, v) có tồn tại trong đồ thị hay không, ta không còn cách nào nhanh hơn là tìm kiếm v trong danh sách kề Adj[u].Có thể khắc phục nhược điểm này bằng một phép biểu diễn ma trận kề của đồ thị, để đổi lại, ta phải dùng nhiều bộ nhớ hơn. Ví dụ 1.1.3. Hai phép biểu diễn đồ thị vô hướng Hình 1.1a. (a) Biểu diễn danh sách kề của G (b) Biểu diễn ma trận kề của G Hình 1.3: Hai phép biểu diễn đồ thị vô hướng trong hình 1.1a Ví dụ 1.1.4. Hai phép biểu diễn của đồ thị có hướng Hình 1.1b 13 (a) Biểu diễn danh sách kề của G (b) Biểu diễn ma trận kề của G Hình 1.4: Hai phép biểu diễn đồ thị có hướng trong hình 1.1b Biểu diễn đồ thị bằng ma trận kề Xét đơn đồ thị vô hướng G = (V,E) với tập đỉnh V = {v1, v2, . . . , vn}. Khi đó ma trận kề của đồ thị G là ma trận A = (aij)n×n =  a11 a12 . . . a1n a21 a22 . . . a2n . . . an1 an2 . . . ann  trong đó: aij =  1, nếu (vi, vj) ∈ E 0, nếu (vi, vj) /∈ E 14 Dễ thấy rằng ma trận kề A của đồ thị có hướng G hoàn toàn xác định G. Vì vậy, ma trận kề được coi là một biểu diễn của G. Ta có một số tính chất: Tính chất 1.1.1. i. Ma trận kề của đồ thị vô hướng là một ma trận đối xứng. ii. Tổng các phần tử trên dòng i (cột j) bằng bậc của đỉnh tương ứng. Cũng tương tự phép biểu diễn danh sách kề của một đồ thị, phép biểu diễn ma trận kề có thể được dùng cho các đồ thị có trọng số. Khi đó, nếu G là một đồ thị có trọng số, ta có ma trận A = (aij)n×n trong đó: aij =  w(vi, vj), nếu (vi, vj) ∈ E 0, nếu (vi, vj) /∈ E Ví dụ 1.1.5. Ví dụ về danh sách kề và ma trận kề có trọng số cho đồ thị trong ví dụ 1.2a. (a) Biểu diễn danh sách kề của G (b) Biểu diễn ma trận kề của G Hình 1.5: Hai phép biểu diễn đồ thị có trọng số trong hình 1.2a 15 1.2 ĐƯỜNG ĐI VÀ TÍNH LIÊN THÔNG 1.2.1 Đường đi và chu trình Xét một đồ thị vô hướng Giả sử G = (V,E) là một đồ thị vô hướng. Một đường đi trong G là một dãy v0e1v1e2v2 . . . envn sao cho: + Với mọi i = 0, 1, 2, .., n, vi ∈ V , + Với mọi i = 1, 2, . . . , n, ei ∈ E và ei = (vi−1, vi) hoặc ei = (vi, vi−1). Khi đó, n được gọi là độ dài, đỉnh v0 được gọi là đỉnh đầu, đỉnh vn được gọi là đỉnh cuối của đường đi trên. Một chu trình là một đường có điểm đầu và điểm cuối trùng nhau. Một đường đi đơn (chu trình đơn) là một đường đi (chu trình) không đi qua cạnh nào quá một lần. Xét một đồ thị có hướng Hoàn toàn tương tự, ta có các định nghĩa với đồ thị có hướng. Giả sử G = (V,E) là một đồ thị có hướng. Một đường đi trong G là một dãy v0e1v1e2v2 . . . envn sao cho: + Với mọi i = 0, 1, 2, .., n, vi ∈ V , + Với mọi i = 1, 2, . . . , n, ei ∈ E và ei = (vi−1, vi). Khi đó n được gọi là độ dài, đỉnh v0 được gọi là đỉnh đầu, đỉnh vn được gọi là đỉnh cuối của đường có hướng trên. Một đường đi đơn (chu trình đơn) là một 16 đường đi (chu trình) không đi qua cạnh nào quá một lần. Trong trường hợp đồ thị có hướng, xét một đường đi v0e1v1e2v2 . . . envn, mỗi cạnh ei đều có đỉnh đầu là đỉnh đứng trước và đỉnh cuối là đỉnh đứng sau ei trong dãy, tức là nó được xác định bởi chính hai đỉnh đó. Vì vậy, khi đồ thị không có cạnh bội, ta biểu diễn đường đi bằng dãy các đỉnh, bỏ qua các cạnh, và đơn giản gọi dãy các đỉnh v0v1v2 . . . vn của G là đường đi trong G nếu với mọi i = 0, 1, ...., n− 1, (vi, vi+1) là một cạnh của G. Ví dụ 1.2.1. Giả sử G = (V,E) là đồ thị có hướng như hình 1.6. Khi đó: a. a→ b→ f → e→ b→ c là một đường đi có hướng với đỉnh đầu là a, đỉnh cuối là c với độ dài bằng 5. b. a→ b→ e→ d→ c→ b→ e→ f là một đường đi vô hướng với đỉnh đầu là a, đỉnh cuối là f với độ dài bằng 7. c. b→ f → e→ b là một đường đi có hướng khép kín. d. b→ e→ d→ c→ b là một đường đi vô hướng khép kín. Hình 1.6: Ví dụ về một đồ thị có hướng 17 1.2.2 Tính liên thông Xét một đồ thị vô hướng Định nghĩa 1.2.1. Một đồ thị G = (V,E) được gọi là liên thông nếu với hai đỉnh vivà vj khác nhau bất kỳ của G đều tồn tại một đường đi đơn trong G với đỉnh đầu là vi và đỉnh cuối là vj . Trong trường hợp ngược lại, đồ thị được gọi là không liên thông. Một thành phần liên thông của G là một đồ thị con liên thông cực đại (theo nghĩa bao hàm) của G. Ta có mệnh đề sau: Mệnh đề 1.2.1. Với mọi cặp đỉnh u, v khác nhau, các thành phần liên thông chứa u và chứa v hoặc trùng nhau, hoặc rời nhau. Chúng trùng nhau khi và chỉ khi u và v được nối với nhau bởi một đường đi. Xét một đồ thị có hướng Định nghĩa 1.2.2. Một đồ thị G = (V,E) được gọi là liên thông yếu (liên thông) nếu với hai đỉnh vi và vj khác nhau bất kỳ của G đều tồn tại một đường đi đơn trong G với đỉnh đầu là vi và đỉnh cuối là vj . Trong trường hợp ngược lại, đồ thị được gọi là không liên thông. Ngoài ra, ta có định nghĩa liên thông mạnh cho đồ thị có hướng. Định nghĩa 1.2.3. Một đồ thị G = (V,E) được gọi là liên thông mạnh nếu với hai đỉnh bất kỳ khác nhau vi và vj , tồn tại cả đường đi với đỉnh đầu là vi, đỉnh cuối là vj và đường đi với đỉnh đầu là vj , đỉnh cuối là vi. 18 Nhận xét 1.2.1. Một đồ thị liên thông mạnh thì liên thông. Điều ngược lại chưa chắc đúng. Như vậy hai máy tính bất kỳ trong mạng có thể trao đổi thông tin được với nhau khi và chỉ khi đồ thị tương ứng với mạng này là đồ thị liên thông. Ví dụ 1.2.2. Đồ thị trong hình 1.1a là đồ thị vô hướng không liên thông. 19 CHƯƠNG 2 BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ Một trong số các bài toán quan trọng của lý thuyết đồ thị là bài toán tìm đường đi ngắn nhất giữa hai đỉnh trong một đồ thị. Trong thực tế, bài toán này có một ý nghĩa to lớn, vì nhiều bài toán có thể đưa về dạng bài toán tìm đường đi ngắn nhất. Ví dụ, bài toán chọn một hành trình tiết kiệm nhất (theo khoảng cách hoặc thời gian hoặc chi phí) trên một mạng giao thông đường bộ, đường thủy hoặc đường không, bài toán lập lịch thi công các công đoạn trong một công trình lớn, bài toán lựa chọn đường truyền tin với chi phí nhỏ nhất trong mạng thông tin,. . . Và để giải quyết những bài toán đó, các thuật toán được xây dựng dựa trên cơ sở lý thuyết đồ thị tỏ ra là các thuật toán có hiệu quả. Trong chương này chúng ta sẽ xét một số thuật toán như vậy. 20 2.1 BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT Cho một đồ thị có hướng có trọng số G = (V,E,w). Độ dài một đường đi p = (v0v1...vk) được định nghĩa bởi: w(p) = ∑k 1 w(vi−1, vi) Ta định nghĩa khoảng cách đường đi ngắn nhất δ(u, v) từ u đến v bởi công thức: δ(u, v) =  minw(p), nếu có một lộ trình từ u đến v ∞, nếu không có một lộ trình từ u đến v Khi đó, một đường đi p từ u đến v là ngắn nhất nếu w(p) = δ(u, v). Ta có thể có các dạng của bài toán: 1. Cho trước 2 đỉnh. Tìm một đường đi ngắn nhất giữa chúng. 2. Cho trước 1 đỉnh. Tìm một đường đi ngắn nhất từ đỉnh đó đến các đỉnh còn lại. 3. Cho trước 1 đỉnh. Tìm một đường đi ngắn nhất từ mỗi đỉnh đến đỉnh đó. 4. Tìm một đường đi ngắn nhất giữa tất cả các cặp đỉnh. Ta dễ dàng nhận thấy, bài toán thứ hai và thứ ba là bài toán ngược của nhau, nên độ khó là tương đương. Bài toán thứ nhất là trường hợp con của bài toán thứ hai, và bài toán thứ hai là trường hợp con của bài toán thứ tư. Tuy nhiên, ta sẽ thấy rằng thực chất việc giải bài toán thứ nhất không đơn giản 21 hơn giải bài toán thứ hai, vì muốn tìm đường ngắn nhất giữa hai đỉnh, ta vẫn phải khảo sát cả đồ thị. Ngược lại, việc giải bài toán thứ hai lại thực sự đơn giản hơn bài toán thứ tư, và một trong những thuật toán có độ phức tạp thấp để giải bài toán thứ tư là gọi n lần bài toán thứ hai, mỗi lần chọn đỉnh nguồn là một đỉnh của đồ thị. 2.2 THUẬT TOÁN DIJKSTRA Thuật toán Dijkstra được mang tên nhà khoa học máy tính người Hà Lan Edsger Dijkstra vào năm 1956 và công bố năm 1959, là một thuật toán giải quyết bài toán đường đi ngắn nhất nguồn đơn trong một đồ thị có hướng liên thông không có cạnh mang trọng số âm. Dữ kiện của bài toán quy về việc xét bài toán thứ nhất. Trong phần này, ta sẽ tập trung vào mô tả thuật toán và chứng minh tính đúng đắn của thuật toán. Độ phức tạp sẽ thừa nhận, không chứng minh. 2.2.1 Mô tả thuật toán Thuật toán áp dụng cho các đồ thị liên thông có trọng số không âm. Trong thuật toán này, ở mỗi bước, ta đã xét thêm được một đỉnh v, xác định được đường đi ngắn nhất từ s đến v. Mục đích của việc cập nhật là để xét các đỉnh lân cận u với v xem đường đi mới từ s đến u và thông qua v có ngắn hơn đường đi cũ hay không, nếu ngắn hơn thì ta thay thế nó cho đường đi cũ, và v sẽ được gán cho p[u]. 22 Giả mã: Input: G = (V,E,w); s ∈ V Output:Một đường đi ngắn nhất từ s đến v SP (s, v);∀v ∈ V ; begin d[v]: độ dài đường đi ngắn nhất từ s đến v; p[v]: đỉnh trước v trong đường đi từ s đến v; S := ∅; Q := {s}; foreach {v ∈ V } do if {v = s} then d[v] := 0; else d[v] :=∞; p[v] := null; Q := Q ∪ {v} end end while {Q 6= ∅} do v := đỉnh trong Q sao cho d[v] nhỏ nhất for {u ∈ Adj(v) and u /∈ S} do if {d[u] > d[v] + d[v, u]} then d[u] := d[v] + d[v, u]; p[u] := v; if {u /∈ Q} then Q := Q ∪ {u}; end end end S := S ∪ {v}; Q := Q \ {v}; end end Algorithm 1: Thuật toán Dijkstra 23 2.2.2 Chứng minh tính đúng đắn của thuật toán Ta có nhận xét sau: Nếu tại thời điểm t, d[u] <∞ thì tồn tại một đường đi từ s đến u mà chỉ đi qua những đỉnh thuộc S. Trong quá trình chứng minh, ta kí kiệu thêm biến chỉ số thời gian, St, Qt, dt[v] là S,Q, d[v] tại thời điểm t. Gọi δ(v) là độ dài đường đi ngắn nhất từ s đến v trên đồ thị G. Để chứng minh thuật toán trên đúng đắn, ta sẽ chứng minh các điều sau: 1. Nếu v ∈ St thì dt[v] = δ(v). 2. Nếu u ∈ Qt thì dt(u) là độ dài đường đi ngắn nhất từ s đến u mà chỉ đi qua các đỉnh trong St. Chứng minh. Ta sẽ chứng minh bằng phương pháp quy nạp theo t ≥ 1. Giả sử ý 1 và ý 2 đúng đến thời điểm t− 1. Ta cần chứng minh ý 1 và ý 2 đúng tại thời điểm t. * Chứng minh 1 Giả sử v là điểm được thêm vào tại thời điểm t: St = St−1 ∪ {v} Giả sử có một đường đi p∗ từ s đến v sao cho w(p∗) < dt[v]. Hình 2.1: Minh họa cho chứng minh ý 1. 24 Vì dt[v] = dt−1[v] là độ dài đường đi ngắn nhất từ s đến v và chỉ đi qua các đỉnh thuộc St−1 (dựa vào tính chất 2 trong thời gian t− 1) nên p∗ chứa ít nhất 1 đỉnh nằm ngoài St−1. Gọi z là đỉnh đầu tiên như thế trên p (tính từ s). Gọi p1 là một đường đi từ s đến z chỉ đi qua các đỉnh thuộc St−1, p2 là một đường đi từ z đến v. Khi đó: w(p∗) = w(p1) + w(p2) > w(p1) ≥ dt−1[z] (Vì p1 là đường đi từ s đến z chỉ đi qua các đỉnh thuộc St−1 nên w(p1) ≥ d[z].) Mặt khác, w(p∗) < dt[v] = dt−1[v]. Suy ra dt−1[v] > dt−1[z], mâu thuẫn với cách chọn v. Vậy điều giả sử là sai, hay dt[v] = δ(v). * Chứng minh 2 Ta có, dt[u] = min{dt−1[u], dt[v] + d[v, u]}, với u ∈ Adj(v). Gọi p là một đường ngắn nhất từ s đến u chỉ đi qua các đỉnh thuộc St.Ta phải chứng minh dt[u] = w(p). Mà theo định nghĩa, dt[u] ≥ w(p), nên ta chỉ cần chứng minh dt[u] ≤ w(p). Trường hợp 1: p không đi qua v thì p chỉ đi qua các đỉnh thuộc St−1, nên theo giả thiết quy nạp, ta có: w(p) ≥ dt−1[u] ≥ dt[u]. Hình 2.2: Minh họa cho chứng minh ý 2 trường hợp 1. 25 Trường hợp 2: Nếu p đi qua v nhưng v không phải đỉnh kề trước của u trong p. Gọi z là đỉnh liền trước u trong p (z 6= v). Hình 2.3: Minh họa cho chứng minh ý 2 trường hợp 2. Vì z thêm vào tại thời điểm t′ ≤ t − 1 nên theo giả thiết quy nạp, tồn tại một đường đi ngắn nhất p′ từ s đến z sao cho p′ nằm trọn trong St−1. Suy ra δ(z) = dt−1[z] = w(p′). Ta gọi p1 là một đường đi từ s đến z qua v. Khi đó, w(p1) ≥ dt−1[z]. Đường p′ + (z, u) là một đường từ s đến u mà chỉ đi qua các đỉnh thuộc St−1 nên: w(p′ + (z, u)) ≥ dt−1[u]. Khi đó ta có: w(p) = w(p1) + d[z, u] ≥ w(p′) + d[z, u] ≥ dt−1[u] ≥ dt[u]. Vậy w(p) ≥ dt[u]. 26 Trường hợp 3: Nếu p đi qua v và v là đỉnh kề trước của u trong p. Hình 2.4: Minh họa cho chứng minh ý 2 trường hợp 3. Vì p là đường đi ngắn nhất từ s đến u mà chỉ đi qua các đỉnh thuộc St nên p′ là đường đi ngắn nhất từ s đến v mà chỉ đi qua các đỉnh thuộc St. Vì p′ là một đường đi đơn nên nó chỉ đi qua các đỉnh thuộc St\{v}, tức St−1. Theo giả thiết quy nạp ý 2 ứng với thời điểm t− 1, ta có w(p′) = dt−1[v]. Khi đó, w(p) = w(p′) + d[v, u] = dt−1[v] + d[v, u] ≥ dt[u] (Theo công thức tính dt[u]). Kết hợp 3 trường hợp, suy ra (2) được chứng minh. Vậy sau khi thuật toán kết thúc thì d[v] được cập nhật. Lưu ý: p(v) không dùng trong chứng minh nhưng trong thực tế lại cần sử dụng để tìm ra danh sách các đỉnh của đường đi. 27 2.2.3 Độ phức tạp của thuật toán Xét thấy, chi phí tìm v sao cho d[v] nhỏ nhất tốn O(log n), G = (V,E) có n đỉnh, vậy nên sẽ tốn thời gian là O(n log n) thời gian tìm v. Chi phí cập nhật: Tại mỗi bước, ta duyệt tất cả các cạnh đi ra (bằng bậc đi ra của một đỉnh). Vậy tổng chi phí cập nhật bằng tổng các bậc đi ra của các đỉnh, và bằng số cạnh. Hay chi phí cập nhật là O(m). Khi đó, trong trường hợp tổng quát, độ phức tạp của thuật toán là O(m + n log n). Nếu đồ thị G thưa, độ phức tạp là O(n log n). Nếu đồ thị G trù mật, độ phức tạp là O(n2). 2.2.4 Ví dụ Ví dụ áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất trên đồ thị 2.5.a. Ta có, đỉnh nguồn là s, ta cần tìm đường đi ngắn nhất từ s tới các đỉnh còn lại. Hình 2.5: Thực thi thuật toán Dijkstra Giá trị d được viết trong các đỉnh. Các hình 2.5.b đến 2.5.f là kết quả của mỗi 28 bước thực hiện thuật toán. Kết thúc thuật toán, ta thu được đường đi ngắn nhất từ s tới các đỉnh là đường được tô đậm. 2.3 THUẬT TOÁN BELLMAN-FORD Trong phần trước, ta đã tìm hiểu thuật toán Dijkstra tìm đường đi ngắn nhất từ một đỉnh tới mọi đỉnh khác trong đồ thị có hướng với trọng số không âm trong thời gian O(m + n log n). Nếu đồ thị có trọng số âm, ta không thể áp dụng thuật toán Dijkstra được. Trong trường hợp này, ta sẽ áp dụng thuật toán Bellman-Ford. Ưu điểm của thuật toán Bellman-Ford là giúp phát hiện chu trình âm trong đồ thị. Điểm đặc biệt của đồ thị có trọng số âm là có thể có sự xuất hiện của chu trình âm. Sự xuất hiện này làm cho bài toán trở nên không xác định. Ví dụ một đồ thị tồn tại một chu trình âm là a → b → c → a. Ta muốn tìm đường đi ngắn nhất từ s đến đỉnh t. Ta có thể đi từ s đến a sau đó đi quanh chu trình âm vô hạn lần trước khi đến t. Tuy nhiên, nếu trong đồ thị không có chu trình âm, ta luôn có thể tìm được đường đi ngắn nhất từ một đỉnh đến mọi đỉnh khác trong đồ thị. Thuật toán tìm đường đi ngắn nhất trong đồ thị không có chu trình âm được phát triển bởi Bellman năm 1958 và Ford năm 1956, do đó, nó được đặt tên là thuật toán Bellman-Ford. 2.3.1 Mô tả thuật toán 29 Giả mã: Input: G = (V,E,w); s ∈ V Output:Một đường đi ngắn nhất từ s đến v SP (s, v);∀v ∈ V ; begin d[v]: độ dài đường đi ngắn nhất từ s đến v; p[v]: đỉnh trước v trong đường đi từ s đến v; for v ∈ V do if v = s then d[v] := 0; else d[v] :=∞; p[v] := null; end end for t := 1→ |V | − 1 do foreach (u, v) ∈ E do if d[u] + d[u, v] < d[v] then d[v] := d[u] + d[u, v]; p[v] := u; end end end foreach (u, v) ∈ E do if d[v] > d[u] + d[u, v] then Đồ thị chứa chu trình âm! return false; end end return true; end Algorithm 2: Thuật toán Bellman-Ford 30 2.3.2 Chứng minh tính đúng đắn của thuật toán Định lý 2.3.1. (Định lý tính đúng đắn của thuật toán Bellman-Ford) Sau vòng lặp t, với mọi đỉnh v ta có: 1. Nếu d[v] <∞ thì d[v] là độ dài một đường đi từ s đến v. 2. Nếu có một đường đi p từ s đến v đi qua nhiều nhất t cạnh thì dt[v] ≤ w(p). Khi kết thúc thuật toán, ta có d[v] = δ(v). Chứng minh. Ta chứng minh quy nạp theo t ≥ 0. Với t = 0, định lý trên đúng. Giả sử định lý trên đúng cho tới thời điểm t − 1. Ta cần chứng minh định lý đúng tại thời điểm t. Chứng minh 1: Nếu tại bước t − 1 đã có dt−1[v] < ∞. Suy ra tồn tại một đường đi từ s đến v (Do giả thiết quy nạp). Ngược lại, theo giả thiết quy nạp, tồn tại u sao cho dt[v] = dt[u] + d[u, v] <∞. Chứng minh 2: Có dt[u] ≤ dt−1[u] (vì d[u] không tăng). Nên: dt[v] = min{dt−1[v], dt[u] + d[u, v]} ≤ min{dt−1[v], dt−1[u] + d[u, v]}. Gọi p là một đường đi từ s đến v có nhiều nhất t cạnh. Trường hợp 1: p có nhiều nhất t− 1 cạnh. 31 Khi đó: w(p) ≥ dt−1[v]( theo giả thiết quy nạp tại thời điểm t− 1) ≥ dt[v]. Trường hợp 2: p có t cạnh. Hình 2.6: Minh họa cho chứng minh trường hợp 2 Gọi u là đỉnh liền trước của v trong p, p′ là một đường đi từ s đến u có t− 1 cạnh. Theo giả thiết quy nạp với u, ta có: w(p) = w(p′) + d[u, v] ≥ dt−1[u] + d[u, v] ≥ dt[v]. Suy ra dt[v] là độ dài một đường đi ngắn nhất từ s đến v có nhiều nhất t cạnh. 2.3.3 Độ phức tạp của thuật toán Đối với thuật toán Bellman-Ford, chi phí tính d[v] tốn O((n − 1).m), vì G = (V,E) có n đỉnh nên duyệt n− 1 vòng for, tại mỗi thời điểm lại xét tất cả các cặp cạnh, tốnm thời gian. 32 Chi phí kiểm tra chu trình âm: Ta duyệt tất cả các cặp cạnh của đồ thị. Vậy tổng chi phí cập nhật bằng bằng số cạnh. Hay chi phí cập nhật là O(m). Khi đó, trong trường hợp tổng quát, độ phức tạp của thuật toán là O(nm). 2.3.4 Ví dụ Ví dụ áp dụng thuật toán Bellman-Ford tìm đường đi ngắn nhất trên đồ thị 2.7.a. Ta có, đỉnh nguồn là s, ta cần tìm đường đi ngắn nhất từ s tới các đỉnh còn lại. Hình 2.7: Thực thi thuật toán Bellman-Ford Giá trị d được viết trong các đỉnh. Các hình 2.7.b đến 2.7.e là kết quả của mỗi bước thực hiện thuật toán. Kết thúc thuật toán, ta thu được đường đi ngắn nhất từ s tới các đỉnh là đường được tô đậm. 33 2.4 SO SÁNH Dựa vào các kết quả nêu trên cho thấy, với cùng một bài toán thì thuật toán Di- jkstra có thời gian chạy tốt hơn so với thuật toán Bellman-Ford, song lại không giải quyết được bài toán chứa cạnh trọng số âm. Do đó, thuật toán Bellman-Ford thường được sử dụng trong bài toán chứa cạnh có trọng số âm. Cả hai thuật toán này đều giải quyết bài toán tìm đường đi ngắn nhất nguồn đơn. Sự khác biệt chính của hai thuật toán là thuật toán Dijkstra không thể xử lý các cạnh có trọng số âm. Thuật toán Bellman-Ford có thể xử lý vấn đề đó. Tuy nhiên, phải nhắc lại rằng, nếu có một chu trình âm thì không có đường đi ngắn nhất. 34 CHƯƠNG 3 ỨNG DỤNG: BÀI TOÁN LẬP KẾ HOẠCH Trong thực tế, việc lập kế hoạch tiến độ là một trong những công cụ chính của quản lý dự án. Các hoạt động của dự án có thể được lập kế hoạch tiến độ với mức độ chi tiết khác nhau. Dự án là một tập hợp các hoạt động liên quan với nhau và phải được thực hiện theo một thứ tự nào đó cho đến khi hoàn thành toàn bộ các hoạt động. Hoạt động được hiểu là một việc đòi hỏi thời gian, nguyên liệu để hoàn thành. Việc lập kế hoạch cho biết thời điểm hoàn thành công việc. Cách tiếp cận cơ bản của các kỹ thuật lập kế hoạch là xây dựng một mạng lưới các công việc và mối liên hệ giữa chúng nhằm biểu diễn trình tự giữa các công việc trong dự án. Đồng thời cần xác định rõ các nhiệm vụ cần hoàn thành trước hay sau. Một số thuật ngữ được dùng phổ biến: Công việc (Task/Activity): là một nhiệm vụ hay một tập hợp các nhiệm vụ cụ thể mà dự án yêu cầu, nó tiêu dùng các nguồn lực và cần thời gian để hoàn thành. Sự kiện (Event): là kết quả của việc hoàn thành một hay nhiều công việc. Ta có 35 thể ghi nhận trạng thái kết thúc của các công việc tại một thời điểm cụ thể. Các sự kiện không sử dụng nguồn lực. Đường (Path): là một chuỗi các công việc liên tiếp nhau giữa hai sự kiện trong mạng. Đường tới hạn (Critical path): là các công việc, hay đường mà nếu nó trễ sẽ kéo dài thời gian hoàn thành dự án. Mỗi đường tới hạn của dự án có nghĩa là trình tự các công việc tới hạn (và sự kiện tới hạn) mà nối sự kiện bắt đầu dự án với sự kiện kết thúc dự án. 3.1 MÔ TẢ BÀI TOÁN Một dự án có thể chia thành nhiều công việc T1, . . . , Tn. Trong đó mỗi công việc có một khoảng thời gian dự kiến hoàn thành. Công việc T1 cần c1 đơn vị thời gian thực hiện Công việc T2 cần c2 đơn vị thời gian thực hiện . . . Giữa các công việc có thể có ràng buộc về thời gian, thứ tự, nguồn lực. Trong khuôn khổ luận văn, ta không xét đến việc nguồn lực của dự án: con người, máy móc, . . . , nên giả sử nguồn lực là vô tận, có thể chạy song song nhiều công việc. Có một số ràng buộc về thời gian như sau: Tj phải thực hiện sau Ti, Tk phải thực hiện sau Ti và Tj , 36 Tl phải thực hiện xong trước thời điểm xl, . . . Mục tiêu của bài toán: tính toán ngày kết thúc dự án sao cho sớm nhất. Ta cần tìm các thời điểm d1, d2, . . . , dn, f1, f2, . . . , fn sao cho: + Ti được bắt đầu thực hiện tại thời điểm