Tà liệu tham khảo: Một số bài toán tối ưu trên đồ thị

Tài liệu tham khảo cho các bạn sinh viên học chuyên ngành có tư liệu ôn thi tốt đạt kết quả cao trong các kì thi giữa kì và cuối kì với những bài toán khó và hướng dẫn cách giải.
Nội dung trích xuất từ tài liệu:
Tà liệu tham khảo: Một số bài toán tối ưu trên đồ thịCHƯƠNG VMỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊĐỒ THỊ CÓ TRỌNG SỐ VÀ BÀI TOÁNĐƯỜNG ĐI NGẮN NHẤT Đồ thị có trọng số là đồ thị G=(V,E) mà mỗi cạnh e∈E được gán bởimộtsốthựcm(e),gọilàtrọngsốcủa cạnhe Trọng số của mỗi cạnh được xét là một số dương và còn gọi làchiều dài của cạnh đó. Mỗi đường đi từ đỉnh u đến đỉnh v, có chiều dài là m(u,v), bằngtổng chiều dài các cạnh mà nó đi qua. Khoảng cách d(u,v) giữa hai đỉnh u và v là chiềudài đường đi ngắn nhất (theo nghĩa m(u,v) nhỏ nhất) trong các đường đi từ u đến v.BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮNNHẤT: Cho đơn đồ thị liên thông, có trọng số G=(V,E). Tìm khoảng cách d(u0,v) từ mộtđỉnh u0 cho trước đến một đỉnh v bất kỳ của G và tìm đường đi ngắn nhất từ u0 đến v.THUẬTTOÁNDIJKSTRA Trước tiên, đỉnh có khoảng cách đến a nhỏ nhất chính là a, với d(u0,u0)=0. Trongcác đỉnh v ≠ u0, tìm đỉnh có khoảng cách k1 đến u0 là nhỏ nhất. Đỉnh này phải là mộttrong các đỉnh kề với u0. Giả sử đó là u1. Ta có:d(u0,u1)=k1. Trong các đỉnh v ≠ u0 và v ≠ u1, tìm đỉnh có khoảng cách k2 đến u0 là nhỏ nhất. Đỉnhnày phải là một trong các đỉnh kề với u0 hoặc với u1. Giả sử đó là u2. Ta có:d(u0,u2)=k2. Tiếp tục như trên, cho đến bao giờ tìm được khoảng cách từ u0 đến mọi đỉnh v của G. NếuV={u0,u1,...,un}thì:0=d(u0,u0)VÍDỤ Tìm khoảng cách d(a,v) từ a đến mọi đỉnh v và tìm đường đi ngắn nhất từ ađến v cho trong đồ thị G sau.ĐỊNH LÝ: Thuật toán Dijkstra tìm được đường đi ngắn nhất từ một đỉnh cho trướcđến một đỉnh tuỳ ý trong đơn đồ thị vô hướng liên thông có trọng số. Mệnh đề: Thuật toán Dijkstra tìm đường đi ngắn nhất từ một đỉnh cho trước đếnmột đỉnh tuỳ ý trong đơn đồ thị vô hướng liên thông có trọng số có độ phức tạp là O(n2).VÍDỤ1: Dùng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh a đến các đỉnh khác trong đồthịsau:VÍDỤ2: Dùng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh a đến các đỉnh khác trong đồthịsau: