Bài giảng Lý thuyết đồ thị - Trường Đại học Hàng Hải

111 trang Gia Huy 17/05/2022 4190

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Lý thuyết đồ thị - Trường Đại học Hàng Hải", để 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:

bai_giang_ly_thuyet_do_thi_truong_dai_hoc_hang_hai.pdf

Nội dung text: Bài giảng Lý thuyết đồ thị - Trường Đại học Hàng Hải

BỘ GIAO THÔNG VẬN TẢI TRƢỜNG ĐẠI HỌC HÀNG HẢI BỘ MÔN: KHOA HỌC MÁY TÍNH KHOA: CÔNG NGHỆ THÔNG TIN BÀI GIẢNG LÝ THUYẾT ĐỒ THỊ TÊN HỌC PHẦN : LÝ THUYẾT ĐỒ THỊ MÃ HỌC PHẦN : 17205 TRÌNH ĐỘ ĐÀO TẠO : ĐẠI HỌC CHÍNH QUY DÙNG CHO SV NGÀNH : CÔNG NGHỆ THÔNG TIN HẢI PHÒNG - 2009
MỤC LỤC CHƢƠNG 1: CÁC KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ THỊ 1 1.1. Tổng quan về đồ thị 1 1.1.1. Định nghĩa đồ thị 1 1.1.2. Các thuật ngữ căn bản 4 1.1.3. Một số dạng đồ thị 6 1.2. Biểu diễn đồ thị 9 1.2.1. Biểu diễn bằng ma trận kề, ma trận liên thuộc 9 1.2.2. Danh sách cạnh, cung của đồ thị 11 1.2.3. Danh sách kề 12 Bài tập 16 CHƢƠNG 2: CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ 17 2.1. Tìm kiếm theo chiều sâu trên đồ thị 17 2.2. Tìm kiếm theo chiều rộng trên đồ thị 20 2.3. Tìm đƣờng đi và kiểm tra tính liên thông 21 2.4. Tô màu đồ thị 28 2.4.1. Giới thiệu 28 2.4.2. Các khái niệm cơ bản 29 2.4.3. Ví dụ 30 2.4.5. Thuật toán 33 Bài tập 33 CHƢƠNG 3: ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMINTON 34 3.1. Đồ thị Euler 34 3.1.1. Khái niệm về đƣờng đi và chu trình Euler 34 3.1.2. Điều kiện tồn tại đƣờng đi hoặc chu trình Euler 35 3.1.3. Thuật toán tìm đƣờng đi và chu trình Euler 36 3.1.4. Một số vấn đề khác về đƣờng đi và chu trình Euler 37
3.2. Đồ thị Haminton 37 3.2.1. Khái niệm về đƣờng đi và chu trình Haminton 38 3.2.2. Điều kiện tồn tại đƣờng đi hoặc chu trình Haminton 38 3.2.3. Thuật toán tìm đƣờng đi và chu trình Haminton 39 Bài tập 40 4.1. Khái niệm và các tính chất của cây khung 43 4.2. Cây khung của đồ thị 44 4.3. Xây dựng các tập chu trình cơ bản của đồ thị 47 4.4. Cây khung nhỏ nhất của đồ thị 49 4.4.1. Thuật toán Kruskal 50 4.4.2. Thuật toán Prim 56 4.4.3. Ứng dụng của bài toán tìm cây khung nhỏ nhất 59 Bài tập 60 CHƢƠNG 5: BÀI TOÁN ĐƢ NG ĐI NGẮN NHẤT 63 5.1. Các khái niệm mở đầu 63 5.2. Đƣờng đi ngắn nhất xuất phát từ một đỉnh 65 5.3. Thuật toán Dijkstra 68 5.4. Thuật toán Floyd-Washall 71 5.5. Thuật toán Bellman-Ford 75 Bài tập 80 CHƢƠNG 6: BÀI TOÁN LUỒNG C C ĐẠI TRONG MẠNG 83 6.1. Mạng. Luồng trong mạng. Bài toán luồng cực đại 83 6.2. Lát cắt. Đƣờng tăng luồng. Định lý Ford Fulkerson 84 6.4. Một số bài toán luồng tổng quát 91 6.4.1. Mạng với nhiều điểm phát và điểm thu 91 6.4.2. Bài toán với khả năng thông qua của các cung và các đỉnh. 92
Bài tập 95 TÀI LIỆU THAM KHẢO 99
T n ọc p ần: Lý thuyết đồ thị Lo ọc p ần:2 Bộ môn p ụ trác g ảng d y: Khoa học Máy tính K oa p ụ trác : CNTT Mã ọc p ần: 17205 Tổng số TC: 3 TS tiết Lý thuyết Thực hành/Xemina Tự học Bài tập lớn Đồ án môn học 60 45 15 0 0 0 Đ ều k ện t n quyết: Sinh viên phải học xong các học phần sau mới đƣợc đăng ký học phần này: Kỹ thuật lập trình (C), Cấu trúc dữ liệu. Mục t u của ọc p ần: Cung cấp các kiến thức về lý thuyết đồ thị và vận dụng các bài toán trong tin học Nộ dung c ủ yếu Gồm 2 phần: - Phần các kiến thức thức về đồ thị, ứng dụng các bài toán tin học trên đồ thị: các phƣơng pháp biểu diễn đồ thị, các thuật toán tìm kiếm cơ bản trên đồ thị, các chu trình và thuật toán tìm cây khung nhỏ nhất, các thuật toán tìm đƣờng đi ngắn nhất, bài toán luồng cực đại. - Phần thực hành: Sinh viên cài đặt chƣơng trình của các bài tập liên quan đến đồ thị Nộ dung c t ết của ọc p ần: PHÂN PHỐI SỐ TIẾT TÊN CHƢƠNG MỤC TS LT TH/Xemina BT KT C ƣơng 1. Các k á n ệm cơ bản của lý t uyết đồ t ị 5 5 0 0 0 1.1. Tổng quan về đồ thị 3 1.1.1. Định nghĩa đồ thị 1.1.2. Các thuật ngữ căn bản 1.1.3. Một số dạng đồ thị 1.2. Biểu diễn đồ thị 2 1.2.1. Biểu diễn bằng ma trận kề, ma trận liên thuộc 1.2.2. Danh sách cạnh, cung của đồ thị C ƣơng 2. Các t uật toán tìm k ếm tr n đồ t ị 11 7 3 0 1 2.1. Tìm kiếm theo chiều sâu trên đồ thị 2 1 2.2. Tìm kiếm theo chiều rộng trên đồ thị 2 1 2.3. Tìm đƣờng đi và kiểm tra tính liên thông 1 2.4. Tô màu đồ thị 2 1 C ƣơng 3. Đồ t ị Euler và đồ t ị Ham nton 10 6 4 0 0
PHÂN PHỐI SỐ TIẾT TÊN CHƢƠNG MỤC TS LT TH/Xemina BT KT 3.1. Đồ thị Euler 3 2 3.1.1. Khái niệm về đƣờng đi và chu trình Euler 3.1.2. Điều kiện tồn tại đƣờng đi hoặc chu trình Euler 3.1.3. Thuật toán tìm đƣờng đi và chu trình Euler 3.1.4. Một số vấn đề khác về đƣờng đi và chu trình Euler 3.2. Đồ thị Haminton 3 2 3.2.1. Khái niệm về đƣờng đi và chu trình Haminton 3.2.2. Điều kiện tồn tại đƣờng đi hoặc chu trình Haminton 3.2.3. Thuật toán tìm đƣờng đi và chu trình Haminton 3.2.4. Một số vấn đề khác về đƣờng đi và chu trình Haminton C ƣơng 4. Cây k ung của đồ t ị 12 8 3 0 1 4.1. Khái niệm và các tính chất của cây khung 1 4.2. Cây khung của đồ thị 1 4.3. Xây dựng các tập chu trình cơ bản của đồ thị 2 1 4.4. Cây khung nhỏ nhất của đồ thị 3 2 4.4.1. Thuật toán Kruskal 4.4.2. Thuật toán Prim 4.4.3. Ứng dụng của bài toán tìm cây khung nhỏ nhất C ƣơng 5. Bà toán đƣờng đ ngắn n ất 12 8 3 0 1 5.1. Các khái niệm mở đầu 2 5.2. Đƣờng đi ngắn nhất xuất phát từ một đỉnh 1 5.3. Thuật toán Dijkstra 2 1 5.4. Thuật toán Floyd-Washall. 1 1 5.5. Thuật toán Bellman-Ford 2 1 C ƣơng 6. Bà toán luồng cực đ trong m ng 10 8 2 0 0 6.1. Mạng. Luồng trong mạng. Bài toán luồng cực đại 1 6.2. Lát cắt, luồng. Định lý Ford Fulkerson 2 6.3. Thuật toán tìm luồng cực đại 2 1 6.4. Một số bài toán luồng tổng quát 3 1
PHÂN PHỐI SỐ TIẾT TÊN CHƢƠNG MỤC TS LT TH/Xemina BT KT 6.4.1. Mạng với nhiều điểm phát và điểm thu 6.4.2. Bài toán với khả năng thông qua của các cung và các đỉnh 6.4.3. Mạng trong đó khả năng thông qua của mỗi cung bị chặn 2 phía 6.4.4. Một số ứng dụng khác N ệm vụ của s n v n : Tham dự các buổi thuyết trình của giáo viên, tự học, tự làm bài tập do giáo viên giao, tham dự các bài kiểm tra định kỳ và cuối kỳ. Tà l ệu ọc tập : - Nguyễn Thanh Hùng. Nguyễn Đức Nghĩa, Giáo Trình Lý Thuyết Đồ Thị, NXB Đại học Quốc Gia TPHCM, 2007. - Doãn Châu Long. Lý thuyết quy hoạch tuyến tính và lý thuyết đồ thị. NXB Giáo dục. 1982. - Kenneth Rosen. Toán học rời rạc và ứng dụng trong tin học. NXB KHKT Hà nội. 1998. Hìn t ức và t u c uẩn đán g á s n v n: - Hình thức thi cuối kỳ : Thi viết. - Sinh viên phải đảm bảo các điều kiện theo Quy chế của Nhà trƣờng và của Bộ T ang đ ểm: T ang đ ểm c ữ A, B, C, D, F Đ ểm đán g á ọc p ần: Z = 0,3X + 0,7Y. Bài giảng này là tài liệu c ín t ức và t ống n ất của Bộ môn Khoa học Máy tính, Khoa Công nghệ Thông tin và đƣợc dùng để giảng dạy cho sinh viên. Ngày p duyệt: / /20 TRƢỞNG BỘ MÔN: THS. NGUY N H U TUÂN KÝ VÀ GHI R HỌ TÊN
CHƢƠNG 1: CÁC KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ THỊ 1.1. Tổng quan về đồ thị Lý thuyết đồ thị là một lĩnh vực đã có từ lâu và có nhiều ứng dụng hiện đại. Những tƣ tƣởng cơ bản của lý thuyết đồ thị đƣợc đề xuất vào những năm đầu của thế kỷ 18 bởi nhà toán học lỗi lạc ngƣời Thụy Sỹ Lenhard Eurler. Chính ông là ngƣời đã sử dụng đồ thị để giải bài toán nổi tiếng về các cái cầu ở thành phố Konigsberg. Đồ thị đƣợc sử dụng để giải các bài toán trong nhiều lĩnh vực khác nhau. Chẳng hạn, đồ thị có thể sử dụng để xác định các mạch vòng trong vấn đề giải tích mạch điện. Chúng ta có thể phân biệt các hợp chất hóa học hữu cơ khác nhau với cùng công thức phân tử nhƣng khác nhau về cấu trúc phân tử nhờ đồ thị. Chúng ta có thể xác định hai máy tính trong mạng có thể trao đổi thông tin đƣợc với nhau hay không nhờ mô hình đồ thị của mạng máy tính. Đồ thị có trọng số trên các cạnh có thể sử dụng để giải các bài toán nhƣ: Tìm đƣờng đi ngắn nhất giữa hai thành phố trong mạng giao thông. Chúng ta cũng còn sử dụng đồ thị để giải các bài toán về lập lịch, thời khóa biểu, và phân bố tần số cho các trạm phát thanh và truyền hình 1.1.1. Địn ng ĩ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ị. Để có thể hình dung đƣợc tại sao lại cần đến các loại đồ thị khác nhau, chúng ta sẽ nêu ví dụ sử dụng chúng để mô tả một mạng máy tính. Giả sử ta có một mạng gồm các máy tính và các kênh điện thoại (gọi tắt là kênh thoại) nối các máy tính này. Chúng ta có thể biểu diễn các vị trí đặt náy tính bởi các điểm và các kênh thoại nối chúng bởi các đoạn nối, xem hình 1. Hình 1. Sơ đồ mạng máy tính. Nhận thấy rằng trong mạng ở hình 1, giữa hai máy bất kỳ chỉ có nhiều nhất là một kênh thoại nối chúng, kênh thoại naỳ cho phép liên lạc cả hai chiều và không có máy tính nào lại đƣợc nối với chính nó. Sơ đồ mạng máy cho trong hình 1 đƣợc gọi là đơn đồ thị vô hƣớng. Ta đi đến định nghĩa sau 1
Đị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. Trong trƣờng hợp giữa hai máy tính nào đó thƣờng xuyên phải truyền tải nhiều thông tin ngƣời ta phải nối hai máy nàu bởi nhiều kênh thoại. Mạng với đa kênh thoại giữa các máy đƣợc cho trong hình 2. Trong trƣờng hợp giữa hai máy tính nào đó thƣờng xuyên phải truyền tải nhiều thông tin ngƣời ta phải nối hai máy nàu bởi nhiều kênh thoại. Mạng với đa kênh thoại giữa các máy đƣợc cho trong hình 2. Hình 2. Sơ đồ mạng máy tính với đa kênh thoại. Đị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 e1 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. Hình 3. Sơ đồ mạng máy tính với kênh thoại thông báo. Rõ ràng mỗi đơn đồ thị đều là đa đồ thị, nhƣng không phải đa đồ thị nào cũng là đơn đồ thị, vì trong đa đồ thị có thể có hai (hoặc nhiều hơn) cạnh nối một cặp đỉnh nào đó. Trong mạng máy tính có thể có những kênh thoại nối một náy nào đó với chính nó (chẳng hạn vời mục đính thông báo). Mạng nhƣ vậy đƣợc cho trong hình 3. Khi đó đa đồ thị không thể mô tả đƣợc mạng nhƣ vậy, bởi vì có những khuyên (cạnh nối một đỉnh với chính nó). Trong 2
trƣờng hợp nàychúng ta cần sử dụng đến khái niệm giả đồ thị vô hƣớng, đƣợc định nghĩa nhƣ sau: Đị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). Hình 4. Mạng máy tính với kênh thoại một chiều Các kênh thoại trong mạng máy tính có thể chỉ cho phép truyền tin theo một chiều. Chẳng hạn, trong hình 4 máy chủ ở Hà Nội chỉ có thể nhận tin từ các máy ở địa phƣơng, có một số máy chỉ có thể gửi tin đi, còn các kênh thoại cho phép truyền tin theo cả hai chiều đƣợc thay thế bởi hai cạnh có hƣớng ngƣợc chiều nhau. Ta đi đến định nghĩa sau. Đị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. Nếu trong mạng có thể có đa kênh thoại một chiều, ta sẽ phải sử dụng đến khái niệm đa đồ thị có hƣớng: Đị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. 3
1.1.2. Các thuật ngữ căn bản Trong mục này chúng ta sẽ trình bày một số thuật ngữ cơ bản của lý thuyết đồ thị. Trƣớc tiên, ta xét các thuật ngữ mô tả các đỉnh và cạnh của đồ thị vô hƣớng. Đị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ó bao nhiêu cạnh liên thuộc với một đỉnh, ta đƣa vào định nghĩa sau Đị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). Hình 1. Đồ thị vô hƣớng 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ố cung. Chứng minh. Rõ ràng mỗi cạnh e = (u, v) đƣợc tính một lần trong deg(u) và một lần trong deg(v). Từ đó suy ra tổng tất cả các bậc của 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. Chứng minh. Thực vậy, gọi O và U tƣơng ứng là tập đỉnh bậc lẻ và tập đỉnh bậc chẵn của đồ thị. Ta có 2m = Σ deg(v) + Σ deg(v) v U ; v O 4
Do deg(v) là chẵn với v là đỉnh trong U nên tổng thứ nhất ở trên là số chẵn. Từ đó suy ra tổng thứ hai (chính là tổng bậc của các đỉnh bậc lẻ) cũng phải là số chẵn, do tất cả các số hạng của nó là số lẻ, nên tổng này phải gồm một số chẵn các số hạng. Vì vậy, số đỉnh bậc lẻ phải là số chẵn. Ta xét các thuật ngữ tƣơng tự cho đồ thị vô hƣớng. Đị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)) Hình 2. Đồ thị có hƣớng 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 đó + -(v) Rất nhiều tính chất của đồ thị có hƣớng không phụ thuộc vào hƣớng trên các cung của nó. Vì vậy, trong nhiều trƣờng hợp sẽ thuận tiện hơn nếu ta bỏ qua hƣớng trên các cung của đồ thị. Đồ 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. 5
1.1.3. Một số d ng đồ thị Trong mục này ta xét một số đơn đồ thị vô hƣớng dạng đặc biệt xuất hiện trong nhiều vấn đề ứng dụng thực tế. 1.1.3.1. Đồ t ị đầ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 đủ Đồ thị đầy đủ Kn có tất cả n(n-1)/2 cạnh, nó là đơn đồ thị có nhiều cạnh nhất. 1.1.3.2. Đồ t ị 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). Đồ thị vòng C3, C4, C5, C6 cho trong hình 2. Hình 2. Đồ thị vòng C3, C4, C5, C6 1.1.3.3. Đồ t ị bán xe. Đồ thị Wn thu đƣợc từ Cn bằng cách bổ sung vào một đỉnh mới nối với tất cả các đỉnh của Cn (xem hình 3). Hình 3. Đồ thị bánh xe W3, W4, W5, W6 6
1.1.3.4. Đồ t ị lập p ƣơng. n Đồ thị lập phƣơng n đỉnh Qn là đồ thị với các đỉnh biểu diễn 2 xâu nhị phân độ dài n. Hai đỉnh của nó gọi là kề nhau nếu nhƣ hai xâu nhị phân tƣơng ứng chỉ khác nhau 1 bit. Hình 4 cho thấy Qn với n=1,2,3. Hình 4. Đồ thị lập phƣơng Q1, Q2, Q3 1.1.3.5. Đồ t ị ai 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ẻ. Để kiểm tra xem một đồ thị liên thông có phải là hai phía hay không có thể áp dụng thủ tục sau. Cho v là một đỉnh bất kỳ của đồ thị. Đặt X={v}, còn Y là tập các đỉnh kề của v. Khi đó các đỉnh kề của các đỉnh trong Y phải thuộc vào X. Ký hiệu tập các đỉnh nhƣ vậy là T. Vì thế Y #  thì đồ th Tiếp tục xét nhƣ vậy đối với T’ là tập các đỉnh kề của T,. . .  Y, E) với |X|= m, |Y| = n đƣợc gọi là đồ thị hai phía đầy đủ và ký hiệu là K2,3, K3,3, K3,4 đƣợc cho trong hình 5. Khi E Hình 5. Đồ thị hai phía 1.1.3.6. Đồ t ị p ẳng. 7
Đồ 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 6. Đồ 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). Để 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ặng. 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 7. Các miền tƣơng ứng với biểu diễn phẳng của đồ thị 8
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. 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/20=30. Vì vậy, theo công thức Euler, số miền cần tìm là r=30-20+2=12. 1.2. Biểu diễn đồ thị Để 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, đồng thời cũng phân tích một cách ngắn gọn những ƣu điểm cũng nhƣ những nhƣợc điểm của chúng. 1.2.1. Biểu diễn bằng ma trận kề, ma trận liên thuộc 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 1 0 2 1 0 1 0 1 0 3 1 1 0 1 0 0 9
4 0 0 1 0 1 1 5 1 1 0 1 0 1 6 0 0 0 1 1 0 Hình 1. Đồ thị vô hƣớng G và Đồ thị có hƣớng G1 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. ngƣợc lại, mỗi (0,1)-ma trận đối xứng cấp n sẽ tƣơng ứng, chính xác đến cách đánh số đỉnh (còn nói là: chính xác đến đẳng cấu), với một đơn đồ thị vô hƣớng n đỉnh. 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). p p 3) nếu ký hiệu aịj , i,j=1, 2,. . .,n là phần tử của ma trận A =A.A. . .A p thừa số p Khi đó aịj , i,j=1, 2,. . .,n cho ta số đƣờng đi khác nhau từ đỉnh i đến đỉnh j qua p- 1 đỉnh trung gian. 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. 10
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. 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]= 0 nếu (i,j) E đƣợ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 n2 đơn vị bộ nhớ để lƣu trữ ma trận kề của nó. 1.2.2. Danh sách c nh, cung của đồ thị 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 11
1 3 1 3 1 5 3 2 2 3 3 4 2 5 5 4 3 4 5 6 4 5 6 5 4 6 5 6 Danh sách cạnh của G Danh sánh cung của G1 1.2.3. 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ề là cách biểu diễn thích hợp nhất đƣợ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} Khi đó vòng lặp thực hiện với mỗi một phần tử trong danh sách này theo thứ tự các phần tử đƣợc sắp xếp trong nó sẽ đƣợc viết nhƣ sau: for uÎ Ke(v) do. . . Chẳng hạn, trên PASCAL có thể mô tả danh sách này nhƣ sau (Gọi là cấu trúc Forward Star): Const m=1000; { m-so canh} n= 100; { n-so dinh} var Ke:array[1 m] of integer; Tro:array[1 n+1] of integer; 12
Trong đó Tro[i] ghi nhận vị trí bắt đầu của danh sách kề của đỉnh i, i=1, 2,. . .,n, Tro[n+1]=2m+1. Khi đó dòng lệnh qui ƣớc for uÎ Ke(v) do begin . . . . end. Có thể thay thế bởi cấu trúc lệnh cụ thể trên PASCAL nhƣ sau For i:=Tro[v] to Tro[v+1]-1 do Begin U:=Ke[i]; . . . . End; Trong rất nhiều thuật toán làm việc với đồ thị chúng ta thƣờng xuyên phải thực hiện các thao tác: Thêm hoặc bớt một số cạnh. Trong trƣờng hợp này cấu trúc dữ liệu dùng ở trên là không thuận tiện. Khi đó nên chuyển sang sử dụng danh sách kề liên kết (Linked Adjancency List) nhƣ mô tả trong chƣơng trình nhập danh sách kề của đồ thị từ bàn phím và đƣa danh sách đó ra màn hình sau đây: Program AdjList; Const maxV=100; Type link=^node; node=record v:integer; next:link; End; 13
Var j,x,y,m,n,u,v:integer; t:link; Ke:array[1. .Vmax] of link; Begin Write(‘Cho so canh va dinh cua do thi:’); readln(m,n); (*Khoi tao*) for j:=1 to n do Ke[j]:=nil; for j:=1 to m do begin write(‘Cho dinh dau va cuoi cua canh ‘,j,’:’); readln(x,y); new(t); t^.v:=x, t^.next:=Ke[y]; Ke[y]:=t; new(t); t^.v:=y, t^.next:=Ke[x]; Ke[x]:=t; end; writeln(‘Danh sach ke cua cac dinh cua do thi:’); for J:=1 to m do begin writeln(‘Danh sachcac dinh ke cua dinh ‘,j,’:’); t:=Ke[j]; while t^.next<>nil do begin 14
write(t^.v:4); t:=t^.next; end; end; readln; End. Thí dụ 4. Danh sách kề của các đồ thị trong hình 1 đƣợc mô tả trong hình sau: Đỉnh đầu Đỉnh đầu Hình 2. Danh sách kề của đồ thị vô hƣớng G và có hƣớng G1 cho trong hình 1 Để ý rằng trong cách biểu diễn này chúng ta cần phải sử dụng cỡ m+n đơn vị bộ nhớ. 15
Trong các thuật toán mô tả ở các phần tiếp theo hai cấu trúc danh sách kề và ma trận trọng số đƣợc sử dụng thƣờng xuyên. Bài tập Bài 1: Cho đồ thị nhƣ hình vẽ 1 6 5 4 3 8 2 7 Hãy biểu diễn đồ thị trên dƣới dạng ma trận kề, danh sách cạnh, danh sách kề. Bài 2: Viết chƣơng trình bằng ngôn ngữ lập trình C để nhập vào một đồ thị, in đồ thị ra màn hinh theo dạng ma trận kề. Bài 3: Viết chƣơng trình bằng ngôn ngữ lập trình C để nhập vào một đồ thị, in đồ thị ra màn hinh theo dạng danh sách cạnh. Bài 4: Viết chƣơng trình bằng ngôn ngữ lập trình C để nhập vào một đồ thị, in đồ thị ra màn hinh theo dạng danh sách kề. 16
CHƢƠNG 2: CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ Rất nhiều thuận toán trên đồ thị đƣợc xây dựng trên cơ sở duyệt tất cả các đỉnh của đồ thị sao cho mỗi đỉnh của nó đƣợc viếng thăm đúng một lần. Vì vậy, việc xây dựng những thuật toán cho phép duyệt một cách hệ thống tất cả các đỉnh của đồ thị là một vấn đề quan trọng thu hút sự quan tâm nghiên cứu của nhiều tác giả. Những thuật toán nhƣ vậy chúng ta sẽ gọi là thuật toán tìm kiếm trên đồ thị. Trong mục này chúng ta sẽ giới thiệu hai thuật toán tìm kiếm cơ bản trên đồ thị: Thuật toán tìm kiếm theo chiều sâu (Depth Firt Search) và Thuật toán tìm kiếm theo chiều rộng (Breadth First Search) và ứng dụng của chúng vào việc giải một số bài toán trên đồ thị. Trong mục này chúng ta sẽ xét đồ thị vô hƣớng G=(V,E), với đỉnh n và m cạnh. Chúng ta sẽ quan tâm đến việc đánh giá hiệu quả của các thuật toán trên đồ thị, màmột trong những đặc trƣng quan trọng nhất là độ phức tạp tính toán, tức là số phép toán mà thuật toán cần phải thực hiện trong tình huống xấu nhất đƣợc biểu diễn nhƣ hàm của kích thƣớc đầu vào của bài toán. Trong các thuật toán trên đồ thị, đầu vào là đồ thị G=(V,E), vì vậy, kích thƣớc của bài toán là số đỉnh n và số cạnh m của đồ thị. Khi đó độ phức tạp tính toán của thuật toán sẽ đƣợc biểu diễn nhƣ là hàm của hai biến số f(n,m) là số phép toán nhiều nhất cần phải thực hiện theo thuật toán đối với mọi đồ thị n đỉnh và m cạnh. Khi so sánh tốc độ tăng của hai hàm nhận giá trị không âm f(n) và g(n) chúng ta sẽ sử dụng ký hiệu sau: f(n)=O(g(n)) các hằng sô C, N ≥ 0 sao cho f(n) C g(n) với mọi n≤N. Tƣơng tự nhƣ vậy nếu f(n1, n2,. . .,nk), g(n1, n2,. . .,nk) là các hàm nhiều biến ta viết f(n1, n2,. . .,nk) = O(g(n1, n2,. . .,nk)) f(n1, n2,. . .,nk)≤C g(n1, n2,. . .,nk) với mọi n1, n2,. . .,nk≥N. Nếu độ phức tạp tính toán của thuật toán là O(g(n)) thì ta sẽ còn nói là nó đòi hỏi thời gian tính cỡ O(g(n)). 2.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 v0 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=v0, 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ừ 17
đỉ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: Procedure DFS(v); (*tim kiem theo chieu sau bat dau tu dinh v; cac bien Chuaxet, Ke la bien toan cuc*) Begin Tham_dinh(v); Chuaxet[v]:=false; If Chuaxet[u] then DFS(u); End; (*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: Begin (*Initialization*) for v V do Chuaxet[v]:=true; for v V do if Chuaxet[v] then DFS(v); End. Rõ ràng lệnh gọi SFS(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). Thí dụ 1. Xét đồ thị cho trong hình 1 gồm 13 đỉnh, các đỉnh đƣợc đánh số từ 1 đến 13 nhƣ sau: 18
Hình 1 Khi đó các đỉnh của đồ thị đƣợc đánh số lại theo thứ tự chúng đƣợc thăm theo thủ tục tìm kiếm theo chiều sâu mô tả ở trên nhƣ hình 2. Giả thiết rằng các đỉnh trong danh sách kề của đỉnh v (Ke(v)) đƣợc sắp xếp theo thứ tự tăng dần của chỉ số. Hình 2. Chỉ số mới (trong ngoặc) của các đỉnh đƣợc đánh lại theo thứ tự chúng đƣợc thăm trong thuật toán tìm kiếm theo chiều sâu. Thuật toán tìm kiếm theo chiều sâu trên đồ thị vô hƣớng trình bày ở trên dễ dàng có thể mô tả lại cho đồ thị có hƣớng. Trong trƣờng hợp đồ thị có hƣớng, thủ tcụ DFS(v) sẽ cho phép thăm tất cả các đỉnh u nào mà từ v có đƣờng đi đến u. Độ phức tạp tính toán của htuật toán là O(n+m). 19
2.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 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: Procedure BFS(v); (*Tim kiem theo chieu rong bat dau tu dinh v, cac bien Chuaxet, Ke la bien cuc bo*) begin Chuaxet[v]:=false; Begin Tham_dinh(p); If Chuaxet[u] them Begin Chuaxet[u]:=false; End; End; end; Khi đó, tìm kiếm theo chiều rộng trên đồ thị đƣợc thực hiện nhờ thuật toán sau: Begin (*Initialization*) if Chuaxet[v] then BFS(v); End. 20
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). Thí dụ 2. Xét đồ thị xét trong hình 1. Thứ tự thăm đỉnh của đồ thị theo thuật toán tìm kiếm theo chiều rộng đƣợc ghi trong ngoặc. Hình3. Chỉ số mới (trong ngoặc) của các đỉnh đƣợc đánh lại theo thứ tự chúng đƣợc thăm trong thuật toán tìm kiếm theo chiều sâu. 2.3. Tìm đƣờng đ và k ể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ị.7 a Bà toán tìm đƣờng đ g ữa a đỉn : 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) (BS(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, thì điều đó có nghĩa là không có đƣờng đi từ s đến t, còn nếu Chuaxet[t]=false 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 đế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 21
đ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] then Begin Truoc[u]:=v; DFS(u); End; 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] then Begin Chuaxet[u]:=false; Truoc[u]:=p; End; 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. b Tìm các t àn p ần l n t ông của đồ t ị: 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. Vấn đề còn lại là cách ghi nhận các đỉnh trong từng thành phần liên thông. Ta dùng thêm biến Index[v] đê ghi nhận chỉ số của thành phần liên thông chứa đỉnh v, và dùng thêm biến Inconnect để đếm số thành phần liên thông (biến này cần khởi tạo giá trị 0). Thủ tục Tham_dinh(v) trong các thủ tục DFS(v) và BFS(v) có nhiệm vụ gán: Index[v]:=connect, còn câu lện if trong các chƣơng trình chính gọi đến các thủ tục này cần đƣợc sửa lại nhƣ sau: Inconnect:=0; If Chuaxet[v] then Begin Inconnect:=Inconnect+1; DFS(v); (*BFS(v)*) End; 22
Kết thúc vòng lặp thứ hai trong chƣơng trình chính, Inconnect cho số thành phần liên thông phần liên thông. Chƣơng trình PASCAL giải bài toán trên có thể viết nhƣ sau: uses crt; var a:array[1 20,1 20] fo byte; QUEUE, Chuaxet, Truoc: array[1 20] of byte; i,j,n,solt,k,s,t: integer; Stop: boolean; Ch: char; Procedure Nhapsolieu; Begin Write(‘Cho so dinh cua do thi:’); readln(n); Writeln(‘Nhap so lieu ma tran ke:’); For i:= 1 to n do Begin For j:= i+1 to n do Begin Write(‘a[‘,i,’,’,j,’]=’); readln(a[i,j]); End; a[i,j}:=0; writeln; End; End; {===} Procedure readfile; Var f:text; fn:string; Begin Write(‘ Cho ten file du lieu:’); readln (fn); 23
Assign(fnfn); reset(f); readln(f,n); Writeln(‘Nhap so lieu ma tran ke:’); For i:= 1 to n do For j:=1 to n do read(f, a[i,j}); Close(f); End; {===} Procedure Insolieu; Begin Writeln(‘Ma tran ke:’); For i:= 1 to n do Begin For j:=1 to n do write(a[i,j]:3); Writeln; End; End; {===} Procedure Ketqualienthon; Begin Insolieu; If solt=1 then writeln(‘Do thi la lien thong’) Else Begin Wriyeln(‘Thanh phan lien thon thu ‘,i,’ gom cac dinh:’); For j:=1 to n do if Chuaxet[j]=i then write(j:3); writeln; End; Write(‘Go Enter de tiep tuc ’#7); readln; End; {===} Procedure BFS(i:integer); (*tim kiem theo chieu rong bat dau tu dinh i*); var u, dauQ, CuoiQ,: integer; 24
begin dauQ=1; cuoiQ:=1; QUEUE[cuoiQ]:=i; Chuaxet[i]:=Solt; While dauQ<=cuoiQ do Begin U:= QUEUE[sauQ]; dauQ:=dauQ+1; For j:=1 to n do If a[u,j]=1) and (Chuaxet[j]=0) then Begin cuoiQ:=cuoiQ+1; QUEUE:[cuoiQ]:=j; Chuaxet[j]:=Solt; Truoc[j]:=u; End; End; {===} Procedure DFS(v:integer); (*Tim kiem theo chieu sau bat dau tu dinh v*); var U: integer; begin Chuaxet[v]:=solt; For u:=1 to n do If (a[v,u]=1) and (Chuaxet[u]=0) then Begin Truoc[u]:=v; DFS9(u); End; End; {===} Procedure Lienthong; Begin for j:=1 to n do Chuaxet[j]:=0; solt:=0; 25
for i:=1 to n do if Chuaxet[i]=0 then begin solt:=solt+1; end; Ketqualienthong; End; {===} Procedure Ketquaduongdi; Begin If Truoc[t]=0 then writeln(‘Khong co duong di tu ’, s,’ den ‘,t) Else Begin Writeln(‘Duong di tu ‘,s,’ den ‘,t,’ la:’); J:=t; Write(t,’ s do Begin Write(Truoc[g],’ <==’); J:=Truoc[j]; End; Writeln(s); End; Write(‘Go Enter de tiep tuc ’#7); readln; End; {===} Procedure duongdi; Begin Insolieu; Write(‘Tim duon di tu dinh:’); readln(s); Write(‘ den dinh:’); readln(t); 26
Begin Truoc[j[:=0; Chuaxet[j]:=0; End; Ketquaduondi; End; {===} Procedure menu; Begin Clrscr; Writeln(‘TIM DUONG DI VA KIEM TRA TINH LIEN THONG’); Writeln(‘CUA DO THIJ THEO THUAT TOAN TIM KIEM TREN DO THI’); Writeln(‘===’); Writeln(‘ 1. Nhap so lieu tu ban phim’); Writeln(‘ 2. Nhap so lieu tu file’); Writeln(‘ 3. Kiem tra tinh lien thong’); Writeln(‘ 4. Tim duong di giua hai dinh’); Writeln(‘ 5. Thoat’); Writeln(‘ ’); Write(‘Hay go phim so de chon chuc nang #7); Ch:=readkey; Writeln(ch); End; {===} Begin repeat menu; case ch of ‘1’:Nhapsolieu; ‘2’:Readfile; 27
‘3’:Lienthong; ‘4’:Duongdi; until (ch=’5’) or (upcase (ch)=’Q); End. 2.4. Tô màu đồ thị 2.4.1. Giới thiệu Vấn đề liên quan đến tô màu các miền trên bản đồ, ví dụ bản đồ các vùng trên thế giới đã dẫn đến nhiều kết quả trong lí thuyết đồ thị. Khi tô màu bản đồ, ta thƣờng tô 2 miền có chung đƣờng biên giới bằng 2 màu khác nhau. Để đảm bảo điều này, ta có thể sử dụng màu sắc riêng cho mỗi miền. Tuy nhiên, cách làm này là không hiệu quả, và nếu bản đồ có quá nhiều miền, sẽ rất khó để phân biệt giữa các miền có màu sắc gần giống nhau. Do đó, ta nên sử dụng số màu ít nhất có thể đƣợc. Nó dẫn đến bài toán xác định số màu tối thiểu cần sử dụng để tô màu các miền bản đồ sao cho các miền lân cận luôn khác màu nhau. VD:Bản đồ H1a có thể tô đƣợc bằng 4 màu, nhƣng không thể tô bằng 3 màu -> Số màu tối thiểu phải là 4. Bản đồ H1b có thể tô bằng 3 màu,nhƣng 2 màu là không thể ->Số màu tối thiểu là 3. B G A B C E C D F D E a) b) H1: 2 bản đồ ví dụ. Mỗi bản đồ trên mặt phẳng có thể biểu diễn bằng đồ thị: Mỗi miền biểu diễn bằng 1 đỉnh; 2 đỉnh sẽ đƣợc nối với nhau khi 2 miền tƣơng ứng có chung đƣờng biên giới. Hai miền chỉ tiếp xúc nhau tại 1 điểm coi nhƣ không kề nhau. Đồ thị này đƣợc gọi là đồ thị kép của bản đồ. Từ phƣơng pháp xây dựng đồ thị kép của 1 bản đồ, dễ thấy mỗi bản đồ phẳng sẽ tƣơng ứng với 1 đồ thị kép phẳng . H2 thể hiện đồ thị phẳng tƣơng ứng của các bản đồ trong H1. 28
B B C D G C A A E F D a) E b) H2: Đồ thị kép của các bản đồ trong H1. 2.4.2. Các khái niệm cơ bản Định nghĩa 1: Phép tô màu của một đồ thị đơn là một quy tắc tô mỗi đỉnh đồ thị một màu cụ thể sao cho không có 2 đỉnh kề nhau nào đƣợc tô cùng màu. 1 đồ thị có thể tô màu bằng các màu khác nhau cho mỗi đỉnh. Tuy nhiên, trong phần lớn các đồ thị, ta có thể tô bằng số màu ít hơn số đỉnh. Vậy số màu tối thiểu cần sử dụng là bao nhiêu? Định nghĩa 2: Số màu của một đồ thị G ( kí hiệu c(G))là số màu tối thiểu cần sử dụng để tô màu đồ thị này. Chú ý rằng số màu của 1 đồ thị phẳng chính là số màu tối thiểu cần sử dụng để tô màu các miền bản đồ phẳng sao cho không có 2 miền nào kề nhau và đƣợc tô cùng màu. Bài toán này đã đƣợc nghiên cứu hơn 100 năm,dẫn đến một trong các định lí nổi tiếng nhất của toán học: Định lí 4 màu: Số màu của 1 đồ thị phẳng không lớn hơn 4. Giả thuyết 4 màu đƣợc đề ra từ những năm 1850. Nó cuối cùng đã đƣợc chứng minh bởi 2 nhà toán học Mĩ là Kenneth Appel và Wolfgang Haken năm 1976. Trƣớc đó, nhiều ngƣời đã đề ra các cách chứng minh khác nhau của bài toán, nhƣng tất cả đều sai và thƣờng mắc phải những lỗi khó phát hiện. Bên cạnh đó là những cố gắng vô ích trong việc phủ định giả thuyết bằng cách chỉ ra những bản đồ đòi hỏi nhiều hơn 4 màu. Có lẽ, sai lầm nổi tiếng nhất là chứng minh đƣợc xuất bản năm 1879 bởi một luật sƣ ở Luân Đôn và một nhà toán học nghiệp dƣ, Afred Kempe. Các nhà toán học công nhận chứng minh này là đúng cho đến năm 1890, khi Percy Heawood tìm ra lỗi. Tuy nhiên, 29
hƣớng lí luận của Kempe lại trở thành cơ sở cho thành công của Appel và Haken sau này. Chứng minh của họ dựa trên phân tích cẩn thận từng trƣờng hợp trên máy tính. Họ chỉ ra rằng nếu giả thuyết 4 màu sai, họ phải tìm ra đƣợc phản ví dụ của 1 trong khoảng 2000 trƣờng hợp khác nhau. Họ đã sử dụng máy tính chạy trong 1000 tiếng để thực hiện chứng minh của mình. Chứng minh này đã gây ra nhiều tranh cãi khi sử dụng máy tính để thực hiện các thao tác chính. Ví dụ, chƣơng trình máy tính có thể mắc lỗi dẫn đến kết quả sai. Liệu lí lẽ của họ có thật sự là 1 chứng minh khi phụ thuộc vào những kết quả không đáng tin cậy của máy tính? Định lí 4 màu chỉ ứng dụng trên đồ thị phẳng. Đồ thị không phẳng có thể có số màu lớn hơn 4(Xem ví dụ 2). 2 điều kiện đƣợc yêu cầu để xác định số màu của 1 đồ thị là n: Đầu tiên,phải chứng minh đồ thị có thể tô bằng n màu.Việc này có thể thực hiện bằng cách xây dựng, nhƣ tô màu. Thứ 2, chúng ta phải chỉ ra rằng đồ thị không thể tô bằng số màu ít hơn n. Các ví dụ sau điển hình cho cách tìm số màu đồ thị. 2.4.3. Ví dụ a. Ví dụ 1: Tìm số màu của đồ thị G và H trong hình 3. b e b e g a g a d d c f c f G H H3: Hai đồ thị đơn G và H. Lời giải: - Số màu của đồ thị G tối thiểu là 3 do 3 đỉnh a, b, c phải đôi một khác màu nhau. Giả sử G có thể tô bằng 3 màu. Giả sử ta tô a màu đỏ, b màu xanh và c màu vàng. Tiếp theo, d phải tô màu đỏ vì nó kề các đỉnh b, c; e phải tô màu vàng vì nó chỉ kề các đỉnh màu màu đỏ và xanh; f phải tô màu xanh vì nó chỉ kề các đỉnh màu đỏ và vàng. Cuối cùng g phải tô màu đỏ vì nó chỉ kề các đỉnh màu vàng và xanh. Nhƣ vậy, ta có thể tô màu G bằng 3 màu -> c(G)=3. 30
- Đồ thị H biến đổi từ đồ thị G thông qua việc nối 2 đỉnh a và g. Lí luận tƣơng tự nhƣ trên, ta thấy H phải tô tối thiểu bằng 3 màu. Khi cố gắng tô H bằng 3 màu ta phải thông qua các lí luận tƣơng tự nhƣ G khi tô màu tất cả các đỉnh trừ g. Cuối cùng, g sẽ liền kề với các đỉnh có cả 3 màu đỏ, vàng, xanh, và ta buộc phải sử dụng thêm màu thứ 4 (màu nâu) để tô màu nó. Tóm lại, c(H)=4 (Xem H4). X V X b e b e V g g d d Đ Đ a Đ Đ a Đ c f N c V X f X V G H H4: Tô màu các thị G và H: Đ: đỏ X: xanh V: vàng N: nâu. b. Ví dụ 2: Tìm số màu của đồ thị đầy đủ Kn? Lời giải : Ta có thể tô màu n đỉnh của Kn bằng n màu riêng biệt. Liệu có cách tô nào tiết kiệm màu hơn không? Câu trả lời là không. Đ X a b Đ Đ Đ a b c N c e H d X e X f X g X V d H5. Tô màu K5. H6. Tô màu K3,4. Đ: đỏ X: xanh V: vàng N: nâu H: hồng. 31
Thật vậy, không có 2 đỉnh nào có thể tô cùng màu vì mọi đỉnh đều kề nhau. Vậy, ta có c(Kn) = n (Chú ý: Kn không phải đồ thị phẳng khi n ≥ 5, do đó kết quả này không vi phạm định lí 4 màu). H5 cho ta ví dụ về việc tô màu K5. c. Ví dụ 3: Tìm số màu của đồ thị 2 phía đầy đủ Km,n, với m và n là 2 số nguyên dƣơng ? Lời giải: Số màu của đồ thị có vẻ nhƣ phụ thuộc vào m và n. Nhƣng thực tế, chỉ cần 2 màu là đủ: Tô màu tập hợp m đỉnh với cùng 1 màu, và tập hợp n đỉnh kia tô bằng màu thứ 2. Do mỗi cạnh chỉ nối 1 đỉnh thuộc tập hợp thứ nhất với 1 đỉnh thuộc tập hợp 2 nên sẽ không có 2 đỉnh kề nhau nào cùng màu. H6 cho ta ví dụ về việc tô màu K3,4. Mọi đồ thị 2 phía đơn đều có 2 hoặc 1 màu, với cùng lí luận nhƣ trong ví dụ 3. Ngƣợc lai, ta dễ dàng chứng minh đƣợc mọi đồ thị 2 màu đều là đồ thị 2 phía. d. Ví dụ 4: Tìm số màu của đồ thị vòng Cn ? Lời giải : Do 2 đỉnh kề nhau khác màu nên số màu của đồ thị (với n>1) tối thiểu là 2. Xét 2 trƣờng hợp: - Nếu n chẵn: Ta chỉ cần sử dụng 2 màu. Để xây dựng phép tô màu, chọn 1 đỉnh bất kì và tô màu đỏ. Sau đó, dọc theo chiều kim đồng hồ (trong cách biểu diễn phẳng của đồ thị),ta tô đỉnh 2 màu xanh, đỉnh 3 màu đỏ, đỉnh 4 màu lại màu xanh Nhƣ vậy các đỉnh có số thứ tự chẵn đƣợc tô màu xanh, lẻ đƣợc tô màu đỏ. Đỉnh thứ n (số thứ tự chẵn) có thể tô màu xanh, vì 2 đỉnh kề nó-tức đỉnh 1 và đỉnh thứ n-1 (số thứ tự lẻ) đều tô màu đỏ. - Nếu n lẻ và n>1: Số màu của đồ thị là 3. Thật vậy, đầu tiên chọn 1 đỉnh xuất phát và tô màu đỏ. Nếu chỉ cần 2 màu, khi đi dọc chiều kim đồng hồ, các màu phải xuất hiện luân phiên. Nhƣ vậy, các đỉnh có số thứ tự (< n) chẵn đƣợc tô màu xanh, lẻ đƣợc tô màu đỏ. Tuy nhiên,đỉnh thứ n nằm kề đỉnh 1 và đỉnh thứ n-1(số thứ tự chẵn), tức 2 đỉnh khác màu. Do đó, màu thứ 3 buộc phải sử dụng. H7 thể hiện lời giải bài toán trong trƣờng hợp n = 6 và n = 5. 32
a b a b Đ X Đ X f c X Đ e V Đ c Đ X X e d d C6 C5 H7. Tô màu C5 và C6. Đ: đỏ X: xanh V: vàng 2.4.5. Thuật toán Thuật toán tối ƣu đƣợc biết đến để tìm ra số màu đồ thị có độ phức tạp trong trƣờng hợp tồi nhất là O(en). Nhìn chung việc đi tìm một lời giải xấp xỉ cho bài toán tô màu đồ thị là rất khó. Ngƣời ta đã chỉ ra rằng nếu có 1 thuật toán có độ phức tạp hàm đa thức có thể xấp xỉ đƣợc c(g) theo hệ số 2 (tức xây dựng đƣợc giới hạn của 2.c(G)),thì thuật toán có độ phức tạp hàm đa thức để tìm c(G) là tồn tại. Bài tập Bài 1: Viết chƣơng trình nhập vào một đồ thị từ file input.txt có cấu trúc nhƣ sau: Dòng 1: Số đỉnh Các dòng tiếp theo ứng với ma trận kề tƣơng ứng của đồ thị. Yêu cầu: Duyệt đồ thị theo chiều rộng sử dụng thuật toán BFS. Bài 2: Viết chƣơng trình nhập vào một đồ thị từ file input.txt có cấu trúc nhƣ sau: Dòng 1: Số đỉnh Các dòng tiếp theo ứng với ma trận kề tƣơng ứng của đồ thị. Yêu cầu: Duyệt đồ thị theo chiều sâu sử dụng thuật toán DFS. Bài 3: Viết chƣơng trình nhập vào một đồ thị từ file input.txt có cấu trúc nhƣ sau: Dòng 1: Số đỉnh Các dòng tiếp theo ứng với ma trận kề tƣơng ứng của đồ thị. Yêu cầu: Đếm số thành phần liên thông trong đồ thị. Bài 4: Viết chƣơng trình nhập vào một đồ thị từ file input.txt có cấu trúc nhƣ sau: Dòng 1: Số đỉnh Các dòng tiếp theo ứng với ma trận kề tƣơng ứng của đồ thị. 33
Yêu cầu: Tìm đƣờng đi từ 1 đỉnh X đến đỉnh Y với X,Y đƣợc nhập từ bàn phím. CHƢƠNG 3: ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMINTON 3.1. Đồ thị Euler 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. 3.1.1. Khái niệm về đƣờng đ và c u trìn 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ị G3 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ị H2 trong hình 2 là đồ thị Euler vì nó có chu trình Euler a, b, c, d, e, a. Đồ thị H3 không có chu trình Euler nhƣng nó có đƣờng đi Euler c, a, b, c, d, b vì thế H3 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 34
Đ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ị. 3.1.2. Đ ều kiện tồn t đƣờng đ oặc chu trình Euler Đị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. Để chứng minh định lý trƣớc hết ta chứng minh bổ để: Bổ đề. Nếu bậc của mỗi đỉnh của đồ thị G không nhỏ hơn 2 thì G chứa chu trình. Chứng minh. Nếu G có cạnh lặp thì khẳng định của bồ đề là hiển nhiên. Vì vậy giả sử G là đơn đồ thị. Gọi v là một đỉnh nào đó của G. Ta sẽ xây dựng theo qui nạp đƣờng đi v . . . trong đó v1 là đỉnh kề với v, còn với i≥1 chọn vi+1 # vi-l (có thể chọn vi+1 nhƣ vậy là vì deg(vi) ≥2). Do tập đỉnh của G là hữu hạn, nên sau một số hữu hạn bƣớc ta phải quay lại một đỉnh đã xuất hiện trƣớc đó. Gọi đỉnh đầu tiên nhƣ thế là vk. Khi đó, đoạn của đƣờng đi xây dựng nằm giữa hai đỉnh vk là 1 chu trình cần tìm. Chứng minh định lý: Cần. Giả sử G là đồ thị Euler tức là tồn tại chu trình Euler P trong G. Khi đó cứ mỗi lần chu trình P đi qua một đỉnh nào đó của G bậc của đỉnh đó tăng lên 2. mặt khác mỗi cạnh của đồ thị xuất hiện trong P đúng một lần, suy ra mỗi đỉnh của đồ thị điều có bậc chẵn. Đủ. Quy nạp theo số đỉnh và số cạnh của G. Do G liên thông và deg(v) là số chẵn nên bậc của mỗi đỉnh của nó không nhỏ hơn 2. Từ đó theo bổ đề G phải chứa chu trình C. Nếu C đi qua tất cả các cạnh của G thì nó chính là chu trình Euler. Giả sử C không đi qua tất cả các cạnh của G. Khi đó loại bỏ khỏi G tất cả các cạnh thuộc C ta thu đƣợc một đồ thị mới H vẫn có bậc là chẵn. Theo giả thiết qui nạp, trong mỗi thành phần liên thông của H điều tìm đƣợc chu trình Euler. Do G là liên thông nên trong mỗi thành phần của H có ít nhất một đỉnh chung với chu trình C. Vì vậy, ta có thể xây dựng chu trình Euler trong G nhƣ sau: bắt đầu từ một đỉnh nào đó của chu trình C, đi theo các cạnh của C chừng nào chƣa gặp phải đỉnh không cô lập của H. Nếu gặp phải đỉnh nhƣ vậy ta sẽ đi theo chu trình Euler của thành phần liên thông của H chứa đỉnh đó. Sau đó lại tiếp tục đi theo cạnh của C cho đến khi gặp phải đỉnh không cô lập của H thì lại theo chu trình Euler của thành phần liên thông tƣơng ứng trong Hv.v (xem hình 3). Quá trình sẽ kết thúc khi ta trở về đỉnh xuất phát, tức là thu đƣợc chu trình đi qua mỗi cạnh của đồ thị đúng một lần. 35
Hình 3. Minh hoạ cho chứng minh định lý 1. Hệ quả 2. Đồ 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ẻ. Chứng minh. Thực vậy, nếu G có không quá 2 đỉnh bậc lẻ thì số đỉnh bậc lẻ của nó chỉ có thể là 0 hoặc 2. Nếu G không có đỉnh bậc lẻ thì theo định lý 1, nó là đồ thị Euler. Giả sử G có 2 đỉnh bậc lẻ là u và v. Gọi H là đồ thị thu đƣợc từ G bằng cách thêm vào G một đỉnh mới w và hai cạnh (w,u) và(w,v). Khi đó tất cả các đỉnh của H điều có bậc chẵn, vì thế theo định lý 1, nó có chu trình Euler C. Xoá bỏ khỏi chu trình này đỉnh w và hai cạnh kề nó ta thu đƣợc đƣờng đi Euler trong đồ thị G. Giả sử G là đồ thị Euler, từ chứng minh định lý ta có thủ tục sau để tìm chu trình Euler trong G. 3.1.3. Thuật toán tìm đƣờng đ và c u trìn Euler Procedure Euler_Cycle; Begin Chon u la mot dinh nao do cua do thi; Begin X:=top(STACK); (* x la phan tu dau STACK) Begin Y:=dinh dau tien trong danh sach Ke(x); (* loai bo canh (x,y) khoi do thi *) Ke(x):=Ke(x)\ Ke(y):=Ke(y)\ End Else Begin 36
End; End; End; 3.1.4. Một số vấn đề khác về đƣờng đ và c u trìn Euler 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. 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: (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. Chứng minh tính đúng đắn của thuật toán. Trƣớc tiên ta chỉ ra rằng thủ tục trên có thể thực hiện ở mỗi bƣớc. Giả sử ta đi đến một đỉnh v nào đó, khi đó nếu v # u thì đồ thị con còn lại H là liên thông và chứa đúng hai đỉnh bậc lẻ là v và u. Theo hệ quả trong H có đƣờng đi Euler P từ v tới u. Do việc xoá bỏ cạnh đầu tiên của đƣờng đi P không làm mất tính liên thông của H, từ đó suy ra thủ tục có thể thực hiện ở mỗi bƣớc. Nếu v = u thì lập luận ở trên sẽ vẫn đúng chừng nào vẫn còn cạnh kề với u. Nhƣ vậy chỉ còn phải chỉ ra thủ tục trên dẫn đến đƣờng đi Euler. Thực vậy trong G không thể còn cạnh chƣa đi qua khi mà ta sử dụng cạnh cuối cùng kề với u (trong trƣờng hợp ngƣợc lại, việc loại bỏ một cạnh nào đó kề với một trong số những cạnh còn lại chƣa đi qua sẽ dẫn đến một đồ thị không liên thông, và điều đó là mâu thuẫn với giả thiết ii). Chứng minh tƣơng tự nhƣ trong định lý 1 ta thu đƣợc kết quả sau đây cho đồ thị có hƣớng. Định lý 2. Đồ thị có hƣớng liên thông mạnh là đồ thị Euler khi và chỉ khi Deg+(v)=deg- V. 3.2. Đồ thị Haminton 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. 37
3.2.1. Khái niệm về đƣờng đ và c u trìn Ham nton Đị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 4: G3 là Hamilton, G2 là nửa Hamilton còn G1 không là nửa Hamilton. Hình 4. Đồ 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. 3.2.2. Đ ều kiện tồn t đƣờng đ oặc chu trình Haminton (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. Chứng minh: Thêm vào đồ thị G k đỉnh mới và nối chúng với tất cả các đỉnh của G. giả sử k là số nhỏ nhất các đỉnh cần thêm vào để cho đồ thị thu đƣợc G’ là đồ thị Hamilton. Ta sẽ chỉ ra rằng k=0. Thực vậy, giả sử ngƣợc lại là k >0. Ký hiệu v, p, w, . . ., v là chu trình Hamilton trong G’, trong đó v, w là đỉnh của G còn p là một trong số các đỉnh mới. Khi đó w không kề với v vì nếu ngƣợc lại, ta không cần sử dụng p và điều đó là mâu thuẫn với giả thiết k nhỏ nhất. Hơn thế nữa đỉnh (w’ chẳng hạn) kề với w không thể đi liền sau đỉnh v’ (kề với v) vì rằng khi đó có thể thay bằng cách đảo ngƣợc đoạn của chu trình nằm giữa w và v’. Từ đó suy ra là số đỉnh của đồ thị G’ không kề với w là không nhỏ hơn số đỉnh kề với v (tức là ít nhất cũng là bằng n/2+k), 38
đồng thời số đỉnh của G’ kề với w ít ra là phải bằng n/2+k. Do không có đỉnh nào của G’ vừa không kề, lại vừa kề với w, cho nên tổng số đỉnh của đồ thị G’ (G’ có n+k đỉnh) không ít hơn n+2k. Mâu thuẫn thu đƣợc đã chứng minh định lý. Định lý sau là tổng quát hoá của định lý Dirak cho đồ thị có hƣớng: Địn lý 4. Giả sử G là đồ có hƣớng liên thông với n đỉnh. Nếu deg+ (v)≥n/2, deg – 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: Địn 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 5. Hình 5. Đồ thị đấu loại D5, đấu loại liên thông mạnh D6 3.2.3. Thuật toán tìm đƣờng đ và c u trìn Ham nton Thuật toán sau đây đƣợc xây dựng dựa trên cơ sở thuật toán quay lui cho phép liệt kê tất cả các chu trình Hamilton của đồ thị. Procedure Hamilton(k); (* liet ke cac chu trinh Hamilton thu duoc bang viec phat trien day dinh (X[1],. . . , X[k- *) begin -1]) do if (k =N+1) and (y=v0) then Ghinhan(X[1],. . . , X[n], v0) 39
else if Chuaxet[y] then begin X[k]:=y; Chuaxet[y]:=false; Hamilton(k+1); Chuaxet[y]:=true; end; end; (* Main program*) begin X[1]:=0; (* v0 la mot dinh nao do cua do thi *) Chuaxet[v0]:=false; Hamilton(2); end. Thí dụ 5. Hình 6 dƣới đây mô tả cây tìm kiếm theo thuật toán vừa mô tả. Hình 6. Đồ thị và cây liệt kê chu trình Hamilton của nó theo thuật toán quay lui Trong trƣờng hợp đồ thị có không quá nhiều cạnh thuật toán trên có thể sử dụng để kiểm tra đồ thị có phải là Hamilton hay không. Bài tập 1. Với giá trị nào của n các đồ thị sau đây có chu trình Euler ? Kn, b) Cn, c) Wn, d) Qn. 2. Với giá trị nào của m và n các đồ thị phân đôi đầy đủ Km,n có: a) chu trình Euler ? b) đƣờng đi Euler ? 3. Với giá trị nào của m và n các đồ thị phân đôi đầy đủ Km,n có chu trình Hamilton ? 4. Chứng minh rằng đồ thị lập phƣơng Qn là một đồ thị Hamilton. Vẽ cây liệt kê tất cả các chu trình Hamilton của đồ thị lập phƣơng Q3. 40
5. Trong một cuộc họp có 15 ngƣời mỗi ngày ngồi với nhau quanh một bàn tròn một lần. Hỏi có bao nhiêu cách sắp xếp sao cho mỗi lần ngồi họp, mỗi ngƣời có hai ngƣời bên cạnh là bạn mới, và sắp xếp nhƣ thế nào ? 6. Hiệu trƣởng mời 2n (n 2) sinh viên giỏi đến dự tiệc. Mỗi sinh viên giỏi quen ít nhất n sinh viên giỏi khác đến dự tiệc. Chứng minh rằng luôn luôn có thể xếp tất cả các sinh viên giỏi ngồi xung quanh một bàn tròn, để mỗi ngƣời ngồi giữa hai ngƣời mà sinh viên đó quen. 7. Một ông vua đã xây dựng một lâu đài để cất báu vật. Ngƣời ta tìm thấy sơ đồ của lâu đài (hình sau) với lời dặn: muốn tìm báu vật, chỉ cần từ một trong các phòng bên ngoài cùng (số 1, 2, 6, 10, ), đi qua tất cả các cửa phòng, mỗi cửa chỉ một lần; báu vật đƣợc giấu sau cửa cuối cùng. Hãy tìm nơi giấu báu vật 1 2 3 4 5 6 7 9 8 10 11 12 13 14 15 16 17 18 20 21 19 8. Đồ thị cho trong hình sau gọi là đồ thị Peterson P. a a) Tìm một đƣờng đi Hamilton trong P. b) Chứng minh rằng P \ {v}, với v là một e g b đỉnh bất kỳ của P, là một đồ thị Hamilton. h f k i d c 41
9. Chứng minh rằng đồ thị G cho trong d s r hình sau có đƣờng đi Hamilton (từ s đến r) c nhƣng không có chu trình Hamilton. e g b f a h 10. Cho thí dụ về: 1) Đồ thị có một chu trình vừa là chu trình Euler vừa là chu trình Hamilton; 2) Đồ thị có một chu trình Euler và một chu trình Hamilton, nhƣng hai chu trình đó không trùng nhau; 3) Đồ thị có 6 đỉnh, là đồ thị Hamilton, nhƣng không phải là đồ thị Euler; 4) Đồ thị có 6 đỉnh, là đồ thị Euler, nhƣng không phải là đồ thị Hamilton. 11. Chứng minh rằng con mã không thể đi qua tất cả các ô của một bàn cờ có 4 x 4 hoặc 5 x 5 ô vuông, mỗi ô chỉ một lần, rồi trở về chỗ cũ. 42
CHƢƠNG 4. C Y KHUNG CỦA ĐỒ THỊ 4.1. Khái niệm và các tính chất của cây khung Đồ 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 Định nghĩa1. Ta gọi cây là đồ thị vô hướng liên thông không có chu trình. Đồ thị không có chu trình được gọi là rừng. Nhƣ vậy, rừng là đồ thị mà mỗi thành phần liên thông của nó là một cây. Thí dụ 1. Trong hình 1 là một rừng gồm 3 cây T1, T2, T3. Hình 1. Rừng gồm 3 cây T1, T2, T3. Có thể nói cây là đồ thị vô hƣớng đơn giản nhất. Định lý sau đây cho ta một số tính chất của cây. Định lý 1. Giả sử G=(V,E) là đồ thị vô hƣớng n đỉnh. Khi đó các mệnh đề sau đây là tƣơng đƣơng: (1) T là cây; (2) T không chứa chu trình và có n-1 cạnh; (3) T liên thông và có n-1 cạnh; (4) T liên thông và mỗi cạnh của nó điều là cầu; (5) Hai đỉnh bất kỳ của T đƣợc nối với nhau bởi đúng một đƣờng đi đơn; (6) T không chứa chu trình nhƣng hễ cứ thêm vào một cạnh ta thu đƣợc đúng một chu trình. Chứng minh. Ta sẽ chứng minh định lý theo sơ đồ sau: đỉnh n cho khẳng định: Số cạnh của cây với n đỉnh là n-1. Rõ ràng khẳng định đúng với n=1. 43
Giả sử n>1. Trƣớc hết nhận rằng trong mọi cây T có n đỉnh đều tìm đƣợc ít nhất một đỉnh là đỉnh treo (tức là đỉnh có bậc là 1). Thực vậy, gọi v1, v2, . . .,vk là đƣờng đi dài nhất (theo sốcạnh) trong T. Khi đó rõ ràng v1 và vk là các đỉnh treo, vì từ v1 (vk) không có cạnh nối với bất cứ đỉnh nào trong số các đỉnh v2, v3, . . .,vk (do đồ thị không chứa chu trình), cũng nhƣ với bất cứ đỉnh nào khác của đồ thị (do đƣờng đi đang xét dài nhất). Loại bỏ v1 và cạnh (v1, v2) khỏi T ta thu đƣợc cây T1 với n-1 đỉnh, mà theo giả thiết qui nạp có n-2 cạnh. Vậy cây T có n- 2+1 = n-1 cạnh. thành k≥2 phần liên thông T1, T2,. . . Tk. Do T không chứa chu trình nên mỗi Ti (i=1,2,. . .,k) cũng không chứa chu trình, vì thế mỗi Ti là cây. Do đó nếu gọi n(Ti) và e(Ti) theo thứ tự là số đỉnh và cạnh của Ti, ta có: e(Ti) = n(Ti) – 1, i= 1, 2, . . ., k, suy ra n-1 = e(T) = e(T1) + . . . + e(Tk) = n(T1) + . . . n(Tk) – k = n(T) –k < n-1 Mâu thuẫn thu đƣợc chứng tỏ là T liên thông. -2 cạnh rõ ràng là đồ thị không liên thông. Vậy mọi cạnh trong T đều là cầu. đơn. Nếu có cặp đỉnh nào của T có hai đƣờng đi đơn khác nhau nối chúng, thì từ đó suy ra đồ thị chứa chu trình, và vì thế các cạnh trên chu trình này không phải là cầu. đỉnh của T đƣợc nối với nhau bởi hai đƣờng đi đơn. Bây giờ, nếu thêm vào T một cạnh e nối hai đỉnh u và v nào đó của T. Khi đó cạnh này cùng với đƣờng đi đơn nối u với v sẽ tạo thành chu trình trong T. Chu trình thu đƣợc này là duy nhất, vì nếu thu đƣợc nhiều hơn một chu trình thì suy ra trong T trƣớc đó phải có sẵn chu trình. nếu thêm vào T một cạnh nối hai đỉnh thuộc hai thành phần liên thông khác nhau ta không thu đƣợc thêm một chu trình nào cả. Điều đó mâu thuẫn với giả thiết (6). Định lý đƣợc chứng minh. 4.2. Cây khung của đồ thị Định nghĩa 2. Đồ thị G và cây khung của nó đƣợc cho trong hình 2 44
Hình 2. Đồ thị và các cây khung của nó Định lý sau đây cho biết số lƣợng cây khung của đồ thị đầy đủ Kn: n-2 Định lý 2 (Cayley). Số lƣợng cây khung của đồ thị Kn là n . Định lý 2 cho thấy số lƣợng cây khung của đồ thị là một số rất lớn. Bây giờ ta xét áp dụng của thuật toán tìm kiếm theo chiều sâu và theo chiều rộng trên đồ thị để xây dựng cây khung của đồ thị vô hƣớng liên thông. Trong cả hai trƣờng hợp mỗi khi ta đến đƣợc đỉnh mới u (tức Chuaxet[u]=true) từ đỉnh v thì cạnh (v, u) sẽ đƣợc kết nạp vào cây khung. Hai thuật toán tƣơng ứng đƣợc trình bày trong hai thủ tục sau đây. Procedure stree_DFS(v); (* tim kiem theo chieu sau ap dung vao tim tap canh cua cay khung T cua do thi vo huong lien thong G cho boi danh sach ke. Cac bien Chuaxet, Ke, T la toan cuc*) begin Chuaxet[v]:=false; For u Ke(v) do If Chuaxet[u] then Begin T:=T (u,v); STREE_DFS(u); End; end; (* Main Program *) begin 45
(* Initialition *) for u V do Chuaxet[u]:=true; T := ; (* T la tap canh cua cay khung *) STREE_DFS(root); ( root la dinh nao do cua do thi *) end. Procedure Stree_BFS(v); (* tim kiem theo chieu rong ap dung tim tap canh cua cau khung T cua do thi vo huong lien thong G cho boi danh sach Ke *) begin Queue:= ; Queue r; Chuaxet[r]:=false; While queue <> do Begin V queue; For r Ke(v) do If Chuaxet[u] then Begin Queue u; Chuaxet[u]:=false; T:= T (u,v); End; End; 46
end; (* Main Program *); begin for u V do Chuaxet[u]:=true; T := ; (* T la tap canh cua cay khung *) Stree_BFS(root); (* root la mot dinh tuy y cua do thi *) end. Chú ý: 1. Lập luận tƣơng tự nhƣ trong phần trƣớc có thể chỉ ra đƣợc rằng các thuật toán mô tả ở trên có độ phức tạp tính toán O(m+n). 2. Cây khung tìm đƣợc theo thủ tục Stree_BFS() là cây đƣờng đi ngắn nhất từ gốc r đến tất cả các đỉnh còn lại của đồ thị. 4.3. Xây dựng các tập c u trìn cơ bản của đồ thị Bài toán xây dựng cây khung của đồ thị liên quan chặt chẽ đến một số bài toán ứng dụng khác của lý thuyết đồ thị: bài toán xây dựng tập các chu trình cơ bản của đồ thị mà ta sẽ xét trong mục này. Giả sử G=(V,E) là đơn đồ thị vô hƣớng liên thông, H=(V,T) là cây khung của nó. Các cạnh của đồ thị thuộc cây khung ta sẽ gọi là các cạnh trong, còn các cạnh còn lại sẽ gọi là cạnh ngoài. Địn ng ĩa 3. \T vào cây khung H chúng ta sẽ thu đƣợc đúng một chu trình trong H, ký hiệu chu trình này là Ce. Tập các chu trình \ đƣợc gọi là tập các chu trình cơ bản của đồ thị G. Giả sử A và B là hai tập hợp, ta đƣa vào phép toán sau \ Tên gọi chu trình cơ bản gắn liền với sự kiện là mỗi chu trình của đồ thị đều có thể thu đƣợc từ các chu trình cơ bản nhƣ chỉ ra trong định lý sau đây: Địn lý 3. Giả sử G=(V,E) là đồ thị vô hƣớng liên thông, H=(V,T) là cây khung của nó. Khi đó mọi chu trình của đồ thị G điều có thể biểu diễn nhƣ là hiệu đối xứng của một số các chu trình cơ bản. 47
Việc tìm tập hợp chu trình cơ bản giữ một vai trò quan trọng trong vấn đề giải tích mạng điện. Cụ thể hơn, theo mỗi chu trình cơ bản của đồ thị tƣơng ứng với mạng điện cần phân tích ta sẽ thiết lập đƣợc một phƣơng trình tuyến tính theo định luật Kirchoff: tổng hiệu điện thế dọc theo một mạch vòng là bằng không. Hệ thống phƣơng trình tuyến tính thu đƣợc cho phép tính toán hiệu điện thế trên mọi đƣờng dây của lƣới điện. Ta sẽ xây dựng thuật toán xây dựng các chu trình cơ bản dựa trên thủ tục tìm kiếm theo chiều sâu trên đồ thị. Thuật toán có cấu trúc tƣơng tự nhƣ thuật toán xây dựng cây khung theo thủ tục tìm kiếm theo chiều sâu mô tả trong mục trƣớc. T uật toán xây dựng tập các c u trìn cơ bản. Procedure Cycle(v); (* tim kiem cac chu trinh co ban cua thanh phan lien thong chua dinh v; cac bien d, num , stack, index la bien toan cuc *) begin d:=d+1; stack[d]:=v; num:=num+1;index[v]:=num; if index[u]=0 then cycle(u) else if (u index[u]) then d:=d-1; end; (* Main Program *) begin num:=0; d:=0; stack[0]:=0; if Index[v]=0 then cycle(v); end. Chú ý 48
4.4. Cây khung nhỏ nhất của đồ thị Bài toán cây khung nhỏ nhất của đồ thị là một trong số những bài toán tối ƣu trên đồ thị tìm đƣợc ứng dụng trong nhiều lĩnh vực khác nhau của đời sống. Trong mục này chúng ta trình bày những thuật toán cơ bản để giải bài toán nào. Trƣớc hết chúng ta phát biểu nội dung bài toán. Cho G=(V,E) là đ m cạnh. Mỗi cạnh E của đồ thị G đƣợc gán với một số không âm c(e), gọi là độ dài của nó. Giả sử H=(V,T) là cây khung của đồ thị G. Ta gọi độ dài c(H) của cây khung H là tổng độ dài các cạnh của nó: Bài toán đặt ra là trong tất cả cây khung của đồ thị G hãy tìm cây khung với độ dài nhỏ nhất. Cây khung nhƣ vậy nhƣ vậy đƣợc gọi là cây khung nhỏ nhất của đồ thị và bài toán đặt ra đƣợc gọi là bài toán cây khung nhỏ nhất. Để minh hoạ cho những ứng dụng bài toán cây khung nhỏ nhất, dƣới đây, ta phát biểu hai mô hình thực tế tiêu biểu của nó. Bài toán xây dựng hệ thống đường sắt. Giả sử ta muốn xây dựng một hệ thống đƣờng sắt nối n thành phố sao cho hành khách có thể đi từ bất kỳ một thành phố nào đến bất kỳ một trong các thành phố còn lại. Mặt khác trên quan điểm kinh tế đòi hỏi là chi phí xây dựng hệ thống đƣờng phải nhỏ nhất. Rõ ràng đồ thị mà đỉnh là các thành phố còn các cạnh là các tuyến đƣờng sắt nối các thành phố tƣơng ứng với phƣơng án xây dựng tối ƣu phải là cây. Vì vây, bài toán đặt ra dẫn về bài toán tìm cây khung nhỏ nhất trên đồ thị đầy đủ n đỉnh, mỗi đỉnh tƣơng ứng với một thành phố, với độ dài trên các các cạnh chính là chi phí xây dựng đƣờng ray nối hai thành phố tƣơng ứng (chú ý là trong bài toán này ta giả thiết là không xây dựng tuyến đƣờng sắt có các nhà ga phân tuyến nằm ngoài các thành phố). Bài toán nối mạng máy tính. Cần nối mạng một hệ thống gồm n máy tính đánh số từ 1 đến n. Biết chi phí nối máy i với máy j là c[i,j], i,j = 1, 2, . . . ,n ( thông thƣờng chi phí này phụ thuộc vào độ dài cáp nối cần sử dụng). Hãy tìm cách nối mạng sao cho tổng chi phí nối mạng là nhỏ nhất. Để giải bài toán cây khung nhỏ nhất, tất nhiên có thể liệt kê tất cả các cây khung của đồ thị và chọn trong số cây khung ấy cây khung nhỏ nhất. Phƣơng pháp nhƣ vậy, trong trƣờng hợp đồ thị đầy đủ, sẽ đòi hỏi thời gian cỡ nn-2 , và rõ ràng không thể thực hiện đƣợc ngay cả với những đồ thị với số đỉnh cỡ hàng chục. Rất may là đối với bài toán cây khung nhỏ nhất chúng 49
ta đã có những thuật toán rất hiệu quả để giải chúng. Chúng ta xét hai trong số những thuật toán nhƣ vậy: Thuật toán Kruskal và Thuật toán Prim. 4.4.1. Thuật toán Kruskal Thuật toán sẽ xây dựng tập cạnh T của cây khung nhỏ nhất H=(V,T) theo từng bƣớc. Trƣớc mỗi bƣớc ta sẽ lần lƣợt duyệt trong danh sách cạnh đã sắp xếp, từ cạnh có độ dài nhỏ đến cạnh có độ dài lớn hơn, để tìm ra cạnh mà việc bổ sung nó vào tập T gồm n-1 cạnh. Cụ thể, thuật toán có thể mô tả nhƣ sau: Procedure Kruskal; Begin - Begin E:=E\ End; -1) then Đồ thị không liên thông; End; T í dụ 3.Tìm cây khung nhỏ nhất của đồ thị cho trong hình 3 dƣới. có dãy: (3,5) , (4,6) , (4,5) , (5,6) , (3,4) , (1,3) , (2,3) , (2,4) , (1,2) dãy độ dài tƣơng ứng của chúng 4, 8, 9, 14, 16, 17, 18, 20, 23. 50
Hình 3. Đồ thị và cây khung nhỏ nhất Ở ba lần gặp đầu tiên ta lần lƣợt bổ sung vào tập T các cạnh (3,5) , (4,6) , (4,5). Rõ ràng nếu thêm cạnh (5,6) vào T thì sẽ tạo thành 2 cạnh (4,5), (4,6) đã có trong T chu trình. Tình huống tƣơng tự cũng xảy ra đối với cạnh (3,4) là cạnh tiếp theo của dãy. Tiếp theo ta bổ sung cạnh (1,3), (2,3) vào T và thu đƣợc tập T gồm 5 cạnh: Chính là tập cạnh của cây khung nhỏ nhất cần tìm. C ứng m n tín đúng đắn của t uật toán. Rõ ràng đồ thị thu đƣợc theo thuật toán có n-1 cạnh và không có chu trình, vì vậy theo định lý 1 nó là cây khung của đồ thị G. Nhƣ vậy, chỉ còn phải chỉ ra rằng T có độ dài nhỏ nhất. Giả sử tồn tại cây S của đồ thị G mà c(S) < c(T). Ký hiệu ek là cạnh đầu tiên trong dãy các cạnh của T xây dựng theo thuật toán vừa mô tả không thuộc S. khi đó đồ thị con của G sinh bởi cây S đƣợc bổ sung cạnh ek sẽ chứa một chu trình C duy nhất đi qua ek. Do chu trình C phải chứa cạnh e thuộc S nhƣng không thuộc T nên đồ thị con thu đƣợc từ S bằng cách thay cạnh e của nó bởi cạnh ek (ký hiệu đồ thị là S’) sẽ là cây khung. Theo cách xây dựng c(ek) ≤ c(e) do đó c(S’) ≤ c(S), đồng thời số cạnh chung của S’ và T đã tăng thêm 1 so với số cạnh chung của S và T. Lặp lại quá trình trên từng bƣớc một ta có thể biến đổi S thành T và trong mỗi bƣớc tổng độ dài không tăng, tức là c(T) ≤ c(S). Mâu thuẫn thu đƣợc chúng tỏ T là cây khung nhỏ nhất. Về v ệc lập trìn t ực ện t uật toán. Khối lƣợng tính toán nhiều nhất của thuật toán chính là ở bƣớc sắp xếp các cạnh của đồ thị theo thứ tự không giảm của độ dài để lựa chọn cạnh bổ sung. Đối với đồ thị m cạnh cần phải thực hiện m log m phép toán để sắp xếp các cạnh của đồ thị thành dãy không giảm theo độ dài. Tuy nhiên, để xây dựng cây khung nhỏ nhất với n-1 cạnh, nói chung ta không cần phải sắp thứ tự toàn bộ các cạnh mà chỉ cần xét phần trên của dãy đó chứa r < m cạnh. Để làm việc đó ta có thể sử dụng các thủ tục sắp xếp dạng Vun đống (Heap Sort). Trong thủ tục này, để tạo đống đầu tiên ta mất cỡ O(m) phép toán, mỗi phần tử tiếp theo trong đống có thể tìm sau thời gian O(log m). Vì vậy, với cải tiến này thuật toán sẽ mất thời gian cỡ O(m+p) log m) cho việc sắp xếp các cạnh. Trong thực tế tính toán số p nhỏ hơn rất nhiều so với m. Vấn đề thứ hai trong việc thể hiện thuật toán Kruskal là việc lựa chọn cạnh để bổ sung đòi ý rằng, các cạnh trong T ở các bƣớc lặp trung gian sẽ tạo thành một rừng. Cạnh e cần khảo sát sẽ tạo thành chu trình với các cạnh trong T khi và chỉ khi cả hai đỉnh đầu của nó thuộc vào cùng một cây con của rừng nói trên. Do đó, nếu cạnh e không tạo thành chu trình với các cạnh 51
trong T, thì nó phải nối hai cây khác nhau trong T. vì thế, để kiểm tra xem có thể bổ sung cạnh e vào T ta chỉ cần kiểm tra xem nó có nối hai cây khác nhau trong T hay không. Một trong các phƣơng pháp hiệu quả để thực hiện việc kiểm tra này là ta sẽ phân hoạch tập các đỉnh của đồ thị ra thành các tập con không giao nhau, mỗi tập xác định bởi một cây con trong T(đƣợc hình thành ở các bƣớc do việc bổ sung cạnh vào T). chẳng hạn, đối với đồ thị trong ví dụ 3, đầu tiên ta có sáu tập con 1 ạnh có độ dài tiếp theo là (4,6), do hai đầu của nó thuộc vào cùng một tập con Và thuật toán sẽ tiếp tục chọn cạnh tiếp theo để khảo sát Nhƣ vậy, để giải quyết vấn đề thứ hai này ta phải xây dựng hai thủ tục: Kiểm tra xem hai đầu u, v của cạnh e=(u,v) có thuộc vào hai tập con khác nhau hay không, và trong trƣờng hợp câu trả lời là khẳng định, nối hai tập con tƣơng ứng thành một tập. Chú ý rằng mỗi tập con trong phân hoạch có thể lƣu trữ nhƣ là một cây có gốc, và khi đó mỗi gốc sẽ đƣợc sử dụng làm nhãn nhận biết tập con tƣơng ứng. Chƣơng trình trên Pascal thực hiện thuật toán Kruskal với những nhận xét vừa nêu có thể viết nhƣ sau: (* TÌM C Y KHUNG NHỎ NHẤT THEO THUẬT TOÁN KRUSKAL CỦA ĐỒ THỊ CHO BỞI DANH SÁCH CẠNH *) uses crt; type arrn=array[1. .50] of integer; arrm= array[1 50] of integer; var n,m, minL:integer; Dau, cuoi, W:arrm; DauT, CuoiT, Father:arrn; Connect:boolean; Procedure Nhapdl; Var i:integer; Fanme:string; 52
F:text; Begin Write(‘Cho ten file du lieu:’) readln(fname); Assign(f,fname); reset(f); Readln(f,n,m); For i:=1 to m do readln(f, Dau[i], Cuoi[i], W[i]); Close(f); End; Procedure Indulieu; Var i:integer; Begin Writeln(‘So dinh ‘,n,’. So canh ’,m); Writeln(‘Dinh dau Dinh cuoi Do dai’); For i:=1 to m do Writeln(Dau[i]:4, Cuoi[i}:10, W[i]:12); End; Procedure Heap(First, Last:integer); Var j,k,t1,t2,t3 : integer; Begin J:=first; While (j<=trunc(last/2)) do Begin If (2*j<last) and W[2*j+1]<W[2*j]) then K:= 2*j+1 Else k"=2*j; If W[k]<W[j} then Begin T1:=Dau[j]; t1:=Cuoi[j]; t3:=W[j]; Dau[j]:=Dau[k];Cuoi[j]:=Cuoi[k]; W[j]:=W[k]; Dau[k]:=t1; Cuoi[k]:=t2; W[k]:=t3; J:=k; End Else j:=Last; End; 53
End; Function Find(i:integer):integer; Var Tro:integer; Begin Tro:=i; While Father[Tro]>0 do Tro:=Father[Tro]; Find:=Tro; End; Procedure Union(i,j:integer); Var x:integer; Begin x:=father[i]+father[j]; if father[i]>father[j] then begin father[i]:=f; father[j]:=x; end else begin father[j]:=i; father[i]:=x; end; End; Procedure Kruskal; Var I, Last, u,v,r1,r2, Ncanh, Ndinh:integer; Begin (* Khoi tao mang Father danh dau cay con va khoi tao Heap *) for i:= 1 to n do father[i]:=-1; for i:=trunc(m/2) downto 1 do Heap(i,m); last:=m; Ncanh:=0; Ndinh:=0; MinL:=0; Connect:=true; 54
While (Ndinh r2 then begin (* Ket nap canh (u,v) vao cay khung *) Ndinh:=Ndinh+1; Union(r1, r2); DauT[Ndinh]:=u; CuoiT[Ndinh]:=v; MinL:=MinL+W[1]; end; (* To chuc lai Heap *) Dau[1]:=Dau[Last]; Cuoi[1]:=Cuoi[Last]; W[1]:=W[Last]; Last:=Last-1; End; If Ndinh<>n-1 then Connect:=false; End; Procedure Inketqua; Var i:integer; Begin Writeln(‘ ’); Writeln(‘ Ket qua tinh toan ’); Writeln(‘ ’); Writeln(‘Do dai cua cay khung nho nhat: ‘,MinL); Writeln(‘Cac canh cua cay khung nho nhat’); For i:=1 to n-1 do 55
Writeln(‘(‘,DauT[i]:2,’,’,CuoiT[i]:2,’)’); Writeln(‘ ’); End; Begin Clrscr; Nhapdl;’ Indulieu; Kruskal; If connect then Inketqua Else Writeln(‘ Do thi khong lien thong’); Readln; End. File dữ liệu của bài toán trong ví dụ 3 có dạng sau: 7 9 3 5 4 4 6 8 4 5 9 5 6 14 3 4 16 1 3 17 2 3 18 2 4 20 1 2 23 4.4.2. Thuật toán Prim - 1)/2). Trong trƣờng hợp đó thuật toán Prim tỏ ra hiệu quả hơn. Thuật toán Prim còn đƣợc gọi là phƣơng pháp lân cận gần nhất. Trong phƣơng pháp này bắt đầu từ một đỉnh tuỳ ý của đồ thị, đầu tiên ta nối s với đỉnh lân cận gần nó nhất, chẳng hạn là đỉnh y. Nghĩa là trong số các cạnh kề của đỉnh s, cạnh (s,y) có độ dài nhỏ nhất. Tiếp theo trong số các cạnh kề với hai đỉnh s hoặc y ta tìm cạnh có độ dài nhỏ nhất, cạnh này dẫn đến đỉnh thứ ba z, và ta thu đƣợc cây bộ 56
phận gồm 3 đỉnh và 2 cạnh. Quá trình này sẽ tiếp tục cho đến khi ta thu đƣợc cây gồm n đỉnh và n-1 cạnh sẽ chính là cây khung nhỏ nhất cần tìm. hiện thuật toán, ở mỗi bƣớc để có thể nhanh chóng chọn đỉnh và cạnh cần bổ sung vào cây khung, các đỉnh của đồ thị sẽ đƣợc gán cho các nhãn. Nhãn của một đỉnh v sẽ gồm hai phần và có dạng [d[v], near[v]], trong đó d[v] dùng để ghi nhận độ dài của cạnh có độ dài nhỏ nhất trong số các cạnh nối với đỉnh v với các đỉnh của cây khung đang xây dựng (ta sẽ gọi là khoảng cách từ đỉnh v đến tập đỉnh của cây khung), nói một cách chính xác còn near[v] ghi nhận đỉnh của cây khung gần v nhất (near[v]:=z). T uật toán Pr m đƣợc mô tả đầy đủ trong t ủ tục sau: Procedur Prim; Begin (* buoc khoi tao *) chon s la mot dinh nao do cua do thi; \VH do Begin D[v]:=c[s,v]; near[v]:=s; End; (* buoc lap *) stop:=false; while not stop do begin \VH thoa man: \ VH:= VH u Begin H=( VH,T) la cay khung nho nhat cua do thi; 57
Stop:=true; End Else \ VH do If d[v]>c[u,v] then Begin d[v]:=c[u,v]; near[v]:=u; End; end; End; T í dụ 4. Tìm cây khung nhỏ nhất cho đồ thị xét trong ví dụ 3 theo thuật toán Prim. Ma trận trọng số của đồ thị có dạng 1 2 3 4 5 6 1 0 33 17 2 33 0 18 20 C = 3 17 18 0 16 4 4 20 16 0 9 8 5 4 9 0 14 6 8 14 0 Bảng dƣới đây ghi nhãn của các đỉnh trong các bƣớc lặp của thuật toán, đỉnh đánh dấu * là đỉnh đƣợc chọn để bổ sung vào cây khung (khi đó nhãn của nó không còn bị biến đổi trong các bƣớc lặp tiếp theo, vì vậy ta đánh dấu – để ghi nhận điều đó): Bƣớc Đỉn Đỉn Đỉn Đỉn Đỉn Đỉn VH T lặp 1 2 3 4 5 6 Khởi [0,1] [33,1] [17,1]* 1 tạo ,1] ,1] 58
1 - [18,3] - [16,3] [4,3]* 1,3 (3,1) ,1] 2 - [18,3] - [9,5] - [14,5] 1,3,5 (3,1), (5,3) 3 - [18,3] - - - [8,4] 1,3,5,4 (3,1), (5,3), (4,5) 4 - [18,3]* - - - - 1,3,5,4,6 (3,1), (5,3), (4,5), (6,4) 5 - - - - - - 1,3,5,4,6,2 (3,1), (5,3), (4,5), (6,4), (2,3) 4.4.3. Ứng dụng của bài toán tìm cây khung nhỏ nhất Trong mục này ta nêu hai bài toán có thể dẫn về bài toán cây khung nhỏ nhất, và vì thể có thể giải đƣợc nhờ các thuật toán mô tả trong mục trƣớc a) Bài toán cây khung lớn nhất. Dễ dàng nhận thấy rằng trong các thuật toán trên ta không cần sử dụng đến đòi hỏi về dấu của độ dài. Vì thế có thể áp dụng chúng đối với đồ thị có các cạnh với độ dài có dấu tuỳ ý. Vì vậy, giả sử ta phải tìm cây lớn nhất (tức là có độ dài c(H) lớn nhất) thì chỉ cần đổi dấu tất cả các độ đo và áp dụng một trong hai thuật toán vừa mô tả. b) Bài toán tìm mạng điện với độ tin cậy lớn nhất. Cho lƣới điện có n nút. Đƣờng dây nối nút i với nút j có độ tin cậy 1>p[i ,j]>0, i, j=1, 2, . . . , n. Gọi G = (V, E) là đồ thị tƣơng ứng với lƣới điện này. Hãy tìm cây khung H của đồ thị G với độ tin cậy lớn nhất. Bài toán này dẫn về bài toán tìm cây khung với tổng độ dài nhỏ nhất trên đồ thị G với độ dài của mỗi cạnh –log p(e). Thực vậy, giả sử H là cây khung nhỏ nhất trên đồ thị với độ dài – log p(e), ta có: - - với mọi cây khung H’ của đồ thị G. Từ đó suy ra hay là: với mọi cây khung H’. Vậy H là cây khung có độ tin cậy lớn nhất. 59
Bài tập 1. Vẽ tất cả các cây (không đẳng cấu) có: a) 4 đỉnh b) 5 đỉnh c) 6 đỉnh 2. Một cây có n2 đỉnh bậc 2, n3 đỉnh bậc 3, , nk đỉnh bậc k. Hỏi có bao nhiêu đỉnh bậc 1? 3. Tìm số tối đa các đỉnh của một cây m-phân có chiều cao h. 4. Có thể tìm đƣợc một cây có 8 đỉnh và thoả điều kiện dƣới đây hay không? Nếu có, vẽ cây đó ra, nếu không, giải thích tại sao: a) Mọi đỉnh đều có bậc 1. b) Mọi đỉnh đều có bậc 2. c) Có 6 đỉnh bậc 2 và 2 đỉnh bậc 1. d) Có đỉnh bậc 7 và 7 đỉnh bậc 1. 5. Chứng minh hoặc bác bỏ các mệnh đề sau đây. a) Trong một cây, đỉnh nào cũng là đỉnh cắt. b) Một cây có số đỉnh không nhỏ hơn 3 thì có nhiều đỉnh cắt hơn là cầu. 6. Có bốn đội bóng đá A, B, C, D lọt vào vòng bán kết trong giải các đội mạnh khu vực. Có mấy dự đoán xếp hạng nhƣ sau: a) Đội B vô địch, đội D nhì. b) Đội B nhì, đội C ba. c) Đọi A nhì, đội C tƣ. Biết rằng mỗi dự đoán trên đúng về một đội. Hãy cho biết kết quả xếp hạng của các đội. 7. Cây Fibonacci có gốc Tn đuợc dịnh nghĩa bằng hồi quy nhƣ sau. T1 và T2 đều là cây có gốc chỉ gồm một đỉnh và với n=3,4, cây có gốc Tn đƣợc xây dựng từ gốc với Tn-1 nhƣ là cây con bên trái và Tn-2 nhƣ là cây con bên phải. a) Hãy vẽ 7 cây Fibonacci có gốc đầu tiên. b) Cây Fibonacci Tn có bao nhiêu đỉnh, lá và bao nhiêu đỉnh trong. Chiều cao của nó bằng bao nhiêu? 60
8. Hãy tìm cây khung của đồ thị sau bằng cách xoá đi các cạnh trong các chu trình đơn. a) a b c d e f g h i j b) a b c d e g f i j h k l 9. Hãy tìm cây khung cho mỗi đồ thị sau. a) K5 b) K4,4 c) K1,6 d) Q3 e) C5 f) W5. 10. Đồ thị Kn với n=3, 4, 5 có bao nhiêu cây khung không đẳng cấu? 11. Tìm cây khung nhỏ nhất của đồ thị sau theo thuật toán Kruskal và Prim. 42 a b 4 10 14 3 3 1 11 c d e f 5 20 9 15 7 g h 12. Tìm cây khung nhỏ nhất bằng thuật toán Prim của đồ thị gồm các đỉnh A, B, C, D, E, F, H, I đƣợc cho bởi ma trận trọng số sau. 61
16 15 23 19 18 32 20 16 13 33 24 20 19 11 15 13 13 29 21 20 19 23 33 13 22 30 21 12 19 24 29 22 34 23 21 18 20 21 30 34 17 14 32 19 20 21 23 17 18 20 11 19 12 21 14 18 Yêu cầu viết các kết quả trung gian trong từng bƣớc lặp, kết quả cuối cùng cần đƣa ra tập cạnh và độ dài của cây khung nhỏ nhất. 13. Duyệt các cây sau đây lần lƣợt bằng các thuật toán tiền thứ tự, trung thứ tự và hậu thứ tự. a) b) a a b c b c d e f d e f g g h h i j k l i j m n o p q 14. Viết các biểu thức sau đây theo ký pháp Ba Lan và ký pháp Ba Lan đảo. (A B)(C D) A2 BD a) . (A B)C D C 2 BD 2 4 3 4 c a d (3a 4b 2d) b) (a b) 5d . 3 3 5 15. Viết các biểu thức sau đây theo ký pháp quen thuộc. a) x y + 2 ↑ x y − 2 ↑ − x y * /. b)  / a b 3 c 2 4  c d 5 a c d /  b 2 d 4 3. 62
CHƢƠNG 5: 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. 5.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 0, 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 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 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 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. 63
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ỉ h v sao cho d(s,t) = d(s,v) + a(v,t). Thực vậy, đỉnh v nhƣ vậy chính là đỉnh đi trƣớc đỉnh t trong đƣờng đi ngắn nhất từ s đến t. Tiếp theo ta lại có thể tìm đƣợc đỉnh u sao cho d(s,v) = d(s,u) + a(u,v), . . . Từ giả thiết về tính không âm của các trọng số dễ dàng suy ra rằng dãy t, v, u, . . . không chứa đỉnh lặp lại và kết thúc ở đỉnh s. Rõ ràng dãy thu đƣợc xác định (nếu lật ngƣợc thứ tự các đỉnh trong nó) đƣờng đi ngắn nhất từ s đến t. Từ đó ta có thuật toán sau đây để tìm đƣờng đi ngắn nhất từ s đến t khi biết độ dài của nó. Procedure Find_Path; (* Đầu vào: D[v] - - đỉnh đích; –ma trận trọng số trên các cung. Đầu ra: Mảng Stack chứa dãy đỉnh xác định đường đi ngắn nhất từ s đến t *) begin while v <> s do begin u:=đỉnh thoả mãn d[v]=d[u]+a[u,v]; v:=u; end; end; Chú ý rằng độ phức tạp tính toán của thuật toán là O(n2), 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 đi tìm kiếm. 64
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. 5.2. Đƣờng đ 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 d[v] của khoảng cách từ s đến tất cả các đỉnh 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. Procedure Ford_Bellman (* Đầu vào: Đồ thị có hướng G=(V,E) với n đỉnh, S Giả thiết: Đồ thị không có chu trình âm. Đầu ra: 65
*) begin (* Khởi tạo *) begin d[v]:=a[s,v]; Truoc[v]:=s; end; d[s]:=0; for k:=1 to n-2 do \ if d[v] > d[u] +a[u,v] then begin d[v]:=d[u]+a[u,v]; Truoc[v]:=u; end; end; Tính đúng đắn của thuật toán có thể chứng minh trên cơ sở trên nguyên lý tối ƣu của quy hoạch động. Rõ ràng là độ phức tạp tính toán của thuật toán là O(n3). Lƣu ý rằng chúng ta có thể chấm dứt vòng lặp theo k khi phát hiện trong quá trình thực hiện hai vòng lặp trong không có biến d[v] nào bị đổi giá trị. Việc này có thể xảy ra đối với k d[u] + a[u,v] then Begin D[v]:=d[u]+a[u,v]; Truoc[v]:=u; End; Trong trƣờng hợp này ta thu đƣợc thuật toán với độ phức tạp O(n,m). 66
T í 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 2 3 3 8 A= 1 -5 4 Hình 1. Minh họa thuật toán Ford_Bellman k d[1] d[2] d[3] d[4] d[5] Truoc[1] Truoc[2] Truoc[3] Truoc[4] Truoc[5] 0,1 1,1 3,1 1 0,1 1,1 4,2 4,2 -1,3 2 0,1 1,1 4,2 3,5 -1,3 3 0,1 1,1 4,2 3,5 S Bảng kết quả tính toán theo thuật toán Ford_Bellman Trong các mục tiếp theo chúng ta sẽ xét một số trƣờng hợp riêng của bài toán tìm đƣờng đi ngắn nhất mà để giải chúng có thể xây dựng những thuật toán hiệu quả hơn thuật toán 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. 67
5.3. 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. Procedure Dijstra; (* Đầu vào: Đồ thị có hướng G=(v,E) với n đỉnh, Đầu ra: V. *) Begin (* Khởi tạo *) begin d[v]:=a[s,v]; Truoc[v]:=s; end; d[s]:=0; T:=V\ (* Bước lặp *) begin T:=T\ 68
If d[v]>d[u]+a[u,v] then Begin d[v]:=d[u]+a[u,v]; Truoc[v]:=u; End; end; End; Địn 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). C ứng m n . Trƣớc hết ta chứng minh là thuật toán tìm đƣợc đƣờng đi ngắn nhất từ đỉnh s đến các đỉnh còn lại của đồ thị. Giả sử ở một bƣớc lặp nào đó các nhãn cố định cho ta độ dài các đƣờng đi ngắn nhất từ s đến các đỉnh có nhãn cố định, ta sẽ chứng minh rằng ở lần gặp tiếp theo nếu đỉnh u* thu đƣợc nhãn cố định d(u*) chính là độ dài đƣờng đi ngẵn nhất từ s đến u*. Ký hiệu S1 là tập hợp các đỉnh có nhãn cố định còn S2 là tập các đỉnh có nhãn tạm thời ở bƣớc lặp đang xét. Kết thúc mỗi bƣớc lặp nhãn tạm thời d(u*) cho ta độ dài của đƣờng đi ngắn nhất từ s đến u* không nằm trọng trong tập S1, tức là nó đi qua ít nhất một đỉnh của tập S2 S2 là đỉnh đầu tiên nhƣ vậy trên đƣờng đi này. Do trọng số trên các cung là không âm, nên đoạn đƣờng từ z đến u* có độ dài L>0 và d(z) < d(u*) – L < d(u*). Bất đẳng thức này là mâu thuẫn với cách xác định đỉnh u* là đỉnh có nhãn tạm thời nhỏ nhất. Vậy đƣờng đi ngắn nhất từ s đến u* phải nằm trọn trong S1, và vì thế, d[u*] là độ dài của nó. Do ở lần lặp đầu tiên S1 1 là đúng với bƣớc lặp đầu tiên. Theo qui nạp suy ra thuật toán cho ta đƣờng đi ngắn nhất từ s đến mọi đỉnh của đồ thị. Bây giờ ta sẽ đánh giá số phép toán cần thực hiện theo thuật toán. Ơû mỗi bƣớc lặp để tìm ra đỉnh u cần phải thực hiện O(n) phép toán, và để gán nhãn lại cũng cần thực hiện một số lƣợng phép toán cũng là O(n). thuật toán phải thực hiện n-1 bƣớc lặp, vì vậy thời gian tính toán của thuận toán cỡ O(n2). Định lý đƣợc chứng minh. Khi tìm đƣợc độ dài của đƣờng đi ngắn nhất d[v] thì đƣờng đi này có thể tìm dựa vào nhãn qui tắc giống nhƣ chúng ta đã xét trong chƣơng 3. T í dụ 2. Tìm đƣờng đi ngắn nhất từ 1 đến các đỉnh còn lại của đồ thị ở hình 2. 69
Hình 2. Minh họa thuật toán Dijkstra Kết quả tính toán theo thuật toán đƣợc trình bày theo bảng dƣới đây. Qui ƣớc viết hai thành phần của nhãn theo thứ tự: d[v]. Đỉnh đƣợc đánh dấu * là đỉnh đƣợc chọn để cố định nhãn ở bƣớc lặp đang xét, nhãn của nó không biến đổi ở các bƣớc tiếp theo, vì thế ta đánh dấu -. Bƣớc Đỉn Đỉn 2 Đỉn Đỉn 4 Đỉn Đỉn lặp 1 3 5 6 Khởi tạo 0,1 1,1* 1 - - 6,2 3,2* 8,2 2 - - 4,4* - 7,4 8,2 3 - - - 7,4 5,3* 4 - - - 6,6* - 5 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. Tƣơng tự nhƣ trong mục 2, dễ dàng mô tả thuật toán trong trƣờng hợp đồ thị cho bởi danh sách kề. Để có thể giảm bớt khối lƣợng tính toán trong việc xác định đỉnh u ở mỗi bƣớc lặp, có thể sử dụng thuật toán Heasort (tƣơng tự nhƣ trong chƣơng 5 khi thể hiện thuật toán Kruskal). Khi đó có thể thu đƣợc thuật toán với độ phức tạp tính toán là O(m log n). 70
5.4. T uật toán Floyd-Washall 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(n4) (nếu sử dụng thuật toán Ford_Bellman) hoặc O(n3) đố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 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. Procedure 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. *) begin (* Khởi tạo *) for i:=1 to n do for j:=1 to n do begin d[i,j]:=a[i.j]; p[i.j]:=i; end; (* Bước lặp *) for k:=1 to n do for i:=1 to n do for j:=1 to n do 71
if d[i,j]>d[i,k]+d[k,j] then begin d[i,j]+d[i,k]+d[k,j]; p[i,j]>p[k,j]; end; end; Rõ ràng độ phức tạp tính toán của thuật toán là O(n3). Kết thúc chƣơng này chúng ra trình bày một cách thể hiện thuật toán Dijkstra trên ngôn ngữ Pascal: (* CHƯƠNG TRÌNH TÌM ĐƯỜNG ĐI NGẮN NHẤT TỪ ĐỈNH S ĐẾN ĐỈNH T THEO THUẬT TOÁN DIJKSTRA *) uses crt; const max=50; var n, s, t:integer; chon:char; Truoc:array[1 max] of byte; d: array[1 max] of integer; a: array[1 max,1 max] of integer; final: array[1 max] of boolean; procedure Nhapsolieu; var f:text; fname:string; i,j:integer; begin write(‘Vao ten file du lieu can doc:’); readln(fname); assign(f,fname); reset(f); readln(f,n); for i:=1 to n do 72
for j:=1 to n do read(f, a[i,j]; close(f); end; procedure Insolieu; var i,j:integer; begin writeln(‘So dinh cua do thi:’,n); writeln(‘Ma tran khoang cach:’); for i:=1 to n do begin for j:=1 to n do write(a[i,j]:3,’ ‘); writeln; end; end; Procedure Inketqua; Var i,j:integer; begin writeln(‘Duong di ngan nhat tu ‘,s,’ den ‘,t); while i<> s do begin i:=Truoc[i]; end; end; Procedure Dijkstra; Var U,v,minp:integer; Begin Write(‘Tim duon di tu s=’); Readln(s); 73
Write(‘ den t=’); Readln(t); For v:=1 to n do Begin d[v]:=a[s,v]; Truoc[v]:=s; Filal[v]:=false; End; Truoc[s]:=0; D[s]:=0; Final[s]:=true; While not final[t] do (* Buoc lap *) Begin minp:=maxint; for v:=1 to n do if (not final[v]) ans minp>d[v]) then begin u:=v; minp:=d[v]; end; final[u]:=true; if not final[t] then for v:=1 to n do if (not final[v]) and (d[u]+a[u,v]<d[v]) then begin d[v]:=d[u]+a[u,v]; Truoc[v]:=u; end; End; end; Procedure Menu; Begin 74
Clrscr; Writeln(‘1. Nhap du lieu tu file’); Writeln(‘2. Giai bai toan’); Writeln(‘3. Ket thuc’); Writeln(‘ ‘); Write(‘Hay chon chuc nang:’): End; (* Chuong trinh chinhs *) Begin Repeat Menu; Chon:=readkey; Writeln(chon); Case chon of ‘1’:Nhapsolieu; ‘2’: begin Insolieu; Dijkstra; Inketqua; ‘3’:exit; end; Until false; End. 5.5. T uật toán Bellman-Ford Bây giờ ta xét trƣờng hợp riêng thứ hai của bài toán đƣờng đi ngắn nhất, mà để giải nó có thể xây dựng thuật toán với độ phức tạp tính toán O(n2), đó là khi đồ thị không có chu trình (còn trọng số trên các cung có thể là các số thực tuỳ ý). Trƣớc hết ta chứng minh định lý sau. Địn lý 2. Giả sử G là đồ thị không có chu trình. Khi đó các đỉnh của nó có thể đánh số sao cho mỗi cung của đồ thị chỉ hƣớng từ đỉnh có chỉ số nhỏ hơn đến đỉnh có chỉ số lớn hơn, nghĩa là mỗi cung của nó có sự biểu diễn dƣới dạng (v[i], v[j]), trong đó i<j. T í dụ 3. Đồ thị trong hình 3 có các đỉnh số thoả mãn điều kiện nêu trong định lý. 75
Hình 3. Đồ thị không có chu trình Để chứng minh định lý ta mô tả thuật toán sau đây, cho phép tìm ra cách đánh số thoả mãn điều kiện định lý. Procudure Numbering; (* Đầu vào: Đồ thị có hướng G=(V,E) với n đỉnh không chứa chu trình được cho bởi danh Đầu ra: Với mỗi đ Với mọi cung (u,v) của đồ thị ta đều có NR [u] < NR [v] *) Begin (* Tính Vao[v]=deg-(v) *) num:=0; whi begin num:=num+1; NR[u]:=num; begin Vao[v]:=Vao[v]-1; 76
end; end; End; Thuật toán đƣợc xây dựng dựa trên ý tƣởng rất đơn giản sau: rõ ràng trong đồ thị không có chu trình bao giờ cũng tìm đƣợc đỉnh có bán bậc vào bằng 0 (không có cung đi vào). Thực vậy, bắt đầu từ đỉnh v1 nếu có cung đi vào nó từ v2 thì ta lại chuyển sang xét đỉnh v2 . Nếu có cung từ v3 đi vào v2, thì ta lại chuyển sang xét đỉnh v3. . .Do đồ thị không có chu trình nên sau một số hữu hạn lần chuyển nhƣ vậy ta phải đi đến đỉnh không có cung đi vào. Thoạt tiên, tìm các đỉnh nhƣ vậy của đồ thị. Rõ ràng ta có thể đánh số chúng theo thứ tự tuỳ ý bắt đầu từ 1. Tiếp theo, loại bỏ khỏi đồ thị những đỉnh đã đƣợc đánh số cùng các cung đi ra khỏi chúng, ta thu đƣợc đồ thị mới cũng không có chu trình, và thủ tục đƣợc lặp với đồ thị mới này. Quá trình đó sẽ đƣợc tiếp tục cho đến khi tất cả các đỉnh của đồ thị đƣợc đánh số. Chú ý: Rõ ràng trong bƣớc khởi tạo ra phải duyệt qua tất cả các cung của đồ thị khi tính bán bậc vào của các đỉnh, vì vậy ở đó ta tốn cỡ O(m) phép toán, trong đó m là số cung của đồ thị. Tiếp theo, mỗi lần đánh số một đỉnh, để thực hiện việc loại bỏ đỉnh đã đánh số cùng với các cung đi ra khỏi nó, chúng ta lại duyệt qua tất cả các cung này. Suy ra để đánh số tất cả các đỉnh của đồ thị chúng ta sẽ phải duyệt qua tất cả các cung của đồ thị một lần nữa. Vậy độ phức tạp của thuật toán là O(m). Thuật toán có thể áp dụng để kiểm tra xem đồ thị có chứa chu trình hay không? Thực vậy, nếu kết thúc thuật toán vẫn còn có đỉnh chƣa đƣợc đánh số (num<n) thì điều đó có nghĩa là đồ thị chứa chu trình. Do có thuật toán đánh số trên, nên khi xét đồ thị không có chu trình ta có thể giả thiết là các đỉnh của nó đƣợc đánh số sao cho mỗi cung chỉ đi từ đỉnh có chỉ số nhỏ đến đỉnh có chỉ số lớn hơn. Thuật toán tìm đƣờng đi ngắn nhất trên đồ thị không có chu trình đƣợc mô tả trong sơ đồ sau đây. Procedure Critical_Path; (* Tìm đường đi ngắn nhất từ đỉnh nguồn đến tất cả các đỉnh còn lại trên đô thị không có chu trình *) Đầu vào: 77