Bài giảng "Toán tổ hợp - 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,. Hi vọng đây sẽ là một tài liệu hữu ích dành cho các bạn sinh viên đang theo học môn dùng làm tài liệu học tập và nghiên cứu. | 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 .
