Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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@hcmus.edu.vn http www.math.hcmus.edu.vn luyen cautrucroirac FB fb.com cautrucroirac CuuDuongThanCong.com https fb.com tailieudientucntt Nội dung 1. Tìm đường đi ngắn nhất 2. Đồ thị Euler 3. Đồ thị Hamilton CuuDuongThanCong.com https fb.com tailieudientucntt 2 1. TÌM ĐƯỜNG ĐI NGẮN NHẤT CuuDuongThanCong.com https fb.com 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. CuuDuongThanCong.com https fb.com 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. CuuDuongThanCong.com https fb.com 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 CuuDuongThanCong.com https fb.com 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 CuuDuongThanCong.com https fb.com 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 CuuDuongThanCong.com https fb.com 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
