Tài liệu ứng dụng giải thuật di truyền tìm đường đi tối ưu trong giao thông đường thủy tại tỉnh vĩnh long

ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA LÊ HOÀNG AN ỨNG DỤNG GIẢI THUẬT DI TRUYỀN TÌM ĐƯỜNG ĐI TỐI ƯU TRONG GIAO THÔNG ĐƯỜNG THỦY TẠI TỈNH VĨNH LONG LUẬN VĂN THẠC SĨ KỸ THUẬT Đà Nẵng, Năm 2017 ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA LÊ HOÀNG AN ỨNG DỤNG GIẢI THUẬT DI TRUYỀN TÌM ĐƯỜNG ĐI TỐI ƯU TRONG GIAO THÔNG ĐƯỜNG THỦY TẠI TỈNH VĨNH LONG Chuyên ngành: Khoa học máy tính Mã số: 60.48.01.01 LUẬN VĂN THẠC SĨ KỸ THUẬT Người hướng dẫn khoa học: TS. PHẠM MINH TUẤN Đà Nẵng - Năm 2017 i LỜI CAM ĐOAN Tôi xin cam đoan: - Những nội dung trong luận văn này là do tôi thực hiện dưới sự hướng dẫn trực tiếp của TS. Phạm Minh Tuấn. - Mọi tham khảo dùng trong luận văn đều được trích dẫn rõ ràng và trung thực về tên tác giả, tên công trình, thời gian và địa điểm công bố. Tác giả luận văn Lê Hoàng An ii MỤC LỤC LỜI CAM ĐOAN ...........................................................................................................i MỤC LỤC ..................................................................................................................... ii TÓM TẮT LUẬN VĂN ................................................................................................v DANH MỤC CÁC TỪ VIẾT TẮT .............................................................................vi DANH MỤC CÁC BẢNG.......................................................................................... vii DANH MỤC CÁC HÌNH ......................................................................................... viii MỞ ĐẦU .........................................................................................................................1 1. Lý do chọn đề tài .....................................................................................................1 2. Mục tiêu và nhiệm vụ đề tài.....................................................................................2 3. Đối tượng và phạm vi nghiên cứu ...........................................................................2 4. Phương pháp nghiên cứu .........................................................................................2 5. Mục đích và ý nghĩa của đề tài ................................................................................2 6. Cấu trúc của luận văn...............................................................................................3 CHƯƠNG 1. CƠ SỞ LÝ THUYẾT .............................................................................4 1.1. LÝ THUYẾT ĐỒ THỊ ..........................................................................................4 1.1.1. Các khái niệm trên đồ thị ...............................................................................4 1.1.1.1. Định nghĩa đồ thị .....................................................................................4 1.1.1.2. Các thuật ngữ cơ bản ...............................................................................5 1.1.1.3. Biểu diễn đồ thị trên máy tính .................................................................7 1.1.2. Bài toán đường đi ngắn nhất ..........................................................................9 1.1.2.1. Đặt vấn đề ................................................................................................9 1.1.2.2. Phát biểu bài toán ....................................................................................9 1.1.3. Các thuật toán tìm đường đi ngắn nhất ........................................................10 1.1.3.1. Thuật toán Dijsktra ................................................................................10 1.1.3.2. Thuật toán Bellman-Ford ......................................................................11 1.2. GIẢI THUẬT DI TRUYỀN ...............................................................................13 1.2.1. Giới thiệu......................................................................................................13 1.2.2. Nguyên tắc thiết kế giải thuật di truyền .......................................................13 1.2.2.1. Các toán tử di truyền .............................................................................14 1.2.2.2. Các thành phần của giải thuật di truyền ................................................14 1.2.2.3. Các bước của giải thuật di truyền ..........................................................15 1.2.3. Một số ứng dụng của giải thuật di truyền ....................................................16 1.2.3.1. Bài toán Người bán hàng du hành (TSP) ..............................................16 iii 1.2.3.2. Bài toán lập lịch .....................................................................................18 1.2.3.3. Lập thời khóa biểu cho trường học .......................................................18 1.2.3.4. Phân hoạch đối tượng và đồ thị .............................................................19 1.3. ĐẶC ĐIỂM GIAO THÔNG ĐƯỜNG THỦY TỈNH VĨNH LONG .................19 1.3.1. Các nhân tố ảnh hưởng đến giao thông đường thủy tỉnh Vĩnh Long ..........19 1.3.1.1. Vị trí địa lý ............................................................................................19 1.3.1.2. Địa hình .................................................................................................20 1.3.1.3. Khí hậu ..................................................................................................20 1.3.1.4. Thủy văn ................................................................................................20 1.3.2. Thực trạng giao thông đường thủy tỉnh Vĩnh Long .....................................21 1.3.2.1. Quá trình phát triển giao thông đường thủy ..........................................21 1.3.2.2. Mạng lưới giao thông đường thủy tỉnh Vĩnh Long ...............................21 CHƯƠNG 2. ỨNG DỤNG GIẢI THUẬT DI TRUYỀN TÌM ĐƯỜNG ĐI TỐI ƯU TRONG GIAO THÔNG ĐƯỜNG THỦY TẠI TỈNH VĨNH LONG .............26 2.1. PHÁT BIỂU BÀI TOÁN ....................................................................................26 2.2. XÂY DỰNG ỨNG DỤNG.................................................................................26 2.2.1. Khảo sát, phân tích dữ liệu ...........................................................................26 2.2.1.1. Về hệ thống sông ...................................................................................26 2.2.1.2. Về cảng, bến hàng hóa ..........................................................................27 2.2.2. Tổ chức dữ liệu ............................................................................................27 2.2.2.1. Danh bạ các nút giao, các bến cảng, bến hàng hóa ...............................27 2.2.2.2. Khoảng cách giữa các nút giao, bến cảng, bến hàng hóa ......................28 2.2.3. Triển khai, xây dựng ứng dụng ....................................................................29 2.2.3.1. Khởi tạo quần thể ..................................................................................30 2.2.3.2. Hàm đánh giá cá thể ..............................................................................31 2.2.3.3. Lựa chọn cá thể .....................................................................................32 2.2.3.4. Lai ghép .................................................................................................32 2.2.3.5. Đột biến .................................................................................................33 CHƯƠNG 3. THỬ NGHIỆM VÀ ĐÁNH GIÁ.........................................................34 3.1. GIAO DIỆN CHƯƠNG TRÌNH ........................................................................34 3.2. THỬ NGHIỆM, ĐÁNH GIÁ .............................................................................37 3.2.1. Tìm đường đi qua các nút giao giữa các con sông .......................................37 3.2.1.1. Thử nghiệm lần 1...................................................................................39 3.2.1.2. Thử nghiệm lần 2...................................................................................40 3.2.1.3. Thử nghiệm lần 3...................................................................................42 iv 3.2.1.4. Thử nghiệm lần 4...................................................................................44 3.2.1.5. Thử nghiệm lần 5...................................................................................46 3.2.1.6. Thử nghiệm lần 6...................................................................................47 3.2.1.7. Thử nghiệm lần 7...................................................................................48 3.2.1.8. Thử nghiệm lần 8...................................................................................50 3.2.1.9. Một số thử nghiệm khác ........................................................................51 3.2.2. Tìm đường đi qua các nút giao, các cảng sông, bến hàng hóa .....................57 3.2.2.1. Thử nghiệm lần 1...................................................................................58 3.2.2.2. Thử nghiệm lần 2...................................................................................59 3.2.2.3. Thử nghiệm lần 3...................................................................................59 3.2.2.4. Thử nghiệm lần 4...................................................................................60 3.2.2.5. Thử nghiệm lần 5...................................................................................60 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .................................................................62 TÀI LIỆU THAM KHẢO...........................................................................................63 PHỤ LỤC QUYẾT ĐỊNH GIAO ĐỀ TÀI (bản sao) BẢN SAO KẾT LUẬN CỦA HỘI ĐỒNG, BẢN SAO NHẬN XÉT CỦA CÁC PHẢN BIỆN. v TÓM TẮT LUẬN VĂN ỨNG DỤNG GIẢI THUẬT DI TRUYỀN TÌM ĐƯỜNG ĐI TỐI ƯU TRONG GIAO THÔNG ĐƯỜNG THỦY TẠI TỈNH VĨNH LONG Tóm tắt - Giải thuật di truyền và bài toán đường đi ngắn nhất là một trong số các vấn đề mang tính thực tiễn cao trong toán học và tin học. Trong đó, giải thuật di truyền là phương pháp tìm kiếm mô phỏng quá trình sinh tồn, tiến hóa của tự nhiên. Đó là sự chọn lọc các cá thể có độ thích nghi cao, loại bỏ các cá thể có độ thích nghi thấp tiến tới sàng lọc ra các cá thể tốt nhất. Bài toán đường đi ngắn nhất là vấn đề tìm đường đi giữa hai đỉnh trong một đồ thị hay giữa hai địa điểm trong mạng giao thông với điều kiện chi phí là tối thiểu. Trên thực tế, vấn đề này đã được giải quyết bằng một số thuật toán cổ điển. Tuy nhiên, việc tìm đường đi giữa hai địa điểm với ràng buộc phải qua một số địa điểm khác các giải thuật cổ điển này chưa giải quyết được. Do đó, trong khuôn khổ luận văn này, tôi sẽ đề xuất giải thuật di truyền để giải quyết bài toán vừa nêu và ứng dụng vào thực tiễn tìm đường đi tối ưu trong mạng giao thông đường thủy tỉnh Vĩnh Long. Từ khóa – giải thuật di truyền, GAs, bài toán đường đi ngắn nhất, giao thông đường thủy. APPLYING GENETIC ALGORITHMS TO FIND THE OPTIMAL ROUTE IN THE WATERWAY NETWORK OF VINH LONG PROVINCE Abstract - Genetic algorithms and shortest path problems are among the most practical issues in mathematics and computing. Of which, genetic algorithm is the search method to simulate the process of survival, evolution of nature. It is the selection of highly adaptive individuals, eliminating the low adaptability of individuals to the best individual screening. The shortest path problem is the problem of finding a path between two vertices in a graph or between two locations in a transport network, provided that the cost is minimal. In fact, this problem has been solved by some classical algorithms. However, finding paths between two places with mandatory must through some different places, these classical algorithms are not solved. Therefore, within this thesis, I will propose genetic algorithms to solve the above mentioned problems and apply them to the practice of navigating the waterway network of Vinh Long province. Key words – genetic algorithms, GAs, shortest path problem, waterway traffic. vi DANH MỤC CÁC TỪ VIẾT TẮT GAs GTVT ĐBSCL UBND giải thuật di truyền giao thông vận tải đồng bằng sông Cửu Long Ủy ban Nhân dân vii DANH MỤC CÁC BẢNG Số hiệu bảng Tên bảng Trang 1.1. Kết quả giải thuật Dijsktra 11 1.2. Kết quả giải thuật Ford – Bellman 12 1.3. Bảng thống kê các tuyến sông và cấp kỹ thuật 24 viii DANH MỤC CÁC HÌNH Số hiệu hình 1.1 1.2. 1.3. 1.4. 1.5. 1.6. 1.7. 1.8 1.9 1.1 1.1 1.1 1.1 2.1 2.2 2.3 2.4 3.1. 3.2. 3.3. 3.4. 3.5. 3.6. 3.7. 3.8. 3.9. 3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17 Tên hình Ví dụ về đơn đồ thị vô hướng Ví dụ về đa đồ thị vô hướng (e1 và e2 là các cạnh song song) Ví dụ về đơn đồ thị có hướng Ví dụ về đa đồ thị có hướng (e1 và e2 là các cung song song) Ví dụ các thuật ngữ trên đồ thị vô hướng Ví dụ các thuật ngữ trên đồ thị có hướng Ví dụ về đồ thị có hướng liên thông Đồ thị vô hướng G và đồ thị có hướng G1 Đồ thị có hướng G Đồ thị có hướng G và giải thuật Dijsktra Đồ thị có hướng G và giải thuật Ford - Bellman Lưu đồ giải thuật di truyền Bản đồ đường sông tỉnh Vĩnh Long (Nguồn sở GTVT Vĩnh Long) Đồ thị có trọng số G và bài toán đường đi ngắn nhất Tập tin danh bạ các nút giao Tập tin danh bạ các cảng, bến hàng hóa Biểu diễn khoảng cách giữa các nút Giao diện chương trình Giao diện chọn tập tin dữ liệu vào Cửa sổ Open Giao diện chọn điểm bắt đầu và kết thúc hành trình Cách chọn điểm bắt đầu và kết thúc hành trình Giao diện chọn các nút phải đi qua Cách chọn các nút phải đi qua Kết quả đường đi tối ưu Sơ đồ đường sông tỉnh Vĩnh Long Biểu diễn các nút giao giữa các sông bằng đồ thị Kết quả thử nghiệm lần 1, thế hệ 1 Kết quả thử nghiệm lần 1, thế hệ 4 Kết quả thử nghiệm lần 2, thế hệ 1 Kết quả thử nghiệm lần 2, thế hệ 3 Kết quả thử nghiệm lần 3, thế hệ 5 Kết quả thử nghiệm lần 3, thế hệ 6 Kết quả thử nghiệm lần 4, thế hệ 1 Trang 4 4 5 5 6 6 7 7 8 11 12 16 22 26 27 28 29 34 34 35 35 35 36 36 37 38 38 39 40 41 42 43 44 45 ix Số hiệu hình 3.18 3.19 3.20 3.21 3.22 3.23 3.24 3.25 3.26 3.27 3.28 3.29 3.30 3.31 3.32 3.33 3.34 3.35 3.36 3.37 3.38 3.39 Tên hình Kết quả thử nghiệm lần 4, thế hệ 7 Kết quả thử nghiệm lần 5, thế hệ 8 Kết quả thử nghiệm lần 6, thế hệ 1 Kết quả thử nghiệm lần 7, thế hệ 1 Kết quả thử nghiệm lần 7, thế hệ 5 Kết quả thử nghiệm lần 8, thế hệ 10 Biểu đồ kết quả thử nghiệm trường hợp 1 Biểu đồ kết quả thử nghiệm trường hợp 2 Biểu đồ kết quả thử nghiệm trường hợp 3 Biểu đồ kết quả thử nghiệm trường hợp 4 Biểu đồ kết quả thử nghiệm trường hợp 5 Biểu đồ kết quả thử nghiệm trường hợp 6 Biểu đồ kết quả thử nghiệm trường hợp 7 Biểu đồ kết quả thử nghiệm trường hợp 8 Biểu đồ kết quả thử nghiệm trường hợp 9 Biểu đồ kết quả thử nghiệm trường hợp 10 Biểu diễn các nút giao, cảng, bến hàng hóa bằng đồ thị Biểu đồ kết quả thử nghiệm lần 1 Biểu đồ kết quả thử nghiệm lần 2 Biểu đồ kết quả thử nghiệm lần 3 Biểu đồ kết quả thử nghiệm lần 4 Biểu đồ kết quả thử nghiệm lần 5 Trang 46 47 48 49 50 51 52 52 53 53 54 55 55 56 56 57 58 59 59 60 60 61 1 MỞ ĐẦU 1. LÝ DO CHỌN ĐỀ TÀI Giao thông vận tải là lĩnh vực thuộc kết cấu hạ tầng, có vai trò quyết định trong việc phát triển kinh tế vùng miền. Giao thông vận tải tạo điều kiện cho sự phát triển kinh tế - xã hội, an ninh quốc phòng, phục vụ cho sự nghiệp Công nghệp hóa – hiện đại hoá đất nước. Vì lẽ đó, giao thông vận tải được xem như là huyết mạch của mỗi địa phương trong quá trình phát triển toàn diện tất cả các lĩnh vực kinh tế - xã hội của địa phương đó. Đặc điểm địa lý của Đồng bằng sông Cửu Long (ĐBSCL) nói chung và tỉnh Vĩnh Long nói riêng là hệ thống sông ngòi, kênh rạch dày đặc, thuận lợi cho giao thông đường thủy bậc nhất nước ta. Trong đó có rất nhiều tuyến sông, kênh rạch cho phép các tàu có trọng tải hàng trăm tấn dễ dàng đi lại. Bên cạnh đó, tất cả các sông chính cùng các phụ lưu và hệ thống kênh rạch đã tạo nên một mạng lưới liên hoàn chảy qua nhiều khu công nghiệp tập trung, khu dân cư, các trung tâm kinh tế - xã hội, …tạo nên một sự kết nối, giao thương vô cùng thuận lợi. Ngoài ra cũng có nhiều cảng sông tiếp cận trực tiếp được các hệ thống giao thông đường bộ. Hầu hết các tuyến sông đều có vị trí tiếp cận với các cảng biển quan trọng, tạo nên những điểm nối giao lưu giữa các phương thức vận tải. Vì vậy, việc quan tâm nghiên cứu xây dựng, phát triển hệ thống giao thông đường thủy nhằm tối ưu khả năng khai thác vận tải trên các dòng sông này là điều rất cần thiết. Để phát triển hệ thống giao thông đường thủy, người ta phải phát triển đồng bộ nhiều yếu tố như: khả năng thông luồng giao thông, độ sâu, độ rộng các dòng sông; mở rộng mạng lưới lưới bến cảng, nâng cao năng lực vận chuyển của các cảng hàng hóa, các bến tàu khách hay các bến chuyên dùng, … Ngoài ra, việc có thể tìm được một con đường tối ưu khi lưu thông trên các dòng sông cũng đóng vai trò cực kỳ to lớn quyết định tính hiệu quả của việc khai thác giao thông đường thủy. Trên thế giới, đã có nhiều phương pháp khác nhau giải quyết việc tìm đường đi tối ưu trong một mạng giao thông dựa trên thuật toán Dijsktra, thuật toán BellmanFord, giải thuật tìm kiếm A*, thuật toán Johnson hay Lý thuyết nhiễu. Tuy nhiên, các thuật toán này chỉ dừng lại ở mức giải quyết tìm đường đi ngắn nhất giữa hai địa điểm cho trước. Trong khi đó, thực tế việc tham gia trong mạng giao thông, nhu cầu đi từ địa điểm này đến địa điểm kia và cần phải thông qua một số địa điểm khác là rất phổ biến. Chính vì vậy, tôi quyết định chọn đề tài “Ứng dụng giải thuật di truyền tìm đường đi tối ưu trong giao thông đường thủy tại tỉnh Vĩnh Long” làm đề tài luận văn thạc sĩ. Trong đề tài này, tôi đề xuất phương pháp giải quyết việc tìm đường đi tối ưu qua các địa điểm trong mạng giao thông đường thủy tại tỉnh Vĩnh Long bằng giải thuật di truyền với hy vọng tìm ra được giải pháp hiệu quả nhất. 2 2. MỤC TIÊU VÀ NHIỆM VỤ ĐỀ TÀI 2.1. Mục tiêu Mục tiêu của đề tài là xây dựng chương trình cho phép tìm ra được đường đi tối ưu đi từ địa điểm này đến địa điểm kia với điều kiện phải thông qua một số địa điểm khác trong mạng giao thông đường thủy tại tỉnh Vĩnh Long bằng giải thuật di truyền. 2.2. Nhiệm vụ Đề tài cần giải quyết được các vấn đề sau đây: - Lý thuyết đồ thị và bài toán đường đi ngắn nhất, - Giải thuật di truyền và các nguyên lý thiết kế giải thuật di truyền, - Một số ứng dụng của giải thuật di truyền, - Đặc điểm hệ thống giao thông đường thủy tại tỉnh Vĩnh Long, - Đề xuất giải pháp và triển khai giải quyết vấn đề tìm đường đi tối ưu trong giao thông đường thủy tại tỉnh Vĩnh Long bằng giải thuật di truyền. 3. ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU 3.1. Đối tượng nghiên cứu - Lý thuyết đồ thị, - Giải thuật di truyền, - Hệ thống giao thông đường thủy tại tỉnh Vĩnh Long, - Một số công trình nghiên cứu khoa học có liên quan. 3.2. Phạm vi nghiên cứu Xây dựng giải thuật di truyền giải quyết việc chọn đường đi tối ưu đi từ địa điểm này đến địa điểm kia với điều kiện phải thông qua một số địa điểm khác trên hệ thống giao thông đường thủy tại tỉnh Vĩnh Long. 4. PHƯƠNG PHÁP NGHIÊN CỨU Tôi sử dụng kết hợp nhiều phương pháp, trong đó chủ yếu là nghiên cứu lý thuyết và nghiên cứu thực nghiệm. 4.1. Phương pháp lý thuyết - Thu thập, nghiên cứu các tài liệu về lý thuyết đồ thị, giải thuật di truyền, - Nghiên cứu về giao thông đường thủy, đặc điểm hệ thống giao thông đường thủy tại tỉnh Vĩnh Long. 4.2. Phương pháp thực nghiệm - Khảo sát, phân tích dữ liệu về giao thông đường thủy tại tỉnh Vĩnh Long, - Phân tích, tổ chức dữ liệu, - Triển khai, xây dựng ứng dụng, - Đánh giá, thử nghiệm. 5. MỤC ĐÍCH VÀ Ý NGHĨA CỦA ĐỀ TÀI 5.1. Mục đích Nghiên cứu giải thuật di truyền để xây dựng hệ thống tìm đường đi tối ưu qua các địa điểm trong giao thông đường thủy tại tỉnh Vĩnh Long. 3 5.2. Ý nghĩa của đề tài Về khoa học: Nghiên cứu giải thuật di truyền và đặc điểm hệ thống giao thông đường thủy, hệ thống sông ngòi, bến bãi, cảng hàng hóa tại tỉnh Vĩnh Long, từ đó đưa ra giải pháp tìm đường đi tối ưu đi qua các địa điểm cho trước. Về thực tiễn: Đề tài sẽ góp phần nâng cao hiệu quả trong giao thông đường thủy nhằm tạo tiền đề phát triển kinh tế - xã hội địa phương. 6. CẤU TRÚC CỦA LUẬN VĂN Luận văn được tổ chức thành 3 chương chính như sau: CHƯƠNG 1: CƠ SỞ LÝ THUYẾT Nội dung chương này sẽ trình bày các vấn đề cơ bản về lý thuyết đồ thị bao gồm các khái niệm, cách biểu diễn đồ thị trong máy tính, bài toán đường đi ngắn nhất và các thuật toán cổ điển tìm kiếm đường đi ngắn nhất trên đồ thị. Bên cạnh đó, nội dung chương này cũng đề cập đến giải thuật di truyền, nguyên tắc thiết kế giải thuật di truyền và một số ứng dụng tiêu biểu của giải thuật di truyền. Ngoài ra, nội dung chương này cũng trình bày khái quát về các yếu tố sẽ ảnh hưởng đến giao thông đường thủy và đặc điểm của giao thông đường thủy, đặc điểm của hệ thống sông ngòi tại tỉnh Vĩnh Long. CHƯƠNG 2: ỨNG DỤNG GIẢI THUẬT DI TRUYỀN TÌM ĐƯỜNG ĐI TỐI ƯU TRONG GIAO THÔNG ĐƯỜNG THỦY TẠI TỈNH VĨNH LONG Nội dung chương chủ yếu đi vào phân tích bài toán, các bước triển khai xây dựng hệ thống tìm đường dựa vào giải thuật di truyền từ việc phân tích, tổ chức dữ liệu đến việc triển khai các thuật toán cụ thể trên dữ liệu thu thập được để giải quyết bài toán. CHƯƠNG 3: THỬ NGHIỆM VÀ ĐÁNH GIÁ Nội dung chương chủ yếu trình bày về giao diện hệ thống tìm đường, thử nghiệm hệ thống và đánh giá, phân tích kết quả thu được. 4 CHƯƠNG 1 CƠ SỞ LÝ THUYẾT 1.1. LÝ THUYẾT ĐỒ THỊ 1.1.1. Các khái niệm trên đồ thị 1.1.1.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 đó. Gọi V là tập đỉnh, E = {e = (u,v): u,v V} là tập cạnh, và G = (V,E) gọi là đồ thị. 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ị. Khi đó, các loại đồ thị: đơn đồ thị vô hướng, đa đồ thị vô hướng, đơn đồ thị có hướng, đa đồ thị có hướng. a. Đị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. Ví dụ 1.1: c. Đồ thị G3 b. Đồ thị G2 Hình 1.1. Ví dụ về đơn đồ thị vô hướng Trong hình 1.1, G1 là đơn đồ thị, G2 không là đơn đồ thị vì tồn tại 2 cặp đỉnh có nhiều hơn một cạnh nối giữa chúng, G3 cũng không là đơn đồ thị vì có một cạnh có điểm đầu và điểm cuối trùng nhau. b. Đị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. a. Đồ thị G1 Hình 1.2. Ví dụ về đa đồ thị vô hướng (e1 và e2 là các cạnh song song) Như vậy, ta nhận thấy 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 giữa một cặp đỉnh nào đó. c. Định nghĩa 3 5 Đơ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. Ví dụ 1.2: Hình 1.3. Ví dụ về đơn đồ thị có hướng d. Định nghĩa 4 Đ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. Ví dụ 1.3: Hình 1.4. Ví dụ về đa đồ thị có hướng (e1 và e2 là các cung song song) 1.1.1.2. Các thuật ngữ cơ bản - Khuyên: cạnh (cung) e gọi là khuyên nếu e có dạng (v,v). - Cạnh (cung) lặp: hai cạnh (cung) cùng tương ứng với một cặp đỉnh. - Đỉnh kề: Nếu (u,v) là cạnh (hoặc cung) của đồ thị thì v gọi là kề của u. Trong đồ thị vô hướng, nếu v kề u thì u cũng kề v. - Cạnh liên thuộc: Trong đồ thị vô hướng, cạnh e=(u,v) gọi là cạnh liên thuộc với đỉnh u và liên thuộc với đỉnh v. - Bậc của đỉnh: trong đồ thị vô hướng, bậc của đỉnh v là số cạnh liên thuộc với nó. Ký hiệu deg(v) - Đỉnh cô lập: là đỉnh có bậc là 0. - Đỉnh treo: là đỉnh có bậc là 1. - Đường đi: đường đi độ dài n từ đỉnh u đến đỉnh v (trong đó n là số nguyên dương) trên đồ thị vô hướng (hoặc vô hướng) G=(V,E) là dãy x0, x1,…, xn-1, xn trong đó u = x0 , v = xn , (xi , xi+1) E, i = 0, 1, 2,…, n-1. Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh (hoặc cung): (x0,x1), (x1, x2), …, (xn-1, xn) Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại. 6 Ví dụ 1.5: Xét đồ thị ở hình 1.5: Hình 1.5. Ví dụ các thuật ngữ trên đồ thị vô hướng Ta có: - a d, c, f, e là đường đi đơn độ dài 4. - d, e, c, a không là đường đi, do (c,e) không phải là cạnh của đồ thị. - Dãy b, c, f, e, b là chu trình độ dài 4. - Đường đi a, b, e, d, a, b có độ dài là 5 không phải là đường đi đơn, do cạnh (a, b) có mặt trong nó 2 lần. Ví dụ 1.6: Xét đồ thị ở hình 1.6: Hình 1.6. Ví dụ các thuật ngữ trên đồ thị có hướng Ta có: - a, d, c, f, e là đường đi đơn độ dài 4. - d, e, c, a không là đường đi, do (c,e) không phải là cạnh của đồ thị. - Dãy b, c, f, e, b là chu trình độ dài 4. - Đường đi a, b, e, d, a, b có độ dài là 5 không phải là đường đi đơn, do cạnh (a, b) có mặt trong nó 2 lần. - Đồ thị liên thông: Đồ thị vô hướng G = (V, E) được gọi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó. - Đồ thị liên thông mạnh: Đồ thị có hướng G = (V, E) được gọi là liên thông mạnh nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó. - Đồ thị liên thông yếu: Đồ thị có hướng G = (V, A) được gọi là liên thông yếu nếu đồ thị vô hướng tương ứng với nó là vô hướng liên thông. Ví dụ 1.7: Xét hai đồ thị có hướng ở hình 1.7: 7 Hình 1.7. Ví dụ về đồ thị có hướng liên thông Ta có: G là độ thị liên thông mạng, H là đồ thị liên thông yếu 1.1.1.3. Biểu diễn đồ thị trên máy tính a. Dùng ma trận kề Xét đơn đồ thị G = (V,E). Ma trận A = {ai,j : i,j=1, 2,...,n} với ai, j = 0, nếu (i,j) E và ai,j = 1, nếu (i,j) E, i, j=1, 2,...,n gọi là ma trận kề của đồ thị G. Ví dụ 1.8: Hình 1.8. Đồ thị vô hướng G và đồ thị có hướng G1 Ma trận kề của G như sau: 1 2 3 4 5 6 1 0 1 1 0 0 0 2 1 0 1 0 1 0 3 1 1 0 1 0 0 4 0 0 1 0 1 1 5 0 1 0 1 0 1 6 [0 0 0 1 1 0] Ma trận kề của G1 như 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] * Tính chất của ma trận kề của đồ thị vô hướng - Tính đối xứng: a[i,j ]= a[j,i], i,j = 1,2,...,n. - Tổng các phần tử nằm trên dòng i (cột j) bằng bậc của đỉnh i (đỉnh j). - Gọi aijp , i,j=1, 2,... ,n là phần tử của ma trận Ap =A.A...A (p thừa số). Khi đó, aijp , i,j=1, 2,...,n là số đường đi khác nhau từ đỉnh i đến đỉnh j qua p -1 đỉnh trung gian. 8 * Tính chất của ma trận kề của đồ thị có hướng - Không chắc chắn là ma trận đối xứng. - Tổng các phần tử trên dòng i bằng bán bậc ra của đỉnh i và tổng các phần từ trên cột j bằng bán bậc vào của đỉnh j. - Tương tự tính chất thứ 3 của đồ thị vô hướng. * Ma trận kề của đa đồ thị: a[i,j] = số cạnh (cung) nối hai đỉnh i, j Ưu điểm lớn nhất của phương pháp biểu diễn đồ thị bằng ma trận kề là khi muốn biết hai đỉnh u,v có kề nhau trên đồ thị hay không, chúng ta chỉ thực hiện một phép so sánh duy nhất. 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 nxn đơn vị bộ nhớ để lưu trữ ma trận kề của nó. b. Dùng ma trận liên thuộc Xét G = (V, E) là đơn đồ thị có hướng. Ma trận liên thuộc có dạng: 1, nếu i là đỉnh đầu của cung ej -1, nếu i là đỉnh cuối của cung ej 0, nếu i không là đầu mút của cung ej aij = Ví dụ 1.9: Xét đồ thị có hướng G ở hình 1.9: 2 e4 4 e1 1 e9 e3 e5 e8 e2 6 e7 3 e6 5 Hình 1.9. Đồ thị có hướng G Ma trận liên thuộc của đồ thị như sau: 𝑒1 𝑒2 𝑒3 𝑒 4 𝑒5 𝑒6 𝑒7 𝑒8 𝑒9 1 1 0 0 0 0 0 0 0 1 1 1 −1 0 0 0 0 2 −1 0 𝐴 = 3 0 −1 −1 0 0 1 0 0 0 4 0 0 0 −1 0 0 0 1 1 5 0 0 0 0 1 −1 1 −1 0 [ 6 0 0 0 0 0 0 −1 0 −1] c. Dùng danh sách cạnh Trong trường hợp đồ thị thưa (đồ thị có số cạnh m thoả mãn bất dẳng thức: m<6n) người ta thường dùng cách biểu diễn đồ thị dưới dạng danh sách cạnh. Trong cách biểu diễn đồ thị bởi danh sách cạnh (cung) chúng ta sẽ lưu trữ danh sách tất cả các cạnh (cung) của đồ thị vô hướng (có hướng). Một cạnh (cung) e=(u,v) của đồ thị sẽ tương ứng với hai biến Dau[e], Cuoi[e]. Như vậy, để lưu trữ đồ thị ta cần sử dụng 2m đơn vị bộ nhớ. Nhược điểm của cách biểu diễn này là để xác định những 9 đỉnh nào của đồ thị là kề với một đỉnh cho trước chúng ta phải làm cỡ m phép so sánh (duyệt qua danh sách tất cả các cạnh của đồ thị). Trong trường hợp đồ thị có trọng số ta cần thêm m đơn vị bộ nhớ để lưu trữ trọng số của các cạnh. d. Dùng danh sách kề Trong rất nhiều vấn đề ứng dụng của lý thuyết đồ thị, cách biểu diễn đồ thị dưới dạng danh sách kề là cách biểu diễn thích hợp nhất được sử dụng. Trong cách biểu diễn này, với mỗi đỉnh v của đồ thị chúng ta lưu trữ danh sách các đỉnh kề với nó, mà ta sẽ ký hiệu là: Ke(v)= { u∈ V: (v,u)∈ E} Khi đó, để kiểm tra hai đỉnh u, v có kề nhau hay không ta chỉ cần duyệt qua danh sách kề của u hoặc v. 1.1.2. Bài toán đường đi ngắn nhất 1.1.2.1. Đặt vấn đề 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... Ta có thể đồ thị hóa bài toán bằng cách xem các nút giao thông là đỉnh của đồ thị, đoạn đường giữa các nút giao thông là cạnh nối giữa hai đỉnh tương ứng. 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 qua đoạn đường hoặc cước phí vận chuyển trên đoạn đường đó,... một đồ thị như vậy được gọi là đồ thị có trọng số. Đồ thị có trọng số là đồ thị G=(V,E) mà mỗi cạnh (hoặc cung) được gán một giá trị gọi là trọng số ứng với cạnh (hoặc cung) đó. 1.1.2.2. Phát biểu bài toán a. Đường đi ngắn nhất giữa hai đỉnh Cho đơn đồ thị liên thông có trọng số G=(V,E), tìm đường đi ngắn nhất từ một đỉnh s cho trước đến một đỉnh f trong G. Kết quả của bài toán này là đường đi ngắn nhất giữa một cặp đỉnh cụ thể là s và f. Nếu như đồ thị không có chu trình âm thì ta có thể chứng minh được rằng một trong những đường đi ngắn nhất là đường đi cơ bản. Việc tìm đường đi ngắn nhất giữa 2 đỉnh s và f có thể áp dụng thuật toán sau: Gọi a[u,v] là trọng số của cạnh (u,v). Qui ước a[v,v]=0 với v V Đặt d[s,v] là khoảng cánh từ s tới v. Để tìm đường đi từ s tới f ta nhận thấy rằng luôn tồn tại f1≠ f sao cho d[s,f]=d[s,f1]+a[f1,f].