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 trình bày các nội dung chính như: Tìm đường đi ngắn nhất, đồ thị Euler, đồ thị Hamilton,.! | Chương 6 CÁC BÀI TOÁN VỀ ĐƯỜNG ĐI Nội dung 1. Tìm đường đi ngắn nhất 2. Đồ thị Euler 3. Đồ thị Hamilton 2 1. TÌM ĐƯỜNG ĐI NGẮN NHẤT 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. 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 .
