Bài giảng Toán tổ hợp: Chương 6 - Nguyễn Anh Thi

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.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán tổ hợp: Chương 6 - Nguyễn Anh ThiChương 6CÁC BÀI TOÁN VỀ ĐƯỜNG ĐINội dung1. Tìm đường đi ngắn nhất2. Đồ thị Euler3. Đồ thị Hamilton21. TÌM ĐƯỜNG ĐI NGẮNNHẤT3Định nghĩaĐịnh nghĩa. Cho G = (V,E) là đồ thị có trọng số. VớiH  G thì trọng lượng của H là tổng trọng lượng củacá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) đượcgọ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ắnnhất của các đường đi từ u đến v.4Ma 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à matrận D= (dij) xác định như sau:0khi 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ởima trận khoảng cách.5