Giáo trình Lý thuyết đồ thị - Nguyễn Ngọc Trung

Nội dung text: Giáo trình Lý thuyết đồ thị - Nguyễn Ngọc Trung

1. Tóm tắt bài giảng – Lý thuyết đồ thị Trường ĐHSP TP.HCM Trong đồ thị trên, đỉnh 2 là đỉnh rẽ nhánh vì việc loại đỉnh này cùng với các cạnh (2,3), (2,1), (2,6) sẽ làm đồ thị có 2 thành phần liên thông. Cạnh (2,3) là cầu. Các cạnh còn lại đều không phải là cầu. Đối với đồ thị có hướng khái niệm liên thông khó thỏa mãn hơn do các cung bị hạn chế về chiều.Từ đó, bên cạnh khái niệm liên thông như đề cập trong đồ thị vô hướng, ta sẽ đưa thêm khái niệm liên thông nhẹ hơn: liên thông yếu. Định nghĩa 1.14.Cho G = là đồ thị có hướng. a. G được gọi là liên thông mạnh nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó. b. G được gọi là liên thông yếu nếu đồ thị vô hướng tương ứng với nó (đồ thị vô hướng có được bằng cách biến các cung một chiều thành các cạnh hai chiều) là đồ thị vô hướng liên thông. Ví dụ 1.12. Xét các đồ thị có hướng sau: - Đồ thị G1 là đồ thị liên thông mạnh. - Đồ thị G2 không là đồ thị liên thông mạnh và từ đỉnh 1 đến đỉnh 2 không tồn tại đường đi nào. G2 là đồ thị liên thông yếu vì nếu biến các cung có hướng thành các cạnh vô hướng thì nó là đồ thị liên thông. 1.5 Biểu diễn đồ thị trên máy tính Lý thuyết đồ thị được ứng dụng trong rất nhiều lĩnh vực khác nhau. Để sử dụng được đồ thị hiệu quả và nhanh chóng hơn, chúng ta phải biểu diễn và xử lý được đồ thị với máy tính. Cách biểu diễn thông thường bằng hình vẽ và mô tả tập hợp sẽ không phù hợp với cách thức lưu trữ dữ liệu và xử lý trên máy tính. Chúng ta phải tìm một cấu trúc dữ liệu thích hợp để biểu diễn đồ thị trên máy tính. Có nhiều phương pháp khác nhau để biểu diễn đồ thị trên máy tính. Sau đây chúng ta sẽ lần lượt tìm hiểu một số phương pháp thông dụng. 1.5.1 Biểu diễn đồ thị bằng ma trận kề Trang 11
2. Tóm tắt bài giảng – Lý thuyết đồ thị Trường ĐHSP TP.HCM Định nghĩa 1.15.Cho đồ thị G = , với tập đỉnh V = {v1, v2, , vn}. Ta gọi ma trận kề của đồ thị là ma trận A, kích thước nxn được xác định như sau: ,1 (vi ,v j ) E Aij ,0 (vi ,v j ) E Ví dụ 1.13. a. Xét đồ thị vô hướng sau: 1 2 3 4 5 6 Ma trận kề của đồ thị trên sẽ là: 1 2 3 4 5 6 1 0 1 0 1 1 0 2 1 0 1 1 1 0 3 0 1 0 0 0 0 A 4 1 1 0 0 1 0 5 1 1 0 1 0 0 6 0 0 0 0 0 0 b. Xét đồ thị có hướng sau: Ma trận kề của đồ thị trên sẽ là: 1 2 3 4 1 0 0 0 0 2 1 0 1 1 A 3 1 0 0 0 4 0 0 1 0 Nhận xét. - Chúng ta có thể nhận thấy rằng, ma trận kề của đồ thị vô hướng luôn luôn là mà trận đối xứng. Còn ma trận của đồ thị có hướng thì có thể không có tính chất này. Trang 12
3. Tóm tắt bài giảng – Lý thuyết đồ thị Trường ĐHSP TP.HCM - Đối với đồ thị vô hướng, tổng các phần tử trên dòng i (hay trên cột i) sẽ là bậc của đỉnh vi của đồ thị - Đối với đồ thị có hướng, tổng các phần tử trên dòng i (tương ứng, trên cột i) sẽ là bán bậc ra (bán bậc vào) của đỉnh vi của đồ thị. 1.5.2 Ma trận liên thuộc đỉnh – cạnh Định nghĩa 1.16.Cho G = là đồ thị vô hướng với tập đỉnh V = {v1, v2, , vn} và tập cạnh E = {e1, e2, , em}. Ma trận liên thuộc đỉnh cạnh biểu diễn đồ thị G là ma trận có kích thước nxm được xác định như sau: 1, nếu vi là đỉnh đầu của cạnh ej Aij = 0, nếu vi không là đỉnh đầu của cạnh ej Ví dụ 1.14. Ma trận liên thuộc đỉnh-cạnh của đồ thị dưới đây là: e1 e2 e3 e4 e5 e6 e7 1 e 2 e 3 1 2 1 1 0 1 0 0 0 0 e 2 1 1 0 1 1 1 0 e 4 e e6 3 5 3 0 1 0 0 0 0 0 A 4 0 0 1 1 0 0 1 e 6 4 7 5 5 0 0 0 0 1 0 1 6 0 0 0 0 0 1 0 Định nghĩa 1.17.Cho G = là đồ thị có hướng với tập đỉnh V = {v1, v2, , vn} và tập các cung E = {e1, e2, , em}. Ma trận liên thuộc đỉnh-cạnh biểu diễn đồ thị G là ma trận có kích thước nxm được xác định như sau: 1, nếu vi là đỉnh đầu của cung ej (cung ej đi ra từ vi) Aij = -1, nếu vi là đỉnh cuối của cung ej (cung ej đi vào vi) 0, nếu vi không là đỉnh đầu mút nào của cung ej Ví dụ 1.15. Ma trận liên thuộc đỉnh-cạnh của đồ thị vô hướng dưới đây là: e1 e1 e2 e3 e4 e5 1 1 1 0 0 0 e3 e2 e4 2 1 0 1 1 0 A e5 3 0 1 1 0 1 4 0 0 0 1 1 Trang 13
4. Tóm tắt bài giảng – Lý thuyết đồ thị Trường ĐHSP TP.HCM Nhận xét. - Ma trận liên thuộc đỉnh-cạnh sẽ tiết kiệm bộ nhớ hơn khi đồ thị có ít cạnh/cung. - Trong ma trận của đồ thị vô hướng, số số 1 trên dòng i sẽ là bậc của đỉnh vi. - Trong ma trận của đồ thị có hướng, số số 1 trên dòng i sẽ là bán bậc ra của đỉnh vi, còn số số -1 trên dòng i sẽ là bán bậc vào của đỉnh vi. Ngoài hai phương pháp biểu diễn đồ thị đã trình bày, còn một số cách khác như dùng danh sách cạnh/cung hoặc sử dụng danh sách kề, (xin xem thêm chi tiết trong tài liệu tham khảo). Trang 14
5. Tóm tắt bài giảng – Lý thuyết đồ thị Trường ĐHSP TP.HCM 2 Chương 2. Đồ thị Euler và đồ thị Hamilton 2.1 Đồ thị Euler Định nghĩa 2.1. Cho đồ thị G = . Chu trình đơn trong G đi qua tất cả các cạnh của nó được gọi là chu trình Euler. Đường đi đơn đi qua tất cả các cạnh của đồ thị được gọi là đường đi Euler. Đồ thị G được gọi là đồ thị Euler nếu nó có chứa chu trình Euler. G được gọi là đồ thị nửa Euler nếu nó có chứa đường đi Euler. Ví dụ 2.1. Xét các đồ thị dưới đây: 1 2 1 2 1 2 3 3 4 5 4 5 3 4 5 G1 G2 G3 - Đồ thị G1 là đồ thị Euler (hiển nhiên cũng là nửa Euler) vì nó có chứa chu trình Euler: 1 2 3 5 4 3 1 - Đồ thị G2 không là đồ thị Euler cũng không phải là đồ thị nửa Euler. - Đồ thị G3 dù không có chứa chu trình Euler nhưng nó là đồ thị nửa Euler do có chứa đường đi Euler: 1 2 3 1 4 2 5 4 3. Rõ ràng đồ thị Euler có một tính chất rất hay là chúng ta có thể đi qua tất cả các cạnh của đồ thị, mỗi cạnh chỉ đi qua một lần và quay trở về đỉnh ban đầu. Đồ thị Euler có rất nhiều ứng dụng như: giải bài toán 7 cái cầu ở thành phố Konigsberg, bài toán vẽ hình bằng 1 nét, Để giải được các bài toán này, ta phải mô hình chúng thành đồ thị và xác định xem liệu đó có phải là đồ thị Euler hay không. Câu hỏi đặt ra là “khi nào thì một đồ thị là Euler? ’’. Thật may mắn câu trả lời trọn vẹn đã được Euler tìm ra vào năm 1736 thể hiện qua định lý dưới đây: Định lý 2.1. (Định lý Euler) Đồ thị vô hướng liên thông G là đồ thị Euler khi và chỉ khi mọi đỉnh của G đều có bậc chẵn. Để chứng minh định lý này, trước hết ta sẽ chứng minh bổ đề sau: Trang 15
6. Tóm tắt bài giảng – Lý thuyết đồ thị Trường ĐHSP TP.HCM Bổ đề. Nếu đồ thị vô hướng G có bậc các đỉnh không nhỏ hơn 2 thì G có chứa ít nhất một chu trình đơn. Chứng minh bổ đề. Gọi v là một đỉnh nào đó. Xuất phát từ v, ta bắt đầu đi qua các đỉnh khác theo các cạnh của đồ thị. Do bậc của các đỉnh đều lớn hơn hay bằng 2 nên tại mỗi đỉnh ta đều có thể đi vào bằng một đường và đi ra bằng một đường khác. Do số đỉnh của đồ thị là hữu hạn nêu đến một lúc nào đó, ta sẽ phải đi lại 1 đỉnh đã đi trước đó, và như vậy thì ta đã có một chu trình đơn trong đồ thị. Sau đây ta sẽ chứng minh định lý. Chứng minh định lý. Cần. Nếu G là đồ thị Euler thì các đỉnh trong G đều có bậc chẵn. Giả sử G là đồ thị Euler, khi đó tồn tại chu trình Euler C trong G. Như vậy, cứ mỗi lần chu trình này đi qua một đỉnh thì bậc của đỉnh này sẽ tăng lên 2. Mặt khác, do chu trình C đi qua tất cả các đỉnh nên trong quá trình đi như trên sẽ không còn sót cạnh nào. Vậy các đỉnh của đồ thị đều phải có bậc chẵn. Đủ. Nếu các đỉnh trong G đều có bậc chẵn thì G là đồ thị Euler. Ta phải chứng minh G có chứa 1 chu trình Euler. Việc chứng minh phần này cũng chính là cách tìm chu trình Euler của G. Trước hết, do G liên thông và các đỉnh đều là bậc chẵn nên các đỉnh của G đều có bậc lớn hơn hay bằng 2. Do đó trong G phải có chứa một chu trình đơn C1. Nếu C1 đã đi qua hết tất cả các cạnh của G thì C1 chính là chu trình Euler cần tìm. Nếu không, thì loại bỏ các cạnh đã đi qua (trong C1) ra khỏi đồ thị, ta được đồ thị H với số bậc các đỉnh cũng đều là bậc chẵn. Trong mỗi thành phần liên thông của H, làm tương tự ta cũng thu được các chu trình đơn C2, C3, Quá trình cứ tiếp tục cho đến khi tất cả các đỉnh được đi qua. Giả sử cuối cùng, ta có được k chu trình đơn: C1, C2, , Ck. Ta sẽ tìm cách kết nối chúng thành một chu trình đơn duy nhất. Trong số các chu trình trên, có ít nhất 2 chu trình có chung một đỉnh (vì nếu không, G không phải là đồ thị liên thông). Giả sử Ci và Cj là 2 chu trình có điểm chung, gọi điểm chung đó là x. Ta sẽ “mở“ 2 chu trình này ra tại x và nối chúng lại thành một chu trình đơn lớn hơn theo hình vẽ dưới đây: y x x z Ci Cji 1 1 Trang 16
7. Tóm tắt bài giảng – Lý thuyết đồ thị Trường ĐHSP TP.HCM Theo hình trên, ta thấy rằng quá trình kết nối không bỏ mất cạnh nào, và chu trình thu được cũng là một chu trình đơn. Tiếp tục làm như trên (tìm 2 chu trình có điểm chung, kết nối thành chu trình lớn hơn) cho đến khi ta được một chu trình đơn duy nhất. Đó chính là chu trình Euler cần tìm. Vậy G là đồ thị Euler. Định lý trên cho ta một công cụ hữu hiệu để xác định một đồ thị có là Euler hay không: chỉ việc đếm bậc của các đỉnh. Hệ quả sau đây sẽ đề cập đến việc nhận biết đồ thị nửa Euler. Hệ quả 2.1. Đồ thị vô hướng liên thông G là nửa Euler khi và chỉ khi nó có không quá đỉnh bậc lẻ. Chứng minh. Thật vậy G chỉ có thể có 0 đỉnh bậc lẻ hoặc 2 đỉnh bậc lẻ. Nếu G không có đỉnh bậc lẻ nào thì G là đồ thị Euler và do đó hiển nhiên nó là đồ thị nửa Euler. Nếu G có đúng 2 đỉnh bậc lẻ, khi đó, tưởng tượng rằng ta sẽ thêm vào 1 cạnh ảo nối hai đỉnh này. Và như vậy thì tất cả các đỉnh sẽ đều có bậc chẵn và ta có thể tìm được chu trình Euler theo định lý 2.1. Bây giờ loại bỏ cạnh ảo ra khỏi chu trình, ta sẽ có đường đi Euler của đồ thị ban đầu. Nhận xét. Theo cách chứng minh của hệ quả trên, ta thấy rằng đường đi Euler trong đồ thị nửa Euler phải luôn luôn bắt đầu và kết thúc từ các đỉnh bậc lẻ. Tương tự như đồ thị vô hướng, tư tưởng của định lý Euler vẫn đúng cho đồ thị có hướng. Chỉ có điều, ta phải điều chỉnh một chút các điều kiện cho phù hợp với đồ thị có hướng. Định lý 2.2. Đồ thị có hướng liên thông mạnh là đồ thị Euler khi và chỉ khi mọi đỉnh của nó đều có bán bậc ra bằng bán bậc vào. Nghĩa là: v V ,deg (v) deg (v) 2.2 Đồ thị Hamilton Trong phần trên, chúng ta đã khảo sát một loại đồ thị đặc biệt: đồ thị mà ta có thể đi qua tất cả các cạnh của nó, mỗi cạnh một lần. Cũng tương tự ý tưởng như vậy, trong phần này, chúng ta sẽ xét các đồ thị mà ta có thể đi qua tất cả các đỉnh của nó, mỗi đỉnh một lần. Trang 17
8. Tóm tắt bài giảng – Lý thuyết đồ thị Trường ĐHSP TP.HCM Định nghĩa 2.2. Cho đồ thị G = . Chu trình sơ cấp† trong G đi qua tất cả các đỉnh của nó được gọi là chu trình Hamilton. Đường đi sơ cấp đi qua tất cả các đỉnh của đồ thị được gọi là đường đi Hamilton. Đồ thị G được gọi là đồ thị Hamilton nếu nó có chứa chu trình Hamilton. G được gọi là đồ thị nửa Hamilton nếu nó có chứa đường đi Hamilton. Dễ thấy rằng đồ thị Hamilton cũng là đồ thị nửa Hamilton, ngược lại thì không luôn đúng. Ví dụ 2.2. Xét các đồ thị dưới đây: 1 2 1 2 1 2 3 4 3 4 3 4 G1 G2 G3 - G1 không là đồ thị Hamilton cũng không là đồ thị nửa Hamilton. - G2 là đồ thị nửa Hamilton vì có chứa đường đi Hamilton: 3 1 2 4. Nhưng G2 không là đồ thị Hamilton. - G3 là đồ thị Hamilton vì có chứa chu trình Hamilton: 1 2 4 3 Trong phần trên, khi khảo sát đồ thị Euler, chúng ta được giới thiệu một định lý rất hiệu quả và đầy đủ. Nó thể hiện được điều kiện cần và đủ (hai chiều) để một đồ thị liên thông là đồ thị Euler. Và như vậy, lớp các đồ thị Euler đã được xác định rất rõ ràng. Rất tiếc, đối với việc nhận dạng đồ thị Hamilton, cho đến bây giờ chúng ta vẫn chưa có được một kết quả hoàn hảo như vậy. Phần lớn các kết quả nghiên cứu cho đến thời điểm này chủ yếu cung cấp điều kiện đủ để một đồ thị là Hamilton. Sau đây chúng ta giới thiệu một số định lý về điều kiện đủ để một đồ thị là đồ thị Hamilton. Định lý 2.3. (Dirak, 1952). Nếu đồ thị vô hướng G với n đỉnh (n>2), mỗi đỉnh có bậc không nhỏ hơn n/2 thì G là đồ thị Hamilton. Định lý 2.4. (Dirak, tổng quát) Nếu G là đồ thị có hướng liên thông mạnh với n đỉnh. Nếu các đỉnh đều có bán bậc ra và bán bậc vào không nhỏ hơn n/2 thì G là đồ thị Hamilton. Nghiên cứu đồ thị Hamilton và các tính chất của nó vẫn là một hướng mở hiện nay. Các nhà nghiên cứu vẫn đang tìm kiếm một công cụ hữu hiệu để nhận biết các đồ † Không lặp lại đỉnh Trang 18
9. Tóm tắt bài giảng – Lý thuyết đồ thị Trường ĐHSP TP.HCM thị Hamilton cũng như xác định đầy đủ lớp các đồ thị Hamilton. Đây thực sự là một thách thức trong lĩnh vực lý thuyết đồ thị. Trang 19
10. Tóm tắt bài giảng – Lý thuyết đồ thị Trường ĐHSP TP.HCM 3 Chương 3. Đồ thị có trọng số và bài toán đường đi ngắn nhất 3.1 Đồ thị có trọng số Trong các phần vừa qua, chúng ta đã khảo sát các khái niệm cơ bản trên đồ thị. Cho đến thời điểm này, chúng ta đã nói đến đồ thị như là một bộ gồm có tập các đỉnh và tập các cạnh nối các đỉnh với nhau. Trên thực tế trong một số các ứng dụng, việc sử dụng đồ thị với các đỉnh và các cạnh để biểu diễn là chưa đủ. Chẳng hạn như đối với bài toán giao thông, người ta không chỉ quan tâm một địa điểm này có nối với một địa điểm khác hay không mà người ta còn quan tâm đến cả đường nối ấy xa hay gần, khoảng cách bao nhiêu. Rõ ràng, trong các hệ thống giao thông, việc đưa thêm được yếu tố khoảng cách vào đồ thị có ý nghĩa rất lớn, nó làm tăng thêm khả năng ứng dụng của lý thuyết đồ thị. Trong phần này, chúng ta sẽ tìm hiểu loại đồ thị có khả năng đáp ứng yêu cầu trên: đồ thị có trọng số. Định nghĩa 3.1. Đồ thị có trọng số là đồ thị mà mỗi cạnh (hay cung) của nó được gán thêm một số thực, gọi là trọng số của cạnh (cung), thể hiện chi phí phải tốn (khoảng cách, thời gian, tiền bạc, ) khi đi qua cạnh (cung) đó. Ví dụ 3.1. Xét một mô hình kết nối điện thoại được mô phỏng trên đồ thị có trọng số dưới đây: các đỉnh tương ứng với các trạm điện thoại, các cạnh tương ứng với đường dây kết nối giữa các trạm và trọng số các cạnh thể hiện chi phí phải tốn khi thực hiện một kết nối liên lạc giữa hai trạm. 1 5 2 7 3 3 2 8 6 6 4 1 5 Để biểu diễn đồ thị có trọng số trên máy tính, ta dùng ma trận kề trọng số. Về cơ bản, ma trận kề trọng số của đồ thị cũng gần giống với ma trận kề, chỉ có điều, trong khi ma trận kề chỉ gồm các số 0 hay 1 thì ma trận kề trọng số sẽ bao gồm trọng số của các đỉnh, cũng như các giá trị vô cực, Trang 20
11. Tóm tắt bài giảng – Lý thuyết đồ thị Trường ĐHSP TP.HCM Định nghĩa 3.2. Ma trận kề trọng số của đồ thị có trọng số G = , V = {v1, v2, , vn}, là một ma trận kích thước nxn, được xác định như sau: Trọng số của cạnh (vi, vj), nếu (vi, vj) E Aij = nếu (vi, vj) E Ví dụ 3.2. Ma trận kề trọng số của đồ thị trong ví dụ 3.1 ở trên như sau: 5 2 5 7 3 8 6 7 A 2 3 1 8 1 6 Chú ý: Ta thường dùng ký hiệu a[vi, vj] để chỉ trọng số của cạnh (vi, vj). Trong trường hợp (vi, vj) không là cạnh của đồ thị thì a[vi, vj]= . Điều này cũng hoàn toàn tự nhiên vì một khi hai đỉnh không được nối với nhau thì chi phí để đi từ đỉnh này đến đỉnh kia là vô cùng lớn (lớn đến mức, không thể đi được). 3.2 Bài toán đường đi ngắn nhất Trong các ứng dụng thực tế, bài toán tìm đường đi ngắn nhất giữa hai đỉnh của một đồ thị liên thông có một ý nghĩa to lớn. Có thể dẫn về bài toán như vậy nhiều bài toán thực tế quan trọng. Ví dụ, bài toán chọn một hành trình tiết kiệm nhất (theo tiêu chuẩn hoặc 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 chọn một phương pháp tiết kiệm nhất để đưa ra một hệ thống động lực từ trạng thái xuất phát đến trạng một trạng thái đích, bài toán lập lịch thi công các công các công đoạn trong một công trình thi công 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.v Hiện nay có rất nhiều phương pháp để giải các bài toán như vậy. Thế nhưng, thông thường, 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ả cao nhất. Trong phần này chúng ta sẽ xét bài toán đường đi ngắn nhất và một số thuật toán để giải bài toán này. Định nghĩa 3.3. Cho G là đồ thị có trọng số và (P) là một được đi trên G. Ta định nghĩa độ dài của đường đi (P) là tổng trọng số của tất cả các cạnh trên (P). Ví dụ 3.3. Xét đồ thị có trọng số dưới đây: Trang 21
12. Tóm tắt bài giảng – Lý thuyết đồ thị Trường ĐHSP TP.HCM 1 5 2 7 3 3 2 8 6 6 4 1 5 Độ dài của đường đi (P1): 1 2 5 4 2 3 là: 5 + 8 + 1 + 3 + 7 = 24. Độ dài của đường đi (P2): 1 4 2 6 là: 2 + 1 + 6 = 9. Bài toán tìm đường đi ngắn nhất trên đồ thị dưới dạng tổng quát có thể phát biểu như sau: tìm đường đi có độ dài nhỏ nhất từ một đỉnh xuất phát s V đến đỉnh cuối (đích) t V. Đường đi như vậy ta sẽ gọi là đường đi ngắn nhất từ s đến t còn độ dài của nó ta sẽ ký hiệu là d(s,t) và còn gọi là khoảng cách từ s đến t (khoảng cách định nghĩa như vậy có thể là số âm). Nếu như không tồn tại đường đi từ s đến t thì ta sẽ đặt d(s,t)= . Rõ ràng, nếu như mỗi chu trình trong đồ thị đều có độ dài dương, trong đường đi ngắn nhất không có đỉnh nào bị lặp lại (đường đi sơ cấp). Mặt khác nếu trong đồ thị có chu trình với độ dài âm (chu trình như vậy để gọi ngắn gọn ta gọi là chu trình âm) thì khoảng cách giữa một số cặp đỉnh nào đó của đồ thị có thể là không xác định, bởi vì, bằng cách đi vòng theo chu trình này một số đủ lớn lần, ta có thể chỉ ra đường đi giữa các đỉnh này có độ dài nhỏ hơn bất cứ số thực cho trước nào. Chính vì thế, để bài toán tìm đường đi ngắn nhất có lời giải, ta phải giả thiết: đồ thị không chứa chu trình có độ dài âm. 3.2.1 Đường đi ngắn nhất xuất phát từ một đỉnh. Trong phần này, chúng ta sẽ xét thuật toán để tìm đường đi ngắn nhất từ một đỉnh s V cho trước đến tất cả các đỉnh còn lại của đồ thị. Để biểu diễn lời giải của bài toán này, ta sẽ sử dụng hai mảng: - Mảng d để lưu khoảng cách ngắn nhất từ s đến các đỉnh, chẳng hạn như d[v] là độ dài đường đi ngắn nhất từ s đến v. - Mảng Truoc để lưu đỉnh trước của các đỉnh trên đường đi ngắn nhất ở trên, ví dụ, Truoc[v] sẽ là đỉnh nằm trước v trên đường đi ngắn nhất từ s đến v. Mảng này dùng để lần lại kết quả khi kết thúc thuật toán (giống khái niệm bảng lưu vết trong quy hoạch động). Phần lớn các thuật toán tìm khoảng cách giữa hai đỉnh s và t được xây dựng nhờ kỹ thuật tính toán mà ta có thể mô tả đại thể như sau: từ ma trận trọng số a[u,v], u,v Trang 22
13. Tóm tắt bài giảng – Lý thuyết đồ thị Trường ĐHSP TP.HCM V, ta tính cận trên d[v] của khoảng cách từ s đến tất cả các đỉnh v V. Mỗi khi phát hiện d[u] + a[u,v] d[u] +a[u,v] then Begin d[v]:=d[u]+a[u,v]; Truoc[v]:=u; End; End; Trang 23
14. Tóm tắt bài giảng – Lý thuyết đồ thị Trường ĐHSP TP.HCM Tính đúng đắn của thuật toán có thể chứng minh trên cơ sở trên nguyên lý tối ưu của quy hoạch động. Rõ ràng là độ phức tạp tính toán của thuật toán là O(n3). Lưu ý rằng chúng ta có thể chấm dứt vòng lặp theo k khi phát hiện trong quá trình thực hiện hai vòng lặp trong không có biến d[v] nào bị đổi giá trị. Việc này có thể xảy ra đối với k<n-2, và điều đó làm tăng hiệu quả của thuật toán trong việc giải các bài toán thực tế. Tuy nhiên, cải tiến đó không thực sự cải thiện được đánh giá độ phức tạp của bản thân thuật toán. Ví dụ 3.4. Xét đồ thị trong hình dưới đây. Tìm đường đi ngắn nhất từ đỉnh s=1 đến các đỉnh còn lại. 2 3 3 8 A= 1 -5 4 Các kết quả tính toán theo thuật toán được mô tả trong bảng dưới đây: k d[1] Truoc[1] d[2] Truoc[2] d[3] Truoc[3] d[4] Truoc[4] d[5] Truoc[5] 0,1 1,1 ,1 ,1 3,1 1 0,1 1,1 4,2 4,2 -1,3 2 0,1 1,1 4,2 3,5 -1,3 3 0,1 1,1 4,2 3,5 S Bảng kết quả tính toán theo thuật toán Ford_Bellman Trong các mục tiếp theo chúng ta sẽ xét một số trường hợp riêng của bài toán tìm đường đi ngắn nhất mà để giải chúng có thể xây dựng những thuật toán hiệu quả Trang 24