Luận văn Nghiên cứu, xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất với dữ liệu mờ dạng khoảng

85 trang hapham 2020

Download

Bạn đang xem 20 trang mẫu của tài liệu "Luận văn Nghiên cứu, xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất với dữ liệu mờ dạng khoảng", để 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:

luan_van_nghien_cuu_xay_dung_thuat_toan_giai_bai_toan_tim_du.doc

Nội dung text: Luận văn Nghiên cứu, xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất với dữ liệu mờ dạng khoảng

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG HỌC VIỆN KỸ THUẬT QUÂN SỰ PHAN NHƯ MINH NGHIÊN CỨU, XÂY DỰNG THUẬT TOÁN GIẢI BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT VỚI DỮ LIỆU MỜ DẠNG KHOẢNG Chuyên ngành: Hệ thống thông tin LUẬN VĂN THẠC SĨ KỸ THUẬT Hà Nội - Năm 2011
BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG HỌC VIỆN KỸ THUẬT QUÂN SỰ PHAN NHƯ MINH NGHIÊN CỨU, XÂY DỰNG THUẬT TOÁN GIẢI BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT VỚI DỮ LIỆU MỜ DẠNG KHOẢNG Chuyên ngành: Hệ thống thông tin Mã số: 60 48 05 LUẬN VĂN THẠC SĨ KỸ THUẬT Hà Nội - Năm 2011
CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI HỌC VIỆN KỸ THUẬT QUÂN SỰ Cán bộ hướng dẫn chính: PGS.TS. Nguyễn Thiện Luận Cán bộ chấm phản biện 1: Cán bộ chấm phản biện 2: Luận văn thạc sĩ được bảo vệ tại: HỘI ĐỒNG CHẤM LUẬN VĂN THẠC SĨ HỌC VIỆN KỸ THUẬT QUÂN SỰ Ngày tháng năm 2011
HỌC VIỆN KỸ THUẬT QUÂN SỰ CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM PHÒNG SAU ĐẠI HỌC Độc lập – Tự do – Hạnh phúc Hà Nội, ngày 12 tháng 05 năm 2011 NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên: PHAN NHƯ MINH Giới tính: Nam Ngày, tháng, năm sinh: 23/09/1978 Nơi sinh: Vĩnh Phúc Chuyên ngành: Hệ thống thông tin Mã số: 60 48 05 I- TÊN ĐỀ TÀI: Nghiên cứu, xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất với dữ liệu mờ dạng khoảng. II- NHIỆM VỤ VÀ NỘI DUNG: Trên cơ sở nghiên cứu, thuật toán Dijkstra: Mở rộng, cải tiến áp dụng cho bài toán (Tìm đường đi ngắn nhất) với các dữ liệu về có trọng số dạng khoảng. Đặt ra và giải quyết bài toán tìm đường đi ngắn nhất với độ dài các cung là số mờ dạng khoảng III- NGÀY GIAO NHIỆM VỤ: 12/10/2010 IV- NGÀY HOÀN THÀNH NHIỆM VỤ: 05/05/2011 V- CÁN BỘ HƯỚNG DẪN: PGS.TS. Nguyễn Thiện Luận CÁN BỘ HƯỚNG DẪN CHỦ NHIỆM BỘ MÔN QL CHUYÊN NGÀNH PGS.TS. Nguyễn Thiện Luận Nội dung và đề cương luận văn thạc sĩ đã được Hội đồng chuyên ngành thông qua. Ngày tháng năm 2011 TRƯỞNG PHÒNG SĐH TRƯỞNG KHOA QL NGÀNH
MỤC LỤC Trang Trang phụ bìa Nhiệm vụ luận văn Mục lục Tóm tắt luận văn Danh mục hình vẽ Danh mục bảng: MỞ ĐẦU 1 Chương I LÝ THUYẾT ĐỒ THỊ VÀ THUẬT TOÁN GIẢI BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT CÓ TRỌNG SỐ XÁC ĐỊNH 1.1. Khái niệm cơ bản về lý thuyết đồ thị 5 1.1.1. Các định nghĩa về đồ thị: 5 1.1.2. Bậc của đồ thị 8 1.1.3. Biểu diễn đồ thị bằng ma trận 10 1.1.4. Tính liên thông 11 1.1.5. Đường đi Euler và đồ thị Euler 17 1.1.6. Bài toán người phát thư Trung Hoa: 21 1.1.7. Đường đi Hamilton và đồ thị Hamilton 23 1.2. Đồ thị có trọng số và bài toán tìm đường đi ngắn nhất 28 1.2.1. Bài toán tìm đường đi ngắn nhất: 29 1.2.2. Thuật toán Dijkstra: 30 1.2.3. Bài toán áp dụng: 31 1.2.3. Thuật toán Floyd: 33
Chương 2 LÝ THUYẾT MỜ VÀ ỨNG DỤNG BÀI TOÁN QUY HOẠCH TUYẾN TÍNH DẠNG KHOẢNG 2.1. Khái niệm tập mờ 36 2.1.1. Định nghĩa tập mờ 36 2.1.2. Một số khái niệm của tập mờ 38 2.1.3. Các ví dụ về tập mờ 39 2.2. Các phép toán trên tập mờ 41 2.2.1. Các phép toán trên tập hợp 41 2.2.2. Khái niệm hàm liên thuộc 42 2.3. Mệnh đề và công thức 43 2.3.1. Khái niệm mệnh đề 43 2.3.2. Các kí hiệu 43 2.3.3. Các phép toán trên mệnh đề 44 2.3.4. Các tính chất 47 2.4. Suy luận xấp xỉ dựa trên logic mờ 48 2.5. Ứng dụng logic mờ xây dựng bài toán tối ưu mờ 50 2.5.1. Tối ưu mờ 50 Chương 3 XÂY DỰNG GIẢI THUẬT GIẢI BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT BIỂU DIỄN CUNG ĐƯỜNG ĐI LÀ SỐ MỜ DẠNG KHOẢNG 3.1. Mô hình bài toán 55 3.2. Ví dụ 56 3.3. Bài toán tìm đường đi ngắn nhất có các cung mờ 56 3.3.1. Xây dựng tập mờ 57 3.3.2. Miền xác định của tập mờ: 57 3.3.3. Miền tin cậy của tập mờ 58 3.3.4. Miền biên của tập mờ 58 3.4. Khái niệm số mờ 58
3.4.1. Định nghĩa số mờ 58 3.4.2. Số mờ dạng tam giác: 59 3.4.3. Số mờ dạng hình thang: 59 3.5. Một số phương pháp giải quyết bài toán 61 3.5.1. Phép toán thực hiện trên số mờ tam giác. 61 3.6. Ví dụ áp dụng bài toán: 62 Chương 4 CÀI ĐẶT THỬ NGHIỆM 4.1. Một số giao diện của chương trình 64 4.1.1. Giao diện chính của chương trình 64 4.1.2. Các bước thực hiện chương trình 64 4.1.3. Các chức năng chính của chương trình 64 4.1.3. Các chức năng chính của chương trình 65 4.2. Cài đặt – thử nghiệm 69 4.3. Đánh giá hiệu quả thuật toán đã xây dựng 71 KẾT LUẬN VÀ KIẾN NGHỊ 72 1. Kết luận 72 2. Kiến nghị 73 TÀI LIỆU THAM KHẢO 74
Tóm tắt luận văn Họ và tên học viên: Phan Như Minh Lớp: Hệ thống thông tin Khoá: 21 Cán bộ hướng dẫn: PGS.TS. Nguyễn Thiện Luận Tên đề tài: Nghiên cứu, xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất với dữ liệu mờ dạng khoảng. Tóm tắt: Nghiêu cứu ứng dụng logic mờ trong tin học và thuật toán tìm đường đi ngắn nhất có cung là trọng số xác định từ đó xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất có cung với số mờ dạng khoảng. Đưa ra mô phỏng thuật toán giải bài toán tìm đường đi ngắn nhất với trọng số là số mờ dạng khoảng từ giải thuật Dijsktra và lý thuyết mờ quy hoạch tuyến tính dạng khoảng.  Kiểm tra hàm liên thuộc.  Tìm ra tất cả các đường đi từ các cung mờ.  Tìm ra độ dài cung mờ nhỏ nhất giá trị Lmin.  Tính ra độ tương tự.  Tìm ra đường đi ngắn nhất từ các cung mờ với độ tương tự cao nhất.
DANH MỤC HÌNH VẼ Hình 1.1 Đơn đồ thị, giả đồ thị 6 Hình 1.2. Đồ thị có hướng và Đa đồ thị có hướng 7 Hình 1.3. Bậc của đồ thị 8 Hình 1.4. Bậc của đồ thị có hướng 9 Hình 1.5. Biểu diễn đồ thị bằng ma trận liền kề 10 Hình 1.6. Biểu diễn đồ thị bằng ma trận liền kề 10 Hình 1.7. Biểu diễn đồ thị bằng ma trận liên thuộc 11 Hình 1.8. Biểu diễn đường đi sơ cấp 12 Hình 1.9. Biểu diễn đồ thị G và G’ 12 Hình 1.10. Biểu diễn các đỉnh cắt là v, w, s và các cầu là (x,v), (w,s) 13 Hình 1.11. Đồ thị G là liên thông mạnh đồ thị G’ là liên thông yếu 15 Hình 1.12. Biểu diễn Đường đi Euler và đồ thị Euler 17 Hình 1.13. Đồ thị Euler và đồ thị nửa Euler 18 Hình 1.14. Xây dựng đường đi 18 Hình 1.15. Xây dựng đường đi 19 Hình 1.16. Xây dựng đường đi 20 Hình 1.17. Xây dựng đường đi GT và G 22 Hình 1.18. Chu trình sơ cấp chứa tất cả các đỉnh của đồ thị 24 Hình 1.19. Chu trình sơ cấp chứa tất cả các đỉnh của đồ thị 25 Hình 1.20. Đồ thị Hamilton 27 Hình 1. 21. Đồ thị phân đôi 28 Hình 1.22. Tìm đường đi ngắn nhất d(a,v) của đồ thị 29
Hình 2.1. Tập mờ 34 Hình 2. 2. Đồ thị hàm liên thuộc của tập mờ 35 Hình 2.3. Miền của tập mờ 37 Hình 2.4. Đồ thị đánh giá 38 Hình 2. 5. Đồ thị đánh giá nhiệt độ 38 Hình 2.6. Ví dụ hàm liên thuộc 41 Bảng 2.7. Mô hình suy diễn xấp sỉ 48 Bảng 1.8. Suy luận xấp xỉ 46 Bảng 1.9. Bảng điều kiện suy diễn xấp sỉ 47 Hình 3.1. Đồ thị G(u,v) có hướng 54 Hình 3.2. Miền biên của tập mờ 56 Hình 3.3. Số mờ dạng tam giác 57 Hình 3.4. Số mờ dạng hình thang 58 Hình 3.4.Biểu diễn số mờ dạng hình thang 58 Hình 3.5.Tìm đường đi ngắn nhất 60 Hình 4.1. Giao diện chính của chương trình 62 Hình 4.2. Các bước thực hiện 62 Hình 4.3. Mô phỏng thuật toán 63 Hình 4.4. Chọn số đỉnh 63 Hình 4.5. Chọn cung đường đi 64 Hình 4.6. Nhập các cung a, b, c và thông báo 64 Hình 4.7. Tìm tất cả các đường đi 65 Hình 4.7. Tính giá trị Lmin 65 Hình 4.8. Bảng độ tương tự 66 Hình 4.9. Bảng thông báo kết quả tìm được 66 Hình 4.10. Chọn đỉnh nhập dữ liệu 67 Hình 4.11. Kết quả kiểm tra xây dựng hàm liên 67
Hình 4.12. Kết quả tất cả các đường đi 68 Hình 4.13. Bảng kết quả tìm Lmin 68 Hình 4.14. Bảng kết quả độ tương tự 68 Hình 4.15. Bảng kết quả đường đi ngắn nhất 68
DANH MỤC BẢNG Bảng 1.1. Kết quả tính toán theo thuật toán Dijkstra 31 Bảng 2.1. Phép phủ định 42 Bảng 2.2. Phép hoặc 43 Bảng 2.3. Phép nhân logic 43 Bảng 2.4. Phép cộng XOR 44 Bảng 2.5. Phép kéo theo 44 Bảng 2.6. Phép tương đương 45 Bảng 2.7. Bảng chân lý 45 Bảng 2.8. Suy luận xấp xỉ 46 Bảng 2.9. Bảng điều kiện suy diễn xấp sỉ 47 Bảng 3.1. Độ tương tự giữa hai số mờ 60
1 MỞ ĐẦU 1. Lý do chọn đề tài Trong những năm gần đây, các phương pháp tối ưu hoá ngày càng được áp dụng sâu rộng và hiệu quả vào các ngành giao thông vận tải, mạng viễn thông, kinh tế, kỹ thuật, công nghệ thông tin và các ngành khoa học khác. Các phương pháp tối ưu là công cụ đắc lực giúp người làm quyết định có những giải pháp tốt nhất về định lượng và định tính. Một trong những lớp bài toán tối ưu đầu tiên được nghiên cứu là thuật toán giải bài toán tìm đường đi ngắn nhất có trọng số xác định. Bài toán tìm đường đi ngắn nhất là vấn đề quan trọng trong lý thuyết đồ thị, nó đã được nghiên cứu từ lâu và có nhiều ứng dụng trong nhiều ngành khoa học nói chung, khoa học máy tính và hệ thống thông tin nói riêng. Nhiều giải thuật (Dijkstra, Bellman-Ford, Floyd ) đã được phát triển để tìm đường đi ngắn nhất và ngày nay đã được nhiều nhà nghiên cứu nhằm cải tiến xây dựng giải thuật giải bài toán tìm đường đi ngắn nhất với dữ liệu mờ dạng khoảng. Bài toán tìm đường đi ngắn nhất cũng được phát triển rộng rãi và trở thành một chuyên ngành toán học từ những năm 1950. Giải đáp những câu hỏi đặt ra mà tìm đường đi ngắn nhất với các cạnh có trọng số xác định. Có một số thuật toán tìm đường đi ngắn nhất; ở đây, ta có thuật toán do E. Dijkstra, nhà toán học người Hà Lan, đề xuất năm 1959. Trong báo cáo này mà tôi sẽ trình bày, người ta giả sử đồ thị là vô hướng các trọng số là dương. Chỉ cần thay đổi đôi chút là có thể giải được bài toán tìm đường đi ngắn nhất trong đồ thị có hướng. Phương pháp của thuật toán Dijkstra là: Xác định tuần tự đỉnh có khoảng cách đến u0 từ nhỏ đến lớn.
2 Nhưng câu hỏi cần đặt ra là nếu trọng số đã cho được biểu diễn là một cung mở thuộc khoảng ( a,b) thì sao? Nếu trọng số có khoảng nằm ở đường biên trái thì có thể các phương án là chấp nhận được. Nếu trọng số có khoảng nằm ở đường biên phải thì khó có thể chấp nhận được đó là đường đi tối ưu, do vậy ta chưa thể khẳng định được đó là đường đi ngắn nhất vì giả sử bên cạnh cung đó còn có các cung khác liền kề và có trọng số gần như tương đương thì sao? Nếu áp dụng giải thuật ( Dijkstra, Bellman-Ford, Floyd ) thì rất khó mới có thể tìm ra được theo hướng đi ngắn nhất và tối ưu. Ví dụ : Trong một chuyến đi du lịch từ thành phố A đến thành phố E Vẫn biết rằng : A có thể đi hai đường. A đi qua B rồi lại từ B đi đến D sau đó đến E. A đi qua C rồi lại từ C đi đến D sau đó đến E. Giả sử : Đường đi từ A B và A C là một cung được biểu diễn là một cung mờ dạng khoảng thì sao? Để giải quyết bài toán trên: Nhờ ứng dụng logic mờ trong tin học. Bài toán tối ưu bài toán quy hoạch tuyến tính dạng khoảng sẽ giúp ta giải quyết vấn đề này. Một phương án chấp nhận được được gọi là nghiệm hữu hiệu nếu không tồn tại một phương án chấp nhận được khác tốt hơn nó, ít nhất là theo một mục tiêu, còn các mục tiêu khác không tồi hơn. Tuy nhiên, khối lượng tính toán của các thuật toán này tăng nhanh khi kích thước của bài toán tìm đường đi ngắn nhất với các cung khoảng mờ cho đường đi là quá lớn (tức số ràng buộc của miền chấp nhận, số chiều của không gian quyết định và số hàm mục tiêu) tăng.
3 Trong những năm gần đây nhiều nhà toán học đã chuyển sang nghiên cứu giải quyết bài toán tìm đường đi ngắn nhất có trọng số là các cung mờ dạng khoảng. Trong báo cáo này, tôi sẽ trình bày thuật toán giải bài toán tìm đường đi ngắn nhất với dữ liệu mờ dạng khoảng. Vì những lý do trên, tôi chọn đề tài “Nghiên cứu, xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất với dữ liệu mờ dạng khoảng.” làm đề tài nghiên cứu của mình. 2. Mục đích nghiên cứu Nghiên cứu, thuật toán Dijkstra: Mở rộng, cải tiến áp dụng cho bài toán (Tìm đường đi ngắn nhất) với các dữ liệu về có trọng số dạng khoảng. Giải quyết bài toán tìm đường đi ngắn nhất với độ dài các cung là số mờ dạng khoảng. 3. Phạm vi nghiên cứu Trên cơ sở nghiên cứu, thuật toán Dijkstra: Mở rộng, cải tiến áp dụng cho bài toán (Tìm đường đi ngắn nhất) với các dữ liệu về có trọng số dạng khoảng. Dừng lại ở khâu Tìm đường đi ngắn nhất với các dữ liệu về có trọng số dạng khoảng. 4. Phương pháp nghiên cứu Nghiên cứu, thuật toán Dijkstra: Mở rộng, cải tiến áp dụng cho bài toán (Tìm đường đi ngắn nhất) với các dữ liệu về có trọng số dạng khoảng. Giải quyết bài toán tìm đường đi ngắn nhất với độ dài các cung là số mờ dạng khoảng. Xây dựng phần mềm thử nghiệm. Phân tích đánh giá kết quả để ứng dụng thực tế.
4 Nội dung của luận văn được trình bày trong 4 chương. Chương 1. Lý thuyết đồ thị và thuật toán giải bài toán tìm đường đi ngắn nhất có trọng số xác định Chương 2. Lý thuyết mờ và ứng dụng bài toán quy hoạch tuyến tính dạng khoảng. Chương 3. Xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất biểu diễn cung đường đi là số mờ dạng khoảng. Chương 4. Cài đặt thử nghiệm.
5 Chương 1 LÝ THUYẾT ĐỒ THỊ VÀ THUẬT TOÁN GIẢI BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT CÓ TRỌNG SỐ XÁC ĐỊNH 1.1. Khái niệm cơ bản về lý thuyết đồ thị Lý thuyết đồ thị là ngành khoa học được phát triển từ lâu nhưng lại có nhiều ứng dụng hiện đại. Những ý tưởng cơ bản của nó được đưa ra từ thế kỷ thứ 18 bởi nhà toán học Thụy Sĩ tên là Leonard Euler. Ông đã dùng đồ thị để giải quyết bài toán cầu Konigsberg nổi tiếng. Đồ thị được dùng để giải quyết nhiều bài toán khác nhau. Ví dụ dùng đồ thị để xác định xem có thực hiện được một mạch điện trên một bảng điện phẳng không. Chúng ta cũng có thể phân biệt hai hợp chất hóa học có cùng công thức phân tử nhưng có cấu trúc khác nhau nhờ đồ thị. Chúng ta cũng có thể xác định xem hai máy tính có được nối với nhau bằng một đường truyền thông hay không nếu dùng mô hình đồ thị mạng máy tính. Đồ thị với các trọng số được gán cho các cạnh của nó có thể dùng để giải các bài toán như bài toán: “ Tìm đường đi ngắn nhất” giữa hai thành phố trong một mạng giao thông. 1.1.1. Các định nghĩa về đồ 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 đó. Người ta thường ký hiệu đồ thị G = (V,E), trong đó V là tập hợp các đỉnh (Verterx), E là tập hợp các cạnh (Edge). Người ta phân loại đồ thị theo các đặc tính và số cạnh nối các cặp đỉnh của đồ thị. * Định nghĩa 1: Một đơn đồ thị G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một tập E mà các phần tử của nó gọi là các cạnh, đó là các cặp không có thứ tự của các đỉnh phân biệt.
6 * Định nghĩa 2: Một đa đồ thị G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một họ E mà các phần tử của nó gọi là các cạnh, đó là các cặp không có thứ tự của các đỉnh phân biệt. Hai cạnh được gọi là cạnh bội hay song song nếu chúng cùng tương ứng với một cặp đỉnh. Rõ ràng mỗi đơn đồ thị là đa đồ thị, nhưng không phải đa đồ thị nào cũng là đơn đồ thị. * Định nghĩa 3: Một giả đồ thị G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một họ E mà các phần tử của nó gọi là các cạnh, đó là các cặp không có thứ tự của các đỉnh (không nhất thiết là phân biệt). Với v V, nếu (v,v) E thì ta nói có một khuyên tại đỉnh v. Tóm lại, giả đồ thị là loại đồ thị vô hướng tổng quát nhất vì nó có thể chứa các khuyên và các cạnh bội. Đa đồ thị là loại đồ thị vô hướng có thể chứa cạnh bội nhưng không thể có các khuyên, còn đơn đồ thị là loại đồ thị vô hướng không chứa cạnh bội hoặc các khuyên. v1 v2 v3 v4 v1 v2 v3 v5 v6 v7 v4 v5 v6 Đơn đồ thị Giả đồ thị Hình 1.1 Đơn đồ thị, giả đồ thị * Định nghĩa 4: Một đồ thị có hướng G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một tập E mà các phần tử của nó gọi là các cung, đó là các cặp có thứ tự của các phần tử thuộc V. * Định nghĩa 5: Một đa đồ thị có hướng G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một họ E mà các phần tử của nó gọi là các cung, đó là các cặp có thứ tự của các phần tử thuộc V.
7  Đồ thị vô hướng nhận được từ đồ thị có hướng G bằng cách xoá bỏ các chiều mũi tên trên các cung được gọi là đồ thị vô hướng nền của G. v v v 1 2 v3 v5 v1 v2 3 V 5 v6 v7 v4 v5 v6 Đồ thị có hướng Đa đồ thị có hướng Hình 1.2. Đồ thị có hướng và Đa đồ thị có hướng  Đồ thị ảnh hưởng: Khi nghiên cứu tính cách của một nhóm nguời, ta thấy một số người có thể có ảnh hưởng lên suy nghĩ của những người khác. Đồ thị có hướng được gọi là đồ thị ảnh hưởng có thể dùng để mô hình bài toán này. Mỗi người của nhóm được biểu diễn bằng một đỉnh. Khi một người được biểu diễn bằng đỉnh a có ảnh hưởng lên người được biểu diễn bằng đỉnh b thì có một cung nối từ đỉnh a đến đỉnh b.  Thi đấu vòng tròn: Một cuộc thi đấu thể thao trong đó mỗi đội đấu với mỗi đội khác đúng một lần gọi là đấu vòng tròn. Cuộc thi đấu như thế có thể được mô hình bằng một đồ thị có hướng trong đó mỗi đội là một đỉnh. Một cung đi từ đỉnh a đến đỉnh b nếu đội a thắng đội b.  Các chương trình máy tính có thể thi hành nhanh hơn bằng cách thi hành đồng thời một số câu lệnh nào đó. Điều quan trọng là không được thực hiện một câu lệnh đòi hỏi kết quả của câu lệnh khác chưa được thực hiện. Sự phụ thuộc của các câu lệnh vào các câu lệnh trước có thể biểu diễn bằng một đồ thị có hướng. Mỗi câu lệnh được biểu diễn bằng một đỉnh và có một cung từ một đỉnh tới một đỉnh khác nếu câu lệnh được biểu diễn bằng đỉnh thứ hai không thể thực hiện được trước khi câu lệnh được biểu diễn bằng đỉnh thứ nhất được thực hiện. Đồ thị này được gọi là đồ thị có ưu tiên trước sau.
8 1.1.2. Bậc của đồ thị. * Định nghĩa 1: Hai đỉnh u và v trong đồ thị (vô hướng) G=(V,E) được gọi là liền kề nếu (u,v) E. Nếu e = (u,v) thì e gọi là cạnh liên thuộc với các đỉnh u và v. Cạnh e cũng được gọi là cạnh nối các đỉnh u và v. Các đỉnh u và v gọi là các điểm đầu mút của cạnh e. * Định nghĩa 2: Bậc của đỉnh v trong đồ thị G=(V,E), ký hiệu deg(v), là số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho bậc của nó. Đỉnh v gọi là đỉnh treo nếu deg(v)=1 và gọi là đỉnh cô lập nếu deg(v)=0. v1 v2 v3 v4 v5 v6 v7 Hình 1.3. Bậc của đồ thị Ta có deg(v1)=7, deg(v2)=5, deg(v3)=3, deg(v4)=0, deg(v5)=4, deg(v6)=1, deg(v7)=2. Đỉnh v4 là đỉnh cô lập và đỉnh v6 là đỉnh treo. * Mệnh đề 1: Cho đồ thị G = (V, E). Khi đó 2|E| = deg(v) . v V 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. Hệ quả 1: Số đỉnh bậc lẻ của một đồ thị là một số chẵn. Chứng minh: Gọi V1 và V2 tương ứng là tập các đỉnh bậc chẵn và tập các đỉnh bậc lẻ của đồ thị G = (V, E). Khi đó 2|E| = deg(v) + deg(v) v V1 v V2
9 Vế trái là một số chẵn và tổng thứ nhất cũng là một số chẵn nên tổng thứ hai là một số chẵn. Vì deg(v) là lẻ với mọi v V2 nên |V2| là một số chẵn. Mệnh đề 2: Trong một đơn đồ thị, luôn tồn tại hai đỉnh có cùng bậc. Chứng minh: Xét đơn đồ thị G=(V,E) có |V|=n. Khi đó phát biểu trên được đưa về bài toán: trong một phòng họp có n người, bao giờ cũng tìm được 2 người có số người quen trong số những người dự họp là như nhau (xem Thí dụ 6 của 2.2.3). * Định nghĩa 3: Đỉnh u được gọi là nối tới v hay v được gọi là được nối từ u trong đồ thị có hướng G nếu (u,v) là một cung của G. Đỉnh u gọi là đỉnh đầu và đỉnh v gọi là đỉnh cuối của cung này. * Định nghĩa 4: Bậc vào (t.ư. bậc ra) của đỉnh v trong đồ thị có hướng G, ký hiệu degt(v) (t.ư. dego(v)), là số các cung có đỉnh cuối là v. v1 v2 v3 v4 v5 v6 H 1.4. Bậc của đồ thị có hướng degt(v1) = 2, dego(v1) = 3, degt(v2) = 5, dego(v2) = 1, degt(v3) = 2, dego(v3) = 4, degt(v4) = 1, deg0(v4) = 3, degt(v5) = 1, dego(v5) = 0, degt(v6) = 0, dego(v6) = 0. Đỉnh có bậc vào và bậc ra cùng bằng 0 gọi là đỉnh cô lập. Đỉnh có bậc vào bằng 1 và bậc ra bằng 0 gọi là đỉnh treo, cung có đỉnh cuối là đỉnh treo gọi là cung treo. * Mệnh đề 3: Cho G =(V, E) là một đồ thị có hướng. Khi đó
10 degt (v) dego (v) = |E|. v V v V Chứng minh: Kết quả có ngay là vì mỗi cung được tính một lần cho đỉnh đầu và một lần cho đỉnh cuối. 1.1.3. Biểu diễn đồ thị bằng ma trận Định nghĩa 1: Cho đồ thị G=(V,E) (vô hướng hoặc có hướng), với V={v1,v2, , vn}. Ma trận liền kề của G ứng với thứ tự các đỉnh v 1,v2, , vn là ma trận A=(aij )1 i, j n M (n, Z) , trong đó aij là số cạnh hoặc cung nối từ vi tới vj. Như vậy, ma trận liền kề của một đồ thị vô hướng là ma trận đối xứng, nghĩa là aij a ji , trong khi ma trận liền kề của một đồ thị có hướng không có tính đối xứng. Ví dụ 1: Ma trận liền kề với thứ tự các đỉnh v1, v2, v3, v4 là: v1 v2 0 3 0 2 3 0 1 1 0 1 1 2 v4 v3 2 1 2 0 Hình 1.5. Biểu diễn đồ thị bằng ma trận liền kề Ma trận liền kề với thứ tự các đỉnh v1, v2, v3, v4, v5 là: v1 1 1 0 1 1 0 1 2 1 0 v5 v2 1 0 0 1 0 0 0 2 0 1 v 1 1 0 1 0 4 v3 Hình 1.6. Biểu diễn đồ thị bằng ma trận liền kề * Định nghĩa 2: Cho đồ thị vô hướng G=(V,E), v 1, v2, , vn là các đỉnh và e1, e2, , em là các cạnh của G. Ma trận liên thuộc của G theo thứ tự trên của V và E là ma trận
11 M=(mij )1 i n M (n m, Z) , 1 j m mij bằng 1 nếu cạnh e j nối với đỉnh v i và bằng 0 nếu cạnh e j không nối với đỉnh vi. Ví dụ 2: Ma trận liên thuộc theo thứ tự các đỉnh v 1, v2, v3, v4, v5 và các cạnh e1, e2, e3, e4, e5, e6 là: 1 1 0 0 0 0 e6 0 0 1 1 0 1 v1 v2 v3 e3 0 0 0 0 1 1 e4 e1 e5 1 0 1 0 0 0 e2 0 1 0 1 1 0 v4 v5 Hình 1.7. Biểu diễn đồ thị bằng ma trận liên thuộc 1.1.4. Tính liên thông * Định nghĩa 1: Đường đi độ dài n từ đỉnh u đến đỉnh v, với n là một số nguyên dương, trong đồ thị (giả đồ thị vô hướng hoặc đa đồ thị có hướng) G=(V,E) là một dãy các cạnh (hoặc cung) e1, e2, , en của đồ thị sao cho e1=(x0,x1),e2=(x1,x2), ,en=(xn-1,xn), với x0=u và xn=v. Khi đồ thị không có cạnh (hoặc cung) bội, ta ký hiệu đường đi này bằng dãy các đỉnh x0, x1, , xn. Đường đi được gọi là chu trình nếu nó bắt đầu và kết thúc tại cùng một đỉnh. Đường đi hoặc chu trình gọi là đơn nếu nó không chứa cùng một cạnh (hoặc cung) quá một lần. Một đường đi hoặc chu trình không đi qua đỉnh nào quá một lần (trừ đỉnh đầu và đỉnh cuối của chu trình là trùng nhau) được gọi là đường đi hoặc chu trình sơ cấp. Rõ ràng rằng một đường đi (t.ư. chu trình) sơ cấp là đường đi (t.ư. chu trình) đơn. x y z w v u Hình 1.8. Biểu diễn đường đi sơ cấp
12 Trong đơn đồ thị trên, x, y, z, w, v, y là đường đi đơn (không sơ cấp) độ dài 5; x, w, v, z, y không là đường đi vì (v, z) không là cạnh; y, z, w, x, v, u, y là chu trình sơ cấp độ dài 6. * Định nghĩa 2: Một đồ thị (vô hướng) được gọi là liên thông nếu có đường đi giữa mọi cặp đỉnh phân biệt của đồ thị. Một đồ thị không liên thông là hợp của hai hay nhiều đồ thị con liên thông, mỗi cặp các đồ thị con này không có đỉnh chung. Các đồ thị con liên thông rời nhau như vậy được gọi là các thành phần liên thông của đồ thị đang xét. Như vậy, một đồ thị là liên thông khi và chỉ khi nó chỉ có một thành phần liên thông. x y z a b g k u t v w d c h i l G G’ Hình 1.9. Biểu diễn đồ thị G và G’ Đồ thị G là liên thông, nhưng đồ thị G’ không liên thông và có 3 thành phần liên thông. * Định nghĩa 3: Một đỉnh trong đồ thị G mà khi xoá đi nó và tất cả các cạnh liên thuộc với nó ta nhận được đồ thị con mới có nhiều thành phần liên thông hơn đồ thị G được gọi là đỉnh cắt hay điểm khớp. Việc xoá đỉnh cắt khỏi một đồ thị liên thông sẽ tạo ra một đồ thị con không liên thông. Hoàn toàn tương tự, một cạnh mà khi ta bỏ nó đi sẽ tạo ra một đồ thị có nhiều thành phần liên thông hơn so với đồ thị xuất phát được gọi là cạnh cắt hay là cầu. x y z u v w s t Hình 1.10. Biểu các đỉnh cắt là v, w, s và các cầu là (x,v), (w,s).
13 Mệnh đề 1: Giữa mọi cặp đỉnh phân biệt của một đồ thị liên thông luôn có đường đi sơ cấp. Chứng minh: Giả sử u và v là hai đỉnh phân biệt của một đồ thị liên thông G. Vì G liên thông nên có ít nhất một đường đi giữa u và v. Gọi x 0, x1, , xn, với x 0=u và xn=v, là dãy các đỉnh của đường đi có độ dài ngắn nhất. Đây chính là đường đi sơ cấp cần tìm. Thật vậy, giả sử nó không là đường đi đơn, khi đó xi=xj với 0 i < j. Điều này có nghĩa là giữa các đỉnh u và v có đường đi ngắn hơn qua các đỉnh x 0, x1, , xi-1, xj, , xn nhận được bằng cách xoá đi các cạnh tương ứng với dãy các đỉnh xi, , xj-1. * Mệnh đề 2: Mọi đơn đồ thị n đỉnh (n 2) có tổng bậc của hai đỉnh tuỳ ý không nhỏ hơn n đều là đồ thị liên thông. Chứng minh: Cho đơn đồ thị G=(V,E) có n đỉnh (n 2) và thoả mãn yêu cầu của bài toán. Giả sử G không liên thông, tức là tồn tại hai đỉnh u và v sao cho không có đường đi nào nối u và v. Khi đó trong đồ thị G tồn tại hai thành phần liên thông là G1 có n1 đỉnh và chứa u, G 2 chứa đỉnh v và có n 2 đỉnh. Vì G1, G2 là hai trong số các thành phần liên thông của G nên n1+n2 n. ta có: deg(u)+deg(v) (n1 1)+(n2 1) = n1+n2 2 n 2 <n. Điều mâu thuẫn ở trên dẫn đến kết luận là đồ thị G phải liên thông. * Hệ quả 1: Đơn đồ thị mà bậc của mỗi đỉnh của nó không nhỏ hơn một nửa số đỉnh là đồ thị liên thông. Mệnh đề 3: Nếu một đồ thị có đúng hai đỉnh bậc lẻ thì hai đỉnh này phải liên thông, tức là có một đường đi nối chúng. Chứng minh: Cho G=(V,E) là đồ thị thị có đúng hai đỉnh bậc lẻ là u và v. Giả sử u và v không liên thông với nhau. Khi đó chúng phải thuộc hai thành phần liên thông nào đó của đồ thị G, G1 chứa u và G2 chứa v.
14 Bậc của đỉnh u trong G1 cũng chính là bậc của u trong G, nên trong G1 đỉnh u vẫn có bậc lẻ và G1 có duy nhất một đỉnh bậc lẻ. Điều này mâu thuẫn. Vậy hai đỉnh u và v phải liên thông. Mệnh đề 4: Cho G=(V,E) là một đồ thị liên thông. Khi đó một đỉnh của G là điểm khớp khi và chỉ khi trong G tồn tại hai đỉnh u và v sao cho mỗi đường đi nối u và v đều phải đi qua đỉnh này. Chứng minh mệnh đề 4 như sau: Điều kiện cần: Giả sử đỉnh x là điểm khớp trong đồ thị G. Khi đó đồ thị con G1 của G nhận được bằng cách xoá x và các cạnh liên thuộc với nó là không liên thông. Giả sử G2, G3 là hai trong các thành phần liên thông của G1. Lấy u là đỉnh trong G 2 và v là đỉnh trong G 3. Do u, v thuộc hai thành phần liên thông khác nhau, nên trong G1 các đỉnh u, v không liên thông. Nhưng trong G các đỉnh u, v lại liên thông, nên mọi đường đi nối u, v đều phải đi qua đỉnh x. Điều kiện đủ: Giả sử mọi đường đi nối u, v đều đi qua đỉnh x, nên nếu bỏ đỉnh x và các cạnh liên thuộc với x thì đồ thị con G 1 nhận được từ G chứa hai đỉnh u, v không liên thông. Do đó G1 là đồ thị không liên thông hay đỉnh x là điểm khớp của G. * Định lý: Cho G là một đơn đồ thị có n đỉnh, m cạnh và k thành phần liên thông. Khi đó (n k)(n k 1) n k m . 2 Chứng minh: Bất đẳng thức n k m được chứng minh bằng quy nạp theo m. Nếu m=0 thì k=n nên bất đẳng thức đúng. Giả sử bất đẳng thức đúng đến m 1, với m 1. Gọi G’ là đồ thị con bao trùm của G có số cạnh m 0 là nhỏ nhất sao cho nó có k thành phần liên thông. Do đó việc loại bỏ bất cứ cạnh nào trong G’ cũng tăng số thành phần liên thông lên 1 và khi đó đồ thị
15 thu được sẽ có n đỉnh, k+1 thành phần liên thông và m 0 1 cạnh. Theo giả thiết quy nạp, ta có m0 1 n (k+1) hay m0 n k. Vậy m n-k. Bổ sung cạnh vào G để nhận được đồ thị G’’ có m1 cạnh sao cho k thành phần liên thông là những đồ thị đầy đủ. Ta có m m1 nên chỉ cần chứng minh (n k)(n k 1) m1 . 2 Giả sử Gi và Gj là hai thành phần liên thông của G’’ với n i và nj đỉnh và ni nj >1 (*). Nếu ta thay Gi và Gj bằng đồ thị đầy đủ với n i+1 và nj 1 đỉnh thì tổng số đỉnh không thay đổi nhưng số cạnh tăng thêm một lượng là: (ni 1)ni ni (ni 1) n j (n j 1) (n j 1)(n j 2) ni n j 1. 2 2 2 2 Thủ tục này được lặp lại khi hai thành phần nào đó có số đỉnh thoả mãn (*). Vì vậy m1 là lớn nhất (n, k là cố định) khi đồ thị gồm k-1 đỉnh cô lập và một đồ thị đầy đủ với n-k+1 đỉnh. Từ đó suy ra bất đẳng thức cần tìm. * Định nghĩa 4: Đồ thị có hướng G được gọi là liên thông mạnh nếu với hai đỉnh phân biệt bất kỳ u và v của G đều có đường đi từ u tới v và đường đi từ v tới u. Đồ thị có hướng G được gọi là liên thông yếu nếu đồ thị vô hướng nền của nó là liên thông. Đồ thị có hướng G được gọi là liên thông một chiều nếu với hai đỉnh phân biệt bất kỳ u và v của G đều có đường đi từ u tới v hoặc đường đi từ v tới u. u v w u v w x x y s t y s t G G’ Hình 1.11. Đồ thị G là liên thông mạnh nhưng đồ thị G’ là liên thông yếu (không có đường đi từ u tới x cũng như từ x tới u).
16 * Mệnh đề: Cho G là một đồ thị (vô hướng hoặc có hướng) với ma trận liền kề A theo thứ tự các đỉnh v1, v2, , vn. Khi đó số các đường đi khác nhau độ dài r từ vi tới vj trong đó r là một số nguyên dương, bằng giá trị của phần tử dòng i cột j của ma trận Ar. Chứng minh: Ta chứng minh mệnh đề bằng quy nạp theo r. Số các đường đi khác nhau độ dài 1 từ vi tới vj là số các cạnh (hoặc cung) từ vi tới vj, đó chính là phần tử dòng i cột j của ma trận A; nghĩa là, mệnh đề đúng khi r=1. Giả sử mệnh đề đúng đến r; nghĩa là, phần tử dòng i cột j của Ar là số các r+1 r đường đi khác nhau độ dài r từ vi tới vj. Vì A =A .A nên phần tử dòng i cột j của Ar+1 bằng bi1a1j+bi2a2j+ +binanj, r trong đó b ik là phần tử dòng i cột k của A . Theo giả thiết quy nạp b ik là số đường đi khác nhau độ dài r từ vi tới vk. Đường đi độ dài r+1 từ vi tới vj sẽ được tạo nên từ đường đi độ dài r từ vi tới đỉnh trung gian vk nào đó và một cạnh (hoặc cung) từ v k tới vj. Theo quy tắc nhân số các đường đi như thế là tích của số đường đi độ dài r từ v i tới vk, tức là bik, và số các cạnh (hoặc cung) từ v k tới vj, tức là akj. Cộng các tích này lại theo tất cả các đỉnh trung gian vk ta có mệnh đề đúng đến r+1. 1.1.5. Đường đi Euler và đồ thị Euler Có thể coi năm 1736 là năm khai sinh lý thuyết đồ thị, với việc công bố lời giải “bài toán về các cầu ở Konigsberg” của nhà toán học lỗi lạc Euler (1707-1783). Thành phố Konigsberg thuộc Phổ (nay gọi là Kaliningrad thuộc Nga) được chia thành bốn vùng bằng các nhánh sông Pregel, các vùng này gồm hai vùng bên bờ sông, đảo Kneiphof và một miền nằm giữa hai nhánh
17 của sông Pregel. Vào thế kỷ 18, người ta xây bảy chiếc cầu nối các vùng này với nhau. B B D A D A C G C Hình 1.12. Biểu diễn Đường đi Euler và đồ thị Euler Dân thành phố từng thắc mắc: “Có thể nào đi dạo qua tất cả bảy cầu, mỗi cầu chỉ một lần thôi không?”. Nếu ta coi mỗi khu vực A, B, C, D như một đỉnh và mỗi cầu qua lại hai khu vực là một cạnh nối hai đỉnh thì ta có sơ đồ của Konigsberg là một đa đồ thị G như hình trên. Bài toán tìm đường đi qua tất cả các cầu, mỗi cầu chỉ qua một lần có thể được phát biểu lại bằng mô hình này như sau: Có tồn tại chu trình đơn trong đa đồ thị G chứa tất cả các cạnh? Định nghĩa: Chu trình (t.ư. đường đi) đơn chứa tất cả các cạnh (hoặc cung) của đồ thị (vô hướng hoặc có hướng) G được gọi là chu trình (t.ư. đường đi) Euler. Một đồ thị liên thông (liên thông yếu đối với đồ thị có hướng) có chứa một chu trình (t.ư. đường đi) Euler được gọi là đồ thị Euler (t.ư. nửa Euler). Đồ thị Euler Đồ thị không nửa Euler Đồ thị nửa Euler
18 Đồ thị Euler Đồ thị nửa Euler Hình 1.13. Đồ thị Euler và đồ thị nửa Euler Điều kiện cần và đủ để một đồ thị là đồ 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ời đó về bảy cái cầu ở Konigsberg và đây là định lý đầu tiên của lý thuyết đồ thị. * Định lý: Đồ 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: Điều kiện 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 thì 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. Do đó mỗi đỉnh của đồ thị đều có bậc chẵn. * 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 đơn. Chứng minh: Nếu G có cạnh bội hoặc có khuyên thì khẳng định của bổ đề là hiển nhiên. Vì vậy giả sử G là một đơn đồ thị. Gọi v là một đỉnh nào đó của G. Ta sẽ xây dựng theo quy nạp đường đi v v1 v2 Hình 1.14. Xây dựng đường đi trong đó v1 là đỉnh kề với v, còn với i 1, chọn vi+1 là đỉnh kề với vi và vi+1 vi-1 (có thể chọn như vậy vì deg(vi) 2), v0 = v. 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
19 trước đó. Gọi k là số nguyên dương đầu tiên để vk=vi (0 i<k). Khi đó, đường đi vi, vi+1, , vk-1, vk (= vi) là một chu trình đơn cần tìm. Điều kiện đủ: Quy nạp theo số cạnh của G. Do G liên thông và bậc của mọi đỉnh là chẵn nên mỗi đỉnh có bậc không nhỏ hơn 2. Từ đó theo Bổ đề, G phải chứa một chu trình đơn 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 các cạnh thuộc C, ta thu được một đồ thị mới H (không nhất thiết là liên thông). Số cạnh trong H nhỏ hơn trong G và rõ ràng mỗi đỉnh của H vẫn có bậc là chẵn. Theo giả thiết quy nạp, trong mỗi thành phần liên thông của H đều tìm được chu trình Euler. Do G liên thông nên mỗi thành phần trong 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: C Hình 1.15. Xây dựng đường đi 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 thì ta đ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 H, 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. * Hệ quả: Đồ thị liên thông G là nửa Euler (mà không là Euler) khi và chỉ khi có đúng hai đỉnh bậc lẻ trong G.
20 * Chú ý: Ta có thể vạch được một chu trình Euler trong đồ thị liên thông G có bậc của mọi đỉnh là chẵn theo thuật toán Fleury sau đây. Xuất phát từ một đỉnh bất kỳ của G và tuân theo hai quy tắc sau: - Mỗi khi đi qua một cạnh nào thì xoá nó đi; sau đó xoá đỉnh cô lập (nếu có); - Không bao giờ đi qua một cầu, trừ phi không còn cách đi nào khác. u v w s t x y z Hình 1.16. Xây dựng đường đi Xuất phát từ u, ta có thể đi theo cạnh (u,v) hoặc (u,x), giả sử là (u,v) (xoá (u,v)). Từ v có thể đi qua một trong các cạnh (v,w), (v,x), (v,t), giả sử (v,w) (xoá (v,w)). Tiếp tục, có thể đi theo một trong các cạnh (w,s), (w,y), (w,z), giả sử (w,s) (xoá (w,s)). Đi theo cạnh (s,y) (xoá (s,y) và s). Vì (y,x) là cầu nên có thể đi theo một trong hai cạnh (y,w), (y,z), giả sử (y,w) (xoá (y,w)). Đi theo (w,z) (xoá (w,z) và w) và theo (z,y) (xoá (z,y) và z). Tiếp tục đi theo cạnh (y,x) (xoá (y,x) và y). Vì (x,u) là cầu nên đi theo cạnh (x,v) hoặc (x,t), giả sử (x,v) (xoá (x,v)). Tiếp tục đi theo cạnh (v,t) (xoá (v,t) và v), theo cạnh (t,x) (xoá cạnh (t,x) và t), cuối cung đi theo cạnh (x,u) (xoá (x,u), x và u). 1.1.6. Bài toán người phát thư Trung Hoa: Một nhân viên đi từ Sở Bưu Điện, qua một số đường phố để phát thư, rồi quay về Sở. Người ấy phải đi qua các đường theo trình tự nào để đường đi là ngắn nhất? Bài toán được nhà toán học Trung Hoa Guan nêu lên đầu tiên (1960), vì vậy thường được gọi là “bài toán người phát thư Trung Hoa”. Ta xét bài toán ở một dạng đơn giản như sau.
21 Cho đồ thị liên thông G. Một chu trình qua mọi cạnh của G gọi là một hành trình trong G. Trong các hành trình đó, hãy tìm hành trình ngắn nhất, tức là qua ít cạnh nhất. Rõ ràng rằng nếu G là đồ thị Euler (mọi đỉnh đều có bậc chẵn) thì chu trình Euler trong G (qua mỗi cạnh của G đúng một lần) là hành trình ngắn nhất cần tìm. Chỉ còn phải xét trường hợp G có một số đỉnh bậc lẻ (số đỉnh bậc lẻ là một số chẵn). Khi đó, mọi hành trình trong G phải đi qua ít nhất hai lần một số cạnh nào đó. Dễ thấy rằng một hành trình qua một cạnh (u,v) nào đó quá hai lần thì không phải là hành trình ngắn nhất trong G. Vì vậy, ta chỉ cần xét những hành trình T đi qua hai lần một số cạnh nào đó của G. Ta quy ước xem mỗi hành trình T trong G là một hành trình trong đồ thị Euler GT, có được từ G bằng cách vẽ thêm một cạnh song song đối với những cạnh mà T đi qua hai lần. Bài toán đặt ra được đưa về bài toán sau: Trong các đồ thị Euler GT, tìm đồ thị có số cạnh ít nhất (khi đó chu trình Euler trong đồ thị này là hành trình ngắn nhất). Định lý (Gooodman và Hedetniemi, 1973). Nếu G là một đồ thị liên thông có q cạnh thì hành trình ngắn nhất trong G có chiều dài q + m(G), trong đó m(G) là số cạnh mà hành trình đi qua hai lần và được xác định như sau: Gọi V0(G) là tập hợp các đỉnh bậc lẻ (2k đỉnh) của G. Ta phân 2k phần tử của G thành k cặp, mỗi tập hợp k cặp gọi là một phân hoạch cặp của V0(G). Ta gọi độ dài đường đi ngắn nhất từ u đến v là khoảng cách d(u,v). Đối với mọi phân hoạch cặp P i, ta tính khoảng cách giữa hai đỉnh trong từng cặp, rồi tính tổng d(Pi). Số m(G) bằng cực tiểu của các d(Pi):
22 m(G)=min d(Pi). Ví dụ 2: Giải bài toán người phát thư Trung Hoa cho trong đồ thị sau: D C E B J K F G A I H G GT Hình 1.17. Xây dựng đường đi GT và G Tập hợp các đỉnh bậc lẻ VO(G)={B, G, H, K} và tập hợp các phân hoạch cặp là P={P1, P2, P3}, trong đó P1 = {(B, G), (H, K)} d(P1) = d(B, G)+d(H, K) = 4+1 = 5, P2 = {(B, H), (G, K)} d(P2) = d(B, H)+d(G, K) = 2+1 = 3, P3 = {(B, K), (G, H)} d(P3) = d(B, K)+d(G, H) = 3+2 = 5. m(G) = min(d(P1), d(P2), d(P3)) = 3. Do đó GT có được từ G bằng cách thêm vào 3 cạnh: (B, I), (I, H), (G, K) và GT là đồ thị Euler. Vậy hành trình ngắn nhất cần tìm là đi theo chu trình Euler trong GT: A, B, C, D, E, F, K, G, K, E, C, J, K, H, J, I, H, I, B, I, A. * Định lý: Đồ thị có hướng liên thông yếu G là đồ thị Euler khi và chỉ khi mọi đỉnh của G đều có bậc vào bằng bậc ra. Chứng minh: Chứng minh tương tự như chứng minh của Định lý 4.1.2 và điều kiện đủ cũng cần có bổ đề dưới đây tương tự như ở Bổ đề 4.1.3. * Bổ đề: Nếu bậc vào và bậc ra của mỗi đỉnh của đồ thị có hướng G không nhỏ hơn 1 thì G chứa chu trình đơn.
23 * Hệ quả: Đồ thị có hướng liên thông yếu G là nửa Euler (mà không là Euler) khi và chỉ khi tồn tại hai đỉnh x và y sao cho: dego(x) = degt(x)+1, degt(y) = dego(y)+1, degt(v) = dego(v), v V, v x, v y. Chứng minh: Chứng minh tương tự như ở Hệ quả 4.1.4. 1.1.7. Đường đi Hamilton và đồ thị Hamilton Năm 1857, nhà toán học người Ailen là Hamilton(1805-1865) đưa ra trò chơi “đi vòng quanh thế giới” như sau. Cho một hình thập nhị diện đều (đa diện đều có 12 mặt, 20 đỉnh và 30 cạnh), mỗi đỉnh của hình mang tên một thành phố nổi tiếng, mỗi cạnh của hình (nối hai đỉnh) là đường đi lại giữa hai thành phố tương ứng. Xuất phát từ một thành phố, hãy tìm đường đi thăm tất cả các thành phố khác, mỗi thành phố chỉ một lần, rồi trở về chỗ cũ. Trước Hamilton, có thể là từ thời Euler, người ta đã biết đến một câu đố hóc búa về “đường đi của con mã trên bàn cờ”. Trên bàn cờ, con mã chỉ có thể đi theo đường chéo của hình chữ nhật 2 x 3 hoặc 3 x 2 ô vuông. Giả sử bàn cờ có 8 x 8 ô vuông. Hãy tìm đường đi của con mã qua được tất cả các ô của bàn cờ, mỗi ô chỉ một lần rồi trở lại ô xuất phát. Bài toán này được nhiều nhà toán học chú ý, đặc biệt là Euler, De Moivre, Vandermonde, Hiện nay đã có nhiều lời giải và phương pháp giải cũng có rất nhiều, trong đó có quy tắc: mỗi lần bố trí con mã ta chọn vị trí mà tại vị trí này số ô chưa dùng tới do nó khống chế là ít nhất. Một phương pháp khác dựa trên tính đối xứng của hai nửa bàn cờ. Ta tìm hành trình của con mã trên một nửa bàn cờ, rồi lấy đối xứng cho nửa bàn cờ còn lại, sau đó nối hành trình của hai nửa đã tìm lại với nhau.
24 Trò chơi và câu đố trên dẫn tới việc khảo sát một lớp đồ thị đặc biệt, đó là đồ thị Hamilton. * Định nghĩa: Chu trình (t.ư. đường đi) sơ cấp chứa tất cả các đỉnh của đồ thị (vô hướng hoặc có hướng) G được gọi là chu trình (t.ư. đường đi) Hamilton. Một đồ thị có chứa một chu trình (t.ư. đường đi) Hamilton được gọi là đồ thị Hamilton (t.ư. nửa Hamilton). C J K I B D L O P H N Q M R G T S F A E Hình 1.18. Chu trình sơ cấp chứa tất cả các đỉnh của đồ thị Đồ thị Hamilton (hình thập nhị diện đều biểu diẽn trong mặt phẳng) với chu trình Hamilton A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, A (đường tô đậm). Xét đồ thị có hướng G gồm n đỉnh sao cho mỗi đỉnh ứng với một đấu thủ và có một cung nối từ đỉnh u đến đỉnh v nếu đấu thủ ứng với u thắng đấu thủ ứng với v. Như vậy, đồ thị G có tính chất là với hai đỉnh phân biệt bất kỳ u và v, có một và chỉ một trong hai cung (u,v) hoặc (v,u), đồ thị như thế được gọi là đồ thị có hướng đầy đủ. Từ Mệnh đề 4.2.2 dưới đây, G là một đồ thị nửa Hamilton. Khi đó đường đi Hamilton trong G cho ta sự sắp xếp cần tìm. Đường đi Hamilton tương tự đường đi Euler trong cách phát biểu: Đường đi Euler qua mọi cạnh (cung) của đồ thị đúng một lần, đường đi Hamilton qua mọi đỉnh của đồ thị đúng một lần. Tuy nhiên, nếu như bài toán tìm đường đi Euler trong một đồ thị đã được giải quyết trọn vẹn, dấu hiệu
25 nhận biết một đồ thị Euler là khá đơn giản và dễ sử dụng, thì các bài toán về tìm đường đi Hamilton và xác định đồ thị Hamilton lại khó hơn rất nhiều. Đường đi Hamilton và đồ thị Hamilton có nhiều ý nghĩa thực tiễn và đã được nghiên cứu nhiều, nhưng vẫn còn những khó khăn lớn chưa ai vượt qua được. Người ta chỉ mới tìm được một vài điều kiện đủ để nhận biết một lớp rất nhỏ các đồ thị Hamilton và đồ thị nửa Hamilton. Sau đây là một vài kết quả. * Định lý (Rédei): Nếu G là một đồ thị có hướng đầy đủ thì G là đồ thị nửa Hamilton. Chứng minh: Giả sử G=(V,E) là đồ thị có hướng đầy đủ và =(v1,v2, , vk-1, vk) là đường đi sơ cấp bất kỳ trong đồ thị G. Nếu đã đi qua tất cả các đỉnh của G thì nó là một đường đi Hamilton của G. Nếu trong G còn có đỉnh nằm ngoài , thì ta có thể bổ sung dần các đỉnh này vào và cuối cùng nhận được đường đi Hamilton. Thật vậy, giả sử v là đỉnh tuỳ ý không nằm trên . a) Nếu có cung nối v với v1 thì bổ sung v vào đầu của đường đi để được 1=(v, v1, v2, , vk-1, vk). b) Nếu tồn tại chỉ số i (1 i k-1) mà từ vi có cung nối tới v và từ v có cung nối tới vi+1 thì ta chen v vào giữa vi và vi+1 để được đường đi sơ cấp 2=(v1, v2, , vi, v, vi+1, , vk). c) Nếu cả hai khả năng trên đều không xảy ra nghĩa là với mọi i (1 i k) vi đều có cung đi tới v. Khi đó bổ sung v vào cuối của đường đi và được đường đi 3=(v1, v2, , vk-1, vk, v). Nếu đồ thị G có n đỉnh thì sau n-k bổ sung ta sẽ nhận được đường đi Hamilton.
26 * Định lý (Dirac, 1952): Nếu G là một đơn đồ thị có n đỉnh và mọi đỉnh n của G đều có bậc không nhỏ hơn thì G là một đồ thị Hamilton. 2 Chứng minh: Định lý được chứng minh bằng phản chứng. Giả sử G không có chu trình Hamilton. Ta thêm vào G một số đỉnh mới và nối mỗi đỉnh mới này với mọi đỉnh của G, ta được đồ thị G’. Giả sử k (>0) là số tối thiểu các đỉnh cần thiết để G’ chứa một chu trình Hamilton. Như vậy, G’ có n+k đỉnh. y b a a' b’ Hình 1.19. Chu trình sơ cấp chứa tất cả các đỉnh của đồ thị là chu trình Hamilton ayb a trong G’, trong đó a và b là các đỉnh của G, còn y là một trong các đỉnh mới. Khi đó b không kề với a, vì nếu trái lại thì ta có thể bỏ đỉnh y và được chu trình ab a, mâu thuẩn với giả thiết về tính chất nhỏ nhất của k. Ngoài ra, nếu a’ là một đỉnh kề nào đó của a (khác với y) và b’ là đỉnh nối tiếp ngay a’ trong chu trình P thì b’ không thể là đỉnh kề với b, vì nếu trái lại thì ta có thể thay P bởi chu trình aa’ bb’ a, trong đó không có y, mâu thuẩn với giả thiết về tính chất nhỏ nhất của k. Như vậy, với mỗi đỉnh kề với a, ta có một đỉnh không kề với b, tức là số đỉnh không kề với b không thể ít hơn số đỉnh kề với a (số đỉnh kề với a không n nhỏ hơn +k). Mặt khác, theo giả thiết số đỉnh kề với b cũng không nhỏ hơn 2 n +k. Vì không có đỉnh nào vừa kề với b lại vừa không kề với b, nên số đỉnh 2
27 n của G’ không ít hơn 2( +k)=n+2k, mâu thuẩn với giả thiết là số đỉnh của G’ 2 bằng n+k (k>0). Định lý được chứng minh. * Hệ quả: Nếu G là đơn đồ thị có n đỉnh và mọi đỉnh của G đều có bậc n 1 không nhỏ hơn thì G là đồ thị nửa Hamilton. 2 Chứng minh: Thêm vào G một đỉnh x và nối x với mọi đỉnh của G thì ta nhận được đơn đồ thị G’ có n+1 đỉnh và mỗi đỉnh có bậc không nhỏ hơn n 1 . Do đó theo Định lý 4.2.3, trong G’ có một chu trình Hamilton. Bỏ x ra 2 khỏi chu trình này, ta nhận được đường đi Hamilton trong G. * Định lý (Ore, 1960): Nếu G là một đơn đồ thị có n đỉnh và bất kỳ hai đỉnh nào không kề nhau cũng có tổng số bậc không nhỏ hơn n thì G là một đồ thị Hamilton. * Định lý: Nếu G là đồ thị phân đôi với hai tập đỉnh là V1, V2 có số đỉnh n cùng bằng n (n 2) và bậc của mỗi đỉnh lớn hơn thì G là một đồ thị 2 Hamilton. e da f e a b c d a b c g f h g Hình 1.20. Đồ thị Hamilton Đồ thị G này có 8 đỉnh, đỉnh nào cũng Đồ thị G’ này có 5 đỉnh bậc 4 và 2 đỉnh có bậc 4, nên theo Định lý 4.2.3, G là bậc 2 kề nhau nên tổng số bậc
28 của hai đỉnh đồ thị Hamilton. không kề nhau bất kỳ bằng 7 hoặc 8, nên theo Định lý 4.2.5, G’ là đồ thị Hamilton. a b b Đồ thị phân đôi này có bậc của mỗi đỉnh bằng 2 hoặc 3 (> 3/2), nên theo Định lý 4.2.6, nó là đồ thị Hamilton. d e c Hình 1. 21. Đồ thị phân đôi 1.2. Đồ thị có trọng số và bài toán tìm đường đi ngắn nhất Trong đời sống, chúng ta thường gặp những tình huống như sau: để đi từ địa điểm A đến địa điểm B trong thành phố, có nhiều đường đi, nhiều cách đi; có lúc ta chọn đường đi ngắn nhất (theo nghĩa cự ly), có lúc lại cần chọn đường đi nhanh nhất (theo nghĩa thời gian) và có lúc phải cân nhắc để chọn đường đi rẻ tiền nhất (theo nghĩa chi phí), v.v Có thể coi sơ đồ của đường đi từ A đến B trong thành phố là một đồ thị, với đỉnh là các giao lộ (A và B coi như giao lộ), cạnh là đoạn đường nối hai giao lộ. Trên mỗi cạnh của đồ thị này, ta gán một số dương, ứng với chiều dài của đoạn đường, thời gian đi đoạn đường hoặc cước phí vận chuyển trên đoạn đường đó, Đồ thị có trọng số là đồ thị G=(V,E) mà mỗi cạnh (hoặc cung) e E được gán bởi một số thực m(e), gọi là trọng số của cạnh (hoặc cung) e. Trong phần này, trọng số của mỗi cạnh được xét là một số dương và còn gọi là chiều dài của cạnh đó. Mỗi đường đi từ đỉnh u đến đỉnh v, có chiều dài là m(u,v), bằng tổng chiều dài các cạnh mà nó đi qua. Khoảng cách d(u,v) giữa hai đỉnh u và v là chiều dài đường đi ngắn nhất (theo nghĩa m(u,v) nhỏ nhất) trong các đường đi từ u đến v. Có thể xem một đồ thị G bất kỳ là một đồ thị có trọng số mà mọi cạnh đều có chiều dài 1. Khi đó, khoảng cách d(u,v) giữa hai đỉnh u và v là chiều dài của đường đi từ u đến v ngắn nhất, tức là đường đi qua ít cạnh nhất.
29 1.2.1. Bài toán tìm đường đi ngắn nhất: Cho đơn đồ thị liên thông, có trọng số G=(V,E). Tìm khoảng cách d(u0,v) từ một đỉnh u0 cho trước đến một đỉnh v bất kỳ của G và tìm đường đi ngắn nhất từ u0 đến v. Có một số thuật toán tìm đường đi ngắn nhất; ở đây, ta có thuật toán do E. Dijkstra, nhà toán học người Hà Lan, đề xuất năm 1959. Trong phiên bản mà ta sẽ trình bày, người ta giả sử đồ thị là vô hướng, các trọng số là dương. Chỉ cần thay đổi đôi chút là có thể giải được bài toán tìm đường đi ngắn nhất trong đồ thị có hướng. Phương pháp của thuật toán Dijkstra là: xác định tuần tự đỉnh có khoảng cách đến u0 từ nhỏ đến lớn. Trước tiên, đỉnh có khoảng cách đến a nhỏ nhất chính là a, với d(u0,u0)=0. Trong các đỉnh v u 0, tìm đỉnh có khoảng cách k 1 đến u0 là nhỏ nhất. Đỉnh này phải là một trong các đỉnh kề với u0. Giả sử đó là u1. Ta có: d(u0,u1) = k1. Trong các đỉnh v u0 và v u1, tìm đỉnh có khoảng cách k2 đến u0 là nhỏ nhất. Đỉnh này phải là một trong các đỉnh kề với u 0 hoặc với u 1. Giả sử đó là u2. Ta có: d(u0,u2) = k2. Tiếp tục như trên, cho đến bao giờ tìm được khoảng cách từ u 0 đến mọi đỉnh v của G. Nếu V={u0, u1, , un} thì: 0 = d(u0,u0) < d(u0,u1) < d(u0,u2) < < d(u0,un). 1.2.2. Thuật toán Dijkstra: procedure Dijkstra (G=(V,E) là đơn đồ thị liên thông, có trọng số với trọng số dương) {G có các đỉnh a=u0, u1, , un=z và trọng số m(ui,uj), với m(ui,uj) =
30 nếu (ui,uj) không là một cạnh trong G} for i := 1 to n L(ui) := L(a) := 0 S := V \ {a} u := a while S  begin for tất cả các đỉnh v thuộc S if L(u) +m(u,v) < L(v) then L(v) := L(u)+m(u,v) u := đỉnh thuộc S có nhãn L(u) nhỏ nhất {L(u): độ dài đường đi ngắn nhất từ a đến u} S := S \ {u} end 1.2.3. Bài toán áp dụng: Tìm khoảng cách d(a,v) từ a đến mọi đỉnh v và tìm đường đi ngắn nhất từ a đến v cho trong đồ thị G sau. b 4 6 d 1 1 2 2 2 2 3 3 a e 4 g h 3 2 3 5 5 1 n 3 m k 6 3 Hình 1.22. Tìm đường đi ngắn nhất d(a,v) của đồ thị
31 Bảng1.22. Tìm đường đi ngắn nhất d(a,v) của đồ thị L(a) L(b) L(c) L(d) L(e) L(g) L(h) L(k) L(m) L(n) 0 1 3 3 2 5 2 3 2 5 2 3 4 6 3 4 6 6 10 6 6 8 9 6 8 7 8 * Định lý: Thuật toán Dijkstra tìm được đường đi ngắn nhất từ một đỉnh cho trước đến một đỉnh tuỳ ý trong đơn đồ thị vô hướng liên thông có trọng số. Chứng minh: Định lý được chứng minh bằng quy nạp. Tại bước k ta có giả thiết quy nạp là: (i) Nhãn của đỉnh v không thuộc S là độ dài của đường đi ngắn nhất từ đỉnh a tới đỉnh này; (ii) Nhãn của đỉnh v trong S là độ dài của đường đi ngắn nhất từ đỉnh a tới đỉnh này và đường đi này chỉ chứa các đỉnh (ngoài chính đỉnh này) không thuộc S. Khi k=0, tức là khi chưa có bước lặp nào được thực hiện, S=V \ {a}, vì thế độ dài của đường đi ngắn nhất từ a tới các đỉnh khác a là và độ dài của
32 đường đi ngắn nhất từ a tới chính nó bằng 0 (ở đây, chúng ta cho phép đường đi không có cạnh). Do đó bước cơ sở là đúng. Giả sử giả thiết quy nạp là đúng với bước k. Gọi v là đỉnh lấy ra khỏi S ở bước lặp k+1, vì vậy v là đỉnh thuộc S ở cuối bước k có nhãn nhỏ nhất (nếu có nhiều đỉnh có nhãn nhỏ nhất thì có thể chọn một đỉnh nào đó làm v). Từ giả thiết quy nạp ta thấy rằng trước khi vào vòng lặp thứ k+1, các đỉnh không thuộc S đã được gán nhãn bằng độ dài của đường đi ngắn nhất từ a. Đỉnh v cũng vậy phải được gán nhãn bằng độ dài của đường đi ngắn nhất từ a. Nếu điều này không xảy ra thì ở cuối bước lặp thứ k sẽ có đường đi với độ dài nhỏ hơn Lk(v) chứa cả đỉnh thuộc S (vì Lk(v) là độ dài của đường đi ngắn nhất từ a tới v chứa chỉ các đỉnh không thuộc S sau bước lặp thứ k). Gọi u là đỉnh đầu tiên của đường đi này thuộc S. Đó là đường đi với độ dài nhỏ hơn L k(v) từ a tới u chứa chỉ các đỉnh không thuộc S. Điều này trái với cách chọn v. Do đó (i) vẫn còn đúng ở cuối bước lặp k+1. Gọi u là đỉnh thuộc S sau bước k+1. Đường đi ngắn nhất từ a tới u chứa chỉ các đỉnh không thuộc S sẽ hoặc là chứa v hoặc là không. Nếu nó không chứa v thì theo giả thiết quy nạp độ dài của nó là L k(v). Nếu nó chứa v thì nó sẽ tạo thành đường đi từ a tới v với độ dài có thể ngắn nhất và chứa chỉ các đỉnh không thuộc S khác v, kết thúc bằng cạnh từ v tới u. Khi đó độ dài của nó sẽ là Lk(v)+m(v,u). Điều đó chứng tỏ (ii) là đúng vì Lk+1(u)=min(Lk(u), Lk(v)+m(v,u)). * Mệnh đề: Thuật toán Dijkstra tìm đường đi ngắn nhất từ một đỉnh cho trước đến một đỉnh tuỳ ý trong đơn đồ thị vô hướng liên thông có trọng số có độ phức tạp là O(n2). Chứng minh: Thuật toán dùng không quá n 1 bước lặp. Trong mỗi bước lặp, dùng không hơn 2(n 1) phép cộng và phép so sánh để sửa đổi nhãn của
33 các đỉnh. Ngoài ra, một đỉnh thuộc S k có nhãn nhỏ nhất nhờ không quá n 1 phép so sánh. Do đó thuật toán có độ phức tạp O(n2). 1.2.3. Thuật toán Floyd: Cho G=(V,E) là một đồ thị có hướng, có trọng số. Để tìm đường đi ngắn nhất giữa mọi cặp đỉnh của G, ta có thể áp dụng thuật toán Dijkstra nhiều lần hoặc áp dụng thuật toán Floyd được trình bày dưới đây. Giả sử V={v1, v2, , vn} và có ma trận trọng số là W  W 0. Thuật toán Floyd xây dựng dãy các ma trận vuông cấp n là Wk (0 k n) như sau: procedure Xác định Wn for i := 1 to n for j := 1 to n W[i,j] := m(vi,vj) {W[i,j] là phần tử dòng i cột j của ma trận W0} for k := 1 to n if W[i,k] +W[k,j] < W[i,j] then W[i,j] := W[i,k] +W[k,j] {W[i,j] là phần tử dòng i cột j của ma trận Wk}
34 Chương 2 LÝ THUYẾT MỜ VÀ ỨNG DỤNG BÀI TOÁN QUY HOẠCH TUYẾN TÍNH DẠNG KHOẢNG Một trong nền tảng của toán học hiện đại và các ngành khoa học cơ bản liên quan đến toán học là lý thuyết tập hợp, những khái niệm mới, hệ tiên đề mới làm thay đổi khái niệm tập hợp, dẫn đến thay đổi toàn bộ hệ thống tư duy toán học. Năm 1965 lần đầu tiên nhà toán học người Ba Lan L.A. Zadeh đã đưa ra khái niệm tập hợp mờ. Dựa trên khái niệm mới này nhiều lĩnh vựa của toán học và các ứng dụng mới được phát triển mang lại hiệu quả bất ngờ. 2.1. Khái niệm tập mờ 2.1.1. Định nghĩa tập mờ Tập mờ A được xác định trên không gian nền kinh điển X là một tập mà mỗi phần tử của nó là một cặp (x, (x)) trong đó x X và (x) là ánh xạ A A  : X 0,1 A Ánh xạ  được gọi là hàm liên thuộc (hàm phụ thuộc) của tập mờ A. A Hình 1.1. Tập mờ Giả sử tập mờ B các số tự nhiên nhỏ hơn nhiều so với 6. Xác định phụ thuộc hàm  (x) có dạng liệt kê sau: B B = {(1,1),(2,1),(3,0.8),(4,0.7)} Các số tự nhiên 1 và 2 có độ phụ thuộc  (1) = 1 và  (2)=1 ; các số tự B B nhiên 3 và 4 có độ phụ thuộc nhỏ hơn 1  (3) = 0,8 và  (4) = 0,07. Những B B
35 số không được liệt kê đều có độ phụ thuộc bằng 0. Sử dụng hàm liên thuộc để tính độ phụ thuộc của phần tử x nào đó có ba cách: Tính trực tiếp (nếu  (x) A cho trước dưới dạng công thức tường minh) hoặc - Tra bảng (nếu  (x) dưới dạng bảng ) A - Tìm các giá trị tương ứng trên đồ thị (nếu  (xđược) biểu diễn dạng A đồ thị ) Trong nhiều tài liệu để biểu diễn tập mờ người ta cũng thường dùng ký hiệu sau:  (x )  (x )  (x )  (x ) n  (x ) A A 1 A 2 A 3 A n   A i x1 x2 x3 xn  i 1 xi  (x) Cho các tập hữu hạn và A A cho tập vô hạn. x Phép cộng (+) được hiểu là phép hợp. Ví dụ. Đồ thị hàm liên thuộc của tập mờ A(x) 1 m1 m2 m3 m4 Hình 2. 2 Đồ thị hàm liên thuộc của tập mờ Các hàm liên thuộc  (x) có dạng “trơn” như ở hình vẽ được gọi là hàm A liên thuộc kiểu S. Đối với hàm liên thuộc kiểu S do các công thức biểu diễn có độ phức tạp lớn nên thời gian tính độ phụ thuộc cho một phần tử lâu. Bởi vậy trong kỹ thuật điều khiển mờ thông thường các hàm liên thuộc kiển S hay được thay gần đúng bằng một hàm tuyến tính từng đoạn. Một hàm liên thuộc có dạng tuyến tính từng đoạn được gọi là hàm liên thuộc có mức chuyển đổi tuyến tính. Hàm liên thuộc  (x) như ở hình vẽ với A
36 m1=m2 và m3=m4 chính là hàm thuộc của một tập kinh điển 2.1.2. Một số khái niệm của tập mờ Trong những ví dụ trên các hàm liên thuộc đều có độ cao bằng 1. Điều đó nói rằng các tập mờ đó đều có ít nhất một phần tử với độ phụ thuộc bằng 1. Trong thực tế không phải tập mờ nào cũng có phần tử có độ phụ thuộc bằng 1. Tương ứng với điều đó thì không phải mọi hàm liên thuộc đều có độ cao là 1. Định nghĩa 1. Độ cao của một tập mờ A trên không gian nền X là giá trị h sup (x). x X Ký hiệu sup (x) chỉ giá trị nhỏ nhất trong tất cả các giá trị chặn trên của x X hàm (x) . Một tập mờ với ít nhất một phần tử có độ phụ thuộc bằng 1 được gọi là tập mờ chính tắc tức là h =1 ngược lại một tập mờ A với h < 1 được gọi là tập mờ không chính tắc. Bên cạnh khái niệm về độ cao mỗi tập mờ A còn có hai khái niệm quan trọng khác là: miền xác định và miền tin cậy Định nghĩa 2. Miền xác định của tập mờ A trên không gian nền X được ký hiệu bởi S là tập con của X thoả mãn S Supp (x) {x X /  (x) 0} A A Ký hiệu supp viết tắt của từ tiếng Anh support đã chỉ rõ là tập con trong X chứa các phần tử x mà tại đó hàm  (x) có giá trị dương A Định nghĩa 3. Miền tin cậy của tập mờ tập mờ A trên không gian nền X được ký hiệu bởi T là tập con của X thoả mãn T {x X /  (x) 1} A Định nghĩa 4. Miền biên của tập mờ tập mờ A trên không gian nền X được ký hiệu bởi U là tập con của X thoả mãn
37 U {x X / 0  (x) 1} A Miền tin cậy Miền U Miền xác định Hình 2.3. Miền của tập mờ Định nghĩa 5. Tập cắt ( [0,1]) của tập mờ tập mờ A trên không gian nền X được ký hiệu bởi A là tập con của X thoả mãn A = {x / A(x) } và được gọi là tập cắt mạnh nếu A + = {x / A(x) < } Định nghĩa 6. Tập mức, hay là tập các nhát cắt của tập mờ tập mờ A trên không gian nền X được ký hiệu bởi (A) là tập các tập con của X thoả mãn A = {x / A(x) = } với [0,1] Định nghĩa 7. Tập mờ A trên không gian nền X tuyến tính được gọi là tập mờ lồi nếu A(x) thoả mãn A(x1 +(1-)x2) min{A(x1), A(x2)}I với  x1, x2 X,   [0,1] Định nghĩa 8. Lực lượng của tập mờ A trên không gian nền X được biểu diễn như sau: N(A,  (x))  (x) A  A x A 2.1.3. Các ví dụ về tập mờ Ví dụ. Tập đánh giá nhiệt độ của thời tiết 1 nÕu - 45 x 10 Lạnh = x /10 2 nÕu 10 x 20 0 nÕu x 20
38 Ví dụ trên có thể được hiểu như sau: - Nếu nhiệt độ thấp hơn 10 oC ( -45< x <10 ) tất cả mọi người đều đánh giá mức độ lạnh là 1 (tương ứng với 100%). - Nếu nhiệt độ đạt khoảng từ 10 oC đến 20 oC ( 10≤ x ≤20) thì số người đánh giá mức độ lạnh khác nhau nằm trong khoảng từ 0 ( 0% ) đến 1 (100%), đạt 15oC mức độ lạnh được đánh giá 0.5 (tương ứng với việc có 50% số người cho là lạnh), nếu nhiệt độ là 17 oC mức độ lạnh được đánh giá 0.3 (tương ứng với việc có 30% số người cho là lạnh), . . . Ta có đồ thị sau: 1 0.5 0.3 10 15 17 20 Hình 2.4. Đồ thị đánh giá Ví dụ. Đánh giá nhiệt độ của thời tiết 1 nÕu - 45 x 10 0 nÕu x 10 hoÆc x 30 Lạnh = x /10 2 nÕu 10 x 20 Mát = x /10 1 nÕu 10 x 20 0 nÕu x 20 - x/10 3 nÕu 20 x 30 0 nÕu x 20 hoÆc x 40 1 nÕu x 40 Ấm = x /10 2 nÕu 20 x 30 Nóng = x /10 3 nÕu 30 x 40 - x/10 4 nÕu 30 x 40 0 nÕu x 30 1  lạnh  mát  ấm  nóng 10 20 30 40 Hình 2. 5. Đồ thị đánh giá nhiệt độ
39 2.2. Các phép toán trên tập mờ Những phép toán cơ bản trên tập mờ là phép hợp, phép giao và phép bù giống như định nghĩa về tập mờ các phép toán trên tập mờ cũng sẽ được định nghĩa thông qua các hàm liên thuộc được xây dựng tương tự như các hàm thuộc của các phép hợp, giao, bù giữa hai tập hợp kinh điển. Nói cách khác việc xây dựng các phép toán trên tập mờ được hiểu là việc xác định các hàm liên thuộc cho phép hợp AB, giao AB, bù A từ những tập mờ A, B. Một nguyên tắc cơ bản trong việc xây dựng các phép toán trên tập mờ là không được mâu thuẫn với những phép toán đã có trong lý thuyết tập hợp kinh điển. Mặc dù không giống tập hợp kinh điển, hàm liên thuộc của các tập mờ A B, giao A  B , bù A được định nghĩa cùng với tập mờ, song sẽ không mâu thuẫn với các phép toán tương tự của tập hợp kinh điển nếu như chúng thoả mãn những tính chất tổng quát được phát biểu như “tiên đề” của lý thuyết tập hợp kinh điển. Đó là các “tiên đề” cho phép giao AB, phép hợp và phép bù. 2.2.1. Các phép toán trên tập hợp. 2.2.1.1. Phép hợp Hợp của hai tập hợp A và B ký hiệu là A  B là một tập hợp chứa tất cả các phần tử của A và chứa tất cả các phần tử của B. A  B = {x/ x A hoặc x B } 2.2.1.2. Phép giao Giao của hai tập hợp A và B ký hiệu là AB là một tập hợp gồm các phần tử vừa thuộc A , vừa thuộc B. A  B = {x/ x A và x B } 2.2.1.3. Phép hiệu Cho hai tập hợp A và B. Hiệu của A và B ký hiệu là A\B một tập hợp gồm các phần tử thuộc A , nhưng không thuộc B. A \ B = {x/ x A và x B }
40 2.2.1.4. Phép lấy phần bù Cho A là tập con của tập X. Phần bù của A trong X ký hiệu là A X một tập hợp gồm các phần tử thuộc X , nhưng không thuộc A. AX = {x/ x X và x A } 2.2.1.5. Phép hiệu đối xứng Cho hai tập hợp A và B. Hiệu đối xứng của A và B ký hiệu là A  B một tập hợp gồm các phần tử thuộc A hoặc thuộc B, nhưng không thuộc A  B . A B = (A  B) \ (A  B) = (A \ B) (B \ A) Như vậy phép hiệu đối xứng cho phép đánh giá độ sai lệch giữa hai tập A và B. Đứng trên quan điểm so sánh ta có thể coi nếu N(A  B) càng “bé” thì tập A càng ít sai khác so với tập B. 2.2.1.6. Tích Đề các Cho hai tập hợp A và B. Tích Đề các của A và B ký hiệu là A X B một tập hợp mà mỗi phần tử của nó là một cặp có thứ tự phần tử (a,b) với a thuộc A và b thuộc B. A X B = { (a,b)/ a A; b B) } Ta có thể mở rộng cho tích Đề các của n tập hợp. A1 X A2 X . . . X An= { (a1,a2, ,an )/ ai Ai} 2.2.2. Khái niệm hàm liên thuộc Như trên đã trình bày, nếu A là một tập hợp trong không gian nền X, khi đó phần tử x bất kỳ của X, chỉ có thể có hai khả năng xảy ra, hoặc x A hoặc a A , như vậy để đánh giá khả năng thuộc vào tập A của các phần tử x trong không gian nền X, người ta có thể xây dựng một ánh xạ hàm gọi là hàm liên thuộc (Membership Function). Hàm liên thuộc  A (x)định nghĩa cho tập A trên không gian nền X trong khái niệm tập hợp kinh điển chỉ có hai giá trị là 1 nếu x A hoặc 0 nếu x A. 1 nÕu x A A(x) = 0 nÕu x A
41 Ví dụ . A = { x R/ 2 < x< 6 } Hình sau mô tả hàm thuộc của tập A : 2 6 Hình 2.6 Ví dụ hàm liên thuộc 2.3. Mệnh đề và công thức 2.3.1. Khái niệm mệnh đề Mệnh đề logic được hiểu như là một khẳng định chỉ cho phép trả lời đúng hoặc sai. Mệnh đề sơ cấp là mệnh đề không thể tách nhỏ hơn, nói cách khác nếu ta bỏ đi một phần của nó thì không còn là mệnh đề nữa. Ví dụ. "6 là một số chẵn" là một mệnh đề sơ cấp nhận giá trị "đúng" hay còn gọi có giá trị chân lý là 1. "Với mọi số nguyên dương n, đều có số nguyên lớn hơn nó" là một mệnh đề sơ cấp nhận giá trị "đúng" hay giá trị 1 "Mua hai vé xem ca nhạc vào tối mai " không phải là một mệnh đề. "2000 là một số chẵn và chia hết cho 10 " không phải là một mệnh đề sơ cấp, vì nó có thể tách thành hai mệnh đề đơn giản hơn. 2.3.2. Các kí hiệu Khi thành lập mệnh đề phức tạp từ các mệnh đề đã có, ta thường dùng các liên từ "hay", "và", "không", "nếu thì " các liên từ cũng dùng để biểu diễn các phép toán logic mà chúng ta sẽ đề cập ở mục sau. Các mệnh đề sơ cấp ta kí hiệu bằng các chữ cái A, B, C, Các mệnh đề
42 phức tạp được xây dựng từ các mệnh đề sơ cấp gọi là công thức. Giá trị của công thức là giá trị của các phép toán cho các trường hợp, sau khi các mệnh đề sơ cấp đã có những giá trị xác định. Giá trị của công thức thường được mô tả dạng bảng, theo các trường hợp tương ứng của các mệnh đề sơ cấp, bảng này còn gọi là bảng "chân lý" của công thức. Hai công thức được gọi là đồng nhất bằng nhau, nếu chúng cùng nhận giá trị như nhau cho mọi trường hợp giá trị của các mệnh đề sơ cấp tương ứng. 2.3.3. Các phép toán trên mệnh đề * Phép phủ định. Phủ định của một mệnh đề là một mệnh đề, nhận giá trị đúng nếu mệnh đề đã cho sai và nhận giá trị sai nếu mệnh đề đã cho đúng. Nếu A là mệnh đề, kí hiệu A là phủ định của nó. Bảng 1.1. Phép phủ định A A 0 1 1 0 Ví dụ. A = “Lan có tiền” khi đó Asẽ là “Lan không có tiền” B= “Trái đất là hành tinh duy nhất có sự sống”, B = “Trái đất không phải là hành tinh duy nhất có sự sống” * Phép “hoặc” hay còn gọi là phép cộng logic. Cho A và B là hai mệnh đề, liên kết A hoặc B là một mệnh đề chỉ nhận giá trị sai nếu cả hai mệnh đề đã cho cùng sai, kí hiệu AB. Bảng 1.2. Phép hoặc A B A  B 0 0 0 1 0 1 0 1 1 1 1 1
43 Ví dụ. A= “n là một số chẵn”, B= “n là một số chia hết cho 3” AB =” n là một số chẵn hoặc chia hết cho 3” Khi đó với n= 4 mệnh đề trên đúng, n= 9 mệnh đề trên đúng, n= 6 mệnh đề trên đúng, n= 7 mệnh đề trên sai. * Phép “và ” hay còn gọi là phép nhân logic. Cho A và B là hai mệnh đề, liên kết A và B là một mệnh đề chỉ nhận giá trị đúng nếu cả hai mệnh đề đã cho cùng đúng, kí hiệu AB. Bảng 1.3. Phép nhân logic A B A  B 0 0 0 1 0 0 0 1 0 1 1 1 Ví dụ. Cho A, B là các mệnh đề như trong ví dụ I.4, AB =” n là một số chẵn và chia hết cho 3” Khi đó với n= 4 mệnh đề trên sai, n= 9 mệnh đề trên sai, n= 7 mệnh đề trên sai, n= 6 mệnh đề trên đúng. * Phép cộng XOR. Cho A và B là hai mệnh đề, liên kết A XOR B là một mệnh đề chỉ nhận giá trị đúng nếu chỉ một trong hai mệnh đề đã cho đúng, kí hiệu AB. Bảng 1.4. Phép cộng XOR A B AB 0 0 0 1 0 1 0 1 1 1 1 0
44 Ví dụ. A=” n là một số chẵn”, B=” m là một số lẻ”, trong trường hợp này ta có thể định nghĩa AB = “n+m là một số chẵn” Khi đó với n=3 , m=4 mệnh đề trên sai; n=4, m=6 mệnh đề trên đúng, n= 7, m=3 mệnh đề trên đúng, n= 4, m=3 mệnh đề trên sai. Phép toán  thường được sử dụng để kiểm tra tính chẵn lẻ. * Phép kéo theo. Cho A và B là hai mệnh đề, liên kết A kéo theo B (còn được phát biểu dạng nếu A thì B) là một mệnh đề chỉ nhận giá trị sai nếu A đúng, B sai, kí hiệu A B. Bảng 1.5. Phép kéo theo A B A B 0 0 1 1 0 0 0 1 1 1 1 1 Ví dụ. A=” n là một số chẵn”, B=” n là một số chia hết cho 2”, A B = “n là một số chẵn ” suy ra ” n chia hết cho 2” A=” Lan là một sinh viên chăm chỉ”, B=” Lan là một sinh viên giỏi”, A B = Nếu “Lan là một sinh viên chăm chỉ ” thì ” Lan là một sinh viên giỏi” * Phép tương đương (còn gọi là mệnh đề khi và chỉ khi). Cho A và B là hai mệnh đề, liên kết A tương đương B là một mệnh đề nhận giá trị đúng nếu cả hai mệnh đề đã cho cùng đúng, hoặc cùng sai, kí hiệu AB. Bảng 1.6. Phép tương đương A B A  B 0 0 1 1 0 0 0 1 0 1 1 1
45 Ví dụ. A=” n là một số chẵn”, B=” n là một số chia hết cho 2”, A  B = ” n là một số chẵn” khi và chỉ khi ” n là một số chia hết cho 2” 2.3.4. Các tính chất 1. Công thức De Morgan Các công thức sau được gọi là công thức De Morgan logic A  B A  B, A  B A  B (2.1) Để chứng minh các công thức này ta chỉ cần kiểm tra bảng chân lý sau: Bảng 1.7. Bảng chân lý A B A  B A  B A B A  B A  B 1 1 0 0 1 1 0 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 1 1 0 0 1 1 0 0 1 1 * Các tính chất Một số tính chất cơ bản sau đây ta có thể dễ dàng chứng minh bằng cách lập và so sánh các bảng chân lý tương ứng. a- A B A  B b- A  B = ( A B )  ( B A ) c- A B B A 2.4. Suy luận xấp xỉ dựa trên logic mờ Suy diễn xấp xỉ hay còn gọi là suy luận mờ đó là quá trình suy ra những kết luận dưới dạng các mệnh đề mờ trong điều kiện các quy tắc, các luật, dữ liệu đầu vào cho trước cũng không hoàn toàn xác định. Trong công trình của mình Zadeh đưa ra khái niệm lập luận xấp xỉ như sau:
46 Bảng 1.8. Suy luận xấp xỉ Tiền đề 1 Nếu màu của quả cà chua nào đó là đỏ thì quả cà chua đó là chín. Điều kiện Màu của cà chua Q là rất đỏ. Kết luận Quả cà chua Q rất chín. Chúng ta thấy lược đồ này tương tự như luật Modus ponens trong logic kinh điển: A B, có A cho phép ta rút ra kết luận B. Tuy nhiên ở lược đồ trên trong giả thiết (tiền đề) ta không có A mà có A' =' Rất đỏ' một biến tướng của A, khi đó ta có thể rút ra kết luận nào đó xấp xỉ B là B' = 'Rất chín' chẳng hạn. Vấn đề là cần xây dựng phương pháp luận cho phép lựa chọn kết luận B' như thế nào phù hợp với quy luật thực tiễn. Nhờ tính mềm dẻo của phương pháp lập luận mờ chúng ta sẽ có nhiều phương pháp suy diễn xấp xỉ. Xét lược đồ lập luận mờ đa điều kiện sau: Bảng 1.9. Bảng điều kiện suy diễn xấp sỉ Tiên đề 1 if X = A1 then Y = B1 Tiên đề 2 if X = A2 then Y = B2 : : : : Tiên đề n if X = An then Y = Bn Tiên đề if X = An+1 then Y = Bn+1 n+1 Kết luận Y = B0 Trong đó A i và B i là các điều kiện mờ, mô hình này mô tả quan hệ phụ thuộc giữa hai đại lượng A và B. Giá trị X = A 0 được gọi là Input còn Y = B 0 gọi là Output. Phương pháp lập luận xấp xỉ tính Y = B0 gồm các bước sau: Bước 1. Giải nghĩa các mệnh đề điều kiện: Chúng ta xem các khái niệm mờ Ai, Bi là các nhãn của tập mờ biểu thị ngữ nghĩa của A i, Bi. Để cho tiện ta
47 ký hiệu hàm giá trị chân lý tương ứng A i(u) và B i(v) trên không gian tham chiếu U và V. Một cách trực cảm, mỗi mệnh đề Nếu . . . thì được hiểu là một phép kéo theo logic mờ A i(u) B i(v) . Khi u và v biến thiên, biểu thức này xác định ánh xạ hàm giá trị chân lý i : UX V [0,1]. Bước 2. Kết nhập (aggregation): Qua các phép toán logic mờ chúng ta thu được công thức dạng  @n  trong đó @ là một trong các công thức mô tả giá trị chân lý i 1 i của các phép toán logic hội và tuyển ( chẳng hạn ta có thể chọn các hàm tương ứng là ( Min và Max). Việc kết nhập như vậy bảo đảm  chứa các thông tin được cho bởi các mệnh đề if . . then dạng mệnh đề logic mờ. Bước 3. Tính OutputB0: Để tính B0 ta sử dụng công thức B0 = A0o , trong đó o là phép hợp thành của A0 và . Bước 4. Khử mờ: Kết quả tính ở bước 3 là một giá trị mờ. Trong nhiều bài toán điều khiển người ta cần xác định giá trị thực của biến trong Y. Phương pháp tính giá trị thực "tương ứng" với giá trị chân lý của B 0 được gọi là phương pháp khử mờ. Sẽ không có phương pháp nào "tốt nhất" được đưa ra mà chỉ có thể đánh giá theo một giá trị ngưỡng nào đó tuỳ thuộc quá trình thử nghiệm hoặc trực cảm nào đó. Ví dụ ta có thể khử mờ theo trung bình cộng có trọng số, được cho bởi công thức:  vB0 (v) v V defuz(B0 )  B0 (v) v V Có thể hình dung phương phương pháp lập luận mờ bằng mô hình tổng quát sau:
48 Phương pháp Input A0 lập luận và suy Output B0 diễn xấp xỉ Bảng 2.7. Mô hình suy diễn xấp sỉ 2.5. Ứng dụng logic mờ xây dựng bài toán tối ưu mờ 2.5.1. Tối ưu mờ Tối ưu mò (Fuzzy Optimization) hiện nay cũng được rất nhiều người quan tâm, các kết quả trong lĩnh vực này đã đạt được nhiều thành tựu quan trọng. Như chúng ta đều biết bản chất của bài toán tối ưu là tìm trong tập các phương án chấp nhận được, phương án tốt nhất theo tiêu chí nào đó mà có thể chấp nhận được là mờ. Bài toán hàm mục tiêu là mờ. Bài toán điều kiện tập chấp nhận được là mờ. Bài toán hàm mục tiêu và điều kiện tập chấp nhận được là mờ. 2.5.1.1. Quy hoạch tuyến tính mờ * Bài toán Xét bài toán quy hoạch tuyến tính tổng quát n min{f (x)  c j x j } (6) j 1 n  a ij x j b i ,i 1,2, , k j 1 n với điều kiện  aij x j bi ,i k 1, , m (7) j 1 n  aij x j bi ,i m 1, ,l j 1 x j 0, j 1,2, , r;r n (8) Trong đó: (6) Hàm mục tiêu Là một tổ hợp tuyến tính của các biến số, biểu thị một đại lượng nào đó mà ta cần phải quan tâm của bài toán.
49 (7) Các ràng buộc của bài toán Là các phương trình hoặc bất phương trình tuyến tính n biến số, sinh ra từ điều kiện của bài toán. (8) Các hạn chế về dấu của các biến số. Trong truờng hợp đặc biệt, bài toán quy hoạch tuyến tính có dạng n min{f (x)  c j x j } (9) j 1 n với điều kiện (10)  a ij x j bi , i 1,2, , m j 1 x j 0, j 1,2 , n (11) Bài toán có dạng (9), (10), (11) được gọi là bài toán quy hoạch tuyến tính dạng chính tắc. Bài toán quy hoạch tuyến tính tổng quát có thể đưa về bài toán quy hoạch tuyến tính dạng chính tắc tương đương nhờ các quy tắc sau. n n + Nếu có bất đẳng thức  aij x j b ihoặc  aij x j b ithì ta đưa thêm ẩn j 1 j 1 n phụ xn i 0, với hệ số hàm mục tiêu cn i 0 để có  aij xn i bi hoặc j 1 n  aij xn i bi j 1 + Nếu có ẩn xk chưa ràng buộc về dấu, thì có thể thay nó bởi hai biến mới xk và xk không âm, với xk xk xk . Ví dụ: Đưa bài toán sau về dạng chính tắc min (x1 x2 x3 ) x1 x2 x3 5 x 2x x 3 Với điều kiện 1 2 3 x1 x2 x3 4 x1, x3 0 Ta đưa thêm ẩn phụ x4 , x5 0 và thay x2bởi x2 , x2 0,với x2 x2 x2 để có min (x1 x2 x3 )
50 x1 x2 x2 x3 5 x1 2x2 2x2 x3 x4 3 Với điều kiện x1 x2 x2 x3 x5 4 x1, x2 , x2 , x3 , x4 , x5 0 Như vậy từ nay về sau ta chỉ cần nghiên cứu bài toán quy hoạch tuyến tính ở dạng chính tắc. 2.5.1.2. Quy hoạch tuyến tính mờ dạng khoảng Trong phần này chúng ta xem xét bài toán quy hoạch tuyến tính mờ dạng khoảng như sau ~ ~ ~ ~ ~ max c1 x1 cn xn ~ ~ ~ ~ ~ ~ Với điều kiện ai1 x1 ain xn R bi ,i M , (12) x j 0, j N ~ ~ ~ ở đây các tham số c j ,a ij và bi được xem như các khoảng trong R. ~ ~ ~ Ví dụ: c j [c j ,c j ],a ij [a ij ,a ij ] và bi [bi ,bi ] khi đó c j ,c j ,a ij ,a ij và bi ,bi là các giới hạn trên và dưới ứng với các khoảng, các giá trị hàm liên ~ ~ ~ thuộc của c j ,a ij và bi là các hàm số đặc trưng của khoảng.
51 Chương 3 XÂY DỰNG GIẢI THUẬT GIẢI BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT BIỂU DIỄN CUNG ĐƯỜNG ĐI LÀ SỐ MỜ DẠNG KHOẢNG Giả sử xét đồ thị có hướng G=(V,E) mỗi cung (u,v) E được đặt tương ứng là số mờ dạng khoảng. Các bài toán đường đi ngắn nhất được chia thành 3 dạng chính: Tìm đường đi ngắn nhất từ một nút nguồn đến một nút đích Tìm đường đi ngắn nhất từ một nút nguồn đến tất cả các nút đích Tìm đường đi ngắn nhất giữa hai nút bất kỳ. Bài toán được đề cập đến ở đây là bài toán ở dạng thứ nhất: tìm đường đi ngắn nhất từ một nút nguồn đến một nút đích cho trước. Input: Tập hữu hạn các đỉnh V, tập các cung E, nút nguồn 1; nút đích: n Tải năng (hoặc chiều dài) của các cung Output Đường đi ngắn nhất từ đỉnh 1 đến đỉnh n Mục đích chính là chuyển bài toán đường đi ngắn nhất về dạng bài toán quy hoạch tuyến tính. * Xây dựng đường đi trong đồ thị: Theo định nghĩa với bài toán đường đi ngắn nhất ta xây dựng đường đi trên cung i,j là một hàm x(i,j) thỏa mãn các tính chất sau: - xij=0 hoặc xij=1 ứng với việc có hay không sử dụng cung i,j trong đường đi Tổng đường đi ra tại nút nguồn bằng 1; tổng đường đi vào tại nút đích bằng 1
52 Tổng đường đi vào một nút i bất kỳ bằng tổng đường đi ra tại nút đó. * Giới hạn đường đi: Đường đi trên cung không vượt quá tải năng của cung f (u,v) c(u,v) * Cân bằng đường đi tại nút đỉnh: Tổng đường đi vào tại một đỉnh bằng tổng đường đi ra tại đỉnh đó (trừ đỉnh đầu và đỉnh đích) n n  f (i, j)  f ( j,i) (với i là một đỉnh thông thường trong đồ thị) j 1 j 1 Tổng đường đi ra khỏi đỉnh nguồn bằng tổng đường đi vào đỉnh đích n n  f (s, j)  f ( j,t) j 1 j 1 3.1. Mô hình bài toán Gọi cij là chiều dài cung i,j. Bài toán đường đi ngắn nhất trong đồ thị được phát biểu như sau: * Hàm mục tiêu: n n Min cij xij i 1 j 1 * Các ràng buộc: 1 i 1  n n  xij  x ji 1 i n  j 1 j 1 0 otherwise xij 0 hoặc 1 i=1,2, ,n j=1,2, ,n
53 3.2. Ví dụ Giả sử có đồ thị G(u,v) như trong sơ đồ 1. Ta chuyển bài toán tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh 6 về bài toán quy hoạch tuyến tính: 2 4 1 Hàm mục tiêu: 6 6 6 minimize cij xij i 1 j 1 3 5 Hình 3.1. Đồ thị G(u,v) có hướng Các ràng buộc: x12+x13 = 1 -x12 + x23 + x24+ x25 = 0 -x13 – x23 + x35 = 0 -x24 + x45 + x46 = 0 -x35 – x25 – x45 + x56 = 0 -x46 – x56 = -1 xij = 0 hoặc 1 3.3. Bài toán tìm đường đi ngắn nhất có các cung mờ Trong thực tế, chiều dài các cung của mạng không biểu thị bằng các số rõ mà hay được thể hiện thông qua các giá trị xấp xỉ. Ví dụ quãng đường từ A đến B khoảng 70 km. Trong những trường hợp này phải dùng số mờ để biểu diễn chiều dài các cung.
54 ~ Gọi l ij là giá trị mờ của cung i,j. Khi đó bài toán đường đi ngắn nhất được phát biểu như sau: Hàm mục tiêu: n n ~ Min  l ij xij i 1 j 1 Các ràng buộc: 1 i 1  n n  xij  x ji 1 i n  j 1 j 1 0 otherwise xij 0 hoặc 1 i=1,2, ,n j=1,2, ,n Để giải quyết bài toán này, trước tiên chúng ta xem các cách biểu diễn số ~ mờ l ij . Sau đó trong chương sau sẽ giới thiệu thuật toán tìm đường đi ngắn nhất áp dụng trên các số mờ. 3.3.1. Xây dựng tập mờ Tập mờ A xác định trên không gian nền X là một tập hợp thỏa mãn: + Mỗi phần tử của A có dạng (x,A(x)) + A(x) là một ánh xạ từ X [0,1] được gọi là hàm liên thuộc xác định độ thuộc của x vào tập A 3.3.2. Miền xác định của tập mờ: Miền xác định của tập mờ A trên không gian nền X là một tập con các phần tử của X được ký hiệu S thỏa mãn S= {x X | A(x) > 0}
55 3.3.3. Miền tin cậy của tập mờ Miền tin cậy của tập mờ A trên không gian nền X là một tập con các phần tử của X được ký hiệu T thỏa mãn T= {x X | A(x) = 1} 3.3.4. Miền biên của tập mờ Miền biên của tập mờ A trên không gian nền X là một tập con các phần tử của X được ký hiệu U thỏa mãn U= {x X | 0< A(x) <1} Ví dụ: Ta định nghĩa young - trẻ. Là tập hợp những người từ 20 tuổi trở xuống, những người từ 30 tuổi trở lên không còn trẻ nữa, nhưng những người từ 21 đến 30 tuổi vẫn thuộc tập Young với độ liên thuộc nào đó nhỏ hơn 1. Ta định nghĩa hàm liên thuộc của tập Young như sau: 1 age(x) 20 age(x) 20  young 1 10 age(x) 30 10 0 age(x) 30 Hàm liên thuộc được thể hiện dưới dạng đồ thị như sau:  young 1 20 30 age(x) Hình 3.2. Miền biên của tập mờ 3.4. Khái niệm số mờ 3.4.1. Định nghĩa số mờ Số mờ là một trường hợp đặc biệt của tập mờ khi hàm liên thuộc thỏa mãn các tính chất sau:
56 - A là normalized (miền tin cậy khác rỗng) - A là singular (mỗi giá trị rõ phải thuộc miền tin cậy) - A là đơn điệu tăng trên biên trái và đơn điệu giảm trên biên phải Trong ngôn ngữ nói, có thể mô tả số mờ với các từ như xấp xỉ, khoảng; gần đến, 3.4.2. Số mờ dạng tam giác: - Là số mờ được mô tả kiểu "x xấp xỉ bằng a" - Biểu diễn một khoảng (a- , a, a+) - Hàm thuộc được xác định như sau:  A ( x ) x 1 0 a1 a2 x a3 Hình 3.3. Số mờ dạng tam giác 0 x a1 x a1 a1 x a2 a2 a1  A (x) a3 x a2 x a3 a3 a2 0 x a3 3.4.3. Số mờ dạng hình thang: - Là số mờ được mô tả kiểu "x khoảng từ a đến b" - Biểu diễn một khoảng (a- , a, b,b+)
57 - Hàm thuộc được xác định như sau: a x 1 x [a , a) 1 x [a,b] A = x b 1 x (b,b  ]  0 other 1 a- a b b+ Hình 3.4. Số mờ dạng hình thang ~ _ Thường được biểu diễn qua bộ 4 số: l (l,l, , ) 1 _ 0 l l  Hình 3.4.Biểu diễn số mờ dạng hình thang
58 3.5. Một số phương pháp giải quyết bài toán 3.5.1. Phép toán thực hiện trên số mờ tam giác. Trình bày khái niệm về độ tương tự giữa hai số mờ tam giác và một giải thuật tìm đường đi ngắn nhất dựa trên các phép toán đã định nghĩa 3.5.1.1. Tổng hai số mờ: ~ ~ Giả sử có 2 số mờ dạng tam giác L1 (a1,b1,c1) và L2 (a2 ,b2 ,c2 ) ~ ~ Khi đó: L1 L2 (a1 a2 ,b1 b2 ,c1 c2 ) 3.5.1.2. Chiều dài nhỏ nhất: ~ ~ Với hai số mờ tam giác L1 (a1,b1,c1) và L2 (a2 ,b2 ,c2 ) ~ min L sup Lk | Lk min(L1, L2  k 1,2, ,n ~ ~ ~ min L (a,b,c)=Min(L1, L2 )=(min(a1,a2), min(b1,b2), min(c1,c2)) 3.5.1.3. Độ tương tự giữa hai số mờ: ~ ~ Giả sử có 2 số mờ dạng tam giác Li (ai ,bi ,ci ) và L (a,b,c) Ta tìm cách thể hiện độ tương tự giữa hai số này. Khi giao của hai tam giác càng lớn thì độ tương tự giữa hai số mờ càng ~ ~ cao. Ký hiệu Si là độ tương tự giữa Li và L ~ ~ Li  L  0 ~ ~ 100(c a )2 Si i Li  L j  2(ci ai)(c b) (bi ai )
59 3.5.1.4. Giải thuật tìm đường đi mờ ngắn nhất Step1: Tìm tất cả các đường đi có thể từ đỉnh nguồn s đến đỉnh đích d Tính khoảng cách từng đường đi ~ Step 2: Tìm L min của tất cả các đường đi đã tính ~ Step 3: Tính độ tương tự của từng đường đi với L min Step 4: Đưa ra đường đi có độ tương tự lớn nhất 3.6. Ví dụ áp dụng bài toán: * Ví dụ 1. Cho sơ đồ mạng như hình sau. Tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh 6 (56,58,72) 2 4 (33,45,50) (88,92,134) (32,40,46) 1 (50,52,61) 6 (51,79,85) (42,57,61) (75,110,114) 3 5 (43,55,60) Step1: Tính độ dài các đường đi có thể có từ đỉnh 1 đến đỉnh 6 P1: 1-2-3-5-6 L 1=(201,262,285) P2: 1-2-4-5-6 L 2=(196,253,282) P3: 1-2-4-6 L 3=(177,195,256) P4: 1-2-5-6 L 4=(159,234,249) P5: 1-3-5-6 L 5=(160,222,235) ~ ~ Step2: Tìm L min Ta được L min = (159,195,235)
60 ~ min Step3: Tính độ tương tự giữa L và các Li Path ~ Ranking S(L, L min) P1: 1-2-3-5-6 6.81 5 P2: 1-2-4-5-6 9.11 4 P3: 1-2-4-6 36.70 2 P4: 1-2-5-6 27.9 3 P5: 1-3-5-6 36.76 1 Step4: Đưa ra đường đi có độ tương tự lớn nhất. Ta thu được kết quả đó là P5 đi qua các đỉnh 1-3-5-6.
61 Chương 4 CÀI ĐẶT THỬ NGHIỆM 4.1. Một số giao diện của chương trình 4.1.1. Giao diện chính của chương trình Hình 4.1. Giao diện chính của chương trình 4.1.2. Các bước thực hiện chương trình. Hình 4.2. Các bước thực hiện
62 4.1.3. Các chức năng chính của chương trình 4.1.3.1. Thuật toán tìm đường đi ngắn nhất. Hình 4.3. Mô phỏng thuật toán 4.1.3.2. Chọn số đỉnh Hình 4.4. Chọn số đỉnh
63 4.1.3.3. Chọn số cung đường đi Hình 4.5. Chọn cung đường đi 4.1.3.4. Nhập các cung mờ 4.1.3.5.Hình 4.6. Tìm Nhập tất cáccả các cung đường a, b, đic và thông báo
64 4.1.3.5 Tìm tất cả các đường đi Hình 4.7. Tìm tất cả các đường đi 4.1.3.6. Tính giá trị L nhỏ nhất Hình 4.7. Tính giá trị Lmin
65 4.1.3.7. Tính độ tương tự Hình 4.8. Bảng độ tương tự 4.1.3.8. Tìm đường đi tối ưu Hình 4.9. Bảng thông báo kết quả tìm được
66 4.2. Cài đặt – thử nghiệm Chương trình được xây dựng bằng ngôn ngữ Visual studio 6.0, Sau khi chọn đỉnh chọn đường đi nhập dữ liệu cho các cung mờ của đồ thị. Hình 4.10. Chọn đỉnh nhập dữ liệu Hình 4.11. Kết quả kiểm tra xây dựng hàm liên thuộc
67 Hình 4.9. Kết quả tất cả các đường đi Hình 4.9. Bảng kết quả tìm Lmin Hình 4.9. Bảng kết quả độ tương tự Hình 4.9. Bảng kết quả đường đi ngắn nhất
68 4.3. Đánh giá hiệu quả thuật toán đã xây dựng Qua quá trình nghiên cứu, xây dựng thuật toán tôi đã đề xuất trong báo cáo: ứng dụng các giải thuật tìm đường đi ngắn nhất cổ điển và logic mờ để cải tiến tìm đường đi ngắn nhất với dữ liệu cung mờ dạng khoảng. Giải thuật tìm đường đi ngắn nhất được xây dựng trên phương pháp là tìm tất cả các phương án đường đi từ đỉnh đầu đến đỉnh cuối và lọc ra phương án tối ưu nhất từ các cung mờ dạng khoảng. Chương trình đã được xây dựng dựa trên các giải thuật Tìm đường đi ngắn nhất nhưng chủ yếu áp dụng cho các trọng số được biểu diễn cung mờ dạng khoảng đã đưa ra kết quả tối ưu nhất cho bài toán. Với nghiên cứu của tôi đưa ra tập trung xoay quanh Kiểm tra hàm liên thuộc - Tìm ra tất cả các đường đi từ các cung mờ - Tìm ra độ dài cung mờ nhỏ nhất giá trị Lmin - Tính ra độ tương tự - Tìm ra đường đi ngắn nhất từ các cung mờ với độ tương tự cao nhất. Một vài hạn chế của phương pháp là chưa được quan tâm nhiều đến đa đỉnh >10 đa khoảng và Hệ tuyến tính đa mục tiêu. Chương trình xây dựng còn rất nghèo nàn chưa khoa học.
69 KẾT LUẬN VÀ KIẾN NGHỊ 1. Kết luận Luận văn đã trình bày và giải quyết được một số vấn đề sau: Trình bày một cách tổng quan về lý thuyết đồ thị và thuật toán giải bài toán tìm đường đi ngắn nhất có trọng số xác định. Các giải thuật bao gồm ( Dijkstra, Bellman-Ford, Floyd ) và áp dụng giải bài toán mẫu theo giải thuật dijkstra. Lý thuyết mờ và ứng dụng giải bài toán quy hoạch tuyến tính dạng khoảng. Tìm ra phương án tối ưu trong bài toán: Bài toán hàm mục tiêu là mờ, bài toán điều kiện tập chấp nhận được là mờ, bài toán hàm mục tiêu và điều kiện tập chấp nhận được là mờ. Tập trung nghiên cứu xây dựng thuật toán xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất được biểu diễn dưới dạng cung đường đi là số mờ dạng khoảng. Các bài toán đường đi ngắn nhất được chia thành 3 dạng chính: Tìm đường đi ngắn nhất từ một nút nguồn đến một nút đích Tìm đường đi ngắn nhất từ một nút nguồn đến tất cả các nút đích Tìm đường đi ngắn nhất giữa hai nút bất kỳ. Bài toán được đề cập đến ở đây là bài toán ở dạng thứ nhất: tìm đường đi ngắn nhất từ một nút nguồn đến một nút đích cho trước. Mục đích chính là chuyển bài toán đường đi ngắn nhất về dạng bài toán quy hoạch tuyến tính dạng khoảng. Đồng thời chỉ ra được đường đi có các cung mờ ngắn nhất và đường đi tối ưu nhất dựa trên độ tương tự cao nhất
70 2. Kiến nghị Một trong những quan tâm hàng đầu là không chỉ tìm ra được đường đi có các cung mờ ngắn nhất và đường đi tối ưu nhất dựa trên độ tương tự cao nhất mà còn áp dụng được với bài toán dạng quy hoạch tuyến tính dạng khoảng và bài toán dạng quy hoạch tuyến đa mục tiêu. Như những hạn chế đã nêu ở phần trên thì hướng phát triển tiếp theo sẽ là quan tâm tới giải thuật bài toán quy hoạch tuyến đa mục tiêu
71 TÀI LIỆU THAM KHẢO Tiếng Việt [1] PGS. TS Nguyễn Thiện Luận (2006), Toán rời rạc. Học Viện Kỹ Thuật Quân sự - Hà Nội. [2] PGS. TS Nguyễn Thiện Luận (2006), Lý thuyết mờ và ứng dụng. Học Viện Kỹ Thuật Quân sự - Hà Nội. [3] Nguyễn Doãn Phước (2001), Hệ mờ, mạng nơron và ứng dụng, NXB Khoa học kỹ thuật. [4] PGS. TS. Bùi Minh Trí (2006), Tối ưu hóa . Đại học Bách khoa - Hà Nội. Tiếng Anh [1] Bortolan, G. and R. Degani. 1985. A review of some methods for ranking fuzzy subsets, Fuzzy Sets and Systems 15, 1–19. [2] Buckley, J.J. 1987. The fuzzy mathematics of finance. Fuzzy Sets and Systems 21, 257–273. [3] Chen, S.-H .1985. Ranking Fuzzy Numbers with Maximizing Set and Minimizing Set, Fuzzy Sets and Systems 17, 113–129. [4] Cheng, C.-H. 1998. A New Approach for Ranking Fuzzy Numbers by Distance Method, Fuzzy Sets and Systems 95, 307–317. [5] Chuang T.N, Kung J.Y, 2005 .The fuzzy shortest path length and the corresponding shortest path in a network, Computers and Operations Research 32 , 1409–1428.
72 [6] Delgado, M., J. L. Verdegay, and M. A. Vila. 1988. A Procedure for Ranking Fuzzy Numbers using Fuzzy Relations, Fuzzy Sets and Systems 26, 49–62. [7] Dubois D, Prade H. 1980. Fuzzy sets and systems: theory and applications. New York: Academic Press. [8] Dubois, D. and H. Prade. 1983. Ranking Fuzzy Numbers in the Setting of Possibility Theory, Information Sciences 30, 183–224. [9] Hansen P, Beckmann M, Kunzi HP. 1980. Multiple criteria decision making. In: Theory and applications, Lecture Note in Economics and in Mathematical Systems, vol. 177. Berlin: Springer, pp. 109–27. [10] Henig MI. 1994. Efficient interactive methods for a class of multi- attribute shortest path problems. Management Science, 40, 891–7. [11] Hyung LK, Song YS, Lee KM. 1994. Similarity measure between fuzzy sets and between elements. Fuzzy Sets and Systems, 62291–3.
73 LÝ LỊCH TRÍCH NGANG Họ và tên: PHAN NHƯ MINH Ngày tháng năm sinh: 23/ 09/ 1978 Nơi sinh: Vĩnh Phúc Địa chỉ liên lạc: Khu tập thể . Trường CD GTVT – Vĩnh Yên – Vĩnh Phúc QUÁ TRÌNH ĐÀO TẠO - Từ tháng 9/1999 đến 7/2004: Học tại Đại học Khoa học tự nhiên - ĐHQGHN - Khoa tin học- Chuyên ngành tin học. QUÁ TRÌNH CÔNG TÁC - Từ 9/2004 đến 10/2008: Công tác tại Công ty máy tính Vinh Quang. Ngõ 16 – Khu tập thể Đại học thủy lợi. Đống đa – Hà Nội - Từ 15/2008 đến nay: Công tác tại trường Cao đẳng Giao thông vận tải.