Giáo trình Lý thuyết đồ thị

121 trang phuongnguyen 4210

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Lý thuyết đồ thị", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_ly_thuyet_do_thi.doc

Nội dung text: Giáo trình Lý thuyết đồ thị

GIÁO TRÌNH LÝ THUYẾT ĐỒ THỊ Trang 1
CHƯƠNG I CÁC KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ THỊ 1. ĐỊNH NGHĨA ĐỒ THỊ Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này. Chúng ta phân biệt các loại đồ thị khác nhau bởi kiểu và số lượng cạnh nối hai đỉnh nào đó của đồ thị. Định nghĩa 1. Đơn đồ thị vô hướng G = (V,E) bao gồm V là tập các đỉnh, và E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Định nghĩa 2. Đa đồ thị vô hướng G= (V, E) bao gồm V là tập các đỉnh, và E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Hai cạnh e 1 và e2 được gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh. Định nghĩa 3. Giả đồ thị vô hướng G = (V, E) bao gồm V là tập các đỉnh và E là tập các cặp không có thứ tự gồm hai phần tử (không nhất thiết phải khác nhau) của V gọi là cạnh. Cạnh e được gọi là khuyên nếu nó có dạng e = (u, u). Định nghĩa 4. Đơn đồ thị có hướng G = (V, E) bao gồm V là tập các đỉnh và E là tập các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung. Định nghĩa 5. Đa đồ thị có hướng G = (V, E) bao gồm V là tập các đỉnh và E là tập các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung. Hai cung e1, e2 tương ứng với cùng một cặp đỉnh được gọi là cung lặp. Trong các phần tiếp theo chủ yếu chúng ta sẽ làm việc với đơn đồ thị vô hướng và đơn đồ thị có hướng. Vì vậy, để cho ngắn gọn, ta sẽ bỏ qua tính từ đơn khi nhắc đến chúng. 2. CÁC THUẬT NGỮ CƠ BẢN Định nghĩa 1. Hai đỉnh u và v của đồ thị vô hướng G được gọi là kề nhau nếu (u,v) là cạnh của đồ thị G. 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). Để có thể biết có vao nhiêu cạnh liên thuộc với một đỉnh, ta đưa vào định nghĩa sau Trang 2
Định nghĩa 2. Ta gọi bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với nó và sẽ ký hiệu là deg(v). Thí dụ 1. Xét đồ thị cho trong hình 1, ta có deg(a) = 1, deg(b) = 4, deg(c) = 4, deg(f) = 3, deg(d) = 1, deg(e) = 3, deg(g) = 0 Đỉnh bậc 0 gọi là đỉnh cô lập. Đỉnh bậc 1 được gọi là đỉnh treo. Trong ví dụ trên đỉnh g là đỉnh cô lập, a và d là các đỉnh treo. Bậc của đỉnh có tính chất sau: Định lý 1. Giả sử G = (V, E) là đồ thị vô hướng với m cạnh. Khi đó tông bậc của tất cả các đỉnh bằng hai lần số cạnh. Thí dụ 2. Đồ thị với n đỉnh có bậc là 6 có bao nhiêu cạnh? Giải: Theo định lý 1 ta có 2m = 6n. Từ đó suy ra tổng các cạnh của đồ thị là 3n. Hệ quả. Trong đồ thị vô hướng, số đỉnh bậc lẻ (nghĩa là có bậc là số lẻ) là một số chẵn. Định nghĩa 3. Nếu e = (u, v) là cung của đồ thị có hướng G thì ta nói hai đỉnh u và v là kề nhau, và nói cung (u, v) nối đỉnh u với đỉnh v hoặc cũng nói cung này là đi ra khỏi đỉnh u và vào đỉnh v. Đỉnh u(v) sẽ được gị là đỉnh đầu (cuối) của cung (u,v). Tương tự như khái niệm bậc, đối với đồ thị có hướng ta có khái niệm bán bậc ra và bán bậc vào của một đỉnh. Định nghĩa 4. Ta gọi bán bậc ra (bán bậc vào) của đỉnh v trong đồ thị có hướng là số cung của đồ thị đi ra khỏi nó (đi vào nó) và ký hiệu là deg+(v) (deg-(v)) Trang 3
Thí dụ 3. Xét đồ thị cho trong hình 2. Ta có deg-(a)=1, deg-(b)=2, deg-(c)=2, deg-(d)=2, deg-(e) = 2. deg+(a)=3, deg+(b)=1, deg+(c)=1, deg+(d)=2, deg+(e)=2. Do mỗi cung (u, v) sẽ được tính một lần trong bán bậc vào của đỉnh v và một lần trong bán bậc ra của đỉnh u nên ta có: Định lý 2. Giả sử G = (V, E) là đồ thị có hướng. Khi đó Tổng tất cả các bán bậc ra bằng tổng tất cả các bán bậc vào bằng số cung. Đồ thị vô hướng thu được bằng cách bỏ qua hướng trên các cung được gọi là đồ thị vô hướng tương ứng với đồ thị có hướng đã cho. 3. ĐƯỜNG ĐI. CHU TRÌNH. ĐỒ THỊ LIÊN THÔNG Định nghĩa 1. Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị vô hướng G = (V, E) là dãy x0, x1, , xn-1, xn trong đó u = x0 , v = xn , (xi , xi+1) E, i = 0, 1, 2, , n-1. Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh: (x0, x1), (x1, x2), , (xn-1, xn) Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại. Thí dụ 1. Trên đồ thị vô hướng cho trong hình 1: a, d, c, f, e là đường đi đơn độ dài 4. Còn d, e, c, a không là đường đi, do (c,e) không phải là cạnh của đồ thị. Dãy b, c, f, e, b là chu trình độ dài 4. Đường đi a, b, e, d, a, b có độ dài là 5 không phải là đường đi đơn, do cạnh (a, b) có mặt trong nó 2 lần. Trang 4
Khái niệm đường đi và chu trình trên đồ thị có hướng được định nghĩa hoàn toàn tương tự như trong trường hợp đồ thị vô hướng, chỉ khác là ta có chú ý đến hướng trên các cung. Định nghĩa 2. Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó, n là số nguyên dương, trên đồ thị có hướng G = (V, E) là dãy x0, x1, , xn-1, xn trong đó u = x0, v = xn, (xi, xi+1) E, i = 0, 1, 2, , n-1. Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cung: (x0, x1), (x1, x2), , (xn-1, xn) Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại. Thí dụ 2. Trên đồ thị có hướng cho trong hình 1: a, d, c, f, e là đường đi đơn độ dài 4. Còn d, e, c, a không là đường đi, do (c,e) không phải là cạnh của đồ thị. Dãy b, c, f, e, b là chu trình độ dài 4. Đường đi a, b, e, d, a, b có độ dài là 5 không phải là đường đi đơn, do cạnh (a, b) có mặt trong nó 2 lần. Định nghĩa 3. Đồ thị vô hướng G = (V, E) được gọi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó. Định nghĩa 4. Ta gọi đồ thị con của đồ thị G = (V, E) là đồ thị H = (W, F), trong đó W  V và F  E. Trong trường hợp đồ thị là không liên thông, nó sẽ rã ra thành một số đồ thị con liên thông đôi một không có đỉnh chung. Những đồ thị con liên thông như vậy ta sẽ gọi là các thành phần liên thông của đồ thị. Định nghĩa 5. Trang 5
Đỉnh v được gọi là đỉnh rẽ nhánh nếu việc loại bỏ v cùng với các cạnh liên thuộc với nó khỏi đồ thị làm tăng số thành phần liên thông của đồ thị. Cạnh e được gọi là cầu nếu việc loại bỏ nó khỏi đồ thị làm tăng số thành phần liên thông của đồ thị. Định nghĩa 6. Đồ thị có hướng G = (V, E) đượ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ó. Định nghĩa 7. Đồ thị có hướng G = (V, E) được gọi là liên thông yếu nếu đồ thị vô hướng tương ứng với nó là vô hướng liên thông. 4. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆT a.Đồ thị đầy đủ. Đồ thị đầy đủ n đỉnh, ký hiệu bởi Kn, là đơn đồ thị vô hướng mà giữa hai đỉnh bất kỳ của nó luôn có cạnh nối. Các đồ thị K3, K4, K5 cho trong hình dưới đây. Hình 1. đồ thị đầy đủ K3, K4, K5 Đồ thị đầy đủ Kn có tất cả n(n-1)/2 cạnh, nó là đơn đồ thị có nhiều cạnh nhất. b) Đồ thị vòng : Đồ thị vòng Cn (n 3) gồm n đỉnh v1,v2, ,vn và các cạnh (v1,v2), (v2,v3), ,(vn-1,vn),(vn,v1) ( Hình - 2 ) Mô tả đồ thị vòng C6 Trang 6
c.Đồ thị hai phía. Đơn đồ thị G=(V,E) được gọi là hai phía nếu như tập đỉnh V của nó có thể phân hoạch thành hai tập X và Y sao cho mỗi cạnh của đồ thị chỉ nối một đỉnh nào đó trong X với một đỉnh nào đó trong Y. Khi đó ta sẽ sử dụng ký hiệu G=(X  Y, E) để chỉ đồ thị hai phía với tập đỉnh X Y. Định lý sau đây cho phép nhận biết một đơn đồ thị có phải là hai phía hay không. Định lý 1. Đơn đồ thị là đồ thị hai phía khi và chỉ khi nó không chứa chu trình độ dài lẻ. Hình 2. Đồ thị hai phía d.Đồ thị phẳng. Đồ thị được gọi là đồ thị phẳng nếu ta có thể vẽ nó trên mặt phẳng sao cho các cạnh của nó không cắt nhau ngoài ở đỉnh. Cách vẽ như vậy sẽ được gọi là biểu diễn phẳng của đồ thị. Thí dụ đồ thị K4 là phẳng, vì có thể vẽ nó trên mặt phẳng sao cho các cạnh của nó không cắt nhau ngoài ở đỉnh (xem hình 6). Hình 3. Đồ thị K4 là đồ thị phẳng Một điều đáng lưu ý nếu đồ thị là phẳng thì luôn có thể vẽ nó trên mặt phẳng với các cạnh nối là các đoạn thẳng không cắt nhau ngoài ở đỉnh (ví dụ xem cách vẽ K4 trong hình 6). Trang 7
Để nhận biết xem một đồ thị có phải là đồ thị phẳng có thể sử dụng định lý Kuratovski, mà để phát biểu nó ta cần một số khái niệm sau: Ta gọi một phép chia cạnh (u,v) của đồ thị là việc loại bỏ cạnh này khỏi đồ thị và thêm vào đồ thị một đỉnh mới w cùng với hai cạnh (u,w), (w, u) . Hai đồ thị G(V,E) và H=(W,F) được gọi là đồng cấu nếu chúng có thể thu được từ cùng một đồ thị nào đó nhờ phép chia cạnh. Định lý 2 (Kuratovski). Đồ thị là phẳng khi và chỉ khi nó không chứa đồ thị con đồng cấu với K3,3 hoặc K5. Trong trường hợp riêng, đồ thị K3,3 hoặc K5 không phải là đồ thị phẳng. Bài toán về tính phẳng của đồ thị K3,3 là bài toán đố nổi tiếng về ba căn hộ và ba hệ thống cung cấp năng lượng cho chúng: Cần xây dựng hệ thống đường cung cấp năng lượng với mỗi một căn hộ nói trên sao cho chúng không cắt nhau. Đồ thị phẳng còn tìm được những ứng dụng quan trọng trong công nghệ chế tạo mạch in. Biểu diễn phẳng của đồ thị sẽ chia mặt phẳng ra thành các miền, trong đó có thể có cả miền không bị chặn. Thí dụ, biểu diễn phẳng của đồ thị cho trong hình 7 chia mặt phẳng ra thành 6 miền R1, R2,. . . .R6. Hình 4. Các miền tương ứng với biểu diễn phẳng của đồ thị Euler đã chứng minh được rằng các cách biểu diễn phẳng khác nhau của một đồ thị đều chia mặt phẳng ra thành cùng một số miền. Để chứng minh điều đó, Euler đã tìm được mối liên hệ giữa số miền, số đỉnh của đồ thị và số cạnh của đồ thị phẳng sau đây. Định lý 3 (Công thức Euler). Giả sử G là đồ thị phẳng liên thông với n đỉnh, m cạnh. Gọi r là số miền của mặt phẳng bị chia bởi biểu diễn phẳng của G. Khi đó r = m-n + 2 Có thể chứng minh định lý bằng qui nạp. Xét thí dụ minh hoạ cho áp dụng công thức Euler. Thí dụ.: Cho G là đồ thị phẳng liên thông với 20 đỉnh, mỗi đỉnh đều có bậc là 3. Hỏi mặt phẳng bị chia làm bao nhiêu phần bởi biểu diễn phẳng của đồ thị G? Giải: Trang 8
Do mỗi đỉnh của đồ thị đều có bậc là 3, nên tổng bậc của các đỉnh là 3x20=60. Từ đó suy ra số cạnh của đồ thị m=60/2=30. Vì vậy, theo công thức Euler, số miền cần tìm là r=30-20+2=12. Bài toán tô màu đồ thị Cho đơn đồ thị vô hướng G. Hãy tìm cách gán mỗi đỉnh của đồ thị một màu sao cho hai đỉnh kề nhau không bị tô bởi cùng một màu. Một phép gán màu cho các đỉnh như vậy được gọi là một phép tô màu đồ thị. Bài toán tô màu đòi hỏi tìm phép tô màu với số màu phải sử dụng là ít nhất. Số màu ít nhất cần dùng để tô màu đồ thị được gọi là sắc số của đồ thị. Hãy lập trình cho bài toán này. Thuật giải 1: Dùng màu thứ nhất tô cho tất cả các đỉnh của đồ thị mà có thể tô được, sau đó dùng màu thứ hai tô tất cả các đỉnh của đồ thị còn lại có thể tô được và cứ như thế cho đến khi tô hết cho tất cả các đỉnh của đồ thị. m=1; số đỉnh đã được tô=0; mọi đỉnh đều chưa được tô do { for i=1 to n if đỉnh i là chưa xét và có thể tô được bằng màu m then { tô đỉnh i bằng màu m tăng số đỉnh đã được tô lên 1 đơn vị } m++ } while (số đỉnh đã được tô<n) Thuật giải 2: Tính bậc của tất cả các đỉnh while (còn đỉnh chưa được tô ) { -Tìm đỉnh(chưa được tô) có bậc lớn nhất. Chẳng hạn đó là đỉnh i0. -tìm màu để tô đỉnh i0, Chẳng hạn đó là màu j. -Ngăn cấm việc tô màu j cho các đỉnh kề với đỉnh i0 Trang 9
-tô màu đỉnh i0 là j. -Gán bậc của đỉnh được tô 0. } Chú ý:Các thuật toán trên chưa cho ta sắc số của một đồ thị G, nó chỉ giúp ta một cách tiếp cận để tìm sắc số của một đồ thị. Để tìm sắc số của một đồ thị thì sau khi tô màu xong ta phải sử dụng các định lý, các tính chất đã học của lý thuyết đồ thị để khẳng định số màu được dùng là ít nhất và từ đó suy ra sắc số của đồ thị. Bài toán tìm sắc số của một đồ thị là một bài toán khó và không phải đồ thị nào cũng tìm được sắc số của nó một cách dễ dàng. Gợi ý cài đặt cho thuật giải 2 Dữ liệu vào được lưu trên một trận vuông c[i][j]. Nếu c[i][j]=1 thì hai thành phố i,j là kề nhau. c[i][j]=0 thì hai thành phố i,j không kề nhau. Thuật toán Tính bậc của tất cả các đỉnh while (còn đỉnh chưa được tô ) { -Tìm đỉnh(chưa được tô) có bậc lớn nhất; chẳng hạn đó là đỉnh i0. -tìm màu để tô đỉnh i0; chẳng hạn đó là màu j. -Ngăn cấm việc tô màu j cho các đỉnh kề với đỉnh i0 -Tô màu đỉnh i0 là j. -Gán bậc của đỉnh được tô 0. } Mã giả: +Danh sách bảng màu cho các đỉnh được cho là 1 và bậc của các đỉnh cho là 0. for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) mau[i][j]=1; dinh[i]=0; bac[i]=0; } +Tính bậc cho mỗi đỉnh của đồ thị ban đầu for (i=1;i<=n;i++) for (int j=1;j<=n;j++) if (c[i][j]==1) Trang10
bac[i]=bac[i]+1; +i= 0 // là số đỉnh được tô tại thời điểm đang xét //Lặp lại đoạn sau đến khi nào số đỉnh đã được tô bằng n thì dừng lại { // tìm đỉnh có bậc cao nhất tại thời điểm đang xét // Tìm đỉnh (CHUA XET) có bậc cao nhất maxtemp=-1; for (int j=1;j maxtemp && dinh[j]==0) { maxtemp=bac[j]; i0=j; } //tìm và tô màu cho đỉnh có bậc cao nhất (giả sử đó là i0 ) và tô màu cho đỉnh này (giả sử đó là màu j) //Tìm và tô màu cho đỉnh có bậc cao nhất – màu m j=1; while (mau[i0][j]==0) j++; //bậc của các đỉnh kề với đỉnh i0 thì trừ đi 1 và ngăn cấm việc tô màu j các đỉnh kề với đỉnh i0 for (int k=1;k<=n;k++) if (c[i0][k]==1) { bac[k] ; mau[k][j]=0; } //Bậc của đỉnh được tô thì cho 0 dinh[i0]=j; bac[i0]=0; i++; } Trang11
Bài tập lý thuyết 1-1.Vẽ đồ thị (nếu tồn tại) a.Vẽ một đồ thị có 4 đỉnh với bậc các đỉnh là 3, 2, 2, 1. b.Vẽ các đồ thị mà mọi đỉnh của nó đều có bậc là lần lượt là k (1 k 5) c.Vẽ các đồ thị mà mọi đỉnh của nó đều có bậc là 3 và có số đỉnh lần lượt là:4,5,6,8. d.Vẽ một đồ thị có 15 đỉnh và mỗi đỉnh của nó đều có bậc là 5. 1-2.a.Một đồ thị phẳng liên thông có 8 đỉnh, các đỉnh lần lượt có bậc là 2, 2, 3, 3, 3, 3, 4, 6. Hỏi đồ thị có bao nhiêu cạnh ? b.Một đơn đồ thị phẳng liên thông có 10 mặt, tất cả các đỉnh đều có bậc 4. Tìm số đỉnh của đồ thị. c.Xét một đồ thị liên thông có 8 đỉnh bậc 3. Hỏi biểu diễn phẳng của đồ thị này sẽ chia mặt phẳng thành mấy miền. d.Đơn đồ thị phẳng liên thông G có 9 đỉnh, bậc các đỉnh là 2,2,2,3,3,3,4,4,5. Tìm số cạnh và số mặt của G. 1-3.a.Một đồ thị có 19 cạnh và mỗi đỉnh đều có bậc 3, hỏi đồ thị này có tối đa bao nhiêu đỉnh ? b.Cho một đồ thị vô hướng có n đỉnh. Hỏi đồ thị này có thể có tối đa bao nhiêu cạnh. Trong trường hợp số cạnh là tối đa thì mỗi đỉnh sẽ có bậc là bao nhiêu ? c.Cho một đồ thị vô hướng có n đỉnh và 2n cạnh. Chứng minh rằng trong đồ thị này luôn tồn tại một đỉnh có bậc không nhỏ hơn 4. d.Chứng minh rằng trong một đơn đồ thị vô hướng nếu không chứa chu trình thì sẽ luôn tồn tại ít nhất là hai đỉnh treo. e.Chứng minh rằng nếu đồ thị G có chứa một chu trình có độ dài lẻ thì số màu của G ít nhất phải là 3. 1-4.a.Xét đồ thị vô hướng đơn có số đỉnh n > 2 . Chứng minh rằng đồ thị có ít nhất 2 đỉnh cùng bậc với nhau. b.Cho 1 đồ thị G có chứa đúng 2 đỉnh bậc lẽ (các đỉnh khác nếu có phải bậc chẵn) Chứng minh rằng 2 đỉnh này liên thông với nhau. c.xét đồ thị vô hướng đơn có số đỉnh n > 2. Giả sử đồ thị không có đỉnh nào có bậc < (n- 1)/2. Chứng minh rằng đồ thị này liên thông d.Chứng minh rằng một đơn đồ thị vô hướng là hai phía nếu và chỉ nếu số màu của nó là 2. 1-5.Vẽ đồ thị phẳng liên thông a.có 6 cạnh và 3 miền. b.có 4 đỉnh và 5 miền. 42
c.có 6 đỉnh và 7 cạnh. 1-6.Giả sử có 6 cuộc mitting A,B,C,D,E,F cần được tổ chức. Mỗi cuộc mitting được tổ chức trong một buổi. Các cuộc mitting sau không được diễn ra đồng thời:BEF, CEF, ABE, CD, AD. Hãy bố trí các cuộc mitting vào các buổi sao cho số buổi diễn ra là ít nhất. 1-7.Chứng minh rằng một đồ thị đầy đủ có 5 đỉnh không là đồ thị phẳng. 1-8.Hãy tìm sắc số của đồ thị sau: A D K G E B L C F H 1-9.Có ba nhà ở gần ba cái giếng, từ mỗi nhà có đường đi thẳng đến mỗi giếng. Có lần do bất hòa với nhau, cả ba người này muốn tìm cách làm các con đường khác để đến các giếng sao cho các đường này không cắt nhau. Hỏi ý định này có thực hiện được không ? vì sao ? 1-10.Tìm số đỉnh, cạnh và miền của các đồ thị sau: 43
1-11.Với mỗi đồ thị sau đây hãy cho biết nó có phải là đồ thị phẳng hay không ? Nếu có hãy vẽ sao cho các cạnh của đồ thị đó không cắt nhau ngoài đỉnh. 44
a) b) c) d) e) f) g) h) i) 45
CHƯƠNG 2 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY VI TÍNH Để lưu trữ đồ thị và thực hiện các thuật toán khác nhau với đồ thị trên máy tính cần phải tìm những cấu trúc dữ liệu thích hợp để mô tả đồ thị. Việc chọn cấu trúc dữ liệu nào để biểu diễn đồ thị có tác động rất lớn đến hiệu quả của thuật toán. Vì vậy, việc chọn lựa cấu trúc dữ liệu để biểu diễn đồ thị phụ thuộc vào từng tình huống cụ thể (bài toán và thuật toán cụ thể). Trong mục này chúng ta sẽ xét một số phương pháp cơ bản được sử dụng để biểu diễn đồ thị trên máy tính. 1. MA TRẬN KỀ. MA TRẬN TRỌNG SỐ Xét đơn đồ thị vô hướng G = (V,E), với tập đỉnh V={1, 2,. . . ,n}, tập cạnh E={e1, e2,. . .,em} . Ta gọi ma trận kề của đồ thị G là ma trận. A={ai,j : i,j=1, 2,. . . ,n} Với các phần tử được xác định theo qui tắc sau đây: ai, j = 0, nếu (i,j) E và ai,j = 1 , nếu (i,j) E, i, j=1, 2,. . .,n. Thí dụ 1. Ma trận trận kề của đồ thị vô hướng cho trong hình 1 là: 1 2 3 4 5 6 1 0 1 1 0 0 0 2 1 0 1 0 1 0 3 1 1 0 1 0 0 4 0 0 1 0 1 1 5 0 1 0 1 0 1 6 0 0 0 1 1 0 (G) (G1) Hình 1. Đồ thị vô hướng G và Đồ thị có hướng G1 46
Các tính chất của ma trận kề: 1)Rõ ràng ma trận kề của đồ thị vô hướng là ma trận đối xứng, tức là a[i,j]=a[j,i], i,j=1,2,. . .,n. 2)Tổng các phần từ trên dòng i (cột j) của ma trận kề chính bằng bậc của đỉnh i (đỉnh j). Ma trận kề của đồ thị có hướng Được định nghĩa một cách hoàn toàn tương tự. Thí dụ 2. Đồ thị có hướng G1 cho trong hình 1 có ma trận kề là ma trận sau: 1 2 3 4 5 6 1 0 1 1 0 0 0 2 0 0 0 0 0 0 3 0 1 0 1 0 0 4 0 0 0 0 0 0 5 0 0 0 1 0 1 6 0 0 0 0 1 0 Lưu ý rằng ma trận kề của đồ thị có hướng không phải là ma trận đối xứng. Chú ý: Trên đây chúng ta chỉ xét đơn đồ thị. Ma trận kề của đa đồ thị có thể xây dựng hoàn toàn tương tự, chỉ khác là thay vì ghi 1 vào vị trí a[i,j] nếu (i,j) là cạnh của đồ thị, chúng ta sẽ ghi k là số cạnh nối hai đỉnh i, j. Ma trận trọng số Trong rất nhiều vấn đề ứng dụng của lý thuyết đồ thị, mỗi cạnh e=(u,v) của đồ thị được gán với một con số c(e) (còn viết là c(u,v) - gọi là trọng số của cạnh e). Đồ thị trong trường hợp như vậy được gọi là đồ thị có trọng số. Trong trường hợp đồ thị có trọng số, thay vì mà trận kề, để biểu diễn đồ thị ta sử dụng ma trận trọng số. C= {c[i,j], i,j=1, 2,. . .,n} với c[i,j] = c(i,j) nếu (i,j) E và c[i,j] =  nếu (i,j) E 47
trong đó số  , tuỳ từng trường hợp cụ thể, có thể được đặt bằng một trong các giá trị sau: 0, + , - . Ưu điểm lớn nhất của phương pháp biểu diễn đồ thị bằng ma trận kề (hoặc ma trận trọng số) là để trả lời câu hỏi: Hai đỉnh u,v có kề nhau trên đồ thị hay không, chúng ta chỉ phải thực hiện một phép so sánh; nhược điểm lớn nhất của phương pháp này là: không phụ thuộc vào số cạnh của đồ thị, ta luôn phải sử dụng n 2 đơn vị bộ nhớ để lưu trữ ma trận kề của nó. 2.2.Ma trận liên thuộc đỉnh-cạnh Xét G = (V,E) là đơn đồ thị có hướng, giả sử V ={ 1, 2, , n }; E = { e1, e2, , em}. Ma trận liên thuộc đỉnh – cạnh có n dòng (1 dòng ứng với 1 đỉnh) và m cột (1 cột ứng với 1 cạnh). Trong đó 1 nếu đỉnh i là đỉnh đầu của cung ej Aij = -1 nếu đỉnh i là đỉnh cuối của cung ej 0 nếu đỉnh i không là đầu mút của cạnh ej Ví dụ: Xét đồ thị 2 4 1 1 1 6 1 1 3 5 1 1 (1,2) (1,3) (2,3) (2,4) (3,5) (4,5) (4,6) (5,2) (5,6) 1 1 1 0 0 0 0 0 0 0 2 -1 0 1 1 0 0 0 -1 0 3 0 -1 -1 0 1 0 0 0 0 4 0 0 0 -1 0 1 1 0 0 5 0 0 0 0 -1 -1 0 1 1 6 0 0 0 0 0 0 -1 0 -1 48
2.3.DANH SÁCH CẠNH (CUNG) Trong trường hợp đồ thị thưa (đồ thị có số cạnh m thoả mãn bất dẳng thức: m < 6n) người ta thường dùng cách biểu diễn đồ thị dưới dạng danh sách cạnh. Trong cách biểu diễn đồ thị bởi danh sách cạnh (cung) chúng ta sẽ lưu trữ danh sách tất cả các cạnh (cung) của đồ thị vô hướng (có hướng). Một cạnh (cung) e = (x,y) của đồ thị sẽ tương ứng với hai biến Dau[e], Cuoi[e]. như vậy, để lưu trữ đồ thị ta cần sử dụng 2m đơn vị bộ nhớ. Nhược điểm của cách biểu diễn này là để xác định những đỉnh nào của đồ thị là kề với một đỉnh cho trước chúng ta phải làm cỡ m phép so sánh (khi duyệt qua danh sách tất cả các cạnh của đồ thị). Chú ý: Trong trường hợp đồ thị có trọng số ta cần thêm m đơn vị bộ nhớ để lưu trữ trọng số của các cạnh. Thí dụ 3. Danh sách cạnh (cung) của đồ thị G (G1) cho trong hình 1 là: Dau Cuoi Dau Cuoi 1 2 1 2 1 3 1 3 2 3 3 2 2 5 3 4 3 4 5 4 4 5 5 6 4 6 6 5 5 6 Danh sách cạnh của G Danh sánh cung của G1 2.4. DANH SÁCH KỀ Trong rất nhiều vấn đề ứng dụng của lý thuyết đồ thị, cách biểu diễn đồ thị dưới dạng danh sách kề cũng là cách biểu diễn được sử dụng. Trong cách biểu diễn này, với mỗi đỉnh v của đồ thị chúng ta lưu trữ danh sách các đỉnh kề với nó, mà ta sẽ ký hiệu là: ke(v)= { u V: (v,u) E} 49
Bài tập lý thuyết 2-1.Cho đồ thị vô hướng liên thông G như hình vẽ bên. 2 3 a.Hãy biểu diễn đồ thị G bằng ma trận kề, danh sách cạnh. b.Số màu ít nhất cần dùng để tô màu 1 4 5 8 một đồ thị được gọi là sắc số của đồ thị (bài toán tô màu). Hãy cho biết sắc số của đồ thị G trên. 2-2.Cho đồ thị G như hình vẽ bên: 6 7 a.Hãy biểu diễn đồ thị G bằng ma 2 4 4 trận liên thuộc đỉnh - cạnh, ma trận trọng số, danh sách cung. 6 8 b.Gọi G’ là đồ thị vô hướng thu 1 1 3 3 được bằng cách loại bỏ hướng trên 6 các cung của đồ thị G. Hãy cho biết 9 7 sắc số k của G’ và chỉ ra một cách tô 7 màu G’ với k màu. 3 5 2-3. Xét đồ thị G gồm 8 đỉnh được cho bởi ma trận trọng số(các đỉnh của đồ thị được đánh số từ 1) 0 2 0 5 2 0 0 0 2 0 5 0 3 6 0 0 0 5 0 0 10 3 0 1 5 0 0 0 4 0 7 0 2 3 10 4 0 1 6 0 0 6 3 0 1 0 3 5 0 0 0 7 6 3 0 4 0 0 1 0 0 5 4 0 a.Hãy biểu diễn đồ thị G bằng danh sách kề, danh sách cạnh. b.Đồ thị G có phải là đồ thị phẳng hay không ? Chứng minh. 50
2-4. Xét đồ thị có hướng G gồm 6 đỉnh được cho bởi hình vẽ dưới đây: a.Hãy biểu diễn G bằng ma trận trọng số và ma trận liên thuộc đỉnh – cạnh. b.Gọi G’ là đồ thị vô hướng được tạo bằng cách loại bỏ hướng trên các cung của G. Hãy cho biết sắc số k của G’ và chỉ ra một cách tô màu G’ với k màu. 2-5.Xét đồ thị có hướng G gồm 5 đỉnh được cho bởi hình vẽ dưới đây: a.Hãy biểu diễn G bằng ma trận trọng lượng và ma trận liên thuộc. b.Gọi G’ là đồ thị vô hướng được tạo bằng cách loại bỏ hướng trên các cung của G (và bỏ cung (3,4) có trọng lượng là 1). Hãy cho biết sắc số k của G’ và chỉ ra một cách tô màu G’ với k màu. Bài tập thực hành 2-6.Lập trình nhập đồ thị với các phương pháp biểu diễn: ma trận kề, ma trận trọng số và danh sách cạnh, ma trận liên thuộc. 2-7.Lập trình cho phép chuyển đổi cấu trúc dữ liệu biểu diễn đồ thị dưới dạng ma trận trọng số qua dạng danh sách cạnh và ngược lại. 2-8.Lập trình cho phép chuyển đổi cấu trúc dữ liệu biểu diễn đồ thị dưới dạng ma trận kề qua dạng danh sách kề và ngược lại. 2-9.Cho đồ thị vô hướng được biểu diễn bằng ma trận kề. Dữ liệu được lưu trên file text dothi.inp có cấu trúc như sau: 51
Dòng đầu ghi số n, trong n dòng tiếp theo mỗi dòng ghi n số, các số cách nhau ít nhất một dấu cách. Hãy viết chưong trình thực hiện các yêu cầu sau: a.Đọc ma trận kề từ file dothi.inp b.Kiểm tra tính hợp lệ của ma trận (kiểm tra xem các giá a[i][i] có giá trị nào khác 0 hay không ? kiểm tra xem có giá trị nào mà a[i][j] khác a[j][i] hay không ?) 2-10.Cho một đơn đồ thị. Hãy viết các hàm thực hiện các yêu cầu sau: a.Đồ thị là có hướng hay vô hướng ? b.Tính bậc của mỗi đỉnh. c.Kiểm tra xem có phải là đồ thị hai phía hay không? 52
CHƯƠNG 3 CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ VÀ ỨNG DỤNG 1. TÌM KIẾM THEO CHIỀU SÂU TRÊN ĐỒ THỊ Ý tưởng chính của thuật toán có thể trình bày như sau. Ta sẽ bắt đầu tìm kiếm từ một đỉnh v0 nào đó của đồ thị. Sau đó chọn u là một đỉnh tuỳ ý kề với v 0 và lặp lại quá trình đối với u. Ở bước tổng quát, giả sử ta đang xét đỉnh v. Nếu như trong số các đỉnh kề với v tìm được đỉnh w là chưa được xét thì ta sẽ xét đỉnh này (nó sẽ trở thành đã xét) và bắt đầu từ nó ta sẽ bắt đầu quá trình tìm kiếm còn nếu như không còn đỉnh nào kề với v là chưa xét thì ta nói rằng đỉnh này đã duyệt xong và quay trở lại tiếp tục tìm kiếm từ đỉnh mà trước đó ta đến được đỉnh v (nếu v=v 0, thì kết thúc tìm kiếm). Có thể nói nôm na là tìm kiếm theo chiều sâu bắt đầu từ đỉnh v được thực hiện trên cơ sở tìm kiếm theo chiều sâu từ tất cả các đỉnh chưa xét kề với v. Quá trình này có thể mô tả bởi thủ tục đệ qui sau đây void DFS(v); (*tim kiem theo chieu sau bat dau tu dinh v; cac bien chuaxet, Ke la bien toan cuc*) { tham_dinh(v); chuaxet[v]=0; for u ke(v) If (chuaxet[u]) DFS(u); } (*dinh v da duyet xong*) Khi đó, tìm kiếm theo chiều sâu trên đồ thị được thực hiện nhờ thuật toán sau: void main() { (*Initialization*) for v V chuaxet[v]=1; for v V if (chuaxet[v]) DFS(v); } 53
Rõ ràng lệnh gọi DFS(v) sẽ cho phép đến thăm tất cả các đỉnh thuộc cùng thành phần liên thông với đỉnh v, bởi vì sau khi thăm đỉnh là lệnh gọi đến thủ tục DFS đối với tất cả các đỉnh kề với nó. Mặt khác, do mỗi khi thăm đỉnh v xong, biến chuaxet[v] được đặt lại giá trị false nên mỗi đỉnh sẽ được thăm đúng một lần. Thuật toán lần lượt sẽ tiến hành tìm kiếm từ các đỉnh chưa được thăm , vì vậy, nó sẽ xét qua tất cả các đỉnh của đồ thị (không nhất thiết phải là liên thông). Để đánh giá độ phức tạp tính toán của thủ tục, trước hết nhận thấy rằng số phép toán cần thực hiện trong hai chu trình của thuật toán (hai vòng for ở chương trình chính) là cỡ n. Thủ tục DFS phải thực hiện không quá n lần. Tổng số phép toán cần phaỉ thực hiện trong các thủ tục này là O(n+m), do trong các thủ tục này ta phải xét qua tất cả các cạnh và các đỉnh của đồ thị. Vậy độ phức tạp tính toán của thuật toán là O(n+m). Ví dụ : Xét đồ thị cho trong hình sau . Các đỉnh của nó được đánh số lại theo thứ tực chúng được thăm theo thủ tục tìm kiếm theo chiều sâu mô tả ở trên . 3( 9) 2(2) 7(8) 5( 5) 1(1) 6(4) 4( 3) 8(6) 10(11) 13(10) 9(7) 12(13) 11(12) Ví dụ TIMSAU.INP TIMSAU.OUT 13 1 2 4 6 5 8 9 7 3 13 10 11 12 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 54
0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 Chỉ số mới (trong ngoặc) của các đỉnh được đánh lại theo thứ tự chúng được thăm theo thuật toán tìm kiếm theo chiều sâu Ta có thể mô tả bằng Ngôn ngữ C như sau: #include #include #include #include #include #define MAX 20 #define TRUE 1 #define FALSE 0 /* tim kiem theo chieu sau */ void Init(int A[][MAX],int *n) { FILE *fp; int i,j; fp=fopen("c:\TIMRONG.INP","r"); if(fp==NULL) { printf("\n khong co tap *.inp"); delay(2000); return; } fscanf(fp,"%d",n); printf("\n so dinh cua do thi la=%d",*n); printf("\n\n ma tran ke cua do thi la"); for(i=1;i<=*n;i++) { printf("\n\n"); 55
for(j=1;j<=*n;j++) { fscanf(fp,"%d",&A[i][j]); printf("%3d",A[i][j]); } } } /* */ void DFS(int A[][MAX],int n,int v,int chuaxet[]) { int u; printf("%3d",v);chuaxet[v]=FALSE; for(u=1;u<=n;u++) { if(A[v][u]==1 && chuaxet[u]) DFS(A,n,u,chuaxet); } } /* */ void main() { clrscr(); int A[MAX][MAX],n,chuaxet[MAX]; Init(A,&n); for(int i=1;i<=n;i++) chuaxet[i]=TRUE; printf("\n\n\n\n"); for(i=1;i<=n;i++) if( chuaxet[i]) DFS(A,n,i,chuaxet); getch(); } 2. TÌM KIẾM THEO CHIỀU RỘNG TRÊN ĐỒ THỊ Để ý rằng trong thuật toán tìm kiếm theo chiều sâu đỉnh được thăm càng muộn sẽ càng sớm trở thành đã duyệt xong. Điều đó là hệ quả tất yếu của việc các đỉnh được 56
thăm sẽ được kết nạp vào trong ngăn xếp (STACK). Tìm kiếm theo chiều rộng trên đồ thị, nếu nói một cách ngắn gọn, được xây dựng trên cơ sở thay thế ngăn xếp (STACK) bởi hàng đợi (QUEUE). Với sự cải biên như vậy, đỉnh được thăm càng sớm sẽ càng sớm trở thành đã duyệt xong (tức là càng sớm dời khỏi hàng đợi). Một đỉnh sẽ trở thành đã duyệt xong ngay sau khi ta xét xong tất cả các đỉnh kề (chưa được thăm) với nó. Thủ tục có thể mô tả như sau: void BFS(v); (*Tim kiem theo chieu rong bat dau tu dinh v, cac bien chuaxet, Ke la bien cuc bo*) { QUEUE= ; QUEUE  v; (*ket qua nap vao QUEUE*) Chuaxet[v]=0; While (QUEUE<> ) { P  QUEUE; (*lay p tu QUEUE:*) Tham_dinh(p); for u Ke(v) If (chuaxet[u]) { QUEUE  u; chuaxet[u]=0; } } } Khi đó, tìm kiếm theo chiều rộng trên đồ thị được thực hiện nhờ thuật toán sau: void main() { (*Initialization*) for f V do chuaxet[v]=1; for v V 57
if (chuaxet[v]) BFS(v); } Lập luận tương tự như trong thủ tục tìm kiếm theo chiều sâu, có thể chỉ ra được rằng lệnh gọi BFS(v) sẽ cho phép thăm đến tất cả các đỉnh thuộc cùng thành phần liên thông với đỉnh v, và mỗi đỉnh của đồ thị sẽ được thăm đúng một lần. Độ phức tạp tính toán của thuật toán là O(m+n). Ví dụ . Xét đồ thị được cho trong hình sau . các đỉnh của nó được đánh số lại theo thứ thụ được thăm theo thủ tục tìm kiếm theo chiều rộng mô tả ở trên 3(10) 2(2) 7(6) 5(9) 1(1) 6(5) 4(3) 10(4) 13(11) 8(12) 9(13) 12(8) 11(7) Ví dụ: TIMRONG.INP TIMRONG.OUT 13 1 2 4 1 0 6 7 11 12 5 13 3 8 9 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 58
0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 Mô tả thuật toán tìm kiếm theo chiều rộng Ta coù theå moâ taûchöông trình baèng Ngoân ngöõ C nhö sau : Chỉ số mới (trong ngoặc ) của các đỉnh được đánh lại theo thứ tự chúng được thăm theo thuật toán tìm kiếm theo chiều rộng #include #include #include #include #include #define MAX 20 #define TRUE 1 #define FALSE 0 /* tim kiem theo chieu rong */ void Init(int A[][MAX],int *n,int *solt,int *chuaxet) { FILE *fp;int i,j; fp=fopen("timrong.inp","r"); if(fp==NULL) { printf("\n khong co tap *.inp"); delay(2000); return; } fscanf(fp,"%d",n); printf("\n so dinh cua do thi la=%d",*n); printf("\n ma tran ke cua do thi la"); for(i=1;i<=*n;i++) { printf("\n\n"); for(j=1;j<=*n;j++) { fscanf(fp,"%d",&A[i][j]); printf("%4d",A[i][j]); } } for(i=1;i<=*n;i++) chuaxet[i]=0; *solt=0; } /* */ void BFS(int A[][MAX],int n,int i,int *solt,int chuaxet[],int QUEUE[MAX]) { int u,dauQ,cuoiQ,j; dauQ=1;cuoiQ=1; 59
QUEUE[cuoiQ]=i; chuaxet[i]=*solt; while(dauQ<=cuoiQ) { u=QUEUE[dauQ]; printf("%4d",u); dauQ=dauQ+1; for(j=1;j<=n;j++) { if(A[u][j]==1 && chuaxet[j]==0) { cuoiQ=cuoiQ+1; QUEUE[cuoiQ]=j; chuaxet[j]=*solt; } } } } /* */ void main() { clrscr(); int A[MAX][MAX],n,chuaxet[MAX],QUEUE[MAX],solt,i; Init(A,&n,&solt,chuaxet); for(i=1;i<=n;i++) chuaxet[i]=0; printf("\n\n\n\n"); for(i=1;i<=n;i++) if( chuaxet[i]==0) { solt=solt+1; BFS(A,n,i,&solt,chuaxet,QUEUE); } getch(); 3. TÌM ĐƯỜNG ĐI VÀ KIỂM TRA TÍNH LIÊN THÔNG Trong mục này ta xét ứng dụng các thuật toán tìm kiếm mô tả trong các mục trước vào việc giải bài toán cơ bản trên đồ thị: bài toán về tìm đường đi và bài toán về xác định tính liên thông của đô thị. a) Bài toán tìm đường đi giữa hai đỉnh: Giả sử s và t là hai đỉnh nào đó của đồ thị. Hãy tìm đường đi từ s đến t. Như trên đã phân tích, thủ tục DFS(s) (BFS(s)) sẽ cho thăm tất cả các đỉnh thuộc cùng một thành phần liên thông với s. vì vậy, sau khi thực hiện xong thủ tục, nếu chuaxet[t]=true(1), thì điều đó có nghĩa là không có đường đi từ s đến t, còn nếu chuaxet[t]=false(0 ) thì t thuộc cùng thành phần liên thông với s, hay nói một cách khác: tồn tại đường đi từ s 60
đến t. Trong trường hợp tồn tại đường đi, để ghi nhận đường đi, ta dùng thêm biểu thức Truoc[v] để ghi nhận đỉnh đi trước đỉnh v trong đường đi tìm kiếm tứ s đến v. Khi đó, đối với thủ tục DFS(v) cần sửa đổi câu lệnh trong nó như sau: If (chuaxet[u]) { Truoc[u]=v; DFS(u); } Còn đối với thủ tục BFS(v) cần sửa đổi câu lện if trong nó như sau: If (chuaxet [u]) { QUEUE  u; chuaxet[u]=0; Truoc[u]=p; } Chú ý: Đường đi tìm được theo thuật toán tìm kiếm theo chiều rộng là đường đi ngắn nhất (theo số cạnh) từ s đến t. Điều này suy trực tiếp từ thứ tự thăm đỉnh theo thuật toán tìm kiếm theo chiều rộng. Ví dụ: Cho đồ thị với ba thành phần liên thông sau:          H K P Đồ thị G ( với 3 thành phần liên thông là : H, K, P ) Giả sử s và t là hai đỉnh nào đó của đồ thị . Hãy tìm đường đi từ s đến t . Như đã phân tích ở trên thủ tục DFS(s) và BFS(s) sẽ cho phép thăm tất cả các đỉnh của một thành phần liên thông với s . Vì vậy sau khi thực hiện xong thủ tục mà đỉnh t vẫn chưa được xét thì điều đó có nghĩa là sẽ không có đường đi từ s đến t . Ngược lại thì tồn tại đường đi từ s đến t . 61
Mô tả bằng ngôn ngữ C như sau : #include #include #include #include #include #define TRUE 1 #define FALSE 0 #define MAX 20 void in(); void init(); int n,truoc[MAX],chuaxet[MAX],queue[MAX]; int A[MAX][MAX]; int s,t; // /* tim kiem theo chieu rong */ // void init() { FILE *fp; int i,j; fp=fopen("lthong.inp","r"); if(fp==NULL) { printf("\n khong co tep INP"); delay(2000); return; } fscanf(fp,"%d",&n); printf("\n so dinh do thi la:%d",n); printf("\n ma tran ke cua do thi"); printf("\n\n"); for(i=1;i<=n;i++) { printf("\n"); for(j=1;j<=n;j++) { fscanf(fp,"%3d",&A[i][j]); printf("%3d",A[i][j]); } } for(i=1;i<=n;i++) { chuaxet[i]=TRUE; truoc[i]=0; } } 62
// void result() { printf("\n\n"); if(truoc[t]==0) { printf("\n khong co duong di tu %d den %d",s,t); getch(); return; } printf("\n duong di tu %d den %d la :",s,t); int j=t;printf("%2d <-",t); while(truoc[j]!=s) { printf("%3d<-",truoc[j]); j=truoc[j]; } printf("%3d",s); } // // void BFS(int s) { int u,dauQ,cuoiQ,p;printf("\n"); dauQ=1;cuoiQ=1; queue[cuoiQ]=s; chuaxet[s]=FALSE; printf("\n cac dinh lien thong voi %d:",s,"la:"); while(dauQ<=cuoiQ) { u=queue[dauQ]; dauQ=dauQ+1; printf("%3d",u); for(p=1;p<=n;p++) { if(A[u][p]==1 && chuaxet[p]==TRUE) { cuoiQ=cuoiQ+1; queue[cuoiQ]=p; chuaxet[p]=FALSE; truoc[p]=u; } } } } // 63
// void duongdi() { int chuaxet[MAX],truoc[MAX],queue[MAX]; init(); printf("\n"); BFS(s); getch(); result(); } // // void main() { clrscr(); printf("\n nhap dinh dau s="); scanf("%d",&s); printf("\n nhap dinh cuoi t="); scanf("%d",&t); duongdi(); getch(); } b) Tìm các thành phần liên thông của đồ thị: Hãy cho biết đồ thị gồm bao nhiêu thành phần liên thông và từng thành phần liên thông của nó là gồm những đỉnh nào. ? Do thủ tục DFS(v) (BFS(s)) cho phép thăm tất cả các đỉnh thuộc cùng một thành phần liên thông với s, nên số thành phần liên thông của đồ thị bằng số lần gọi đến thủ tục này. Moâ taû baèng ngoân ngöõ C nhö sau: Mô tả bằng ngôn ngữ C #include #include #include #include #include #define TRUE 1 #define FALSE 0 #define MAX 20 64
void BFS(int A[][MAX],int n,int i,int *solt,int chuaxet[],int QUEUE[MAX]); // - void Init(int A[][MAX],int *n,int *solt,int *chuaxet) { FILE *fp;int i,j; fp=fopen("lthong.inp","r"); if(fp==NULL) { printf("\n khong co tep INP"); delay(2000); return; } fscanf(fp,"%d",n); printf("\n so dinh do thi la:%d",*n); printf("\n ma tran ke cua do thi"); for(i=1;i<=*n;i++) { printf("\n"); for(j=1;j<=*n;j++) { fscanf(fp,"%3d",&A[i][j]); printf("%3d",A[i][j]); } } for(i=1;i<=*n;i++) chuaxet[i]=0; *solt=0; } // void result(int *chuaxet,int n,int solt) { printf("\n\n"); if(solt==1) 65
{ printf("\n do thi lien thong"); getch(); return; } for(int i=1;i<=solt;i++) { printf("\n so thanh phan lien thong la: %3d",solt); for(i=1;i<=solt;i++) { printf("\n thanh phan lien thong thu %3d:",i); for(int j=1;j<=n;j++) { if(chuaxet[j]==i) printf("%3d",j); } } } } // void BFS(int A[][MAX],int n,int i,int *solt,int chuaxet[],int QUEUE[MAX]) { int u,dauQ,cuoiQ,j; dauQ=1;cuoiQ=1;QUEUE[cuoiQ]=i;chuaxet[i]=*solt; while(dauQ<=cuoiQ) { u=QUEUE[dauQ]; printf("%4d",u); dauQ=dauQ+1; for(j=1;j<=n;j++) { if(A[u][j]==1 && chuaxet[j]==0) { cuoiQ=cuoiQ+1; 66
QUEUE[cuoiQ]=j; chuaxet[j]=*solt; } } } } // // void lien_thong() { int A[MAX][MAX],n,chuaxet[MAX],QUEUE[MAX],solt,i; clrscr(); Init(A,&n,&solt,chuaxet); printf("\n\n"); for(i=1;i<=n;i++) if(chuaxet[i]==0) { solt=solt+1; BFS(A,n,i,&solt,chuaxet,QUEUE); } result(chuaxet,n,solt); getch(); } // void main() { clrscr(); lien_thong(); } 67
Bài tập lý thuyết: 3-1.Hãy liệt kê các đỉnh của đồ thị được duyệt theo phương pháp tìm kiếm theo chiều sâu, tìm kiếm theo chiều rộng. Tìm đường đi từ đỉnh A đến đỉnh H. A B C D E F G H 3-2.Cho đồ thị vô hướng liên thông G 2 3 như hình vẽ bên. a.Hãy liệt kê danh sách các đỉnh của G theo thuật toán tìm kiếm theo chiều 4 sâu (DFS), theo thuật toán tìm kiếm 1 5 8 theo chiều rộng (BFS) bằt đầu từ đỉnh 1. b.Hãy tìm một đường đi từ đỉnh 1 đến 6 7 đỉnh 6 trên G theo thuật toán DFS và từ đỉnh 1 đến đỉnh 7 theo thuật toán BFS. 3-3.Cho đồ thị vô hướng liên thông G như hình vẽ bên. 2 3 a.Hãy biểu diễn đồ thị G bằng ma trận kề. b.Hãy liệt kê danh sách các đỉnh của 1 4 5 8 G theo thuật toán tìm kiếm theo chiều sâu (DFS), theo thuật toán tìm kiếm theo chiều rộng (BFS) bằt đầu từ đỉnh 1. 6 7 68
Bài tập thực hành 3-4.Một khóa học gồm N môn học, môn học i phải học trong ti ngày. Giữa các môn học có mối quan hệ trước/sau: có môn học chỉ học được sau khi đã học một số môn học khác. Mối quan hệ đó được thể hiện bởi một mảng hai chiều A[i, j]; i, j = 1, , N trong đó A[i, j] = 1/0 và A[i, i] bằng 0 với mọi i, A[i,j] = 1 khi và chỉ khi môn học i phải được dạy xong trước khi học môn j (ngày kết thúc môn i phải trứơc ngày bắt đầu môn j). Môn học i phải dạy trước môn học j nếu có một dãy môn học i 1, i2, , ik sao cho a[it, it+1] = 1, 1 1, mà môn i1 phải dạy trước môn i2, môn i2 phải dạy trước môn i 3, , môn ik-1 phải dạy trước môn ik, môn ik phải dạy trước môn i1. Hãy viết chương trình với tên KT3.CPP làm các việc sau: Hãy xét xem mảng A có bế tắc hay không. Nếu mảng A không bế tắc, hãy tính xem khóa học có thể kết thúc trong thời gian nhanh nhất là bao nhiêu ngày. Theo các học bảo đảm thời gian hoàn thành ngắn nhất ở câu 2, hãy tính xem một học sinh trong quá trình học phải học đồng thời trong một ngày nhiều nhất bao nhiêu môn. Dữ liệu vào được cho bởi file text có tên MH.DAT trong đó số N ghi ở dòng thứ nhất, trong nhóm N dòng tiếp theo, dòng thứ i ghi N số A[i, 1], , A[i, N] dòng cuối cùng ghi N số nguyên dượng ti không lớn hơn 30, 1 <= i <= N; N <= 30. Kết quả ghi ra file TKB.DAT như sau: dòng thứ nhất ghi số 1/0 tùy theo mảng A bế tắc / không bế tắc. Nếu dòng thứ nhất ghi số 0, ta mới ghi tiếp kết quả câu 2 và 3. Kết quả câu 2 ghi tiếp vào file TKB.DAT N+1 dòng như sau: dòng dầu ghi số T là số ngày tối thiểu có thể hoàn thành khóa học, tiếp theo là N dòng trong đó dòng thứ i ghi 2 số X, Y với ý nghĩa môn học thứ i học từ ngày thứ X đến ngày thứ Y (chú ý rằngY–X=ti–1). Kết quả câu 3 ghi tiếp vào file TKB.DAT như sau: dòng thứ nhất ghi 2 số Z, W với ý nghĩa trong ngày Z phải học W môn (W là số nhiều nhất các môn học phải học đồng thời trong một ngày), tiếp theo là một dòng ghi tên các môn học phải học đồng thời trong ngày Z. Trong các câu 2 và 3, có thể có nhiều lời giải tương đương chỉ cầu đưa ra một lời giải. Ví dụ 1 MH.DAT TKB.DAT 4 1 69
0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 1 Ví dụ 2 MH.DAT TKB.DAT 7 0 0 1 0 0 0 0 0 22 0 0 0 1 0 0 0 1 2 0 0 0 1 0 0 0 3 4 0 0 0 0 1 1 0 1 8 0 0 0 0 0 0 0 9 12 0 0 0 0 0 0 1 13 22 0 0 0 0 0 0 0 13 14 2 2 8 4 10 2 3 15 17 1 2 1 3 3-5.Cho một mạng N (N <= 20) máy tính được đánh số từ 1 đến N. Sơ đồ mạng được cho bởi hệ gồm M kênh (đoạn) nối trực tiếp giữa một số cặp máy trong mạng, m kênh tương ứng với m cặp. Cho biết chi phí truyền 1 đơn vị thông tin theo mỗi kênh của mạng. Người ta cần chuyển một bức thông điệp từ máy s đến máy t. Để đảm bảo an toàn, người ta chuyển bức thông điện này theo hai đường truyền tin khác nhau (tức không có kênh nào) của mạng được sử dụng trong cả hai đường truyền tin; cho phép hai đường truyền tin cùng đi qua một số máy tính). Chi phí của một đường truyền được hiểu là tổng chi phí trên các kênh của nó. Đơn giá đường truyền từ máy s sang máy t được tính như sau: Với hai máy s và t, cùng bức thông điệp có độ dài là 1 đơn vị thông tin, đơn giá truyền cho cặp (s, t) được tính bằng tổng chi phí chuyển thông điệp an toàn (bằng tổng chi phí của hai đường truyền tin) là nhỏ nhất. Người ta mong muốn mạng máy tính (mạng truyền tin nói trên thỏa mãn tính chất an toàn theo nghĩa là từ một máy bất kỳ luôn truyền được (một cách an toàn) thông điệp tới một 70
máy bất kỳ khác. Khi một mạng an toàn, người ta tính được đơn giá của mạng là tổng đơn giá mọi đường truyền từ một máy bất kỳ tới một máy bất kỳ khác. Ma trận đơn giá của mạng là mảng hai chiều A có N dòng và N cột, mà giá trị phần tử A[i,j] chính là đơn giá từ máy i sang máy j. 3-6.Truyền tin trên mạng Có một nhóm gồm N lập trình viên được đánh số từ 1 tới N, một số người trong họ có biết địa chỉ email của nhau. Khi biết một thông tin nào mới họ gửi thông tin đó cho nhau. Bạn là một người rất quan trọng và bạn biết tất cả các mối quan hệ của họ cũng như bạn có một thông tin rất đặc biệt mà muốn cho tất cả họ đều biết. Hãy lập trình chỉ ra một số ít nhất các lập trình viên cần cho họ biết thông tin sao cho những người đó có thể thông báo cho tất cả những người còn lại thông tin của bạn. Dữ liệu cho trong file văn bản với tên INFOR.INP trong đó dòng đầu chức số N (N <= 1000), dòng thứ I trong N dòng tiếp theo chứa danh sách các lập trình viên mà người I biết địa chỉ email của họ. Nếu người thứ I không biết địa chỉ của bất cứ ai thì dòng này là dòng trống. Kết quả ghi ra file văn bản với tên INFOR.OUT trong đó dòng đầu ghi số K là số người cần cho họ biết thông tin. Dòng thứ hai ghi ra chỉ số của những người đó. Ví dụ: INFOR.INP INFOR.OUT 6 3 2 3 1 1 4 1 6 5 4 71
CHƯƠNG 4 ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON Trong chương này chúng ra sẽ nghiên cứu hai dạng đồ thị đặc biệt là đồ thị Euler và đồ thị Hamilton. Dưới đây, nếu không có giải thích bổ sung, thuật ngữ đồ thị được dùng để chỉ chung đa đồ thị vô hướng và có hướng, và thuật ngữ cạnh sẽ dùng để chỉ chung cạnh của đồ thị vô hướng cũng như cung của đồ thị có hướng. 4.1. ĐỒ THỊ EULER Định nghĩa 1. Chu trình đơn trong đồ thị G đi qua mỗi cạnh của nó một lần được gọi là chu trình Euler. Đường đi đơn trong G đi qua mỗi cạnh của nó một lần được gọi là đường đi Euler. Đồ thị được gọi là đồ thị Euler nếu nó có chu trình Euler, và gọi là đồ thị nửa Euler nếu nó có đường đi Euler. Rõ ràng mọi đồ thị Euler luôn là nửa Euler, nhưng điều ngược lại không luôn đúng. Thí dụ 1. Đồ thị G1 trong hình 1 là đồ thị Euler vì nó có chu trình Euler a, e, c, d, e, b, a. Đồ thị G 3 không có chu trình Euler nhưng nó có đường đi Euler a, c, d, e, b, d, a, b, vì thế G3 là đồ thị cửa Euler. Đồ thị G2 không có chu trình cũng như đường đi Euler. Hình 1. Đồ thị G1, G2, G3 Thí dụ 2. Đồ thị H 2 trong hình 2 là đồ thị Euler vì nó có chu trình Euler a, b, c, d, e, a. Đồ thị H 3 không có chu trình Euler nhưng nó có đường đi Euler c, a, b, c, d, b vì thế H 3 là đồ thị nửa Euler. Đồ thị H1 không có chu trình cũng như đường đi Euler. Hình 2. Đồ thị H1, H2, H3 72
Điều kiện cần và đủ để một đồ thị là một đồ thị Euler được Euler tìm ra vào năm 1736 khi ông giải quyết bài toán hóc búa nổi tiếng thế giới thời đó về bảy cái cầu ở thành phố Konigsberg và đây là định lý đầu tiên của lý thuyết đồ thị. Định lý 1 (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. Hệ quả. Đồ thị vô hướng liên thông G là nửa Euler khi và chỉ khi nó có không quá 2 đỉnh bậc lẻ. Thuật tóan 1: Xây dựng một chu trình Euler (mở rộng chu trình): Bắt đầu từ một đỉnh a, đi theo các cạnh của đồ thị một cách ngẫu nhiên nhưng không lặp lại cạnh nào đã đi qua cho đến khi không thể đi tiếp được nữa, nghĩa là phải dừng ở một đỉnh b nào đó. Lúc này mọi cạnh tới đỉnh b đều đã đi qua, nếu đỉnh a khác đỉnh b thì dễ thấy rắng sồ lần đi đến đỉnh b nhiều hơn số lần rời khỏi đỉnh b là 1: vô lý. Vậy phải có đỉnh b trùng với đỉnh a. Nói cách khác khi không thể di tiếp được là các cạnh đã đi qua đã tạo thành một chu trình. Nếu có một đỉnh c trong chu trình này là đỉnh đầu của một cạnh chưa đi qua thì ta sẽ mở rộng chu trình này thành một chu trình lớn hơn bằng cách khởi hành lại từ đỉnh c, rồi tiếp tục đi theo cạnh tới đỉnh c chưa đi qua nói ở trên cho đến khi không thể đi tiếp được nữa, ta sẽ tạo được một chu trình mói chứa chu trình cũ. Cứ tiếp tục như thế cho đến khi được một chu trình mà không thể tiếp tục mở rộng ra được nữa, đều này xảy ra khi mọi đỉnh trong chu trình hiện có đều không còn cạnh nào chưa đi qua. Hình 4. Minh hoạ cho chứng minh định lý 1 Giả sử G là đồ thị Euler, thuật toán đơn giản sau đây cho phép xác định chu trình Euler khi làm bằng tay. 73
void Euler_Cycle() { STACK= ; CE= ; Chon u la mot dinh nao do cua do thi; STACK u; while STACK  { y=dinh dau tien trong danh sach Ke(x); STACK y; // loai bo canh (x,y) khoi do thi Ke(x)=Ke(x)\ y ; Ke(y)=Ke(y)\ x ; } else { x STACK; CE x; } } } Thuật toán 2: (Thuật toán Flor) Xuất phát từ một đỉnh u nào đó của G ta đi theo các cạnh của nó một cách tuỳ ý chỉ cần tuân thủ 2 qui tắc sau: 74
(1) Xoá bỏ cạnh đã đi qua đồng thời xoá bỏ cả những đỉnh cô lập tạo thành. (2) Ở mỗi bước ta chỉ đi qua cầu khi không còn cách lựa chon nào khác. Định lý 2. Đồ thị có hướng liên thông mạnh là đồ thị Euler khi và chỉ khi deg+(v)=deg - (v),  v V. Thuaät toaùn Flor ñeå tìm moät chu trình EULER Böôùc 1: Tìm moät chu trình baát kyø C trong G baèng caùch baét ñaàu töø moät ñænh baát kyø S, ta ñi doïc theo caùc caïnh cuûa G, moãi caïnh chæ qua moät laàn cho ñeán khi naøo khoâng ñi ñöôïc nöõa. Ta chaéc chaén phaûi quay veà ñænh xuaát phaùt (do trong ñoà thò Euler taát caû caùc ñænh ñeàu coù baäc chaün) Böôùc 2 Neáu chu trình C vöøa tìm ñöôïc chöùa toaøn boä caùc caïnh cuûa G thì C laø chu trình Euler caàn tìm, ngöôïc laïi do tính chaát cuûa ñoà thò Euler neân trong C toàn taïi moät ñænh I keà vôùi moät caïnh khoâng thuoäc C. Ta ñaûo chu trình C ñeå ñænh I trôû thaønh ñænh baét ñaàu cuûa noù. Tieáp tuïc quay laïi böôùc 1 ñeå môû roäng C. Ví duï: ( aùp duïng cho thuaät toaùn Flor) Cho ñoà thò G nhö sau : 1 1 2 3 4 5 6 2 3 1 1 1 2 1 1 1 1 Ta coù ma traän keà 3 1 1 1 1 4 4 1 1 5 1 1 6 1 1 5 6 Nhaän xeùt : Toång caùc phaàn töû treân moãi haøng cuûa ma traän keà ñeàu laø soá chaün ( nghóa laø moïi ñænh cuûa Ñoà thò ñeàu laø chaün) , Vaäy G coù chu trình Euler . Xeùt haøng 1 ( choïn ñænh 1) , phaàn töû ôû coät 2 laø moät soá khaùc khoâng (=1) vaäy ta choïn ñænh 2 vaø coù ñöôøng 12 Giaûm moät ôû phaàn töû m12 ( haøng 1 coät 2) vaø m21 ( xoùa caïnh 12 vöøa ñi qua) ñoà thò vaø ma traän trôû thaønh . 75
1 1 2 3 4 5 6 2 3 1 1 2 1 1 1 3 1 1 1 1 4 4 1 1 5 1 1 6 1 1 5 6 Xeùt haøng 2 , m23=1 , vaäy choïn ñænh keá tieáp laø 3 vaø coù ñöôøng 1 2 3. Ñoà thò vaø ma traän trôû thaønh 1 - 1 2 3 4 5 6 2 3 1 1 2 1 1 3 1 1 1 4 4 1 1 5 1 1 6 1 1 5 6 Xeùt haøng 3 , m31=1 choïn ñænh keá tieáp laø 1 vaø ta coù ñöôøng 1 2 3 1 . Ñoà thò vaø ma traän trôû thaønh . 1 1 2 3 4 5 6 2 3 1 2 1 1 3 1 1 4 4 1 1 5 1 1 6 1 1 5 6 Xeùt haøng 1 , moïi phaàn töû treân haøng naøy ñeàu baèng 0 : Khoâng theå ñi tieáp ñöôïc nöõa . Xeùt ñænh keá tieáp laø ñænh 2 . Treân haøng 2 coù phaàn töû m24=1 . Vaäy ta môû roäng chu trình (breakout) töø ñænh 2 . Vieát laïi chu trình 2 3 1 2 Ñoà thò vaø chu trình nhö cuõ . 76
XEÙt haøng 2 , m24=1 , choïn ñænh keá tieáp laø 4 vaø ta coù ñöôïc ñöôøng : 2 3 1 2 4 . Khi ñoù ñoà thò vaø ma traän nhö sau: 1 1 2 3 4 5 6 1 2 1 2 3 3 1 1 4 1 4 5 1 1 6 1 1 5 6 Xeùt haøng 4 , m43=1 , choïn ñænh keá tieáp laø 3 vaø coù ñöôïc ñöôøng 2 3 1 2 4 3 1 1 2 3 4 5 6 2 3 1 2 1 3 1 4 4 5 1 1 6 1 1 5 6 Xeùt haøng 3 , m36=1 , choïn ñænh keá tieáp laø 6 vaø ta coù ñöôïc ñöôøng : 2 3 1 2 4 3 6 1 1 2 3 4 5 6 2 3 1 2 1 3 4 4 5 1 1 6 1 5 6 xeùt haøng 6 , m65=1 , choïn ñænh keá tieáp laø 5 vaø ta coù ñöôøng : 2 3 1 2 4 3 6 5 . 77
1 1 2 3 4 5 6 2 3 1 2 1 3 4 4 5 1 6 5 6 Xeùt haøng 5 , m52=1 , choïn ñænh keá tieáp laø 2 vaø coù ñöôïc ñöôøng : 2 3 1 2 4 3 6 5 2 Ta coù ma traän coøn laïi laø ma traän 0 . vaø coù ngay chu trình Euler .( keát thuùc) 1 1 2 3 4 5 6 2 3 1 2 3 4 4 5 6 5 6 4.2.ĐỒ THỊ HAMILTON Trong mục này chúng ta xét bài toán tương tự như trong mục trước chỉ khác là ta quan tâm đến đường đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần. Sự thay đổi tưởng chừng như là không đáng kể này trên thực tế đã dẫn đến sự phức tạp hoá vấn đề cần giải quyết. Định nghĩa 2. Đường đi qua tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần được gọi là đường đi Hamilton. Chu trình bắt đầu từ một đỉnh v nào đó qua tất cả các đỉnh còn lại mỗi đỉnh đúng một lần rồi quay trở về v được gọi là chu trình Hamilton. Đồ thị G được gọi là đồ thị Hamilton nếu nó chứa chu trình Hamilton và gọi là đồ thị nữa Hamilton nếu nó có đường đi Hamilton. Rõ ràng đồ thị Hamilton là nửa Hamilton, nhưng điều ngược lại không còn đúng. Thí dụ 3. Trong hình 3: G3 là Hamilton, G2 là nửa Hamilton còn G1 không là nửa Hamilton. 78
Hình 3. Đồ thị Hamilton G3, nửa Hamilton G2 , và G1. Cho đến nay việc tìm một tiêu chuẩn nhận biết đồ thị Hamilton vẫn còn là mở, mặc dù đây là một vấn đề trung tâm của lý thuyết đồ thị. Hơn thế nứa, cho đến nay cũng chưa có thuật toán hiệu quả để kiểm tra một đồ thị có là Hamilton hay không. Các kết quả thu được phần lớn là điều kiện đủ để một đồ thị là đồ thị Hamilton. Phần lớn chúng điều có dạng "nếu G có số cạnh đủ lớn thì G là Hamilton". Một kết quả như vậy được phát biểu trong định lý sau đây. Định lý 3 (Dirak 1952). Đơn đồ thị vô hướng G với n>2 đỉnh, mỗi đỉnh có bậc không nhỏ hơn n/2 là đồ thị Hamilton. Định lý 4. Giả sử G là đồ có hướng liên thông với n đỉnh. Nếu deg + (v) ≥ n/2, deg – (v) ≥ n/2, v thì G là Hamilton. Có một số dạng đồ thị mà ta có thể biết khi nào là đồ thị Hamilton. Một ví dụ như vậy là đồ thị đấu loại. Đồ thị đấu loại là đồ thị có hướng mà trong đó hai đỉnh bất kỳ của nó được nối với nhau bởi đúng một cung. Tên đấu loại xuất hiện như vậy vì đồ thị như vậy có thể dùng để biểu diễn kết quả thi đấu bóng chuyền, bóng bàn hay bất cứ một trò chơi nào mà không cho phép hoà. Ta có định lý sau: Định lý 5. i) Mọi đồ thị đấu loại là nửa Hamilton. ii) Mọi đồ thị đấu loại liên thông mạnh là Hamilton. Thí dụ 4. Đồ thị đấu loại D5, D6 được cho trong hình 4. 79
Hình 4. Đồ thị đấu loại D5, đấu loại liên thông mạnh D6 Liệt kê các chu trình Hamilton (đối với đồ thị không có trọng số và được biểu diễn bằng ma trận kề) Gợi ý thuật tóan sau : void Hamilton(k); (*Liệt kê các chu trình Hamilton thu được bằng việc phát triển dãy X[1],X[2], ,X[K-1] của đồ thị G=(V,E) cho bởi danh sách kề *) { for y ke(X[k-1]) if (k==n-1 && y=vo) ghinhan(X[1],X[2], ,X[N],Vo) else if (chuaxet(y)) { X[k]=y; chuaxet[y]=0; Hamilton(k+1) chuaxet[y]=1; } } void main() { for v V chuaxet(v)=1 X[1]=vo; (*vo là một đỉnh nào đó của đồ thị*) chuaxet(vo)=0; Hamilton(2); } 80
Qui tắc tìm chu trình Hamilton Döïa vaøo nhaän xeùt laø moãi ñænh trong chu trình Hamilton ñeàu lieân keát vôùi ñuùng hai caïnh trong chu trình naøy, ta suy ra caùc qui taéc sau ñaây ñeå tìm chu trình Hamilton: 1.Neáu toàn taïi moät ñænh cuûa G coù baäc 1 thì G khoâng coù chu trình Hamilton. 2.Neáu ñænh x coù baäc laø 2 thì caû hai caïnh tôùi x ñeàu phaûi thuoäc chu trình Hamilton. 3.Chu trình Hamilton khoâng chöùa baát kyø chu trình con thöïc söï naøo. 4.Trong quaù trình xaây döïng chu trình Hamilton, sau khi ñaõ laáy hai caïnh tôùi ñænh x ñaët vaøo chu trình Hamilton roài thì khoâng theå laáy theâm caïnh naøo tôùi x nöõa, do ñoù coù theå xoùa moïi caïnh coøn laïi tôùi x. Ñaây laø quy taéc quan troïng ñeå tìm chu trình hamilton theo thuaät giaûi tham lam hoaëc laøm cô sôû tri thöùc baøi toaùn toát cho phöông phaùp thuaät giaûi di truyeàn. Ñònh Lyù 2.2.1.a. Moïi ñoà thò ñaày ñuû ñeàu coù chu trình Hamilton. Ñònh lyù 2.2.1.b Cho ñoà thò G lieân thoâng coù n ñænh (n 3). Neáu moïi ñænh cuûa G ñeàu coù baäc n/2 thì G coù chu trình Hamilton. Ñònh lyù 2.2.1.c. Moïi ñoà thò coù höôùng ñaày ñuû ñeàu coù chu trình Hamilton 81
Bài tập lý thuyết: 4-1.Kiểm tra xem các đồ thị sau có chứa chu trình hoặc đường đi Euler hay không ? 4-2. Kiểm tra xem các đồ thị sau có chứa chu trình hoặc đường đi Euler hay không ? 4-3.Cho đồ thị PeterSon(P) a.Tìm một đường đi Hamilton trong P b.P có chứa chu trình Hamilton hay không ? 4-4.Hãy cho ví dụ về: a.Đồ thị có một chu trình, vừa là chu trình Euler vừa là chu trình Hamilton b.Đồ thị có 1 chu trình Euler , 1 chu trình Hamilton , nhưng hai chu trình đó không trùng nhau c.Đồ thị có 6 đỉnh, là đồ thị Hamilton, nhưng không là đồ thị Euler d.Đồ thị có 6 đỉnh, là đồ thị Euler, nhưng không là đồ thị Hamilton 82
4-5.Kiểm tra xem các đồ thị sau có chứa chu trình hoặc đường đi Hamilton hay không ? 1 ` 2 4 3 5 Bài tập thực hành 4-6.Bài toán người đưa thư: Cho n thành phố, các thành phố được đánh số từ 1 đến n. Một người đưa thư muốn đi qua tất cả các con đường, mỗi con đường đúng 1 lần. Hãy lập lộ trình cho người đưa thư hoặc thông báo không tồn tại đường đi. 4-7.Cho đồ thị được biểu diễn bằng ma trận kề. Hãy liệt kê tất cả các chu trình Hamilton của đồ thị. 4-8.Bài toán hành trình người bán hàng (TRAVELING SALESMAN PROBLEM) Có n thành phố (được đánh số từ 1 đến n), một người bán hàng xuất phát từ một thành phố, muốn đi qua các thành phố khác, mỗi thành phố một lần rồi quay về thành phố xuất phát Giả thiết biết được chi phí đi từ thành phố i đến thành phố j là c[I,j]. Hãy tìm một hành trình cho người bán hàng sao cho tổng chi phí theo hành trình này là thấp nhất. 4-9.Kiểm tra đường Một trạm quảng đường giao thông phải chịu trách nhiêm về tình trạng của một mạng lưới giao thông nối giữa các điểm dân cư. Hàng tháng, họ phải cử một đội đi kiểm tra một vòng qua khắp mạng lưới để xem xét tình trạng hiện thời của các đường giao thông nhằm báo sửa chữa kịp thời nếu có nhu cầu. Hãy viết chương trình nhập vào mạng lưới giao thông và giúp trạm quyết định lộ trình của đội kiểm tra sao cho có thể thăm tất cả các con đường mà tổng chiều dài đoạn đường đi qua là nhỏ nhất. 4-10.Hội nghị bàn tròn Tổng thư ký Đại hội đồng Liên hợp quốc triệu tập một cuộc họp có N nhà ngoại giao của N tổ chức tham gia. Các đại diện ngoại giao được bố trí ngồi quanh một bàn tròn. Giữa một số tổ chức có quan hệ căng thẳng, vì vậy không thể xếp họ ngồi cạnh nhau được. Thông tin về quan hệ giữa các tổ chức được cho dưới dạng cặp số nguyên i, j nếu giữa 2 tổ chức này có quan hệ căng thẳng. 83
Hãy lập trình giúp Tổng thư ký Liên hợp quốc bố trí chỗ ngồi quanh bàn họp. Các tổ chức được đánh số từ 1 tới N, 0 < N <= 500. Dữ liệu vào: từ file CONF.INP, dòng đầu tiên chứa số nguyên N, các dòng sau, mỗi dòng một cặp số i, j cho biết các đại diện i và j không ngồi cạnh nhau được. Kết thúc là một dòng chứa 2 số 0. Kết quả: đưa ra file CONF.OUT. Nếu không có cách bố trí thỏa mãn yêu cầu thì đưa ra thông báo KHONG CO, trong trường hợp ngược lại – đưa ra dãy N số nguyên xác định vị trí ai ngồi cạnh ai quanh bàn tròn. Ví dụ: CONF.INP CONF.OUT 11 1 9 7 4 11 5 8 2 10 3 6 1 4 1 7 5 7 10 7 10 8 10 9 3 4 0 0 84
Cài đặt một số thuật toán căn bản quan trọng 1.Tìm chu trình Euler (bài toán người đưa thư). (Lưu ý chương trình sau được cài đặt theo thuật toán quay lui/vét cạn) 1. #include 2. #include 3. #include 4. #include 5. int m[20][20]; 6. int a[20]; 7. int b[20]; 8. int tc,dau,n; 9. int co; 10. void nhap() 11. { 12. FILE *f; 13. int i,j; 14. f=fopen("D:\\DOTHI\\EULER1.inp","rt"); 15. fscanf(f,"%d",&n); 16. cout >dau; 85
32. co=0; 33. // cout "<<a[i]; 42. co=1; 43. } 44. cout<<endl; 45. getch(); 46. exit(1); 47. } 48. void euler(int d,int i) 49. { 50. int j; 51. for (j=1;j<=n;j++) 52. if (m[d][j]==1) 53. { 54. a[i]=j; 55. m[d][j]=0; 56. m[j][d]=0; 57. if (i == tc) xuat(); 58. else euler(j,i+1); 59. m[d][j]=1; 60. m[j][d]=1; 61. } 62. } 63. void main() 64. { 65. nhap(); 86
66. euler(dau,1); 67. if (!co) cout<<"khong co duong di :"; 68. getch(); 69. } EULER1.inp 5 0 0 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 EULER2.inp 5 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 EULER3.inp 4 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 Yêu cầu sinh viên cài đặt thuật toán tìm chu trình Euler như đã nêu trong phần lý thuyết. 87
2.Tìm chu trình Hamilton (bài toán người bán hàng) Đi qua mỗi đỉnh một lần sao cho tổng chi phí là thấp nhất. Thuật toán tối ưu cho bài toán hành trình người bán hàng Besttour=0; Bestcost=maxint; while tìm thấy một hoán vị {xi} của tập {1,2, ,n} { với mỗi hoán vị {xi} ta được một hành trình, tính chi phí cho từng hành trình này cost=0; for i:=1 to n-1 cost+=c[xi,xi+1]; cost+=c[xn,x1]; if cost 2. #include 3. #include 4. #include 5. void output(); 6. void readfile(); 7. void permute(int i); 8. void result(); 9. const max=50; 10. int c[max][max]; 11. int tourbest[max],b[max],x[50],n,costbest; 12. void main() 13. { 14. readfile(); 88
15. permute(1); 16. result(); 17. } 18. void output() 19. { 20. int cost=0; 21. for (int i=1;i<n;i++) 22. cost=cost+c[x[i]] [x[i+1]]; 23. cost=cost+c[x[n]] [x[1]]; 24. if (cost<costbest) 25. { 26. costbest=cost; 27. for (int j=1;j<=n;j++) 28. tourbest[j]=x[j]; 29. } 30. } 31. void permute(int i) 32. { 33. for (int j=1;j<=n;j++) 34. if (b[j]==1) 35. { 36. x[i]=j; b[j]=0; 37. if (i==n) output(); 38. else permute(i+1); 39. b[j]=1; 40. } 41. } 42. void readfile() 43. { 44. clrscr(); 45. FILE *f; 46. f=fopen("d:\\dothi\\tsp1.inp","rt"); 47. fscanf(f,"%d",&n); 48. for (int i=1;i<=n;i++) 89
49. for (int j=1;j<=n;j++) 50. { 51. fscanf(f,"%d",&c[i][j]); 52. if (i==j) c[i][j]=MAXINT; 53. } 54. fclose(f); 55. costbest=MAXINT; 56. for (i=1;i<=n;i++) b[i]=1; 57. } 58. void result() 59. {cout<<costbest<<endl; 60. for (int i=1;i<=n;i++) cout<<tourbest[i]<<" "; 61. getch(); 62. } Tsp1.inp 6 0 3 5 7 5 6 2 0 2 3 1 7 4 7 0 2 2 4 3 7 4 0 5 2 4 6 2 4 0 2 5 6 2 5 3 0 Tsp2.inp 5 0 1 2 7 4 1 0 4 4 3 2 4 0 1 2 7 4 1 0 4 5 3 2 4 0 Tsp3.inp 5 90
0 21 40 32 28 15 0 18 37 25 19 17 0 6 7 9 50 28 0 4 25 6 5 10 0 SỬ DỤNG NGUYÊN LÝ THAM LAM GIẢI BÀI TÓAN NGƯỜI BÁN HÀNG: Với những bài toán mà không gian trạng thái có thể phát sinh cực lớn thì việc dùng phương pháp vét cạn là điều không thể. Nguyên lý tham lam lấy tiêu chuẩn tối ưu toàn cục để làm tiêu chuẩn chọn lựa hành động trong phạm vi cục bộ. Một số ví dụ có thể áp dụng nguyên lý này như các bài toán có mô hình toán học là bài toán người bán hàng, bài toán tô màu đồ thị. Hơn nữa nếu có một chiến lược tham lam hợp lý, thì phương pháp này sẽ tìm được lời giải tối ưu (thuật toán Kruskal, thuật toán Prim). Lược đồ của phương pháp tham lam Procedure Greedy(A,S) { là tập các ứng cử viên, S là tập nghiệm} begin S= While A  do Begin X=select(A); { chọn phần tử tốt nhất trong A} A=A-{x} If S  {x} chấp nhận được then S= S  {x} End; End; Thuật giải GTS1(u) Thuật giải GTS1 (Greedy Traveling Saleman) INPUT: số thành phố là n đỉnh xuất phát u và ma trận chi phí c OUTPUT: tour (thứ tự các thành phố đi qua), cost – chí phí ứng với tour tìm được v:=u; tour:={u}; cost=0; for i=1 to n {đặt w là thành phố kề sau thành phố v. tour=tour + {w}; 91
cost=cost+c[v,w] v=w; } tour=tour + {u}; cost=cost+c[v,u] THUẬT GIẢI GTS2 Input n, c, p,Vi (i=1 p)// vi là các thành phố được chọn ngẫu // nhiên trong tập n thành phố ban đầu Output: besttour, bestcost Bestcost=0 Besttour={} For i=1 to p { GTS1(vk); // suy ra được tour(vk) và cost(vk) If cost(vk)<bestcost { bestcost=cost(vk) besttour=tour(vk) } } 92
CHƯƠNG 5 CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ 3.1.Ñònh nghóa vaø caùc tính chaát cô baûn Ta goïi caây (tree) laø ñoà thò voâ höôùng lieân thoâng khoâng coù chu trình. 3.1.1Ñònh lyù 3.1.a Cho T laø moät caây, thì giöõa hai ñænh baát kyø cuûa T luoân luoân toàn taïi moät vaø chæ moät ñöôøng trong T noái chuùng. 3.1.2.Ñònh lyù 3.1.b Neáu caây coù n ñænh thì coù n-1 caïnh 3.1.3.Ñònh lyù 3.1.c (Daisy chainTheorem) Giaû söû T laø moät ñoà thò voâ höôùng n ñænh. Khi ñoù caùc meänh ñeà sau ñaây laø töông ñöông: i). T laø moät caây ii). T khoâng chöùa chu trình vaø coù n-1 caïnh iii). T lieân thoâng vaø moãi caïnh cuûa noù ñeàu laø caàu iv). Hai ñænh baát kyø cuûa T ñöôïc noái vôùi nhau bôûi ñuùng moät ñöôøng ñi ñôn. v). T khoâng chöùa chu trình nhöng heã cöù theâm vaøo noù moät caïnh ta thu ñöôïc ñuùng moät chu trình. vi) T lieân thoâng vaø coù n-1 caïnh Chöùng minh : I ) -> ii ) : Do định lý 3.1.a và 3.1.b ii)-> iii) Mỗi thành phần liên thông của T đều là cây vì T không có chu trình . Trong mỗi cây này , số cạnh +1 bằng số đỉnh . Mà theo giả thiết trong T có số cạnh+1= số đỉnh , Vậy T chỉ có một thành phần , nghĩa là T liên thông .Bây giờ ta hủy đi một cạnh trong T , ta nhận được một đồ thị T’ có số đỉnh là n và số cạnh là n-2 , hơn nữa T lại không có chu trình . nếu T’ liên thông thì T’ là một cây .(vô lý : vì số cạnh +1 iv) : Gọi x,y là hai đỉnh bất kỳ của T . Vì T liên thông nên tồn tại một đường đi nối chúng . Giả sử có 2 đường đi khácnhau nối x và y .khi đó nếu ta hủy bỏ một cạnh 93
nằm trên đường đi thứ nhất mà không nằm trên đường đi thứ hai thì sẽ làm mất tính liên thông của đồ thị . Mâu thuẫn với giả thiết ( vì bỏ đi một cạnh vãn còn liên thông) iv) -> v) : Nếu T có một chu trình , gọi v,w là hai đỉnh phân biệt của chu trình này , rõ ràng , ta có hai đường khác nhau nối v với w trên chu trình này (vô lý : vì T là cây ) vậy T không có chu trình .Bây giờ ta thêm một cạnh mới nối v và w khi đó cạnh mới này kết hợp với một đường đi từ v tới w không chứa cạnh mới sẽ tạo nên một chu trình trong T v)-> vi) : Xét hai đỉnh bất kỳ x,y của T . Thêm vào T cạnh mới nối x,y thì tạo ra một chu trình . Hủy bỏ cạnh mới này ra khỏi chu trình thì ta có một đường nối x và y . vậy T liên thông . Mà theo giả thiết T không có chu trình vậy T là cây . vi) -> i) Giả sử T có chu trình . Hủy bỏ một cạnh trong chu trình này ta có vẫn có T liên thông . Nếu đồ thị vẫn còn chu trình ta tiếp tục hủy một cạnh trong chu trình mới này , cứ tiếp tục như vậy cho đến khi T không còn chu trình ta được một đồ thị liên thông và không có chu trình .Nhưng khi đó đồ thị có n đỉnh mà số cạnh <n-1 (vô lý ) .Vậy T không có chu trình và T là cây . 3.2.Taâm vaø baùn kính cuûa caây Xét một cây có gốc T Mức (level) của một đỉnh v trong T là khoảng cách từ gốc đến v . Mức lớn nhất của một đỉnh bất kỳ trong cây gọi là chiều cao của cây (height) Nếu cạnh xy là cạnh của T thì ta gọi xlà cha (parent) của y , y là con(child) của x . Hai đỉnh cùng cha gọi là anh em (siblings) của nhau . Nếu có một đường (có hướng) từ v đến w thì v được gọi là đỉnh trước (ancestor) của w , w gọi là đỉnh sau (desendant) của v . Những đỉnh không có con gọi là lá (leaves) , những đỉnh không là lá được gọi là đỉnh trong (internal vertices) -một tập hợp gồm nhiều cây đôi một không có đỉnh chung được gọi là rừng (forest). Bây giờ ta xét một cây tự do T Độ lệch tâm (eccentricity) của đỉnh x , ký hiệu là E(x) là khoảng cách lớn nhất từ x đến một đỉnh bất kỳ trong T : E(x)= Max (x,y), y T a) Tâm và bán kinh của Cây : Đỉnh có độ lệch tâm nhỏ nhất trong T được gọi là Tâm (center) của T , độ lệch tâm của tâm được gọi là bán kính của cây Định lý 3.2.1 : Trong một cây tự do có nhiều nhất hai tâm 94
3.3. Caây m – phaân a) Định nghĩa : Cho một cây có gốc T.Nếu số cây con tối đa của một đỉnh trong T là m và có ít nhất một đỉnh có đúng m con thì T gọi là một cây m-phân (m-arytree) Nếu mọi đỉnh trong T đều có đúng m con thì T gọi là một cây m-phân đầy đủ (complete – m arytree) 3.4 Caây nhò phaân vaø pheùp duyeät caây 3.4.1. Định nghĩa : Cây nhị phân là một cây có gốcsao cho mỗi đỉnh đầu có nhiều nhất là hai con . Từ gốc , có thể có một hay hai cạnh đi xuống , đỉnh nối với gốc ở phía trái (phải) bằng các cạnh này gọi là cây con trái (phải) .Mỗi một trong các đỉnh con này lại có con bên trái hay con bên phải .và cứ như thế cho đến lá . Ngưới ta có thể định nghĩa đệ quy cho cây nhị phân như sau: Một cây nhị phân hoặc là tập rỗng hoặc gồm một gốc với hai cây con nhị phân cách biệt gọi là cây con bên trái và cây con bên phải . Gốc Cây con bên phải CâyCây concon bênbên tráitrái 3.4.2. Phép duyệt cây . Duyệt cây ( tree searching)là đưa ra một danh sách liệt kê tất cả các đỉnh của cây , mỗi đỉnh một lần . Thông thường có ba giải thuật để duyệt cây nhị phân . Preorder Search, Inorder search và Posorder search a) Giải thuật Preorder search ( ĐỆ QUY)) Bước 1: Đến gốc Bước 2: Đến cây con bên trái , dùng Preorder Bước 3: Đến cây con bên phải , dùng Preorder . 95 Cây con bên phải
Thí dụ : Xét cây nhị phân : A B C D E F Giải thuật Preorder cho ta thứ tự các đỉnh như sau: A, [ cây con bên trái ],[cây con bên phải] Kết quả : A B D E C F B) Giải thuật Inorder search ( ĐỆ QUY)) Bước 1: Đến cây con bên trái , dùng in order Bước 2: Đến gốc Bước 3: Đến cây con bên phải , dùng Inorder . Thí dụ : Xét cây nhị phân : A B C D E F Giải thuật Inorder cho ta thứ tự các đỉnh như sau: [ cây con bên trái ], A [cây con bên phải] Kết quả : D B E A C F . 96
C) Giải thuật Posorder search ( ĐỆ QUY)) Bước 1: Đến cây con bên trái , dùng Posorder Bước 2: Đến cây con bên phài , dùng Posorder Bước 3: Đến gốc . Thí dụ : Xét cây nhị phân : A B C D E F Giải thuật Posorder cho ta thứ tự các đỉnh như sau: [ cây con bên trái ], [cây con bên phải],A Kết quả : D E B C F A 3.5.Caây bao truøm cuûa ñoà thò: 3.5.1. Đinh nghĩa : Cho một đồ thị vô hướng G .Một cây T gọi là cây bao trùm ( Spanning tree) của G nếu T là một đồ thị con chứa mọi đỉnh của G . Baøi toaùn caây bao truøm nhoû nhaát cuûa ñoà thò laø moät trong nhöõng baøi toaùn toái öu treân ñoà thò tìm ñöôïc öùng duïng trong nhieàu lónh vöïc khaùc nhau cuûa ñôøi soáng. Trong muïc naøy chuùng ta seõ trình baøy nhöõng thuaät toaùn cô baûn ñeå giaûi baøi toaùn naøy, tröôùc heát ta phaùt bieåu noäi dung baøi toaùn. Giaû söû G=(V,E) laø ñoà thò voâ höôùng lieân thoâng. Caây T(V,F) vôùi F  E ñöôïc goïi laø caây bao truøm (spanning) cuûa ñoà thò G. 3.5.1.Ñònh lyù 1. Ñoà thò G coù caây bao truøm neáu vaø chæ neáu G lieân thoâng Ñeå tìm caây bao truøm cuûa ñoà thò ta coù theå söû duïng thuaät toaùn duyeät ñoà thò theo chieàu saâu hoaëc duyeät ñoà thò theo chieàu roäng 3.5.2.Baøi toaùn caây bao truøm toái thieåu: 97
Giaû söû G = (V,E) laø ñoà thò voâ höôùng lieân thoâng vôùi taäp ñænh V ={1,2.,,,.,n} vaø taäp caïnh E goàm m caïnh. Moãi caïnh e cuûa ñoà thò G ñöôïc gaén vôùi moät troïng soá khoâng aâm c(e) ñöôïc goïi laø ñoä daøi cuûa noù. Giaû söû H = (V,T) laø caây bao truøm cuûa ñoà thò G. Ta goïi ñoä daøi c(H) cuûa caây bao truøm H laø toång ñoä daøi cuûa caùc caïnh cuûa noù. C(H)= c(e) vôùi  e T. Caây bao truøm coù ñoä daøi nhoû nhaát ñöôïc goïi laø caây bao truøm toái thieåu(minimal spanning tree: MST) Thuaät toaùn tìm caây bao truøm coù theå duøng thuaät toaùn duyeät ñoà thò theo chieàu roäng vaø duyeät ñoà thò theo chieàu saâu. Ôû ñaây chuùng ta minh hoïa thuaät toaùn tìm caây bao truøm baèng caùch thöù nhaát. 3.5.2.1. Phép duyệt cây theo bề sâu (DFS) : Bước 1 : Chọn một đỉnh bất kỳ của G làm gốc của T Bước 2 : Tạo một đường đi từ gốc đi qua các đỉnh không trong T , kéo dài đường này đến khi không thể kéo dài thêm được nũa . Đặt đường này vào T rồi quay trở về đỉnh trước đó , xem đỉnh này là gốc . lặplại thử tục này cho đến khi mọi đỉnh của G đềnu nằm trong T . procedure SPANNING_TREE_DFS(v) G laø ñoà thò voâ höôùng lieân thoâng ñöôïc cho bôûi danh saùch keà. begin chuaxet[v]:=false; for u ke(v) do if chuaxet(u) then begin T:=T  {(v,u)} SPANNING_TREE_DFS(v) end; end; begin (*khôûi taïo *) for u V do chuaxet:=true; T:=; (*T laø taäp caïnh cuûa caây khung*) SPANNING_TREE_DFS(root) (*root laø ñænh naøo ñoù cuûa ñoà thò*) end. 98
3.5.2.2. Phép duyệt cây theo bề rộng (BFS) : Bước 1 : Chọn một đỉnh bất kỳ của G làm gốc của T Bước 2 : Đặt mọi cạnh nối gốc với một đỉnh ngoài T vào T . lần lượt xét từng đỉnh con của gốc , xem đỉnh này là gốc mới . . lặplại thử tục này cho đến khi mọi đỉnh của G đều nằm trong T . Thí dụ: Cho đồ thị liên thông G như sau : 1 2 3 4 5 6 7 8 Lấy đỉnh 1 làm gốc . Ta có cây bao trùm tạo theo bề sâu là : 1 1 2 3 2 3 5 4 5 7 4 6 8 6 7 8 Ta có cây bao trùm tạo theo chiều rộng . 99
1 2 3 1 2 4 5 3 4 5 7 8 6 7 8 6 3.5.3.Thuaät toaùn Kruskal ñeå tìm caây bao truøm toái thieåu Xeùt ñoà thò G’=(V,T) töùc laø G’ chöùa taát caû caùc ñænh nhö ñoà thò G, nhöng taäp caùc caïnh cuûa G’ T  E. Ban ñaàu T= , thì G’= (V, ) coù n thaønh phaàn lieân thoâng, moãi thaønh phaàn lieân thoâng chæ chöùa moät ñænh. Trong quaù trình xaây döïng T thì G’= (V,T) goàm moät soá thaønh phaàn lieân thoâng. Vieäc choïn (u,v) trong moãi böôùc ñeå theâm vaøo T ñöôïc thöïc hieän nhö sau: Ta xeùt caùc caïnh cuûa ñoà thò G theo thöù töï ñoä daøi taêng daàn. Vôùi moãi caïnh (u,v) E, neáu u vaø v naèm trong hai thaønh phaàn lieân thoâng khaùc nhau cuûa G’ thì ta theâm caïnh (u,v) vaøo T, vaø khi ñoù hai thaønh phaàn lieân thoâng naøy ñöôïc hôïp nhaát thaønh moät thaønh phaàn lieân thoâng cuûa G. coøn neáu u vaø v thuoäc cuøng moät thaønh phaàn lieân thoâng thì ta loaïi boû caïnh (u,v) ñoù ( vì trong tröôøng hôïp naøy neáu ta theâm (u,v) vaøo T thì moät chu trình seõ ñöôïc taïo ra). Quaù trình treân ñöôïc laëp laïi cho ñeán khi naøo G’= (V,T) chæ coù moät thaønh phaàn lieân thoâng vaø khi ñoù T laø caây bao truøm. Caàn löu yù raèng vì T coù n ñænh neân T chöùa ñuùng n-1 caïnh, do ñoù quaù trình treân seõ ñöôïc laëp laïi cho ñeán khi T chöùa ñuùng n-1 caïnh. Cụ thể ta có các bước sau : Bước 1: T= { V,} Bước 2: Nếu T liên thông thì dừng , nếu không qua bước 3 Bước 3: Chọn một cạnh có trọng số nhỏ nhất không trong T sao cho khi thêm cạnh này vào thì T không tạo thành chu trình . Đặt cạnh này vào T . Trở về bước 2 . Procedure Kruskal; Begin 100
T:= While |T| <|n-1| and (E ) do Begin Choïn e laø caïnh coù ñoä daøi nhoû nhaát trong E E:=E\{e} If (T  {e} khoâng chöùa chu trình) then T:=T  {e}; End; If |T| <|n-1| then Ñoà thò khoâng lieân thoâng End; Ví duï 3.5.3. Tìm caây bao truøm toái thieåu cuûa ñoà thò sau A 3 B 2 C 3 6 2 4 D 4 E 8 8 2 3 10 F 3 G 4 H Saép xeáp caùc caïnh theo ñoä daøi taêng daàn: BC,BE,GD,AD,AB,EG,EC,GH,DE,GF,BD,DF,CH,EH Thöù töï caùc caïnh taïo thaønh caây bao truøm laø: BC,BE,GD,AD,AB,GH,GF, 3.5.4.Thuaät toaùn prim ñeå tìm caây bao truøm toái thieåu: Thuaät toaùn kruskal laøm vieäc keùm hieäu quaû ñoái vôùi nhöõng ñoà thò daøy(ñoà thò vôùi soá caïnh m (n-1)/2 caïnh). Trong tröôøng hôïp ñoù thuaät toaùn prim toû ra hieäu quaû hôn. Thuaät toaùn prim coøn ñöôïc goïi laø phöông phaùp laân caän gaàn nhaát. Trong thuaät toaùn prim, ta goïi U laø taäp ñænh keà caùc caïnh trong T. ban ñaàu U chöùa moät ñænh tuøy yù cuûa G, coøn taäp caùc caïnh T roång. Ôû moãi böôùc, ta seõ choïn caïnh (u,v) 101
ngaén nhaát sao cho u U, v V-U, roài theâm v vaøo U vaø theâm (u,v) vaøo T. ñieàu naøy ñaûm baûo raèng sau moãi böôùc T luoân luoân laø moät caây. Chuùng ta tieáp tuïc phaùt trieån caây T cho tôùi khi U = V, luùc ñoù T trôû thaønh caây bao truøm cuûa ñoà thò G. chuùng ta bieåu dieãn thuaät toaùn Prim bôûi thuû tuïc sau: Cụ thể ta có các bước sau : Bước 1: chọn tùy ý một đỉnh của G đặt vào T Bước 2: Nếu mọi đỉnh của G đều nằm trong T thì dừng , nếu không qua bước 3 Bước 3: Tìm một cạnh có trọng số nhỏ nhất nối một đỉnh trong T với một đỉnh ngoài T . Thêm cạnh này vào T . Trở về bước 2 . Procedure Prim Var U: taäp caùc ñænh; U,v: ñænh Begin U:={moät ñænh tuøy yù} T:= ; Repeat Choïn caïnh (u,v) ngaén nhaát vôùi u U, v V-U U:=U {v} T:=T  {(u,v)} Until U=V; End; Đồ thị vô hướng liên thông không có chu trình gọi là cây. Khái niệm cây lần đầu tiên được Cayley đưa ra vào năm 1857, khi ông sử dụng chúng để đếm một dạng cấu trúc phân tử của các hợp chất hoá học trong hoá học hữu cơ. Cây còn được sử dụng rộng rãi trong rất nhiều lĩnh vực khác nhau, đặc biệt trong tin học, cây được sử dụng để xây dựng các thuật toán tổ chức các thư mục, các thuật toán cất giữ, truyền dữ liệu và tìm kiếm 102
Bài tập lý thuyết 5-1.Giả sử đồ thị G liên thông, có 13 đỉnh và 20 cạnh. Hỏi cây khung của G có bao nhiêu đỉnh ? có bao nhiêu cạnh ? 5-2.Tìm cây khung của đồ thị (hình 1,2) sau theo phương pháp DFS, BFS (chọn đỉnh 1 làm gốc) 1 2 3 6 7 8 4 5 3 4 5 2 6 7 8 1 Hình 1 Hình 2 5-3.Tìm cây khung bé nhất của các đồ thị sau (hình 3,4) theo phương pháp KrusKal, Prim 3 2 4 2 20 11 33 8 3 18 5 1 18 9 6 16 9 17 14 13 1 4 4 4 12 3 5 5 Hình 3 Hình 4 103
5-4.Tìm cây khung bé nhất của các đồ thị sau (hình 5,6) theo phương pháp KrusKal, Prim 2 8 3 7 4 4 8 5 0 10 4 9 5 3 2 3 18 7 16 4 1 11 9 5 12 30 6 2 8 10 6 14 4 26 1 2 6 8 7 1 Hình 5 Hình 6 5-5.Tìm cây khung bé nhất của các đồ thị sau (hình 7) theo các phương pháp KrusKal,Prim A 3 B 2 C 3 6 6 2 2 4 4 4 8 D 4 E E 8 2 10 8 2 3 3 10 F 3 G 4 H H 5 4 Hình 7 104
Bài tập thực hành 5-6. Mạng an toàn Cho một mạng N (N <= 20) máy tính được đánh số từ 1 đến N. Sơ đồ mạng được cho bởi hệ gồm M kênh (đoạn) nối trực tiếp giữa một số cặp máy trong mạng, m kênh tương ứng với m cặp. Cho biết chi phí truyền 1 đơn vị thông tin theo mỗi kênh của mạng. Người ta cần chuyển một bức thông điệp từ máy s đến máy t. Để đảm bảo an toàn, người ta chuyển bức thông điện này theo hai đường truyền tin khác nhau (tức không có kênh nào) của mạng được sử dụng trong cả hai đường truyền tin; cho phép hai đường truyền tin cùng đi qua một số máy tính). Chi phí của một đường truyền được hiểu là tổng chi phí trên các kênh của nó. Đơn giá đường truyền từ máy s sang máy t được tính như sau: Với hai máy s và t, cùng bức thông điệp có độ dài là 1 đơn vị thông tin, đơn giá truyền cho cặp (s, t) được tính bằng tổng chi phí chuyển thông điệp an toàn (bằng tổng chi phí của hai đường truyền tin) là nhỏ nhất. Người ta mong muốn mạng máy tính (mạng truyền tin nói trên thỏa mãn tính chất an toàn theo nghĩa là từ một máy bất kỳ luôn truyền được (một cách an toàn) thông điệp tới một máy bất kỳ khác. Khi một mạng an toàn, người ta tính được đơn giá của mạng là tổng đơn giá mọi đường truyền từ một máy bất kỳ tới một máy bất kỳ khác. Ma trận đơn giá của mạng là mảng hai chiều A có N dòng và N cột, mà giá trị phần tử A[i, j] chính là đơn giá từ máy i sang máy j. Câu 1: Cho trước một mạng, hãy kiểm ra tính an toàn của mạng đó. Câu 2: Khi mạng không an toàn được phép bổ sung một số kênh truyền để nó trở thành an toàn. Đơn giá mỗi kênh truyền bổ sung theo được coi bằng hai lần giá trị cực đại đơn giá các kênh đã có. Mọi kênh bổ sung được coi có đơn giá như nhau. Hãy tìm cách bổ sung các kênh mới mà đơn giá mạng là nhỏ nhất. Câu 3: Khi mạng an toàn hoặc sau khi bổ sung kênh để mạng an toàn, hãy in ra đơn giá mạng và ma trận đơn giá. Dữ liệu vào: cho trong file INP.B2 với cấu trúc như sau: Dòng đầu tiên ghi 2 số n, m cách nhau bởi dấu cách. Mỗi dòng thứ i trong số m dòng tiếp theo ghi thông tin về kênh nối thứ i của mạng gồm 3 số d[i], c[i], g[i] trong đó d[i], c[i] là chỉ số của hai máy tương ứng với kênh này và g[i] (nguyên dương) là chi phí để truyền một đơn vị thông tin từ máy d[i] đến máy c[i] theo kênh này. Các giá trị g[i] cho trước không vượt quá 40 (và như vậy đơn giá các kênh bổ sung không vượt quá 80). Kết quả: ghi ra file OUT.B2 theo qui cách sau: 105
Dòng đầu tiên ghi 1 số nguyên p thể hiện mạng có an toàn hay không và p có ý nghĩa là số lượng kênh cần bổ sung. p=0 có nghĩa mạng an toàn; p>0 có nghĩa mạng không an toàn và cần bổ sung p kênh nữa để mạng an toàn với chi phí bổ sung ít nhất. p dòng tiếp theo ghi p kênh bổ sung. Cách ghi như trong file dữ liệu vào. Dòng tiếp theo ghi đơn giá của mạng an toàn. N dòng tiếp theo ghi ma trận đơn giá của mạng an toàn: mỗi hàng của ma trận ghi trên một dòng. 5-7.Xây dựng đường ống nước Có 1 trạm cấp nước và N điểm dân cư. Hãy xây dựng chương trình thiết kế tuyến đường ống nước cung cấp đến mọi nhà sao cho tổng chiều dài đường ống phải dùng là ít nhất. Giả sử rằng các đường ống chỉ được nối giữa 2 điểm dân cư hoặc giữa trạm cấp nước với điểm dân cư. 106
Cài đặt một số thuật toán căn bản quan trọng Tìm cây khung dựa vào DFS 1. #include 2. #include 3. #include 4. int daxet[100]; 5. int a[100][100]; 6. int dau[100],cuoi[100]; 7. int socanh=0; 8. int n; 9. void dfs(int v) 10. { 11. daxet[v]=1; 12. for (int u=1;u<=n;u++) 13. if (a[v][u]!=0 && !daxet[u]) 14. { 15. dau[++socanh]=v; 16. cuoi[socanh]=u; 17. dfs(u); 18. } 19. } 20. void readfile() 21. { 22. FILE *f; 23. clrscr(); 24. f=fopen("d:\\dothi\\tree.inp","rt");// hinh2.inp 25. fscanf(f,"%d",&n); 26. for (int v=1;v<=n;v++) 27. for (int u=1;u<=n;u++) 28. fscanf(f,"%d",&a[u][v]); 29. fclose(f); 30. } 31. void find() 32. { 107
33. for (int v=1;v<=n;v++) 34. daxet[v]=0; 35. for (v=1;v<=n;v++) 36. if (!daxet[v]) 37. dfs(v); 38. } 39. void treedfs() 40. { cout<<"cay khung cua do thi:"<<endl; 41. for (int i=1; i<=socanh;i++) 42. cout<<"("<<dau[i]<<","<<cuoi[i]<<")"<<endl; 43. } 44. void main() 45. { 46. readfile(); 47. find(); 48. treedfs(); 49. } Tree.inp 8 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 1 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 1 0 108
Tìm cây khung dựa vào BFS 1. #include 2. #include 3. #include 4. int daxet[100]; 5. int a[100][100]; 6. int Queue[100]; 7. int dau[100],cuoi[100]; 8. int socanh=0; 9. int n; 10. void BFS(int u) 11. { 12. int w,v; 13. int dauQ,cuoiQ; 14. dauQ=1;cuoiQ=1; 15. Queue[dauQ]=u; 16. daxet[u]=1; 17. while (dauQ<=cuoiQ) 18. { 19. v=Queue[dauQ++]; 20. for (w=1;w<=n;w++) 21. if (a[v][w]==1 && !daxet[w]) 22. { 23. Queue[++cuoiQ]=w; 24. daxet[w]=1; 25. dau[++socanh]=v; 26. cuoi[socanh]=w; 27. } 28. } 29. } 30. void find() 31. { 32. for (int v=1;v<=n;v++) 33. daxet[v]=0; 109
34. for (v=1;v<=n;v++) 35. if (!daxet[v]) 36. BFS(v); 37. } 38. void readfile() 39. { 40. FILE *f; 41. clrscr(); 42. f=fopen("d:\\dothi\\tree.inp","rt"); 43. fscanf(f,"%d",&n); 44. for (int v=1;v<=n;v++) 45. for (int u=1;u<=n;u++) 46. fscanf(f,"%d",&a[u][v]); 47. fclose(f); 48. } 49. void treebfs() 50. { 51. { cout<<"cay khung cua do thi:"<<endl; 52. for (int i=1; i<=socanh;i++) 53. cout<<"("<<dau[i]<<","<<cuoi[i]<<")"<<endl; 54. } 55. } 56. void main() 57. { 58. readfile(); 59. find(); 60. treebfs(); 61. } Tree.inp 8 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 110
1 1 0 0 1 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 1 0 111
THUẬT TOÁN KRUSKAL Dữ liệu vào: Được lưu trên file kruskal.inp có cấu trúc như sau: Dòng đầu ghi 2 số nguyên dương n,m lần lượt là số đỉnh và số cạnh của đồ thị. Trong m dòng tiếp theo mỗi dòng ghi 3 số lần lượt là đỉnh đầu, đỉnh cuối và trọng số của cạnh tương ứng. Dữ liệu ra: Xuất lên màn hình các thông tin: Các cạnh tạo thành cây khung bé nhất và tổng độ dài của cây khung bé nhất này. Ví dụ 6 9 2 3 18 2 4 20 1 2 33 3 5 4 4 6 8 4 5 9 5 6 14 3 4 16 1 3 17 Phần khai báo các biến Khai báo kiểu dữ liệu có tên là canh để lưu trữ thông tin các cạnh của đồ thị, mỗi cạnh của đồ thị được biểu diễn bởi đỉnh đầu (dau), đỉnh cuối (cuoi) và trọng số (w). n là số đỉnh của đồ thị và m là số cạnh của đồ thị. c là một mảng 1 chiều kiểu canh. connect là mảng 2 chiều để cho biết hai đỉnh nào đó trong cây khung tìm được có liên thông nhau hay không ? connect[i][j] =1 nếu i và j là liên thông và ngược lại .const max=100; // hoac viet #define max 100 struct canh { int dau,cuoi; int w; }; int n,m,connect[max][max]; canh c[max]; Chúng ta cần thực hiện một số hàm sau: 112
1.Hàm đọc file 2.Hàm sắp xếp các cạnh theo chiều tăng dần 3.Hàm cập nhật lại các đỉnh liên thông của cây khung tìm được Tại mỗi thời điểm ta xét cạnh (u,v) trong dãy các cạnh đã được sắp, nếu hai đỉnh u,v là không liên thông - nghĩa là connect[u][v]=0 thi cạnh (u,v) này sẽ được đưa vào cây khung kết quả và ta cần cập nhật lại sự liên thông của các đỉnh đã có trong cây khung đang tìm thấy đến thời điểm đó bắng cách cho connect[i][j]=1 và connect[j][i]=1 và chú ý là khi đưa một cạnh (u,v) mới vào cây khung thì ta phải cập nhật để tất cả các đỉnh đã có trong cây khung cùng với hai đinh u,v là liên thông. 4.Hàm KrusKal Nếu tìm thấy một cạnh (trong dãy cạnh được sắp) có 2 đỉnh không liên thông thì ta làm một số bước như sau: Tăng số cạnh của cây khung lên 1 Cập nhật lại sự liên thông của các đỉnh trong cây khung đang tìm được Thêm trọng số cạnh đang xét vào độ dài của cây khung. Toàn văn của chương trình này như sau: 1. #include 2. #include 3. #include 4. const max=100; // hoac viet #define max 100 5. struct canh 6. { int dau,cuoi; 7. int w; 8. }; 9. int n,m,connect[max][max]; 10. canh c[max]; 11. void readfile() 12. { 13. FILE *f; 14. f=fopen("d:\\dothi\\kruskal.inp","rt"); 15. fscanf(f,"%d%d",&n,&m); 16. for (int i=1;i<=m;i++) 17. fscanf(f,"%d%d%d",&c[i].dau,&c[i].cuoi,&c[i].w); 113
18. fclose(f); 19. for (i=1;i c[j].w) 30. { temp=c[i]; 31. c[i]=c[j]; 32. c[j]=temp; 33. } 34. for (i=1;i<=m;i++) 35. cout<<"Canh thu "<<i<<" noi dinh "<<c[i].dau<<" voi dinh "<<c[i].cuoi<<" co trong so = " <<c[i].w<<endl; 36. } 37. void updateconnect(int i, int j) 38. { 39. connect[i][j] = 1; 40. connect[j][i] = 1; 41. for (int k=1;k<=n;k++) 42. for (int l=1;l<=n;l++) 43. if(connect[k][i]==1 && connect[j][l] ==1 ) 44. { 45. connect[k][l]=1; 46. connect[l][k]=1; 47. } 48. } 49. void kruskal() 50. { 114
51. int tong=0,i=1,socanhchon=0,dinhdau,dinhcuoi; 52. while (socanhchon < n-1) 53. {dinhdau=c[i].dau; 54. dinhcuoi=c[i].cuoi; 55. if( connect[dinhdau][dinhcuoi]==0) 56. { 57. socanhchon++; 58. updateconnect(dinhdau,dinhcuoi); 59. cout<<dinhdau<<","<<dinhcuoi<<","<<c[i].w<<endl; 60. tong=tong+c[i].w; 61. } 62. i++; 63. } 64. cout<<tong; 65. } 66. void main() 67. { 68. readfile(); 69. sort(); 70. kruskal(); 71. } 115
Toàn văn của chương trình cho thuật toán Prim này như sau: 1. #include 2. #include 3. #include 4. const max=100; // hoac viet #define max 100 5. const MAXINT=32767; 6. int n,c[max][max]; 7. void readfile() 8. { 9. FILE *f; 10. f=fopen("d:\\dothi\\prim1.inp","rt"); 11. fscanf(f,"%d",&n); 12. for (int i=1;i<=n;i++) 13. for (int j=1;j<=n;j++) 14. fscanf(f,"%d",&c[i][j]); 15. fclose(f); 16. } 17. void prim() 18. { 19. int vh[max],daxet[max]; 20. int tong=0,dinhdau, dinhcuoi,sodinh=1; 21. vh[sodinh]=1; 22. for (int i=1;i<=n;i++) daxet[i]=0; 23. daxet[sodinh]=1; 24. while (sodinh<n) 25. { 26. int min=MAXINT; 27. for (int i=1;i<=sodinh;i++) 28. for (int j=1;j<=n;j++) 29. if (vh[i]!=j && c[vh[i]][j]!=0 && !daxet[j] && c[vh[i]][j]<min) 30. { 31. min=c[vh[i]][j]; 32. dinhdau=vh[i]; 33. dinhcuoi=j; 116
34. } 35. daxet[dinhcuoi]=1; 36. vh[++sodinh]=dinhcuoi; 37. tong=tong+c[dinhdau][dinhcuoi]; 38. cout<<dinhdau<<"," <<dinhcuoi<<endl; 39. } 40. cout<<"Tong do dai cua cay khung nho nhat la : "<< tong; 41. } 42. void main() 43. { 44. clrscr(); 45. readfile(); 46. prim(); 47. } Prim1.inp 6 0 33 17 0 0 0 33 0 18 20 0 0 17 18 0 16 4 0 0 20 16 0 9 8 0 0 4 9 0 14 0 0 0 8 14 0 117
CHƯƠNG 6 BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT Trong các ứng dụng thực tế, và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 chương này chúng ta sẽ xét một số thuật toán như vậy. 1. CÁC KHÁI NIỆM MỞ ĐẦU Trong chương này chúng ta chỉ xét đồ thị có hướng G =(V,E), |V|=n, |E|=m với các cung được gán trọng số, nghĩa là, mỗi cung (u,v) E của nó được đặt tương ứng với một số thực a(u,v) gọi là trọng số của nó. Chúng ta sẽ đặt a(u,v) = , nếu (u,v) E. Nếu dãy v0, v1, . . ., vp là một đường đi trên G, thì độ dài của nó được định nghĩa là tổng sau p a(vi-1, vi). i=1 tức là, độ dài của đường đi chính là tổng của các trọng số trên các cung của nó. (Chú ý rằng nếu chúng ta gán trọng số cho tất cả cung đều bằng 1, thì ta thu được định nghĩa độ dài của đường đi như là số cung của đường đi giống như trong các chương trước đã xét). 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 không có đỉnh lặp lại sẽ gọi là đường đi cơ bản). 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 118
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. Trong những trường hợp như vậy, có thể đặt vấn đề tìm đường đi cơ bản ngắn nhất, tuy nhiên bài toán đặt ra sẽ trở nên phức tạp hơn rất nhiều, bởi vì nó chứa bài toán xét sự tồn tại đường đi Hamilton trong đồ thị như là một trường hợp riêng. Trước hết cần chú ý rằng nếu biết khoảng cách từ s đến t, thì đường đi ngắn nhất từ s đến t, trong trường hợp trọng số không âm, có thể tìm được một cách dễ dàng. Để tìm đường đi, chỉ cần để ý là đối với cặp đỉnh s, t V tuỳ ý (s s) { u=đỉnh thoả mãn d[v]=d[u]+a[u,v]; stack u; v=u; } } 119
Chú ý rằng độ phức tạp tính toán của thuật toán là O(n 2), do để tìm đỉnh u ta phải xét qua tất cả các đỉnh của đồ thị. Tất nhiên, ta cũng có thể sử dụng kỹ thuật ghi nhận đường đi đã trình bày trong chương 3: dùng biến mảng Truoc[v], v V, để ghi nhớ đỉnh đi trước v trong đường đi tìm kiếm. Cũng cần lưu ý thêm là trong trường hợp trọng số trên các cạnh là không âm, bài toán tìm đường đi ngắn nhất trên đồ thị vô hướng có thể dẫn về bài toán trên đồ thị có hướng, bằng cách thay đổi mỗi cạnh của nó bởi nó bởi hai cung có hướng ngược chiều nhau với cùng trọng số là trọng số của các cạnh tương ứng. Tuy nhiên, trong trường hợp có trọng số âm, việc thay như vậy có thể dẫn đến chu trình âm. 2.ĐƯỜNG ĐI NGẮN NHẤT XUẤT PHÁT TỪ MỘT ĐỈNH 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ả tổng quan như sau: từ ma trận trọng số a[u][v], u,v 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[v] (1) cận trên d[v] sẽ được làm tốt lên: d[v] + a[u][v]. Quá trình đó sẽ kết thúc khi nào chúng ta không làm tốt thêm được bất kỳ cận trên nào. Khi đó, rõ ràng giá trị của mỗi d[v] sẽ cho khoảng cách từ đỉnh s đến đỉnh v. Khi thể hiện kỹ thuật tính toán này trên máy tính, cận trên d[v] sẽ được gọi là nhãn của đỉnh v, còn việc tính lại các cận này sẽ được gọi là thủ tục gán. Nhận thấy rằng để tính khoảng cách từ s đến t, ở đây, ta phải tính khoảng cách từ s đến tất cả các đỉnh còn lại của đồ thị. Hiện nay vẫn chưa biết thuật toán nào cho phép tìm đường đi ngắn nhất giữa hai đỉnh làm việc thực sự hiệu quả hơn những thuật toán tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại. Sơ đồ tính toán mà ta vừa mô tả còn chưa xác định, bởi vì còn phải chỉ ra thứ tự các đỉnh u và v để kiểm tra điều kiện (1). Thứ tự chọn này có ảnh hưởng rất lớn đến hiệu quả của thuật toán. Bây giờ ta sẽ mô tả thuât toán Ford-Bellman tìm đường đi ngắn nhất từ đỉnh s đến tất cả các đỉnh còn lại của đồ thị. Thuật toán làm việc trong trường hợp trọng số của các cung là tuỳ ý, nhưng giả thiết rằng trong đồ thị không có chu trình âm. void Ford_Bellman() (* Đầu vào: Đồ thị có hướng G = (V,E) với n đỉnh, s V là đỉnh xuất phát, a[u][v], u, v V, ma trận trọng số; 120
Giả thiết: Đồ thị không có chu trình âm. Đầu ra: Khoảng cách từ đỉnh s đến tất cả các đỉnh còn lại d[v], v V. Trước[v], v V, ghi nhận đỉnh đi trước v trong đường đi ngắn nhất từ s đến v. *) (* Khởi tạo *) for v V { d[v]=a[s][v]; Truoc[v]=s; }; d[s]=0; for k=1 to n-2 for v V\ s for u V if (d[v] > d[u] +a[u][v] ) { d[v]=d[u]+a[u][v]; Truoc[v]=u; } } 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(n 3). 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 d[u] + a[u][v] ) { 121
d[v]=d[u]+a[u][v]; Truoc[v]=u; } Trong trường hợp này ta thu được thuật toán với độ phức tạp O(n,m). Thí dụ 1. Xét đồ thị trong hình 1. Các kết quả tính toán theo thuật toán được mô tả trong bảng dưới đây (3) 1  3 3 8 A= 1 -5  4 Hình 1. Minh họa thuật toán Ford_Bellman 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 -1,3 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ả hơn thuật toán 122
Ford_Bellman. Đó là khi trọng số của tất cả các cung là các số không âm hoặc là khi đồ thị không có chu trình. 3. TRƯỜNG HỢP MA TRẬN TRỌNG SỐ KHÔNG ÂM - THUẬT TOÁN DIJKSTRA Trong trường hợp trọng số trên các cung là không âm thuật toán do Dijkstra đề nghị làm việc hữu hiệu hơn rất nhiều so với thuật toán trình bày trong mục trước. Thuật toán được xây dựng dựa trên cơ sở gán cho các đỉnh các nhãn tạm thời. Nhãn của mỗi đỉnh cho biết cận của độ dài đường đi ngắn nhất từ s đến nó. Các nhãn này sẽ được biến đổi theo một thủ tục lặp, mà ở mỗi bước lặp có một nhãn tạm thời trở thành nhãn cố định. Nếu nhãn của một đỉnh nào đó trở thành một nhãn cố định thì nó sẽ cho ta không phải là cận trên mà là độ dài của đường đi ngắn nhất từ đỉnh s đến nó. Thuật toán được mô tả cụ thể như sau. 4.1.3.1.Thuaät giaûi Dijkstra (Tröôøng hôïp vôùi ma traän troïng soá khoâng aâm ) Thuaät toaùn ñöôïc döïa treân cô sôû xaây döïng moät caây L vaø caùc haøm : V [0; ] vaø Haøm : V\{v0} V . Procedure Dijkstra ; (*ñaàu vaøo: ñoà thò coù höôùng G=(V,E) vôùi n ñænh . s V laø ñænh xuaát phaùt,a[u,v] V laø ma traän troïng soá giaû söû a[u,v] 0, u,v V ñaàu ra: Khoaûng caùch töø ñænh s ñeán caùc ñænh coøn la d[v], v V. begin Böôc1: (*khôûi taïo*) Ñaët L={v0} , (v0)=0. Vôùi v V\{v0}. (v)=c(v0,v) vaø (v)=v0 Böôùc 2: Neáu moïi ñænh cuûa G ñeàu thuoäc L thì döøng , neáu khoâng qua böôùc 3 Böôùc 3: Choïn v L sao cho (v) nhoû nhaát Ñaët v*=v . Ñöa theâm ñænh v* vaø caïnh (v*)v* vaøo L Böôùc 4: Vôùi moïi w V\L , neáu (w)> (v*) +c(v*,w) thì ñaët (w)= (v*)+c(v*,w) vaø (w)=v* . Trôû veà böôøc 2. 123
Ví duï : Xeùt ñoà thò sau : 2 B C 2 4 1 2 3 4 A D E H 1 3 7 6 5 F G Duøng Thuaät toaùn Dijkstra ñeå tìm ñöôøng ñi ngaén nhaát töø ñænh A ñeán caùc ñænh coøn laïi . B C ÔÛ böôùc 1 , ta laäp baûng sau : A B C D E F G H 2 L L  0 2 1 A D E H A A A A A A A 1 G F Choïn ñænh F ñaët vaø L vaø ta coù baûng sau : B C A B C D E F G H 2 L L L  0 2 4 1 6 A D E H A A F A A F A 4 1 6 Choïn ñænh B vaøo L vaø ta coù baûng sau F G 124
4 B C A B C D E F G H 2 6 L L L L  0 2 4 4 6 1 6 A D E H A B F B A F A 4 1 6 G F 4 B C Choïn Ñænh C vaøo L ta coù baûng sau : 5 2 6 D E H A B C D E F G H A L L L L L 4  0 2 4 4 6 1 6 5 1 A B F B A F A 6 F G Choïn Ñænh D vaøo L vaø ta coù baûg sau : 4 B C 5 A B C D E F G H 2 6 L L L L L L  0 2 4 4 6 1 6 5 A D E H A B F B A F C 4 1 Choïn Ñænh H vaøo L vaø ta coù baûng sau : 6 G F 4 B C 5 A B C D E F G H 2 6 L L L L L L L H  0 2 4 4 6 1 6 5 A D E A B F B A F C 4 125 1 6 F G
Choïn Ñænh E vaøo L vaø ta coù baûng sau : 4 B C 5 A B C D E F G H 2 6 L L L L L L L L  0 2 4 4 6 1 6 5 A D E H A B F B A F C 4 1 Cuoái cuøng ta choïn Ñænh G vaøo L vaø ta coù baûng sau : 6 F G 4 B C 2 5 A B C D E F G H 6 L L L L L L L L L  0 2 4 4 6 1 6 5 A D E H A B F B A F C 4 1 6 F G Thaäut toaùn keát thuùc khi caùc ñænh cuûa ñeàu coù trong L vaø ta coù : Ñöôøng ñi ngaén nhaát töø A ñeán Ñænh H laø : 5 Ñöôøng ñi ngaén nhaát töø A ñeán Ñænh C laø : 4 Ñöôøng ñi ngaén nhaát töø A ñeán Ñænh G laø : 6 Ñöôøng ñi ngaén nhaát töø A ñeán Ñænh E laø : 6 Ñöôøng ñi ngaén nhaát töø A ñeán Ñænh D laø : 4 Ñöôøng ñi ngaén nhaát töø A ñeán Ñænh B laø : 2 Ñöôøng ñi ngaén nhaát töø A ñeán Ñænh F laø : 1 Ta coù chöông trình moâ taû thuaät toaùn Dijkstra theo NN c nhö sau: #include #include #include #include #include #define MAX 50; 126
#define TRUE 1 #define false 0 Int n,s,t; Char chon; Int truoc[MAX],d[MAX],CP[MAX][MAX]; Int final[MAX] ; // Void Init() { FILE *f;int I,j; f=fopen(“Diskstra.INP”,”rt”); fscanf(f,%d”,&n); printf( “ \n so dinh cua DOTHI la %d“,n); printf(“\n Ma tran khoang cach:”); for(i=1; i<=n;i++) { printf(“\n”); for(j=1;j<=n;j++) { fscanf(f,”%d”, &CP[I,j]); printf(”%3d”,CP[i][j]); if(CP[i]j]==0) CP[i][j]=32000; } } } f close(f); } // Void Result() { Int I,j ; Printf(“%d <=”, t); I=truoc[t]; While(I !=s) 127
{ Printf(“%d d[v])) { U=v; Minp=d[v]; } } 128
Final[u]=TRUE; // u la dinh co nhan tam thoi nho nhat If(!final[t]) { For(v=1;v<=n;v++){ If !(final[v]) &&(d[u]+CP[u][v]<d[v])) { D[v]=+CP[u][v]; Truoc[v]=u; } } } } } } // Void main() { Clrscr(); Init(); Disktra(); Result(); Getch(); } Định lý 1. Thuật toán Dijkstra tìm được đường đi ngắn nhất trên đồ thị sau thời gian cỡ O(n2). Chú ý: Nếu chỉ cần tìm đường đi ngắn nhất từ s đến một đỉnh t nào đó thì có thể kết thúc thuật toán khi đỉnh t trở thành có nhãn cố định. 4. ĐƯỜNG ĐI NGẮN NHẤT GIỮA TẤT CẢ CÁC CẶP ĐỈNH Rõ ràng ta có thể giải bài toán tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh của đồ thị bằng cách sử dụng n lần thuật toán mô tả ở mục trước, trong đó ta sẽ chọn s lần lượt là các đỉnh của đồ thị. Rõ ràng, khi đó ta thu được thuật toán với độ phức tạp O(n 4) (nếu sử dụng thuật toán Ford_Bellman) hoặc O(n 3) đối với trường hợp trọng số không âm hoặc đồ thị không có chu trình. Trong trường hợp tổng quát, sử dụng thuật toán Ford_Bellman n lần 129
không phải là cách làm tốt nhất. Ở đây ta sẽ mô tả một thuật toán giải bài toán trên với độ phức tạp tính toán O(n3): thuật toán Floyd. Thuật toán được mô tả trong thủ tục sau đây. void Floyd() (* Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh Đầu vào: Đồ thị cho bởi ma trận trọng số a[i,j], i, j =1, 2,. . ,n. Đầu ra: Ma trận đường đi ngắn nhất giữa các cặp đỉnh d[i][j]=, i,j = 1, 2. . .,n, trong đó d[i,j] cho độ dài đường đi ngắn nhất từ đỉnh i đến đỉnh j. Ma trận ghi nhận đường đi p[i][j], i, j = 1, 2 . , n, trong đó p[i][j] ghi nhận đỉnh đi trước đỉnh j trong đường đi ngắn nhất từ i đến j. *) (* Khởi tạo *) for i=1 to n for j=1 to n { d[i][j]=a[i][j]; p[i][j]=i; } (* Bước lặp *) for k=1 to n for i=1 to n for j=1 to n if (d[i][j]>d[i][k]+d[k][j]) { d[i][j]=d[i][k]+d[k][j]; p[i][j]>p[k][j]; } } Rõ ràng độ phức tạp tính toán của thuật toán là O(n3). Ví dụ: Xét đồ thị G sau: 130