TAILIEUCHUNG - Bài giảng Toán học rời rạc và cấu trúc rời rạc: Chương 6 - Đại học Khoa Học Tự Nhiên Tp. Hồ Chí Minh

Bài giảng "Toán học tổ hợp và cấu trúc rời rạc - Chương 6: Các bài toán về đường đi" cung cấp cho người học các kiến thức: Tìm đường đi ngắn nhất, đồ thị Euler, đồ thị Hamilton. Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết. | Chương 6 CÁC BÀI TOÁN VỀ ĐƯỜNG ĐI lvluyen@ http luyen cautrucroirac FB cautrucroirac https tailieudientucntt Nội dung 1. Tìm đường đi ngắn nhất 2. Đồ thị Euler 3. Đồ thị Hamilton https tailieudientucntt 2 1. TÌM ĐƯỜNG ĐI NGẮN NHẤT https tailieudientucntt 3 Định nghĩa Định nghĩa. Cho G V E là đồ thị có trọng số. Với H G thì trọng lượng của H là tổng trọng lượng của các cạnh của H. w H w e e H Nếu H là đường đi chu trình mạch thì w H được gọi là độ dài của H. Nếu mạch H có độ dài âm thì H được gọi là mạch âm. Khoảng cách giữa 2 đỉnh u và v là độ dài ngắn nhất của các đường đi từ u đến v. https tailieudientucntt 4 Ma trận khoảng cách Định nghĩa. Cho đồ thị G V E V v1 v2 vn có trọng số. Ma trận khoảng cách của G là ma trận D dij xác định như sau 0 khi i j dij w v i v j khi vi v j E khi vi v j E Nhận xét. Mọi đồ thị được hoàn toàn xác định bởi ma trận khoảng cách. https tailieudientucntt 5 Ví dụ. Tìm ma trận khoảng cách của đồ thị sau 0 5 31 40 0 27 73 26 0 8 49 25 38 D 0 16 70 0 9 23 0 12 0 10 https tailieudientucntt 6 Ví dụ. Tìm đồ thị có ma trận khoảng cách sau 0 12 7 5 12 0 15 16 6 7 15 0 10 Đáp án. 5 5 16 0 5 6 10 5 0 12 16 D A B 6 7 5 15 E C 10 https tailieudientucntt 7 Bài toán. Cho G V E là đồ thị có trọng số. Tìm đường đi ngắn nhất từ u đến v và tính khoảng cách d u v . Nhận xét. Nếu đồ thị G có mạch âm trên một đường đi từ u tới v thì đường đi ngắn nhất từ u đến v sẽ không tồn tại. u v https tailieudientucntt 8 Một số lưu ý Khi tìm đường đi ngắn nhất ta có thể bỏ bớt đi các cạnh song song và chỉ để lại một cạnh có trọng lượng nhỏ nhất. Đối với các khuyên có trọng lượng không âm thì cũng có thể bỏ đi mà không làm ảnh hưởng đến kết quả của bài toán. Đối với các khuyên có trọng lượng âm thì có thể đưa

• Toán học
• Toán học rời rạc
• Cấu trúc rời rạc
• Tìm đường đi ngắn nhất
• Đồ thị Euler
• Đồ thị Hamilton
• Bài giảng Toán học rời rạc
• Toán rời rạc
• Bài giảng toán rời rạc
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Bài tập về toán rời rạc
• Ôn tập toán rời rạc
• Đề thi toán rời rạc
• Câu hỏi Toán rời rạc
• Ôn thi Toán rời rạc
• Luyện thi Toán rời rạc
• Bài thi Toán rời rạc
• Hướng dẫn thi Toán rời rạc
• Câu hỏi thi Toán rời rạc
• Học phần Toán rời rạc 1
• Toán rời rạc 1
• Câu hỏi thi Toán rời rạc 1
• Ngân hàng câu hỏi Toán rời rạc 1
• Thi tự luận Toán rời rạc 1
• Hướng dẫn thi Toán rời rạc 1