Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Toán học tổ hợp và cấu trúc rời rạc: Chương 6 - Lê Văn Luyện

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. nội dung chi tiết. | Bài giảng Toán học tổ hợp và cấu trúc rời rạc: Chương 6 - Lê Văn Luyện 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