Bài giảng Toán học tổ hợp - Chương 3: Các bài toán về đường đi

Bài giảng Toán học tổ hợp - Chương 3: Các bài toán về đường đi cung cấp cho người học những kiến thức như: Tìm đường đi ngắn nhất; Đồ thị Euler; Đồ thị Hamilton. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán học tổ hợp - Chương 3: Các bài toán về đường điChương 3. CÁC BÀI TOÁN VỀ ĐƯỜNG ĐI LVL @2020Nội dung 1. Tìm đường đi ngắn nhất 2. Đồ thị Euler 3. Đồ thị Hamilton 21. 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à Hlà đồ thị con của G. Khi đó 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. 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: 0 khi i = j  dij =  w(v i v j ) khi vi v j  E   khi vi v j  ENhận xét. Mọi đồ thị đơn được hoàn toàn xác địnhbởi ma trận khoảng cách. 5Ma trận khoảng cáchVí dụ. Tìm ma trận khoảngcách của đồ thị sau 0 5 31 40     0 27  73      26 0 8 49 25 38   D =    0  16   70   0  9       23 0 12       0   10 6Ma trận khoảng cáchVí dụ. Tìm đồ thị có ma trận khoảng cách sau: 0 12 7 5    12 0 15 16 6 7 15 0  10  Đáp án.   5 5 16  0 5  6 10 5 0   12 16 D A B 6 7 5 15 E C 10 7Đường đi ngắn nhấtBài toán. Cho G = (V, E) là đồ thị có trọng số. Tìmđường đi ngắn nhất từ u đến v và tính khoảng cáchd(u ,v).Nhận xét. Nếu đồ thị G có mạch âm  trên mộtđường đi từ u tới v thì đường đi ngắn nhất từ u đến vsẽ không tồn tại. u v  8Một số lưu ýKhi tìm đường đi ngắn nhất ta có thể bỏ bớt đi cáccạnh song song cùng chiều và chỉ để lại một cạnhcó trọng lượng nhỏ nhất.Đối với các khuyên có trọng lượng không âm thìcũng có thể bỏ đi mà không làm ảnh hưởng đến kếtquả của bài toán.Đối với các khuyên có trọng lượng âm thì có thểđưa đến bài toán tìm đường đi ngắn nhất không cólời giải. 9Nguyên lý BellmanGọi P là đường đi ngắn nhất từ đỉnh u đến đỉnh v vàt  P. Giả sử P=P1P2 với P1 là đường đi con của Ptừ u đến t và P2 là đường đi con của P từ t đến v. Khiđó P1 cũng là đường đi ngắn nhất từ u đến t.Chứng minh. Giả sử tồn tại P1’ là đường đi ngắn hơnP1 ta có t P1 P2 u v P1’ w(P1’) < w(P1)  w(P1’P2) < w(P1P2)=w(P)Vô lý vì P là đường đi ngắn nhất từ u đến v 10Thuật toán tìm đường đi ngắn nhấtĐể tìm đường đi ngắn nhất, chúng ta quan tâm tớihai thuật toán:▪ Thuật toán Dijkstra không thể thực hiện khi đồ thị có cạnh âm▪ Thuật toán Ford – Bellman xác định các mạch (chu trình) âm hoặc trả về cây đường đi ngắn nhất 11Thuật toán DijkstraXác định tuần tự các đỉnh có khoảng cách đến u0 từ nhỏđến lớn.▪ Trước tiên đỉnh có khoảng cách nhỏ nhất đến u0 là u0.▪ Trong V{u0} tìm đỉnh có khoảng cách đến u0 nhỏ nhất (đỉnh này phải là một trong các đỉnh kề với u0) giả sử đó là u1▪ Trong V{u0,u1} tìm ...