tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 5 - ThS. Trần Quốc Việt

Bài giảng Lý thuyết đồ thị: Chương 5 cung cấp cho người đọc những kiến thức như: Ma trận trọng số; thuật toán Dijsktra; thuật toán Floyd; thuật toán Bellman-ford; . Mời các bạn cùng tham khảo! | Nguyễn Cam Chu Đức Khánh Lý thuyết đồ thị - NXB Trẻ Tp. HCM 1998. Kenneth H. Rosen Discrete Mathematics and its Applications 7 Edition McGraw Hill 2010. 2 Đồ thị có trọng số Là đơn đồ thị trong đó mỗi cạnh được gán một giá trị số gọi là trọng số của cạnh Kí hiệu w e là trọng số của cạnh e Ví dụ e8 4 5 A e3 1 1 8 e1 5 e6 6 6 2 3 e7 2 e5 3 e4 4 e2 7 3 Nhiều bài toán có thể được mô hình hóa bằng đồ thị có trọng số Ví dụ Mô hình hóa một hệ thống đường hàng không nối giữa các thành phố Trọng số mỗi cạnh Khoảng cách Ví dụ Mô hình hóa một hệ thống đường hàng không nối giữa các thành phố Trọng số mỗi cạnh Thời gian bay Ví dụ Mô hình hóa một hệ thống đường hàng không nối giữa các thành phố Trọng số mỗi cạnh Giá vé Độ dài của một đường đi trong đồ thị có trọng số là tổng trọng số của tất cả các cạnh có trong đường đi đó. Tìm đường đi ngắn nhất giữa 2 đỉnh trong đồ thị là một trong nhiều vấn đề liên quan đến đồ thị có trọng số. Ví dụ 4 e8 5 1 A Các đường đi từ 4 đến 6 e3 1 4e85e66. Độ dài 5 6 12 8 e1 5 e6 4e85e77e56. Độ dài 5 3 2 10 6 6 2 3 4e32e23e46. Độ dài 1 4 3 8 2 e7 e5 3 e4 4 Đường đi ngắn nhất giữa 4 và 6 là e2 4e32e23e46 với độ dài 8. 7 3 Ví dụ Tìm một đường đi từ San Francisco đến Miami sao cho tổng tiền vé là ít nhất. Cho đồ thị có trọng số G V n Ma trận trọng số của G được định nghĩa w vi vj nếu vi vj E W wij nxn Với wij với 0 - hoặc nếu vi vj E Ví dụ e8 4 5 A 1 2 3 4 5 6 7 e3 1 1 8 1 2 8 4 1 8 e1 3 4 3 5 e6 4 1 5 6 6 2 5 5 6 3 3 6 3 6 2 e7 2 e5 4 7 3 2 3 e4 e2 7 Ma trận trọng số 3 Nếu đường đi s . . . r . . . t là đường đi ngắn nhất từ s đến t thì và cũng là các đường đi ngắn nhất. min s . . . . . . . . r . . . . . . t min min Bài toán Cho G V E đơn đồ thị vô hướng hoặc có hướng w ei 0 là trọng số của cạnh cung ei. Tìm đường đi có độ dài ngắn nhất từ đỉnh đỉnh s cho trước đến các đỉnh khác trong G Ma trận khoảng cách ma trận trọng số được định nghĩa w i j Nếu i j E W wij nxn wij Nếu i j E 4 e8 5 A 1 2 3 4 5 6 7 e3 1 1 8 1 8 e1 2 8 4 1 5 e6 6 6 2 3 4 3 3 .