Luận văn Một số vấn đề ứng dụng của đồ thị trong Tin học

thể tô màu đồ thị như trên với X: xanh; Đ: đỏ; V: vàng. Từ đồ thị ta có lịch sắp xếp các cuộc họp như sau: Đợt họp Tên nhóm I 1 II 2, 3 III 4 Mỗi màu tương ứng cho 1 đợt họp, những nhóm được tô cùng màu có thể họp trong cùng một đợt. Chương 3 CHU TRÌNH, ĐƯỜNG ĐI EULER VÀ HAMILTON TRONG ĐỒ THỊ Lý thuyết về chu trình, đường đi Euler và Hamilton đã có từ lâu và được nghiên cứu nhiều. Ta có thể bắt gặp nhiều bài toán trong thực tiễn mà có thể sử dụng các lý thuyết về chu trình, đường đi Euler và Hamilton để giải quyết, ví dụ sử dụng lý thuyết đường đi, chu trình Euler để tìm hành trình đường đi cho người phát thư, cho xe rửa đường... sao cho hành trình là tối ưu nhất. Hoặc là trong một hệ thống mạng, một máy đơn cần gửi 1 thông điệp đến tất cả các máy còn lại vậy thì đường truyền tin sẽ đi như thế nào để cho hiệu quả nhất, bài toán này có thể được giải quyết bằng cách vận dụng các lý thuyết chu trình và đường đi Hamilton. I. CHU TRÌNH VÀ ĐƯỜNG ĐI EULER 1. Chu trình Euler 1.1 Định nghĩa Cho đồ thị vô hướng G = . Một chu trình trong đồ thị G được gọi là chu trình Euler nếu nó đi qua tất cả các cạnh của G và đi qua mỗi cạnh đúng một lần. Định lý 1: Đồ thị vô hướng G = có chu trình Euler khi và chỉ khi G là liên thông và bậc của tất cả các đỉnh trong đồ thị G là số chẵn. Chứng minh - Điều kiện cần: Giả sử đồ thị G = có chu trình Euler. Ta cần chứng minh G là đồ thị liên thông và với mỗi x Î X có m(x) = 2k với k là một số nguyên dương nào đó. Thật vậy, giả sử G = không liên thông hay G có ít nhất hai thành phần liên thông G1 = và G2 = . Trong đó X1 È X2 = X , U1 È U2 = U, giữa các đỉnh trong X1 và trong X2 không có cạnh hoặc đường nối với nhau. Giả sử w là 1 chu trình Euler trong G. Theo định nghĩa của chu trình Euler thì w là chu trình đi qua tất cả các cạnh trong G, mỗi cạnh đúng 1 lần. Nếu w có đỉnh chung với G1 = thì w là chu trình nằm gọn trong đồ thị G1. Điều này mâu thuẫn với định nghĩa của w. Chứng tỏ đồ thị G = là liên thông. Bây giờ ta chứng minh mỗi đỉnh x Î X trong G đều có bậc chẵn, tức là cần chỉ ra m(x) = 2k, với k Î {1,2,...}. Trước hết thấy rằng k ¹ 0 bởi vì nếu k = 0 thì x là điểm cô lập trong G, tức là G không liên thông, trái với điều đã chỉ ra. Giả sử ngược lại tồn tại một đỉnh xi Î X mà m(xi) là một số lẻ, chẳng hạn m(xi) = 3. Đối với xi có 3 cạnh đi vào nó, giả sử đó là các cạnh (xi, xk), (xi, xj) và (xi, x1) Î U. Chu trình Euler w sẽ đi qua 3 cạnh đó. Khi đó một trong 3 cạnh trên có ít nhất một cạnh mà chu trình Euler w đi qua 2 lần. Điều đó mâu thuẫn với định nghĩa của chu trình w. Vậy m(x) là một số chẵn với mọi x Î X. - Điều kiện đủ: Giả sử G = là đồ thị liên thông và mỗi đỉnh x Î X đều có bậc chẵn: m(x) = 2k, k Î {1, 2,...} ta chứng minh trong đồ thị G tồn tại một chu trình Euler. Với giả thiết trên, trước hết ta chứng minh rằng tại mỗi đỉnh của G có tồn tại chu trình đơn (tức là chu trình đi qua các cạnh, mỗi cạnh đúng một lần). Đề chứng minh điều đó, ta lưu ý rằng không thể có một đỉnh x mà m(x) = 2. Điều đó đúng bởi vì khi đó tại đỉnh x có khuyên và do đó x cũng là một đỉnh cô lập, trái với giả thiết đồ thị G là liên thông. Giả sử x Î X là một đỉnh nào đó. Ta chỉ ra có chu trình đơn P qua x. Do m(x) > 2 suy ra tồn tại các đỉnh x1 sao cho x1 ¹ x và x kề với x1. Do m(x1) > 2 suy ra tồn tại các đỉnh xi sao cho xi ¹ xi-1 và xi kề với xi-1. Khi tới bước thứ i thì ta đã có một đường đi tư x đến xi, qua các cạnh, mỗi cạnh đúng một lần. Quá trình trên không thể kéo dài vô hạn do tính hữu hạn của đồ thị G. Giả sử số bước hữu hạn đó là i. Điều này chứng tỏ x và xi kề nhau, tức là có cạnh nối x và xi. Điều đó là đúng vì bước i là bước cuối cùng. Như vậy tại đỉnh x có chu trình đơn P đi qua. Bây giờ ta chứng minh rằng trong đồ thị G = có chu trình Euler. Theo chứng minh trên với đỉnh x Î X có chu trình đơn đi qua là P1 và P1 là chu trình trong đồ thị G. Hãy "đánh dấu xoá" các cạnh trong P1. Nếu sau khi "đánh dấu xoá" các cạnh trên đường P1 tạo ra một số đỉnh cô lập mới thì hãy "đánh dấu loại bỏ" các đỉnh cô lập mới đó. Kết quả thu được sẽ là một đồ thị mới G1 = là đồ thị con của đồ thị G = đã cho. Ta chỉ ra đồ thị G1 thoả mãn một số tính chất sau: - Chu trình P1 trong đồ thị G và G1 có đỉnh chung, bởi vì G là đồ thị liên thông. - Đồ thị G1 gồm các đỉnh x Î X1 có bậc chẵn. Thật vậy, nếu x Î X1 mà x không thuộc các đỉnh trong P1 thì m(x1) hiển nhiên là một số chẵn. Còn nếu x1 Î X1 mà x1 là đỉnh thuộc P1 thì sau khi "đánh dấu bỏ " hai cạnh của P1 chứa đỉnh đó thì bậc của đỉnh x1 sẽ giảm đi 2 đơn vị, do đó m(x1) cũng là chẵn. Tóm lại với mọi x Î X1 thì m(x) là một số chẵn. Ta có thể minh hoạ đồ thị với chu trình đơn P1 và đồ thị con G1 như hình vẽ dưới đây: G1 = x x1 x1 là đỉnh chung giữa P1 và G1. Đối với G1 = tại đỉnh x1 Î X1 có tồn tại chu trình đơn P2 mà cách xây dựng P2 cũng đối với P1. Trong P2 bỏ tất cả các cạnh, giữ lại các đỉnh có cạnh hoặc đường nối với các đỉnh khác trong G1 ta được đồ thị con G2 = của G1. Đồ thị cũng có tính chất như G1, là liên thông, mọi x Î X2 đều có bậc chẵn và G2 và P2 có điểm chung chẳng hạn x2 G2 = x x1 x2 Do tính hữu hạn của đồ thịi G, quá trình xây dựng các chu trình đơn sẽ dừng lại ở bước thứ k nào đó. Như vậy, trước khi sang bước thứ k ta đã có k - 1 chu trình đơn P1, P2, ..., Pk-1 và đồ thị Gk-1 = là đồ thị con của đồ thị Gk-2 = . Đồ thị Gk-1 là liên thông và mọi đỉnh x Î Xk-1 có bậc chẵn, đồng thời Gk-1 và Pk-1 có điểm chung là xk. Vì quá trình trên dừng lại sau k bước nên đồ thị Gk-1 là một chu trình đơn qua xk và bao gồm hết các cạnh trong đồ thị Gk-1. Vì nếu không sẽ dẫn tới mâu thuẫn do k là bước cuối cùng. x x1 x2 xk-1 P1 P2 Pk-1 Gk-1= Pk xk Ghép các chu trình đơn P1, P2,...,Pk tại các đỉnh chung ta được tập các chu trình Euler trong đồ thị G = . Định lý được chứng minh. Định lý 2: Cho đồ thị có hướng G = G có chu trình Euler khi và chỉ khi G là liên thông và mỗi đỉnh đều có bậc vào bằng bậc ra. 1.2 Thuật toán tìm chu trình Euler Cho đồ thị G = xây dựng thuật toán tìm chu trình Euler Bước 1: Kiểm tra xem G có là đồ thị liên thông hay không. Nếu G là liên thông thì chuyển sang bước 2. Ngược lại thì thuật toán dừng và kết luận rằng đồ thị không có chu trình Euler Bước 2: Kiểm tra xem tất cả các đỉnh trong G đều có bậc chẵn hay không. Nếu tất cả các đỉnh đều có bậc là chẵn thì chuyển sang bước tiếp theo. Nếu không dừng lại và kết luận đồ thị đã cho không có chu trình Euler. Bước 3: Xây dựng các chu trình đơn trong G sao cho tất cả các cạnh của đồ thị đều có các chu trình đơn đi qua và mỗi cạnh chỉ đi qua một lần. Ghép các chu trình đơn như trên tại các đỉnh chung nhau ta được tập các chu trình Euler cần tìm. 2. Đường đi Euler 2.1 Định nghĩa Đường Euler trong đồ thị G = là đường đi qua tất cả các cạnh của đồ thị, mỗi cạnh đi qua đúng một lần. Đinh lý 3: Cho G = là đồ thị vô hướng liên thông. Điều kiện cần và đủ để đồ thị có đường Euler là số đỉnh bậc lẻ trong đồ thị là 0 hoặc 2. Chứng minh: Trường hợp số đỉnh bậc lẻ bằng 0 thì G là đồ thị liên thông và mọi đỉnh đều có bậc chẵn. Theo định lý về chu trình Euler thì trong G có chu trình Euler, tức cũng là đường Euler. Nếu số đỉnh bậc lẻ là 2, chẳng hạn đó là các đinh x1 và x2. Hãy thêm vào một đỉnh mới x và hai cạnh (x, x1) và (x, x2) vào đồ thị G = . Ta có đồ thị mới G' = , ở đây X' = X È {x}, U' = U È {(x, x1), (x, x2)}. Rõ ràng là G' liên thông và mọi đỉnh đều có bậc chẵn. Theo định lý về chu trình Euler đã nêu ở trên thì trong G' có tồn tại chu trình Euler, cũng là đường Euler. Định lý 4: Cho đồ thị có hướng G = , điều kiện cần và đủ để có đường đi Euler từ x đến y (x, y Î X) là G liên thông và đỉnh x có bậc ra lớn hơn bậc vào 1 đơn vị, đỉnh y có bậc vào lớn hơn bậc ra 1 đơn vị, còn tất cả các đỉnh khác đều có bậc vào bằng bậc ra. 2.2 Thuật toán tìm đường Euler Bước 1: Kiểm tra xem đồ thị G có liên thông hay không. Nếu có thì chuyển sang bước 2. Ngược lại, thì dừng thuật toán và khẳng định rằng không có đường Euler. Bước 2: Kiểm tra xem mọi đỉnh trong G đều có bậc chẵn hay không. Nếu có chuyển sang bước 4. Nếu không chuyển sang bước 3. Bước 3: Kiểm tra xem số đỉnh bậc lẻ có bằng 2 hay không. Nếu có chuyển sang bước 4. Nếu không thì dừng lại và kết luận không có đường Euler. Bước 4: Xây dựng đường Euler trong G. II. CHU TRÌNH VÀ ĐƯỜNG ĐI HAMILTON 1. Chu trình Hamilton Định nghĩa: Giả sử G = là đồ thị vô hướng. Chu trình Hamilton là chu trình đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần. Định lý 1: Nếu đơn đồ thị liên thông G = , n đỉnh và n ³ 3 có bậc ở mỗi đỉnh không nhỏ hơn nửa số đỉnh của đồ thị, tức là mọi x Î X ta luôn có m(x) ³ n/2 thì trong đồ thị có tồn tại chu trình Hamilton. Chứng minh: Ta chứng minh định lý bằng phản chứng a b c d k g e h Giả sử G = có n đỉnh là đồ thị không có chu trình Hamilton. Ta thêm vào một số đỉnh mới và nối mỗi đỉnh mới này với mọi đỉnh của G, ta được đồ thị G'. Giả sử có số k > 0 là số tối thiểu các đỉnh cần thiết để G' chứa một chu trình Hamilton. Như vậy G' có n + k đỉnh. a y b a' b' a) b) Hình 2.1 Gọi P là chu trình Hamilton ayb...a trong G', trong đó a và b là các đỉnh của G, còn y là một trong các đỉnh mới. Thế thì b không kề với a, vì nếu trái lại thì ta có thể bỏ đỉnh y và được chu trình ab...a, mâu thuẫn với giả thiết về tính chất tối thiểu của k. Hơn nữa nếu a' là một đỉnh kề nào đó của a (khác với y) và b' là đỉnh nối tiếp ngay a' trong chu trình P (hình 2.1.b) thì b' không thể là đỉnh kề của b (nếu trái lại thì ta có thể thay P bởi chu trình aa'..bb'..a, trong đó không có y). Như vậy, với mỗi đỉnh kề với a ta có một đỉnh không kề với b, tức là số đỉnh không kề với b không thể ít hơn số đỉnh kề với a (số đỉnh kề với a không nhỏ hơn n/2 + k). Mặt khác, theo giả thiết, số đỉnh kề với b cũng không nhỏ hơn n/2 + k. Vì không có đỉnh nào vừa kề với b lại vừa không kề với b, nên số đỉnh của G' không ít hơn 2.(n/2 + k) = n + 2k, mâu thuẫn với giả thiết là số đỉnh của G' bằng n + k, (k > 0). Định lý được chứng minh. Ví dụ: Đồ thị trong hình 2.1.a có 8 đỉnh, đỉnh nào cũng có bậc 4. Vậy G có chu trình Hamilton. Có thể thấy một chu trình Hamilton a-g-c-k-d-h-b-e-a. 2. Đường Hamilton Định nghĩa: Đường Hamilton trong đồ thị G = là đường đi qua tất cả các đỉnh mỗi đỉnh đúng một lần. Định lý 2: Giả sử G = là đồ thị có hướng và đầy đủ khi đó trong đồ thị luôn tồn tại đường Hamilton. Chứng minh: Giả sử w = xi1 xi2 ... xik xik+1 .. xim - 1 xim là một đường sơ cấp bất kỳ trong đồ thị. Để đơn giản, ta chỉ viết các đỉnh mà không có các cạnh xen kẽ như định nghĩa. Nếu trong đường sơ cấp w mà tất cả các đỉnh trong X đều có mặt thì chính w là đường Hamilton. Còn nếu có những đỉnh trong X nhưng chưa có mặt trong w thì ta có thể bổ sung hết những đỉnh đó vào đường w sơ cấp để nó trở thành đường Hamilton theo nguyên tắc sau đây: Giả sử x Î X mà x không nằm trên đường sơ cấp w. Các trường hợp sau đây xảy ra do tính đầy đủ của đồ thị G: - Nếu x có cung tới xi1 thì bổ sung x vào đầu w và nó có dạng: x xi1 xi2 ... xik xik+1 .. xim - 1 xim - Nếu từ xik có cung tới x và từ x có cung tới xik+1 thì ta bổ sung x vào giữa hai đỉnh xik và xik+1. Khi đó w có dạng: xi1 xi2 ... xik x xik+1 .. xim - 1 xim - Nếu từ xik và xik+1 có cung đi tới x và từ x lại cung đi tới xik+2 thì ta bổ sung x vào giữa hai đỉnh xik + 1 và xik+2 ta được w có dạng: xi1 xi2 ... xik xik+1 x xik + 2 .. xim - 1 xim - Nếu mọi k Î [1, m - 1] mà từ xik và xik+1 có cung sang x thì ta bổ sung x vào cuối, khi đó nó có dạng: xi1 xi2 ... xik xik+1 x xik + 2 .. xim - 1 xim x Bằng cách đó ta có thể bổ sung vào w các đỉnh trong đồ thị mà chưa có mặt trong w để nó trở thành đường Hamilton. Định lý được chứng minh. Hệ quả: Giả sử G = là đồ thị đầy đủ có số đỉnh n ³ 3. Khi đó trong đồ thị luôn luôn tồn tại chu trình Hamilton. 4 1 3 2 2 1 3 4 5 6 a) b) Hình 2.2 Ví dụ đồ thị trong hình 2.2.a có chu trình Hamilton nhưng nó không phải là đồ thị đầy đủ. Còn đồ thị hình 2.2.b không có đường Hamilton. 3. Thuật toán liệt kê tất cả các chu trình Hamilton Thuật toán được xây dựng dựa trên cơ sở thuật toán quay lui cho phép liệt kê tất cả các chu trình Hamilton của đồ thị Procedure Hamilton(k); {Liệt kê các chu trình Hamilton thu được bằng việc phát triển dãy đỉnh x[1], ..., x[k-1] của đồ thị G = cho bởi danh sách kề Ke(v), v Î X } Begin For y Î Ke(x[k-1]) do if (k = n +1) and (y = v0) then GhiNhan(x[1],....,x[n],v0) Else if ChuaXet[y] then Begin x[k] := y; ChuaXet[y] := False; Hamilton(k+1); ChuaXet[y] := True; End; End; BEGIN For v Î X do ChuaXet[v] := True; x[1] := v0; {v0 là một đỉnh nào đó của đồ thị} ChuaXet[v0] := False; Hamilton(2); END. Chương 4 ĐƯỜNG ĐI NGẮN NHẤT TRONG ĐỒ THỊ Giới thiệu: 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ó ý nghĩa rất lớn. Bài toán tìm đường đi ngắn nhất được ứng dụng trong thực tế như để chọn một hành trình tiết kiệm nhất (về thời gian hoặc chi phí) trên một mạng giao thông đường thuỷ, đường bộ 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 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... Dùng thuật giải đường đi ngắn nhất trong đồ thị giải quyết bài toán sửa gói tin sai trong việc truyền tin... dưới đây ta xét một số thuật toán để tìm đường đi ngắn nhất trong đồ thị có trọng số và đồ thị không có trọng số. I. ĐƯỜNG ĐI NGẮN NHẤT TRONG ĐỒ THỊ KHÔNG CÓ TRỌNG SỐ 1. Định nghĩa: Đồ thị không có trọng số là đồ thị hữu hạn trên các cạnh không có trọng số. Bài toán tìm đường đi ngắn nhất giữa hai đỉnh a,b trong đồ thị không có trọng số G = là tìm đường đi giữa hai đỉnh a, b sao cho có số các cạnh (cung) là ít nhất. 2. Thuật toán: Bước 1: Tại đỉnh a ta ghi số 0 Các đỉnh có cạnh đi từ đỉnh a đến ta ghi số 1. Giả sử ta đã ghi tới i, tức là ta đã đánh số được các tập đỉnh là A(0) = {a}, A(1), A(2), ... , A(i) trong đó A(i) là tập tất cả các đỉnh được ghi bởi số i. Ta xác định tập đỉnh được đánh số bởi số i + 1 là A(i+1) = {x / x Î X, x Ï A(k) với k = 0, ...,i và tồn tại y Î A(i) sao cho từ y có cạnh (cung) tới x}. Do tính hữu hạn của đồ thị, sau một số hữu hạn các bước, thuật toán dừng lại và cho kết quả là tập các đỉnh có chứa b được đánh số bởi m là A(m). Bước 2: Do bước 1 thì đỉnh b được đánh số bởi m, điều này chứng tỏ đường đi từ a đến b có m cạnh (cung) và là đường ngắn nhất đi từ a đến b. Để tìm tất cả các đường có độ dài m ngắn nhất đi từ a đến b, ta xuất phát từ b đi ngược về a theo đúng nguyên tắc sau đây: - Tìm tất cả các đỉnh có cạnh (cung) tới b được ghi số m - 1, giả sử đó là xik (k = 1, 2,...). - Với mỗi đỉnh xik tìm tất cả các đỉnh có cạnh (cung) với xik (k = 1, 2, ...) được ghi số m -2. x1 x2 x3 x4 x7 x8 x9 x10 x6 x5 b a 0 1 2 3 3 3 2 1 1 2 Bằng cách lùi dần trở lại, đến một lúc nào đó gặp đỉnh ghi số 0, đó chính là đỉnh a. Tất cả các đường xác định theo các bước trên là đường đi từ a đến b có độ dài ngắn nhất là m cần tìm. Hình 1.1 Ví dụ đồ thị như hình 1.1 xây dựng đường đi ngắn nhất theo thuật toán trên: Bước 1: Đỉnh a được đánh số 0 và có A(0) = {a} A(1) = {x1, x6, x7} A(2) = {x2, x5, x8} A(3) = {x3, b, x9} Bước 2: Từ bước 1 ta có b Î A(3) nên từ a đến b là đường đi ngắn nhất có 3 cung. Tiếp theo ta xác định tất cả các đường đi ngắn nhất có độ dài 3: Đỉnh có cung về b được đánh số 2 là x5 Đỉnh có cung tới x5 được đánh số 1 là x6 Đỉnh có cung về x6 được đánh số 0 là a Vậy đường cần tìm là a - x6 - x5 - b. II. ĐƯỜNG ĐI NGẮN NHẤT TRONG ĐỒ THỊ CÓ TRỌNG SỐ 1. Các khái niệm Cho đồ thị hữu hạn G = với mỗi cạnh u Î U ta đặt tương ứng với số dương l(u) gọi là trọng số của u. Đồ thị có cạnh như trên được gọi là đồ thị có trọng số. Gọi a là một đường đi nào đó trong G = Giả sử a = xi1ui1xi2ui2 ... xin - 1uin-1xin, xij Î X , uij Î U (j = 1, 2, ...,n). Khi đó ký hiệu gọi là trọng số của đường a Ta ký hiệu D(a,b) là tập tất cả các đường đi nối đỉnh a với đỉnh b trong đồ thị G. Đường đi a giữa a và b là ngắn nhất nếu a thoả mãn l(a) = min {l(b) / b Î D(a,b)} Bài toán: Cho đơn đồ thị G = liên thông có trọng số, và a, b Î X. Tìm các đường đi ngắn nhất giữa 2 đỉnh a, b. 2. Thuật toán tìm đường đi ngắn nhất cho đồ thị có trọng số 2.1 Cơ sở thuật toán tìm đường đi ngắn nhất Cho G = tìm đường đi ngắn nhất từ đỉnh a tới đỉnh b Với x Î X nếu độ dài đường đi từ đỉnh xuất phát tới đỉnh x có trọng số là l(a) thì s(x) = l(a) gọi là trọng số của đỉnh x. Cơ sở của tất cả các thuật toán tìm đường đi ngắn nhất là xác định được các trọng số nhỏ nhất cho tất cả các đỉnh từ đó tìm đường đi ngắn nhất. Bước 1: Đánh trọng số các đỉnh, trọng số của đỉnh xuất phát là s(a) = 0. Tại các đỉnh còn lại ta ghi một số dương nào đó sao cho nó đủ lớn hơn trọng số của các đỉnh từ a tới. Bước 2: Thực hiện việc giảm trọng số các đỉnh. Giả sử tại đỉnh x được ghi trọng số s(x). Nếu tồn tại đỉnh y có trọng số s(y) từ y sang x mà s(x) > s(y) + l(y, x) thì ta thay trọng số của s(x) bởi trọng số s'(x) = s(y) + l(y, x). Trường hợp s(x) đạt cực tiểu, tức là x Î X không tồn tại y Î X kề với x mà s(y) + l(y, x) < s(x). Bước 3: Xác định đường từ a đến b có trọng số ít nhất. Từ bước 3 ta xác định được trọng số của đỉnh b. Xuất phát từ b đi về đỉnh kề với b, chẳng hạn đó là đỉnh xin có tính chất s(b) = s(x) + l(xin, b). Nếu không có đỉnh kề với xin như vậy thì ta đi về đỉnh kề với b có trọng số cạnh (cung) từ đỉnh đó về b là ít nhất. Từ đỉnh xin ta đi ngược về đỉnh xin-1 có tính chất s(xin) = s(in-1) + l(xin-1, xin) nếu không đi về đỉnh kề với xin mà trọng số cạnh (cung) giữa chúng là ít nhất. Bằng cách đó ta sẽ đi về đỉnh xi1 mà đỉnh kề là a sao cho s(xi1) = s(a) + l(a, xi1) = l(a, xi1) với s(a) = 0. Đường a = axi1xi2 ... xin - 1xinb là đường đi từ a đến b có trọng số ít nhất trong số tất cả các đường từ a đến b. Thật vậy l(a) = l(a,xi1) + l(xi1,xi2) + ... + l(xin-1,xin) + l(xin,b) = [s(xi1)- s(a)] + [s(xi2) - s(xi1)] + ... + [s(xin) - s(xin-1)] + [s(b) - s(xin)] = s(b) (1) Giả sử b Î D(a, b) là 1 đường bất kỳ từ a đến b và có dạng: b = aj1xj2 ... xjk-1xjkb. Theo bước 2 ta có bất đẳng thức sau: l(a, xj1) ³ s(xj1) - s(a) = s(xj1) l(xj1, xj2) ³ s(xj2) - s(xj1) ..................................... l(xjk-1,xjk) ³ s(xjk) - s(xjk-1) l(xjk, b) ³ s(b) - s(xjk) Cộng 2 vế ta có: l(b) = l(a, xj1) + l(xj1, xj2) + ... + l(xjn-1, xjk) + l(xjk, b) ³ s(b) (2) So sánh (1) và (2) ta có: l(a) = min{ l(b) / b Î D(a, b)} 2.2 Thuật toán Dijkstra Có thể khái quát thuật toán bằng thủ tục sau: Procedure Dijikstra(G: đồ thị liên thông có trọng số dương)} {G: có các đỉnh a = v0, v1, ..., vn = b và trọng số l(vi, vj) = ¥ nếu (vi, vj) Ï U của G} For i:=1 to n s(vi) := ¥; s(a) := 0; S := f {ban đầu các trọng số được khởi tạo sao cho trọng số của a = 0, còn các đỉnh khác bằng ¥, tập S rỗng} While b Ï S Begin u:= đỉnh không thuộc S có s(u) nhỏ nhất; S := S È {u}; For tất cả các đỉnh v không thuộc S if s(u) + l(u,v) < s(v) then s(v) := s(u) + l(u,v) {thêm vào S đỉnh có trọng số nhỏ nhất và sửa đổi trọng số của các đỉnh không thuộc S} End; {l(a) = l(a, b) = độ dài đường đi ngắn nhất từ a đến b} Độ phức tạp của thuật toán là O(n2), tức là phải dùng O(n2) phép cộng và so sánh đường đi ngắn nhất giữa 2 đỉnh trong đồ thị đơn vô hướng liên thông có trọng số. 2.3 Thuật toán Ford - Bellman Khác với thuật toán Dijkstra xác định các trọng số bé nhất của tất cả các đỉnh bằng cách "nổi bọt" dần các trọng số bé nhất, mỗi lần trọng số bé nhất được tìm thấy thì lấy nó làm hạt nhân để điều chỉnh và xác lập các trọng số cho các đỉnh khác, còn thuật toán Ford - Bellman xác định các trọng số nhỏ nhất cho tất cả các đỉnh bằng cách duyệt tất cả các đỉnh, trọng số nhỏ nhất của một đỉnh được xác lập là sau một số lần hữu hạn điều chỉnh nhờ các vòng lặp. Thuật toán được mô tả bằng thủ tục sau: Procedure Ford_Bellman; {Input: Đồ thị có hướng G = n đỉnh, a Î X là đỉnh xuất phát. t(i, j) với i, j Î X là ma trận trọng số Output: Với x Î X tìm các s(x) bé nhất và Truoc(x) để ghi nhận đỉnh đi trước x trong các đường đi ngắn nhất từ a đến x. } Begin {Khởi tạo} For x Î X do Begin s(x) := t[a, x]; Truoc[x] := a; End; s(a) := 0; For k:=1 to n - 2 do For x Î X \ {a} do For y Î X do if s(x) > s(y) + t[y, x] then begin s(x) := s(y) + t[y, x]; Truoc(x) := y; End; End; Độ phức tạp của thuật toán là O(n3) 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 2 vòng lặp trong không có biến d[u] nào bị thay đổi giá trị. Đối với những đồ thị có số cạnh m thoả mãn m < 6.n thì tốt hơn là sử dụng danh sách kề để biểu diễn đồ thị, khi đó vòng lặp theo y cần viết dưới dạng For tất cả các đỉnh y kề với x do if s(x) > s(y) + t[y, x] then begin s(x) := s(y) + t[y, x]; Truoc(x) := y; End; Trong trường hợp này thuật toán có độ phức tạp là O(n.m). 2.4 Thuật toán Floyd. Trong nhiều trường hợp ta cần xác định đường đi ngắn nhất giữa tất cả các cặp đỉnh, với bài toán này có thể giải bằng cách sử dụng n lần thuật toán thuật toán Ford_bellman trong đó ta sẽ chọn s lần lượt là các đỉnh của đồ thị cách làm này không phải là cách làm tốt nhất ở đây, ta sẽ trình bày thuật toán để giải quyết bài toán này trên đó là thuật toán Floyd. Thuật toán được trình bày khái quát ở dạng thủ tục sau: Procedure Floyd; { Input: đồ thị cho bởi ma trận trọng số a[i,j], i,j = 1,2,...,n; Output: Ma trận đường đi ngắn nhất giữa tất cả các cặp đỉnh. d[i,j], i,j = 1,2,...n. Trong đó d[i,j] cho độ dài ngắn nhất từ i đến j Ma trận ghi nhận đường đi p[i,j] ghi nhận đường đi trước đỉnh j} Begin For i:=1 to n do For j:=1 to n do Begin d[i,j] := a[i,j] p[i,j] := i; End; For k:=1 to n do For i:=1 to n do For j:=1 to n do if d[i,j] > d[j,k] + d[k,j] then Begin d[i, j] := d[i, k] + d[k,j]; p[i,j] := p[k,j]; End; End; III. CÁC VÍ DỤ ỨNG DỤNG 1. Ứng dụng trong truyền tin Truyền tin trong mạng thường hay gặp sự cố dẫn đến các gói tin có thể bị sai lệch, để phát hiện và sửa chữa các bít sai khôi phục lại gói tin người ta đã tiến hành 1 số cách thức. Có cách thức đó là mã hoá dữ liệu trước khi truyền, nhờ cơ chế mã hoá mà những gói tin sai có thể sửa đúng lại được. Thực hiện điều này, người ta đã dùng máy hữu hạn trạng thái để mã hoá dữ liệu. A B C 00(0) 11(0) 00(1) 01(0) 11(1) Ta xét 1 ôtômát hữu hạn của máy mã hoá dữ liệu cho những gói tin 4 bít như hình 3.1: Hình 3.1 Giả sử cần mã hoá gói tin nhị phân x = 0100; Thì ta đi như sau: A, A, C, B, A với nhãn đặt trong trong dấu ngoặc ta thu được gói tin x = 0100 với nhãn đặt ngoài dấu ngoặc tướng ứng thì ta thu được bản mã của x là 00 11 01 11, bản mã này dài 8 bít. Để tiện minh hoạ, ôtômát thiết kế như trên là đơn giản dẫn đến chưa đầy đủ, vì giả sử có gói tin là x = 1111, ôtômát sẽ không mã hoá được. Để thực hiện được việc sửa sai gói tin, 1 giải thuật gọi là Viterbi được tiến hành như sau: - Thay vì bản mã là 8 bít ta xây dựng bản mã có độ dài là 12 bít bẳng cách xuất phát từ trạng thái ban đầu A đi một chu trình có độ dài 6. Khi đó lúc giải mã ta chỉ giải mã 8 bít đầu bỏ đi 4 bit cuối. - Từ ôtômát xây dựng đồ thị có hướng biểu diễn tất cả các khả năng mã hoá độ dài 12 của gói tin 4 bit như sau: A B C 1 2 3 4 5 6 0 00 11 01 11 00 00 00 00 00 00 11 11 11 11 11 00 01 01 01 01 Hình 3.2 Mỗi cạnh nét đứt biểu thị số 0, cạnh nét liền là số 1, ví dụ với gói tin x = 0100 để mã hoá 12 bit thì đi theo chu trình trong ôtômát là A, A, C, B, A, A, A thì tương ứng đi trong đồ thị là A0, A1, C2, B3, A4, A5, A6 thì bản mã là 001100110000. Gọi d(a, b) là số bit sai khác nhau giữa 2 chuỗi nhị phân a và b cùng độ dài, nếu x, y, z là những chuỗi bít nhị phân cùng độ dài n, thì thoả các tính chất sau: i) d(x, y) ³ 0 ii) d(x, y) = 0 Û x = y iii) d(x, y) + d(y, z) ³ d(x, z) i) và ii) hiển nhiên bây giờ ta chứng minh iii) Đặt x = x1, x2, ..., xn với xi (i = 1..n) là những bit, xi = 0 hoặc 1 tương tự đặt y = y1, y2, ..., yn và z = z1, z2, ..., zn a) Xét trường hợp n = 1, tức các chuỗi chỉ có 1 bit ta có - Nếu d(x1, y1) = 1 và d(y1, z1) = 1 thì d(x1, z1) = 0 hoặc 1 dẫn đến d(x1, y1) + d(y1, z1) = 2 luôn lớn d(x1, z1) - Nếu d(x1, y1) = 1 và d(y1, z1) = 0 thì y1 = z1 nên d(x1, z1) = 1 hoặc d(x1, y1) = 0 và d(y1, z1) = 1 thì x1 = y1 nên d(x1, z1) = 1 hoặc d(x1, y1) = 0 và d(y1, z1) = 0 thì x1 = y1 = z1 nên d(x1, z1) = 0 tất cả các trường hợp đều có d(x1, y1) + d(y1, z1) = d(x1, z1) Kết luận d(xi, yi) + d(yi, zi) ³ d(xi, zi) với i = 1..n b) Xét trường hợp n > 1 Ta thấy d(x, y) = d(x1, y1) + d(x2, y2) + ... + d(xn, yn) d(y, z) = d(y1, z1) + d(y2, z2) + ... + d(yn, zn) d(x, z) = d(x1, z1) + d(x2, z2) + ... + d(xn, zn) mà d(xi, yi) + d(yi, zi) ³ d(xi, zi) với i = 1.. n ta cắt lát theo chiều dọc suy điều phải chứng minh. Nhận xét rằng ôtômát như hình 3.1 được thiết kế với mục đích chỉ sửa sai với những bản mã có sai sót không quá 2 bit. Giả sử a, b là 2 bản mã 12 bit bất kỳ của ôtômát, ôt