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

Chương 5 Một số vấn đề về cây I. Các khái niệm và tính chất cơ bản 1. Định nghĩa Cho đồ thị G = , G được gọi là một cây nếu G liên thông và không có chu trình, ở đây n = ữ Xữ > 1. Khi đó sáu tính chất sau là tương đương 1) G là đồ thị liên thông và không có chu trình 2) G không có chu trình và có n - 1 cạnh 3) G liên thông và có n - 1 cạnh 4) G không có chu trình và nếu thêm vào một cạnh nối 2 đỉnh không kề nhau thì G xuất hiện duy nhất một chu trình. 5) G liên thông và nếu bỏ đi một cạnh tuỳ ý thì đồ thị nhận được sẽ không liên thông. 6) Mỗi cặp đỉnh trong G được nối với nhau bằng một đường duy nhất. Chứng minh: Ta chứng minh theo trình tự sau: 1) ị 2) ị 3) ị 4) ị 5) ị 6) ị 1). Ta sử dụng đẳng thức v(G) = m - n + p là số chu trình độc lập của đồ thị G = , ở đây ữ Xữ = n, ữ Uữ = m và p là số thành phần liên thông của G. 1) ị 2): Vì G không có chu trình nên v(G) = m - n + p = 0. Do G liên thông nên p =1 khi đó m - n + 1 = 0 hay số cạnh m = n - 1. 2) ị 3): Giả sử G không có chu trình và n - 1 cạnh ta chứng minh 3) Thật vậy, giả sử ngược lại G không liên thông, khi đó p ³ 2 . Từ 2) ta có v(G) = m - n + p = 0 và m = n -1, kết hợp ta có (n - 1) - n + p = 0 hay p = 1, trái với giả thiết p ³ 2. Vậy G liên thông và số cạnh là n -1. 3) ị 4): Giả sử G là liên thông và có n - 1 cạnh, ta chứng minh 4). Thật vậy vì G liên thông nên p = 1, mặt khác m = n - 1 nên v(G) = m - n + 1 = 0 hay G không có chu trình . Nếu thêm vào G một cạnh thì ta được đồ thị G' với số cạnh là n, hay v(G') = n - n + 1 = 1 hay G' có một chu trình. 4) ị 5): Giả sử ngược lại G không liên thông, tức là tồn tại cặp đỉnh x, y trong G mà không có đường nào nối x với y. Khi đó nối x và y bởi 1 cạnh, đồ thị nhận được vẫn không có chu trình điều này mâu thuẫn với 4). Hay G là liên thông. Nếu bỏ đi 1 cạnh trong G mà đồ thị vẫn liên thông thì nếu khôi phục lại cạnh này đồ thị sẽ có chu trình. Điều này mâu thuẫn với 4). Vậy ta có 5). 5) ị 6): Giả sử ngược lại, nếu trong G có tồn tại cặp đỉnh x, y không nối với nhau bằng đường nào cả, chứng tỏ G không liên thông mâu thuẫn với 5). Vậy mỗi cặp đỉnh đều có đường đi nối với nhau, đường đó là duy nhất vì nếu có nhiều hơn thì sau khi bỏ đi 1 đường đồ thị vẫn liên thông, trái với 5). 6) ị 1) Với mỗi cặp đỉnh nối với nhau bởi một đường thì G là liên thông. Giả sử G có chu trình thì xét cặp đỉnh x, y trên chu trình đó. Khi đó x, y có 2 cặp đường nối với nhau, mâu thuẫn với 6). 2. Một số khái niệm cơ bản - Gốc: Đối với một cây T bất kỳ có thể chọn 1 đỉnh nào đó làm gốc, một cây đã được chọn 1 đỉnh làm gốc thì được gọi là cây có gốc. Vậy một cây có thể tạo thành nhiều cây có gốc khác nhau. - Quan hệ cha con: Giả sử a là gốc nếu có b, c kề với a thì b, c được gọi là con của a (hoặc gọi a là cha của b, c) tương tự nếu có d, e kề với b thì b là cha của chúng còn d, e là con của b (Xem cây T' hình 1.1). - Trong một cây tất cả các đỉnh là cha được gọi là các đỉnh trong. Các đỉnh không phải là đỉnh trong được gọi là lá (hay lá là đỉnh con không có con), trong cây chỉ có gốc là đỉnh duy nhất không phải là con. - Bậc của đỉnh là số các con của nó, bậc của cây là bậc lớn nhất của đỉnh. - Mức của cây: Mỗi 1 đỉnh đều được gán bằng một mức, mức của gốc là 0, con của gốc có mức là 1. Nếu mức của cha là i thì mức của con là i + 1. Một đỉnh x nào đó có mức bằng độ dài đường đi từ gốc đến x, mức cao nhất trong số các đỉnh được gọi là chiều cao của cây. Khi cây chưa có gốc, chưa phân chia thành các các mỗi quan hệ cha con, bậc, mức... thì cây là cây tự do còn khi được phân chia gọi là cây phân cấp. h a d i j b e k g c f a b d i j e h k c g f T T' Hình 1.1 Ví dụ như hình 1.1 cây T là một cây tự do, nếu chọn a làm gốc thì nó trở thành cây phân cấp T' có gốc. Với cây T' gốc a có bậc 2 và mức 0, đỉnh c có bậc là 3 và mức 1 ... Mức cao nhất là 3 ở các đỉnh là lá như i, j, k nên chiều cao của cây h(T') = 3. 3. Cây m - phân - Định nghĩa: Xét cây phân cấp T nếu mỗi đỉnh trong của nó có không quá m con thì T được gọi là cây m phân. Đặc biệt nếu m = 2 thì cây được gọi là cây nhị phân, cây nhị phân rất quan trọng và có nhiều ứng dụng rộng rãi. - Cây đầy đủ: Cây m - phân T được gọi là cây m - phân đầy đủ nếu mỗi đỉnh trong đều có đúng m con. - Cây cân đối: Xét cây m - phân có chiều cao h. Nêu các lá của cây có mức h - 1 hoặc h thì cây được gọi là cây cân đối. 4. Các ứng dụng 4.1 Mã tiền tố Kỹ thuật nén và mã hoá là 1 trong những lĩnh vực thường hay được sử dụng trong Tin học, cây nhị phân có nhiều ứng dụng trong việc nghiên cứu áp dụng các giải thuật trong lĩnh vực vực này. Một trong những ứng dụng của cây nhị phân đó là mã tiền tố. Ví dụ mã tiền tố như là dùng các xâu nhị phân có độ dài khác nhau để mã các ký tự để không có xâu nhị phân nào ứng với hơn một chữ cái. Trên cây nhị phân mã hoá, các lá là các ký tự cần mã hoá và đường đi từ cha đến con trái là 1 (hoặc 0), còn đi tới con phải là 0 (hoặc 1). Quá trình mã hoá sẽ duyệt cây đó từ gốc tới lá, khi tới nút con sẽ tạo ra một bít 0 hoặc 1 và tới nút lá sẽ tạo ra một xâu bít. Do vậy, mã sinh ra cho một ký tự sẽ không là phần đầu của ký tự khác. 0 0 0 0 0 0 1 1 1 1 1 1 1 1 a e i k o p u Hình 1.2 Ví dụ như hình 1.2 cây nhị phân biểu diễn mã tiền tố của các ký tự a, e, i, k, o, p, u trong đó: a : 000 k : 1100 u : 11111 e : 001 o : 1101 i : 01 p : 11110 Thuật toán mã hoá Huffman: Một số thuật toán về mã tiền tố đã ra đời đã được sử dụng rộng rãi và đem lại hiệu quả cao trong vấn đề nén và mã hoá thông tin. Một trong những thuật toán đó là Huffman xuất hiện từ năm 1952, thuật toán này mã hoá theo phương pháp kiểu thống kê, tạo ra mã có độ dài thay đổi khác nhau khi đã có bảng tần số xuất hiện của các ký tự. Quá trình mã hoá và giải mã phụ thuộc vào việc xây dựng cây nhị phân mã hoá. Thuật toán Huffman tạo cây nhị phân từ nút lá đến nút gốc, ký tự nào có tần số càng cao thì nút lá tương ứng càng gần gốc hơn. Thuật toán: Vào: Bảng tần số xuất hiện các ký tự sắp xếp giảm dần Ra : Cây nhị phân biểu diễn mã, nhánh phải là 1, trái là 0. Bước 1: Lấy hai phần tử cuối bảng tần số xuất hiện ra khỏi bảng Bước 2: Nếu phần tử nào chưa nằm trong cây nhị phân thì tạo ra một nút lá chứa phần tử đó, phần tử này chính là ký tự. Nối hai nút tương ứng với hai phần tử này với nhau thông qua việc tạo nút cha của chúng. Phần tử có tần số xuất hiện lớn hơn là nút trái, nhỏ hơn là nút phải. Bước 3: Tính tổng tần số xuất hiện của 2 phần tử này chèn vào bảng sao cho phù hợp với nguyên tắc giảm dần của bảng. Phần tử mới của bảng sẽ tương ứng với nút vừa được tạo ra ở bước 2. Bước 4: Quay trở lại bước 1 đến khi bảng chỉ còn lại 1 phần tử. Phần tử cuối cùng tương ứng với nút gốc của cây nhị phân. Ví dụ: Ta có kết quả mã Huffman cho các ký tự ở bảng sau: Ký tự Tần suất Mã nhị phân Chiều dài mã a 0.3 00 2 b 0.2 10 2 c 0.2 11 2 d 0.1 011 3 e 0.1 0100 4 f 0.1 0101 4 Cây nhị phân biểu diễn như hình 1.3 a,e,f,d,b,c a,e,f,d b,c e,f,d a e,f d e f b c 0 0 0 0 0 1 1 1 1 1 0,3 0,6 0,2 0,1 0,1 0,1 0,3 0,4 0,2 0,2 Hình 1.3 Với thuật toán Huffman trường hợp xấu nhất là thời gian hình thành cây nhị phân là O(n) với n là số ký tự cần mã hoá. Chương trình viết bằng ngôn ngữ Pascal minh hoạ thuật toán tạo mã Huffman: Const n = 6; {Số ký tự cần mã hoá a, b, c, .....} Type Nod = record S:integer; {tần suất} Code:String; {mã nhị phân} Name:char; {tên ký tự} end; Var a:array[1..n] of Nod; i,m:integer; Procedure InputData; {Khởi tạo bảng tần suất các ký tự} Var i:integer; begin for i:=1 to n do with A[i] do begin S:=Round(exp(n/5)/exp(i/5))+1;Name:=Char(64+i);Code:=''; end; end; Procedure FindCode(m:integer); {Sinh mã huffman} Var y,z:nod; k:integer; Begin if m=1 then exit; y:=a[m-1]; a[m-1].s:=a[m-1].s+a[m].s; k:=m-1; While (k>1) and (a[k].s>a[k-1].s) do Begin z:=a[k]; a[k]:=a[k-1]; a[k-1]:=z; k:=k-1; End; FindCode(m-1); z:=a[k]; for i:=k to m-2 do a[i]:=a[i+1]; a[m-1]:=y; a[m-1].code:=z.code+'1'; a[m].code:=z.code+'0'; End; BEGIN InputData; FindCode(n); For i:=1 to n do writeln(a[i].code); END. 4.2 Cây biểu diễn biểu thức Một biểu thức toán học có thể biểu diễn bằng cây, đây cũng là vấn đề hữu ích trong việc xử lý và lưu trữ biểu thức toán học trong máy tính Xét biểu thức đại số sau: Có thể vẽ 1 cây nhị phân như hình 1.4 biểu diễn biểu thức A, trong đó mỗi đỉnh trong mang dấu của một phép tính, gốc của cây mang phép tính sau cùng của A, ở đây là dấu nhân ký hiệu: *, mỗi lá mang 1 số hoặc một chữ đại diện cho số. a * + - / b c d 2 Hình 1.4 Một phép duyệt cây là tiền thứ tự nếu thăm gốc trước rồi sau đó thăm con trái như là một cây con với phương pháp thăm gốc trước và cuối cùng thăm con phải như là một cây con với phương pháp thăm gốc trước. Duyệt cây như vậy mang tính đệ quy. Khi duyệt cây trên theo tiền thứ tự ta có: * + a b - c / d 2 Cách viết biểu thức theo tiền thứ tự là ký pháp Balan. Bằng duyệt cây ta có thể tính được giá trị biểu thức, ngoài phương pháp tiền thứ tự còn có thể duyệt cây theo phương pháp pháp khác để tính giá trị biểu thức tùy vào yêu cầu và đặc điểm của từng bài toán. 4.3 Cây quyết định Có những bài toán phụ thuộc vào các quyết định. Mỗi quyết định thì có thể có nhiều kết cục và những kết cục cuối cùng chính là lời giải của bài toán. Để giải những bài toán như vậy, người ta biểu diễn mỗi quyết định bằng một đỉnh của đồ thị và mỗi kết cục là 1 lá của quyết định. Một cây được xây dựng như trên gọi là cây quyết định. Trong nhiều bài toán Tin gặp phải, có thể dùng cây quyết định để mô hình hoá từ đó việc cài đặt sẽ dễ dàng thuận tiện hơn. Ví dụ: hình 1.5 là cây quyết định biểu diễn việc sắp xếp 3 số khác nhau a, b, c a ? b a ? c b ? c b ? c a ? c c<a<b c<b<a b<c<a b<a<c a<c<b a<b<c b<a a<b c<a a<c c<b b<c c<b b<c c<a a<c Hình 1.5 Đoạn chương trình sau thể hiện cho cây trên: Var a, b, c: Integer; Function Can(x,y: Integer): Boolean; Begin if x > y then Can:=True Else Can:=False; End; Begin Readln(a,b,c); If Can(a,b) then Begin If Can(a,c) then Begin if Can(b,c) then Writeln(c,' ',b,' ',a) Else Writeln(b,' ',c,' ',a); End Else Writeln(b,' ',a,' ',c); End Else Begin If Can(b,c) then Begin if Can(a,c) then Writeln(c,' ',a,' ',b) Else Writeln(a,' ',c,' ',b); End Else Writeln(a,' ',b,' ',c); End; End. 4.4 Cây sắp xếp và tìm kiếm Sắp xếp và tìm kiếm là một trong những vấn đề cơ bản trong kỹ thuật lập trình, cây nhị phân cũng có khá nhiều ứng dụng quan trọng trong vấn đề này. Ta có thể mô hình hoá việc sắp xếp và tìm kiếm bằng cây từ đó ta có thể đánh giá các kỹ thuật này từ góc độ về cây. 4.4.1 Sắp xếp chèn với tìm kiếm nhị phân ý tưởng được bắt đầu như sau, cho 1 danh sách chưa sắp xếp hãy tìm 1 phần tử x bất kỳ nào đó trong danh sách, rõ ràng để tìm ta phải lần lượt xét từng phần tử cho tới khi nào bắt gặp phần tử cần tìm, nếu danh sách lớn thì thời gian tìm rất lâu. Bây giờ với một danh sách đã sắp xếp, chia đôi danh sách và lấy phần tử là t ở vị trí chia đôi để so sánh. Nếu t = x thì dừng, nếu t < x vì danh sách đã sắp xếp nên x chỉ có thể nằm bên nửa phải danh sách nên ta chỉ việc tìm kiếm trong 1 nửa danh sách bên phải và giảm đi khá nhiều công việc tìm kiếm. Nếu x < t thì tương tự, ta chỉ việc tìm bên nửa trái, đối với việc tìm kiếm cho lần sau với các danh sách con nửa trái hoặc nửa phải ta thực hiện tương tự như vậy một cách đệ quy. a) Từ những ý tưởng thuật toán ta xây dựng cây nhị phân tìm kiếm cho một danh sách như sau: - Chọn 1 phần tử bất kỳ làm gốc - Tất cả các phần tử có giá trị Ê gốc thì thuộc cây con trái - Tất cả các phần tử có giá trị > gốc thì thuộc cây con phải - Đối với các cây con thì cũng có tính chất tương tự như vậy Ví dụ cây nhị phân tìm kiếm cho danh sách 12, 10, 6, 11, 15, 13, 16, 19, 18 như hình 1.6: 12 15 18 10 6 11 13 16 19 Hình 1.6 b) Sắp xếp chèn bằng việc tìm nhị phân vị trí đúng. Có thể tạm gọi là phương pháp sắp xếp chèn nhị phân. ý tưởng như sau: cho trước một danh sách đã sắp xếp A, cần chèn 1 phần tử mới x vào A sao cho danh sách luôn được sắp xếp. Đầu tiên ta tìm vị trí đúng của x trong A sau đó chèn x vào đúng vị trí này trong A, ta có danh sách A = A ẩ {x} luôn được sắp xếp. Để tìm được ví trí đúng cần chèn của x trong A ta sử dụng phương pháp tìm kiếm nhị phân, chèn theo cách này gọi là chèn nhị phân. Ví dụ để sắp xếp B = x1, x2, x3, ... xn ta thực hiện như sau: A := f; For i:=1 to n do Begin - Tìm vị trí đúng của xi trong A theo phương pháp tìm nhị phân - Chèn xi vào A theo đúng vị trí vừa tìm được (A := A ẩ {xi}) End; Kết quả A là danh sách sắp xếp của B. Chương trình Pascal sau sắp xếp tăng dần theo phương pháp chèn nhị phân Const n = 9; Ds : Array[1..n] of Integer = (1,9,1,6,3,10,10,8,7); {Ham tra lai vi tri dung cua Pt trong danh sach} Function FindNp(l,r,Pt: Integer): Integer; Var t: Integer; Begin If Pt<=Ds[l] then FindNp:=l Else If Pt>=Ds[r] then FindNp:= r + 1 Else Begin Repeat t:= (l + r) div 2; If Pt = ds[t] then Begin FindNp:=t+1; Exit End Else If Pt<ds[t] then r:=t Else l:=t; Until r=l+1; FindNp:=l+1; End; End; Var i, j, vt, s: Integer; Begin For i:=2 to n do Begin vt:= FindNp(1,i-1,ds[i]); {Chen dung vi tri sao cho ds luon duoc sap xep} s:=ds[i]; For j:=i-1 Downto vt do ds[j+1]:=ds[j]; ds[vt]:=s; End; For i:=1 to n do Write(ds[i]:3); End. 4.4.2 Thuật toán sắp xếp hoà nhập Giả sử ta có danh sách chưa được sắp 8, 2, 4, 6, 9, 7, 10, 1, 5 ,3 có thể dùng cây nhị phân mô tả quá trình sắp xếp danh sách theo thứ tự tăng dần như sau: Cây nhị phân với gốc được gán là chính là danh sách đó. Các con của gốc được gán theo nguyên tắc: Con bên trái gán nửa danh sách đầu, con bên phải gán nửa danh sách còn lại (danh sách gán ở gốc cây con trái và cây con phải hoặc bằng nhau về số lượng hoặc chênh lệch nhau 1 phần tử). Cứ tiếp tục cho tới khi cây nhị phân có mỗi lá được gán 1 phần tử trong dãy. Đó là cây như hình 1.7 8, 2, 4, 6, 9, 7, 10, 1, 5, 3 8, 2, 4, 6, 9 7, 10, 1, 5, 3 8, 2, 4 6, 9 7, 10, 1 5, 3 8, 2 4 6 9 8 2 7, 10 1 7 10 5 3 Hình 1.7 Đây là cây nhị phân đầy đủ chưa phải cây sắp xếp của dãy đã cho ở trên 8 2 7 10 2, 8 4 6 9 7, 10 1 5 3 2, 4, 8 6, 9 1,7, 10 3, 5 2, 4, 6, 8,9 1, 3,5, 7, 10 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 Hình 1.8 Để có cây nhị phân sắp xếp của một dãy, trước hết cây được xây dựng tương tương tự như vậy, mỗi lá tương ứng với mỗi phần tử của dãy. Bước đầu tiên 2 phần tử được hoà nhập vào 1 danh sách theo thứ tự tăng dần, danh sách tương ứng này như một nút cha, 2 phần tử được hoà nhập là nút con. Sau đó ta tiếp tục hoà nhập các cặp nút tương tự như vậy cho tới toàn bộ danh sách được sắp xếp lại theo thứ tự tăng dần và cây biểu diễn cho dãy là cây nhị phân cân đối được mô tả như hình 1.8 Các bước thuật toán trên được mô tả trên là đã vận dụng thuật toán hoà nhập hai danh sách đã được sắp xếp thành một danh sách mới được sắp xếp, thuật toán này theo nguyên tắc sau: - So sánh phần tử bé nhất trong danh sách trong danh sách thứ nhất với phần tử bé nhất trong danh sách thứ 2. - Quá trình trên được lặp lại cho 2 danh sách nhận được ở bước trên - Sau một số bước sẽ gặp hai trường hợp sau: a) Cả 2 danh sách trở thành rỗng. Trong trường hợp này, các phần tử có mặt trong danh sách hoà nhập chính là danh sách cần xác định b) Một danh sách trở thành rỗng, còn danh sách kia khác rỗng. Trong trường hợp này đưa các phần tử còn lại (trong danh sách không rỗng) nối vào cuối của danh sách hoà nhập. Độ phức tạp thuật toán của thuật toán trên là O(nlogn) trong đó n là số phần tử hoà nhập Chương trình bằng ngôn ngữ Pascal thể hiện thuật toán hoà nhập như sau: Const n = 10; Type Vec = Array[1..n] of Integer; Const cm:Vec = (-3,3,-1,4,1,5,6,7,-8,-9); Var x,y:Vec; Procedure Viet; Var i:byte; Begin For i:=1 to n do Write(x[i]:3); Writeln; End; Procedure Hoa_nhap2p(x:Vec; p,m,n:Integer; Var z:Vec); Var i,j,k: Integer; Begin i:=p;j:=m+1;k:=p; While (i<=m) and (j<=n) do Begin If x[i]<x[j] Then Begin z[k]:=x[i];inc(i); End Else Begin z[k]:=x[j];inc(j);End; Inc(k); End; If i>m Then for K:=j to n Do z[k]:=x[k] Else for k:=i to m Do z[n+k-m]:=x[k]; End; Procedure Merge(l,r:integer); Var i,m:integer; Begin If l<r Then Begin m:=(l+r) div 2; Merge(l,m); Merge(m+1,r); For i:=l to r do y[i]:=x[i]; Hoa_nhap2p(y,l,m,r,x); End; End; BEGIN X := cm; Viet; Merge(1,n); Viet; END. 4.4.3 Thuật toán sắp xếp nhanh Sắp xếp 1 danh sách có nhiều thuật toán, mỗi thuật toán đều có những ưu nhược điểm. Trong các thuật toán sắp xếp thì thuật sắp xếp nhanh (Quick sort) tỏ ra có nhiều ưu điểm được sử dụng phổ biến và rất hiệu quả. Nguyên tắc của thuật toán này có tính đệ quy có thể sử dụng cây nhị phân để mô tả thuật toán này. Thuật toán có thể được mô tả tóm tắt như sau: Ví dụ để sắp xếp danh sách a1, a2, ..., an thuật toán bắt đầu bằng việc lấy ngẫu nhiên 1 phần tử làm chốt nhưng thường thì phần tử đầu tiên được chọn làm chốt. Như danh sách trên ta chọn a1 làm chốt khi đó danh sách được phân đoạn thành 2 danh sách con, một danh sách con gồm các phần tử nhỏ hơn a1 theo thứ tự xuất hiện, còn danh sách con khác gồm các phần tử lớn hơn a1 cũng theo thứ tự xuất hiện. Sau khi đã có hai danh sách con thì a1 được đặt vào sau cùng của danh sách con gồm các phần tử nhỏ hơn a1, như vậy sau a1 là danh sách con gồm các phần tử lớn hơn a1. Thủ tục này được lặp lại một cách đệ quy cho mỗi danh sách con cho tới khi nào mỗi danh sách con chỉ chứa một phần tử theo thứ tự xuất hiện của nó. Với kết quả này ta được một danh sách đã được sắp xếp. Ví dụ cho danh sách: 3, 5, 7, 8, 1, 9, 2, 6; Có thể dùng cây nhị phân biểu diễn thuật toán sắp xếp nhanh để sắp xếp danh sách này như hình 1.9 3, 5, 7, 8, 1, 9, 2, 4, 6 1, 2, 3 5, 7, 8, 9, 4, 6 1 2, 3 4, 5 7, 8, 9, 6 2 3 4 5 6, 7 8, 9 9 8 6 7 Hình 1.9 Danh sách lúc chưa sắp xếp là gốc, danh sách được sắp xếp là danh sách mà mỗi phần tử của nó là lá của cây. Chương trình thể hiện thuật toán sắp xếp nhanh như sau: Uses Crt; const Max = 10; type List = array[1..Max] of Integer; var Data: List; I: Integer; procedure QuickSort(var A: List; Lo, Hi: Integer); procedure Sort(l, r: Integer); var i, j, x, y: integer; begin i := l; j := r; x := a[(l+r) DIV 2]; repeat while a[i] < x do i := i + 1; while x < a[j] do j := j - 1; if i <= j then begin y := a[i]; a[i] := a[j]; a[j] := y; i := i + 1; j := j - 1; end; until i > j; if l < j then Sort(l, j); if i < r then Sort(i, r); end; Begin {QuickSort}; Sort(Lo,Hi); End; Begin {QSort} { Khởi tạo ngẫu nhiên 10 phần tử } Randomize; for i := 1 to Max do Data[i] := Random(3000); Writeln; {Sắp xếp các phần tử bằng Quick Sort} QuickSort(Data, 1, Max); Writeln; for i := 1 to 10 do Write(Data[i]:8); End. Người ta đã chỉ ra rằng độ phức tạp của thuật toán là O(nlog2n) II. Cây bao trùm 1. Định nghĩa và các tính chất Định nghĩa: Cho đồ thị G = với số đỉnh n lớn hơn 1. Giả sử G' là đồ thị bộ phận của G (G' nhận được từ G bằng cách bỏ đi một số cạnh nhưng vẫn giữ nguyên đỉnh). Nếu G' = là một cây thì G' gọi là cây bao trùm của G. Theo đúng tính chất về cây. G' là cây bao trùm phải có n - 1 cạnh và là một đồ thị liên thông không có chu trình. Trong một đồ thị có thể có nhiều cây bao trùm. e a b d c e a b d c a) b) hình 2.1 Ví dụ cây như hình 2.1.b là một cây bao trùm của đồ thị trong hình 2.1.a Định lý: Cho đồ thị G = , G có cây bao trùm khi và chỉ khi G là đồ thị liên thông. Chứng minh: Điều kiện cần: Giả sử G có cây bao trùm là G'. Ta chỉ ra G là liên thông. Thật vậy, nếu G không liên thông thì tồn tại cặp đỉnh x, y mà giữa chúng không được nối bởi đường nào, mà giữa x, y cũng là các đỉnh của G'. Chứng tỏ G' không liên thông, trái với giả thiết G' là một cây. Điều kiện đủ: Giả sử G là liên thông ta chứng minh G có cây bao trùm, thật vậy vì: - Nếu trong G không có chu trình thì theo định nghĩa G là một cây, đó là cây bao trùm. - Nếu trong G có chu trình thì bỏ đi 1 cạnh trong chu trình đó ta được G' liên thông và không có chu trình, G' là cây bao trùm. 2. Các thuật toán tìm cây bao trùm Xét đồ thị G = liên thông có n đỉnh, ta có các thuật toán tìm cây bao trùm như sau: 2.1 Thuật toán theo lý thuyết Giả sử G không có chu trình thì nó là một cây và cũng chính là cây bao trùm của nó. Nếu G có chu trình thì ở 1 chu trình đơn nào đó bỏ đi 1 cạnh đồ thị vẫn liên thông. Nếu G còn chu trình đơn thì bỏ tiếp 1 cạnh nữa ... cho đến khi không còn chu trình thì ta được đồ thị mới G' nhận được từ G và G' chính là 1 cây bao trùm của G. Thuật toán trên chỉ có ý nghĩa lý thuyết vì khi số đỉnh lớn, chu trình lớn thì việc kiểm tra chu trình đối với máy tính đòi hỏi nhiều tính toán 2.2 Thuật toán tìm kiếm ưu tiên chiều sâu và chiều rộng Rất nhiều thuật toán trên đồ thị được xây dựng dựa trên cơ sở duyệt tất cả các đỉnh của đồ thị sao cho mỗi đỉnh của nó được thăm đúng 1 lần, trong mục này ta sẽ đề cập tới 2 thuật toán rất cơ bản của đồ thị về thăm đỉnh theo nguyên tắc trên. Đó là thuật toán tìm kiếm theo chiều sâu và chiều rộng, chúng được sử dụng để tìm cây bao trùm của đồ thị, ngoài ra chúng còn được sử dụng trong các thuật toán tìm đường đi, tìm các thành phần liên thông, kiểm tra tính liên thông... Trước khi đi vào 2 thuật toán, ta sẽ đề cập tới 1 yếu tố cơ bản cấu thành nên ý tưởng của nhiều thuật toán trong đồ thị đó là kỹ thuật quay lui. Đây là một kỹ thuật chính trong kỹ thuật lập trình có nhiều áp dụng, đặc biệt là áp dụng trong giải thuật tìm kiếm theo chiều sâu. 2.2.1 Kỹ thuật quay lui Nội dung của kỹ thuật quay lui có thể tóm tắt như sau: Dùng cây quyết định, còn lá thì biểu thị 1 lời giải có thể. Để tìm nghiệm bằng kỹ thuật quay lui, trước tiên tạo ra dãy quyết định (càng dài càng tốt) để tiến tới lời giải. Dãy quyết định có thể biểu thị một đường đi trong cây quyết định. Mỗi khi biết được không thể có lời giải từ bất kỳ dãy quyết định nào thì ta quay lui lại đỉnh cha của đỉnh hiện tại để hướng tới lời giải bằng dãy quyết định khác (nếu có thể). Thủ tục tiếp tục cho tới khi tìm được lời giải hoặc là kết luận không có lời giải. Ví dụ cho 1 tập A = {1, 2, 3, 4} hãy tìm tập con của A gồm 3 phần tử sao cho tổng các phần tử của tập con này là 8. Trước hết ta xây dựng cây quyết định cho bài toán này như sau: 6 7 8 9 1 2 3 4 3 4 2 3 4 Hình 2.2 Mỗi một nhánh là 1 phần tử của một tập con 3 phần tử nào đó của A, một dãy liên tiếp đường đi gồm 3 nhánh từ gốc tới lá là một tập con của A, mỗi một lá là tổng của một tập con. Dãy quyết định cho lời giải như sau: Đầu tiên đi theo các nhánh 1 - 2 - 3 tổng dãy ở lá là 6 . Không phải, quay lui một nhánh về nhánh 2 đi vào nhánh 4 được: 1 - 2 - 4 ở lá là 7 . Không đúng quay lại về nhánh 1 đi tiếp nhánh 3 và 4 được: 1 - 3 - 4 ở lá là 8, đây là nghiệm cần tìm, vậy tập con cần tìm là {1, 3, 4} Đây cũng là bài toán tổ hợp có tính đệ quy, rõ ràng ở đây ta thấy được một áp dụng của cây trong kỹ thuật này. 2.2.2 Thuật toán tìm kiếm theo chiều sâu Bước 1: Lấy một đỉnh bất kỳ làm gốc của cây bao trùm Bước 2: Xây dựng đường đi từ đỉnh này bằng cách lần lượt ghép thêm các cạnh vào, sao cho mỗi cạnh ghép mới sẽ nối đỉnh cuối cùng trên đường đi với đỉnh chưa thuộc đường đi. Bước này thực hiện cho tới khi nào không thể ghép thêm cạnh mới được nữa. Bước 3: Nếu đường đi chứa tất cả các đỉnh của đồ thị G thì đó chính là cây bao trùm cần tìm. Ngược lại thì thực hiện tiếp bước sau đây: Bước 4: Quay lui lại đỉnh trước đỉnh cuối cùng của đường đi và xây dựng đường đi mới xuất phát từ đỉnh này. Nếu không xây dựng được đường đi mới từ đỉnh này thì lùi tiếp lại một đỉnh nữa trên đường đi và lặp lại quá trình xây dựng đường mới càng dài càng tốt. Bước 5: Vì đồ thị là hữu hạn nên quá trình trên sau một số hữu hạn bước sẽ dừng lại và cho ta cây bao trùm của G = 2.2.3 Thuật toán tìm kiếm theo chiều rộng: Bước 1: Chọn một đỉnh làm gốc của cây Bước 2: Ghép các cạnh liên thuộc với đỉnh này. Các đỉnh mới kề với gốc trong bước này đều nằm trên mức 1 của cây (với thứ tự tuỳ ý). Bước 3: Tiếp tục với mỗi đỉnh ở mức 1, ta ghép các cạnh liên thuộc nó sao cho chúng không tạo nên chu trình. Các đỉnh kề được tạo ra ở bước này nằm trên mức 2 của cây. Bước 4: Quá trình này sẽ dừng lại sau một số bước làm việc (do tập cạnh hữu hạn) và tất cả các đỉnh của đồ thị đều được ghép vào cây. 2.3 Các chương trình thể thiện cho các thuật toán: 2.3.1 Chương trình Pascal về thuật toán quay lui thể hiện cây ở hình 2.2 { m là tổng của tập con, n là số phần tử của tập A, k là số phần tử của tập con của A} Var s: Array[1..10] Of Integer; t,n,k,m,tg: Integer; Procedure Try(h,a:Integer); Var i: Integer; Begin h:=h+1; For i:=a to n-(k-h) do Begin s[h]:=i; If h<k then Try(h,i+1) Else Begin tg:=0; For t:=1 to k do tg:= tg+ s[t]; if tg = 8 then For t:=1 to k do Write(s[t]:3); Writeln; End; End; End; Begin n:=4; k:=3; m:=8; Try(0,1); {Tạo cây bắt đầu từ mức 0} End. 2.3.2 Chương trình Pascal thể hiện thuật toán tìm kiếm ưu tiên theo chiều sâu và chiều rộng tìm cây bao trùm Uses Crt; Var mG,mT : Array[1..100,1..100] of Integer; {mG: mt ke cua do thi G mT: mt ke cua cay bao trum cho dt G} n: Integer; ChuaXet: Array[1..100] Of Boolean; Queue: Array[1..100] of Integer; tl: Char; {Nhap du lieu cho do thi} Procedure NhapDl; Var i,j: Integer; Begin {Nhap du lieu cho do thi G} Write('So dinh: '); Readln(n); For i:=1 to n do Begin ChuaXet[i]:=True; Queue[i]:=0; For j:=i+1 to n do Begin Write('a',i,j,' = '); Readln(mG[i,j]); mG[j,i]:=mG[i,j]; End; mG[i,i]:=0; End; {Khoi tao du lieu cho cay bao trum} For i:=1 to n do For j:=1 to n do mT[i,j]:=0; End; Procedure Display; Var i,j: Integer; Begin Writeln('Ma tran ke cua do thi'); For i:=1 to n do Begin For j:=1 to n do Write(mG[i,j]:3); Writeln; End; Writeln; Writeln('Ma tran ke cua cay bao trum'); For i:=1 to n do Begin For j:=1 to n do Write(mT[i,j]:3); Writeln; End; End; {Thu tuc tim cay bao trum theo chieu sau} Procedure Dfs(v: Integer); Var u: Integer; Begin ChuaXet[v]:=False; {Dinh v da duoc tham} For u:=1 to n do If (mG[v,u]0) and (ChuaXet[u]) then Begin {Duyet nhung canh ke voi v} mT[v,u]:=mG[v,u]; {Bo sung vao tap canh cua cay} mT[u,v]:=mT[v,u]; Dfs(u); End; End; {Tim cay bao trum cua do thi theo chieu rong} Procedure Bfs(v: Integer); Var i,u,First,Last: Integer; Begin First:=1; Last:=1; Queue[Last]:=v; ChuaXet[v]:=False; {Dinh v da duoc tham} While First<=Last do Begin {Trong khi hang doi chua rong} u:=Queue[First]; Inc(First); For i:=1 to n do If (mG[u,i]0) and (ChuaXet[i]) then Begin {Duyet nhung canh ke voi v} mT[u,i]:=mG[u,i]; {Bo sung vao tap canh cua cay} mT[u,i]:=mT[i,u]; ChuaXet[i]:=False; Inc(Last); Queue[Last]:=i; End; End; End; BEGIN NhapDl; Write('Chon chieu sau hay chieu rong (s/r)? '); Readln(tl); If Upcase(tl) = 'S' then Dfs(1) Else Bfs(1); Display; END. 3. Cây bao trùm bé nhất 3.1 Định nghĩa: Cho đồ thị n đỉnh G = liên thông, n > 1. Mỗi cạnh u ẻ U ta gán cho nó trọng số l(u). Giả sử G' = <X, U') là cây bao trùm của G. Ký hiệu gọi là trọng số hay là độ dài của G'. Ký hiệu Ă là tập các cây bao trùm của G, khi đó nếu cây bao trùm g ẻ Ă thoả mãn l(g) = Min {l(g') / g' ẻ Ă} thì ta nói rằng g là cây bao trùm bé nhất trong G. 3.2 Thuật toán tìm cây bao trùm bé nhất Cho đồ thị G = với số đỉnh n tìm cây bao trùm bé nhất của G. 3.2.1 Thuật toán Kruskal Thuật toán sẽ xây dựng tập cạnh của cây bao trùm nhỏ nhất theo từng bước. Trước hết sắp xếp các cạnh của đồ thị G theo thứ tự không giảm của độ dài. Bắt đầu từ tập cạnh của cây là rỗng , ở mỗi bước ta sẽ lần lượt duyệt trong danh sách cạnh đã sắp xếp, từ cạnh có độ dài nhỏ đến cạnh có độ dài lớn hơn, để tìm ra cạnh mà việc bổ sung nó vào tập cạnh của cây không tạo thành chu trình trong tập này. Thuật toán sẽ kết thúc khi ta thu được 1 tập cạnh gồm n - 1 cạnh. Cụ thể thuật toán có thể mô tả như sau: - Bước 1: Chọn cạnh u1 thoả mãn l(u1) = min {l(u) : u ẻ U} đặt U1 = {u1} - Bước 2: Chọn u2 thoả mãn : l(u2) = min{l(u) : u ẻ U\U1} đặt U2 = {u1, u2} .......... - Bước k + 1: Giả sử đã có tập Uk = {u1, u2, ..., uk} chọn uk+1 thoả mãn l(uk+1) = min(l(u) : u ẻ U\Uk} đặt Uk+1 = Uk ẩ {uk+1} Chú ý ở các bước, cạnh mới được chọn phải không lập thành chu trình với các cạnh đã chọn ở các bước trước. Thuật toán dừng lại lại ở bước thứ n - 1. Vậy cây T = tìm được là cây bao trùm ngắn nhất. 3.2.2 Thuật toán Prim Thuật toán Prim còn được gọi là phương pháp lân cận gần nhất. Trong phương pháp này, bắt đầu từ một đỉnh s tuỳ ý của đồ thị, đầu tiên ta nối s với đỉnh lân cận gần nó nhất, chẳng hạn là đỉnh y. Nghĩa là trong số các cạnh kề của đỉnh s, cạnh (s, y) có độ dài nhỏ nhất. Tiếp theo, trong số các cạnh kề với 2 đỉnh s hoặc y ta tìm cạnh có độ dài nhỏ nhất, cạnh này dẫn đến đỉnh thứ ba z, và ta thu được cây bộ phận gồm 3 đỉnh và 2 cạnh. Quá trình này sẽ được tiếp tục cho tới khi ta thu được được cây gồm n đỉnh và n - 1 cạnh, cây đó cũng là cây bao trùm nhỏ nhất cần tìm. Các bước thuật toán như sau: - Bước 1: Chọn u1 sao cho l(u1) = min{l(u)} với u ẻ U đặt U1 = {u1} - Bước 2: Chọn u2 sao cho l(u2) = min{l(u)} với u ẻ U\U1 và u kề với 1 cạnh thuộc U1 ......... - Bước k +1: Giả sử đã có Uk = {u1, u2, ..., uk} Chọn uk + 1 sao cho l(uk+1) = min{l(u)} với u ẻ U\Uk và u kề với 1 cạnh thuộc Uk. Với thuật toán Prim, cạnh mới được chọn cũng phải không lập thành chu trình với các cạnh đã chọn ở các bước trước. Thuật toán dừng ở bước n - 1. Kết luận: cây T = là cây bao trùm ngắn nhất của G. * Về hình thức thuật toán Prim phức tạp hơn thuật toán Kruskal nhưng về khối lượng tính toán sẽ giảm đi rất nhiều lần. Bởi vì thuật toán Prim chỉ cần xét các cạnh kề với các cạnh đã được chọn, còn trong thuật toán Kruskal phải xem xét tất cả các cạnh còn lại của đồ thị. Chính vì thế thuật toán Prim tỏ ra hiệu quả hơn, còn thuật toán Kruskal phải tính toán nhiều nên làm việc kém hiệu quả đối với những đồ thị có số cạnh lớn. 3.2.3 Chương trình thể hiện thuật toán. Chương trình Pascal thể hiện thuật toán Kruskal tìm cây bao trùm nhỏ nhất Uses crt; Type Arrn = Array[1..50] of integer; Arrm = Array[1..5000] of Integer; Var n, m, MinL : Integer; Dau, Cuoi, W: Arrm; DauT, CuoiT, Father: Arrn; Connect: Boolean; Procedure NhapDl; Var i: Integer; FName: String; f: Text; Begin Write('Cho ten file du lieu: '); Readln(Fname); Assign(f, Fname); Reset(f); Readln(f,n,m); For i:=1 to m do Readln(f,dau[i],Cuoi[i],W[i]); Close(f); End; Procedure Indulieu; Var i: Integer; Begin Writeln('So dinh: ',n,' So canh: ',m); Writeln('Dinh dau Dinh cuoi Do dai'); For i:=1 to m do Writeln(Dau[i]:4, Cuoi[i]:10, W[i]:12); End; Procedure Heap(First, Last: Integer); Var j, k ,t1, t2, t3: Integer; Begin j:= First; While (j<=Trunc(last/2)) do Begin If (2*j < Last) and (W[2*j + 1] < W[2*j]) then k:= 2*j + 1 Else k:= 2*j; If W[k]<W[j] then Begin t1:= Dau[j]; t2:=Cuoi[j]; t3:=W[j]; Dau[j] := Dau[k]; Cuoi[j]:=Cuoi[k]; W[j]:=W[k]; Dau[k]:=t1; Cuoi[k]:=t2; W[k]:=t3; j:=k; End Else j:=Last; End; End; Function Find(i: Integer): Integer; Var Tro: Integer; Begin Tro:=i; While Father[Tro]>0 do Tro:=Father[Tro]; Find:= Tro; End; Procedure Union(i, j : Integer); Var x: Integer; Begin x:=Father[i] + Father[j]; If Father[i]>Father[j] then Begin Father[i]:=j; Father[j]:=x; End Else Begin Father[j]:=i; Father[i]:=x; End; End; Procedure Kruskal; Var i,Last, u, v, r1, r2, Ncanh, Ndinh: Integer; Begin {Khoi tao mang Father danh dau cay con va khoi tao Heap} For i:=1 to n do Father[i]:=-1; For i:=Trunc(m/2) downto 1 do Heap(i,m); Last:=m; Ncanh:=0; Ndinh:=0; MinL :=0; Connect := True; While (Ndinh< n - 1) and (Ncanh<m) do Begin NCanh := NCanh + 1; u:= Dau[1]; v:= Cuoi[1]; {Kiem tra u va v co thuoc cung mot cay con} r1:= Find(u); r2:= Find(v); If r1r2 then Begin {ket nap canh (u,v) vao cay khung} Ndinh := Ndinh + 1; Union(r1,r2); DauT[Ndinh]:=u; CuoiT[Ndinh]:=v; MinL := Minl + W[1]; End; {To chuc lai Heap} Dau[1]:= Dau[Last]; Cuoi[1]:= Cuoi[Last]; W[1]:=W[Last]; Last := Last - 1; Heap(1,Last); End; If Ndinh n - 1 then Connect:= False; End; Procedure InKetQua; Var i: Integer; Begin Writeln('Do dai cua cay khung nho nhat: ',MinL); Writeln('Cac canh cua cay khung nho nhat: '); For i:=1 to n - 1 do Writeln('(',DauT[i]:2,', ',CuoiT[i]:2,')'); End; BEGIN NhapDl; InDuLieu; KrusKal; If Connect then InKetQua Else Writeln('Do thi khong lien thong'); END. 3.3 ứng dụng cho bài toán kết nối hệ thống mạng 0 1 2 4 5 3 6 7 8 5 2 8 9 6 11 3 7 3 4 6 9 Hình 2.3 Xét 1 ứng dụng của đồ thị trong bài toán nối mạng máy tính: Cần nối mạng 1 hệ thống mạng gồm nhiều máy tính, kết nối làm sao giữa 2 máy bất kỳ đều có 1 đường thông tin qua lại, cho biết chi phí kết nối giữa các máy hãy tìm cách kết nối sao có tổng chi phí là thấp nhất. Để giải bài toán này, có thể mô hình bằng đồ thị trong đó mỗi máy là 1 đỉnh, các cạnh của đồ thị là tất cả các khả năng có thể kết nối giữa các máy, trên mỗi cạnh là trọng số tương ứng với chi phí kết nối. Rõ ràng đây là bài toán tìm cây bao trùm ngắn nhất của đồ thị. Giả sử có 1 hệ thống mạng như hình 2.3, cây bao trùm nhỏ nhất có những cạnh được tô đậm. 4. Cây bao trùm lớn nhất 4.1 Định nghĩa: Cây bao trùm lớn nhất của 1 đồ thị liên thông có trọng số là cây bao trùm có trọng số lớn nhất. Định nghĩa này cũng tương tự như định nghĩa cây bao trùm nhỏ nhất chỉ 1 điểm khác là ta thay trọng số bé nhất bằng trọng số lớn nhất như sau: l(g) = Max {l(g') / g' ẻ Ă} 4.2 Thuật toán tìm cây bao trùm lớn nhất Vấn đề tìm cây bao trùm lớn nhất cũng có thể tiến hành tương tự như cho cây bao trùm nhỏ nhất. Có thể áp dụng thuật toán Kruskal hoặc thuật toán Prim để tìm cây bao trùm lớn nhất, chỉ có khác là ở mỗi bước của thuật toán cạnh mới được chọn là cạnh có trọng số lớn nhất. Khi đó cạnh uk+1 được chọn sao cho l(uk+1) = Max{l(u) : u ẻ U\Uk}. Ví dụ có thể cải tiến thuật toán Prim để tìm cây bao trùm lớn nhất của đồ thị n đỉnh như sau: - Bước 1: Chọn u1 sao cho l(u1) = max{l(u)} với u ẻ U đặt U1 = {u1} - Bước 2: Chọn u2 sao cho l(u2) = max{l(u)} với u ẻ U\U1 và u kề với 1 cạnh thuộc U1 ......... - Bước k +1: Giả sử đã có Uk = {u1, u2, ..., uk} Chọn uk + 1 sao cho l(uk+1) = max{l(u)} với u ẻ U\Uk và u kề với 1 cạnh thuộc Uk và không lập thành chu trình với các cạnh ẻ Uk Thuật toán dừng ở bước thứ n - 1 khi đó ta tìm được cây bao trùm lớn nhất.