Bài giảng Lý thuyết đồ thị (Bản đẹp)

Nội dung text: Bài giảng Lý thuyết đồ thị (Bản đẹp)

1. 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
2. 11.5. Tên học phần: Lý thuyết đồ thị Loại học phần: 2 Bộ môn phụ trách giảng dạy: Khoa học Máy tính Khoa phụ trách: CNTT Mã học phầ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 Điều kiện tiê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 tiêu của học phầ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ội dung chủ 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ội dung chi tiết của học phần: PHÂN PHỐI SỐ TIẾT TÊN CHƢƠNG MỤC TS LT TH/Xemina BT KT Chƣơng 1. Các khái niệm cơ bản của lý thuyết đồ thị 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ị Chƣơng 2. Các thuật toán tìm kiếm trên đồ thị 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 Chƣơng 3. Đồ thị Euler và đồ thị Haminton 10 6 4 0 0 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 i
3. PHÂN PHỐI SỐ TIẾT TÊN CHƢƠNG MỤC TS LT TH/Xemina BT KT 3.2.4. Một số vấn đề khác về đường đi và chu trình Haminton Chƣơng 4. Cây khung của đồ thị 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 Chƣơng 5. Bài toán đƣờng đi ngắn nhấ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 Chƣơng 6. Bài toán luồng cực đại 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. Đường tăng 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 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 Nhiệm vụ của sinh viê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ài liệu họ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ình thức và tiêu chuẩn đánh giá sinh viê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ộ Thang điểm: Thang điểm chữ A, B, C, D, F Điểm đánh giá học phần: Z = 0,3X + 0,7Y. ii
4. CHƢƠNG I CÁC KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ 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. ĐỊNH NGHĨA ĐỒ THỊ Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này. Chúng ta phân biệt các loại đồ thị khác nhau bởi kiểu và số lượng cạnh nối hai đỉnh nào đó của đồ thị. Để 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 3
5. 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 Đị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. 4
6. 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 5
7. 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 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. 6
8. 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. 7
9. CHƢƠNG 2 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY VI TÍNH Để lưu trữ đồ thị và thực hiện các thuật toán khác nhau với đồ thị trên máy tính cần phải tìm những cấu trúc dữ liệu thích hợp để mô tả đồ thị. Việc chọn cấu trúc dữ liệu nào để biểu diễn đồ thị có tác động rất lớn đến hiệu quả của thuật toán. Vì vậy, việc chọn lựa cấu trúc dữ liệu để biểu diễn đồ thị phụ thuộc vào từng tình huống cụ thể (bài toán và thuật toán cụ thể). Trong mục này chúng ta sẽ xét một số phương pháp cơ bản được sử dụng để biểu diễn đồ thị trên máy tính, đồ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. MA TRẬN KỀ. MA TRẬN TRỌNG SỐ Xét đơn đồ thị vô hướng G=(V,E), với tập đỉnh V= 1, 2,. . . ,n , tập cạnh E= e1, e2,. . .,em . Ta gọi ma trận kề của đồ thị G là ma trận. A= ai,j : i,j=1, 2,. . . ,n Với các phần tử được xác định theo qui tắc sau đây: ai, j = 0, nếu (i,j) E và ai,j = 1 , nếu (i,j) E, i, j=1, 2,. . .,n. Thí dụ 1. Ma trận trận kề của đồ thị vô hướng cho trong hình 1 là: 1 2 3 4 5 6 1 0 1 1 0 1 0 2 1 0 1 0 1 0 8
10. 3 1 1 0 1 0 0 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). 3) nếu ký hiệu p aịj , i,j=1, 2,. . . ,n là phần tử của ma trận 9
11. Ap =A.A. . .A p thừa số Khi đó p 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 10
12. Lưu ý rằng ma trận kề của đồ thị có hướng không phải là ma trận đối xứng. Chú ý: Trên đây chúng ta chỉ xét đơn đồ thị. Ma trận kề của đa đồ thị có thể xây dựng hoàn toàn tương tự, chỉ khác là thay vì ghi 1 vào vị trí a[i,j] nếu (i,j) là cạnh của đồ thị, chúng ta sẽ ghi k là số cạnh nối hai đỉnh i, j. Trong rất nhiều vấn đề ứng dụng của lý thuyết đồ thị, mỗi cạnh e=(u,v) của đồ thị được gán với một con số c(e) (còn viết là c(u,v) gọi là trọng số của cạnh e. Đồ thị trong trường hợp như vậy được gọi là đồ thị có trọng số. Trong trường hợp đồ thị có trọng số, thay vì mà trận kề, để biểu diễn đồ thị ta sử dụng ma trận trọng số. C= {c[i,j], i,j=1, 2,. . .,n} với c[i,j]=c(i,j) nếu (i,j) E và c[i,j]= nếu (i,j) E trong đó số  , tuỳ từng trường hợp cụ thể, có thể được đặt bằng một trong các giá trị sau: 0, + , - . Ưu điểm lớn nhất của phương pháp biểu diễn đồ thị bằng ma trận kề (hoặc ma trận trọng số) là để trả lời câu hỏi: Hai đỉnh u,v có kề nhau trên đồ thị hay không, chúng ta chỉ phải thực hiện một phép so sánh. nhược điểm lớn nhất của phương pháp này là: không phụ thuộc vào số cạnh của đồ thị, ta luôn phải sử dụng n2 đơn vị bộ nhớ để lưu trữ ma trận kề của nó. 11
13. CHƢƠNG 3 CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ VÀ ỨNG DỤNG 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)) tìm được các hằng sô C, N ≥ 0 sao cho 12
14. 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)) tìm được các hằng số C,N >0 sao cho 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)). 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ừ đỉ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*) 13
15. Begin Tham_dinh(v); Chuaxet[v]:=false; For u Ke(v) do 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). 14
16. Để đá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: 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ố. 15
17. 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). CHƢƠNG 4 ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON Trong chương này chúng ra sẽ nghiên cứu hai dạng đồ thị đặc biệt là đồ thị Euler và đồ thị Hamilton. Dưới đây, nếu không có giải thích bổ sung, thuật ngữ đồ thị được dùng để chỉ chung đa đồ thị vô hướng và có hướng, và thuật ngữ cạnh sẽ dùng để chỉ chung cạnh của đồ thị vô hướng cũng như cung của đồ thị có hướng. 1. ĐỒ THỊ EULER 16
18. Đị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. 17
19. Hình 2. Đồ thị H1, H2, H3 Điều kiện cần và đủ để một đồ thị là một đồ thị Euler được Euler tìm ra vào năm 1736 khi ông giải quyết bài toán hóc búa nổi tiếng thế giới thời đó về bảy cái cầu ở thành phố Konigsberg và đây là định lý đầu tiên của lý thuyết đồ thị. Định lý 1 (Euler). Đồ thị vô hướng liên thông G là đồ thị Euler khi và chỉ khi mọi đỉnh của G đều có bậc chẵn. Để 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 v1 v2 . . . 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 18
20. đầ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. 19
21. 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. Procedure Euler_Cycle; Begin STACK:= ; CE:= ; Chon u la mot dinh nao do cua do thi; 20
22. STACK u; While STACK  then Begin Y:=dinh dau tien trong danh sach Ke(x); STACK y; (* loai bo canh (x,y) khoi do thi *) Ke(x):=Ke(x)\ y ; Ke(y):=Ke(y)\ x ; End Else Begin x STACK; CE x; End; End; End; 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. 21
23. 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 22
24. Deg+(v)=deg- (v),  v V. 23
25. CHƢƠNG 5 CÂY VÀ CÂY KHUNG CỦA ĐỒ THỊ Đồ 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 1. CÂY VÀ CÁC TÍNH CHẤT CƠ BẢN CỦA CÂY Đị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: 24
26. (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: (1) (2) (3) (4) (5) (6) (1) (1) (2) Theo định nghĩa T không chứa chu trình. Ta sẽ chứng minh bằng qui nạp theo số đỉ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. 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. (2) (3) Ta chứng minh bằng phản chứng. Giả sử T không liên thông. Khi đó T phân rã 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ì 25
27. 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. (3) (4) Việc loại bỏ một cạnh bất kỳ khỏi T dẫn đến đồ thị với n đỉnh và n-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. (4) (5) Do T là liên thông nên hai đỉnh bất kỳ của nó được nối với nhau bởi một đường đi đơ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. (5) (6) T không chứa chu trình, bởi vì thế nếu có chu trình thì hoá ra tìm được cặp đỉ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. (6) (1) Giả sử T không liên thông. Khi đó gồm ít ra là 2 thành phần liên thông. Vì vậy, nếu thêm vào T một cạnh nối hai đỉnh thuộc hai thành 26
28. 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. 27
29. CHƢƠNG 6 BÀI TOÁN ĐƢỜNG ĐI NGẮN NHẤT Trong các ứng dụng thực tế, vài toán tìm đường đi ngắn nhất giữa hai đỉnh của một đồ thị liên thông có một ý nghĩa to lớn. Có thể dẫn về bài toán như vậy nhiều bài toán thực tế quan trọng. Ví dụ, bài toán chọn một hành trình tiết kiệm nhất (theo tiêu chuẩn hoặc khoảng cách hoặc thời gian hoặc chi phí) trên một mạng giao thông đường bộ, đường thủy hoặc đường không; bài toán chọn một phương pháp tiết kiệm nhất để đưa ra một hệ thống động lực từ trạng thái xuất phát đến trạng một trạng thái đích, bài toán lập lịch thi công các công các công đoạn trong một công trình thi công lớn, bài toán lựa chọn đường truyền tin với chi phí nhỏ nhất trong mạng thông tin, v.v Hiện nay có rất nhiều phương pháp để giải các bài toán như vậy. Thế nhưng, thông thường, các thuật toán được xây dựng dựa trên cơ sở lý thuyết đồ thị tỏ ra là các thuật toán có hiệu quả cao nhất. Trong chương này chúng ta sẽ xét một số thuật toán như vậy. 1. CÁC KHÁI NIỆM MỞ ĐẦU Trong chương này chúng ta chỉ xét đồ thị có hướng G =(V,E), |V|=n, |E|=m với các cung được gán trọng số, nghĩa là, mỗi cung (u,v) E của nó được đặt tương ứng với một số thực a(u,v) gọi là trọng số của nó. Chúng ta sẽ đặt a(u,v) = , nếu (u,v) E. Nếu dãy v0, v1, . . ., vp là một đường đi trên G, thì độ dài của nó được định nghĩa là tổng sau p  a(vi-1, vi). i=1 28
30. tức là, độ dài của đường đi chính là tổng của các trọng số trên các cung của nó. (Chú ý rằng nếu chúng ta gán trọng số cho tất cả cung đều bằng 1, thì ta thu được định nghĩa độ dài của đường đi như là số cung của đường đi giống như trong các chương trước đã xét). Bài toán tìm đường đi ngắn nhất trên đồ thị dưới dạng tổng quát có thể phát biểu như sau: tìm đường đi có độ dài nhỏ nhất từ một đỉnh xuất phát s V đến đỉnh cuối (đích) t V. Đường đi như vậy ta sẽ gọi là đường đi ngắn nhất từ s đến t còn độ dài của nó ta sẽ ký hiệu là d(s,t) và còn gọi là khoảng cách từ s đến t (khoảng cách định nghĩa như vậy có thể là số âm). Nếu như không tồn tại đường đi từ s đến t thì ta sẽ đặt d(s,t)= . Rõ ràng, nếu như mỗi chu trình trong đồ thị đều có độ dài dương, trong đường đi ngắn nhất không có đỉnh nào bị lặp lại (đường đi không có đỉnh lặp lại sẽ gọi là đường đi cơ bản). Mặt khác nếu trong đồ thị có chu trình với độ dài âm (chu trình như vậy để gọi ngắn gọn ta gọi là chu trình âm) thì khoảng cách giữa một số cặp đỉnh nào đó của đồ thị có thể là không xác định, bởi vì, bằng cách đi vòng theo chu trình này một số đủ lớn lần, ta có thể chỉ ra đường đi giữa các đỉnh này có độ dài nhỏ hơn bất cứ số thực cho trước nào. Trong những trường hợp như vậy, có thể đặt vấn đề tìm đường đi cơ bản ngắn nhất, tuy nhiên bài toán đặt ra sẽ trở nên phức tạp hơn rất nhiều, bởi vì nó chứa bài toán xét sự tồn tại đường đi Hamilton trong đồ thị như là một trường hợp riêng. Trước hết cần chú ý rằng nếu biết khoảng cách từ s đến t, thì đường đi ngắn nhất từ s đến t, trong trường hợp trọng số không âm, có thể tìm được một cách dễ dàng. Để tìm đường đi, chỉ cần để ý là đối với cặp đỉnh s, t V tuỳ ý (s <> t) luôn tìm được đỉnh v sao cho d(s,t) = d(s,v) + a(v,t). 29
31. 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] - khoảng cách từ đỉnh s đến tất cả các đỉnh còn lại v V; - đỉnh đích; a[u,v], u, v V –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 stack:= ; stack t; v:=t; 30
32. while v <> s do begin u:=đỉnh thoả mãn d[v]=d[u]+a[u,v]; stack u; 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 bày trong chương 3: dùng biến mảng Truoc[v], v V, để ghi nhớ đỉnh đi trước v trong đường đi tìm kiếm. Cũng cần lưu ý thêm là trong trường hợp trọng số trên các cạnh là không âm, bài toán tìm đường đi ngắn nhất trên đồ thị vô hướng có thể dẫn về bài toán trên đồ thị có hướng, bằng cách thay đổi mỗi cạnh của nó bởi nó bởi hai cung có hướng ngược chiều nhau với cùng trọng số là trọng số của các cạnh tương ứng. Tuy nhiên, trong trường hợp có trọng số âm, việc thay như vậy có thể dẫn đến chu trình âm. 31
33. CHƢƠNG 7 BÀI TOÁN LUỒNG CỰC ĐẠI TRONG MẠNG Bài toán luồng cực đại trong mạng là một trong số bài toán tối ưu trên đồ thị tìm được những ứng dụng rộng rãi trong thực tế cũng như những ứng dụng thú vị trong lý thuyết tổ hợp. Bài toán được đề xuất vào đầu năm 1950, và gắn liên với tên tuổi của hai nhà toán học Mỹ là Ford và Fulkerson. Trong chương này chúng ra sẽ trình bày thuật toán Ford và Fulkerson để giải bài toán đặt ra và nêu một sô ứng dụng của bài toán. 1. MẠNG. LUỒNG TRONG MẠNG. BÀI TOÁN LUỒNG CỰC ĐẠI Định nghĩa 1. Ta gọi mạng là đồ thị có hướng G=(V,E), trong đó duy nhất một đỉnh s không có cung đi vào gọi là đỉnh phát, duy nhất một đỉnh t không có cung đi ra gọi là điểm thu và mỗi cung e=(v,w) E được gán với một số không âm c(e) =c(v,w) gọi là khả năng thông qua của cung e. Để thuận tiện cho việc trình bày ta sẽ qui ước rằng nếu không có cung (v,w) thì khả năng thông qua c(v,w) được gán bằng 0. Định nghĩa 2. Giả sử cho mạng G=(V,E). Ta gọi mạng f trong mạng G=(V,E) ;là ánh xạ f: E R+ gán cho mỗi cung e=(v,w) E một số thực không âm f(e)=f(v,w), gọi là luồng trên cung e, thoả mãn các điểu kiện sau: Luồng trên cung e E không vượt quá khả năng thông qua của nó: 0≤f(e)≤c(e), Điều kiện cân bằng luồng trên mỗi đỉnh của mạng: Tổng luồng trên các cung đi vào đỉnh v bằng tổng luồng trên các cung đi ra khỏi đỉnh v, nếu v#s, t: 32
34. Div f (v) =  f(w,v) -  f(v,w) = 0 w  - (v) w  + (v) trong đo  - (v) – tập các đỉnh của mạng mà từ đó có cung đến v,  + (v) - tập các đỉnh của mạng mà từ v có cung đến nó:  - (v) = w V : (w,v) E ,  + (v) = w V : (v,w) E . Giá trị của luồng f là số Val(f) =  f(s,w ) =  f(w,t). w  + (s) w  - (t) Bài toán luồng cực đại trong mạng: Cho mạng G(V,E). Hãy tìm luồng f* trong mạng với giá trị luồng val(f*) là lớn nhất. Luồng như vậy ta sẽ gọi là luồng cực đại trong mạng. Bài toán như vậy có thể xuất hiện trong rất nhiều ứng dụng thực tế. Chẳng hạn khi cần xác định cường độ lớn nhất của dòng vận tải giữa hai nút của một bản đồ giao thông. Trong ví dụ này lời giải của bài toán luồng cực đại sẽ chỉ cho ta các đoạn đường đông xe nhất và chúng tạo thành "chỗ hẹp" tương ứng với dòng giao thông xét theo hai nút được chọn. Một ví dụ khác là nếu xét đồ thị tương ứng với một hệ thống đường ống dẫn dầu. Trong đó các ống tương ứng với các cung, điểm phát có thể coi là tầu chở dầu, điểm thu là bể chứa, còn những điểm nối giữa các ống là các nút của đồ thị. Khả năng thông qua của các cung tương ứng với tiết diện của các ống. Cần phải tìm luồng dầu lớn nhất có thể bơm từ tàu chở dầu vào bể chứa. 33
35. TÀI LIỆU THAM KHẢO 1. 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. 2. 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. 3. Kenneth Rosen. Toán học rời rạc và ứng dụng trong tin học. NXB KHKT Hà nội. 1998. 34