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
