Bài giảng Toán rời rạc và lý thuyết đồ thị - Chương 5: Đường đi trên Đồ Thị - Võ Tấn Dũng

Company L/O/G/O Chương 5 ĐƯỜNG ĐI TRÊN ĐỒ THỊ GV: Võ Tấn Dũng TRƯỜNG CAO ĐẲNG CÔNG NGHỆ THÔNG TIN TP.HCM MÔN TOÁN RỜI RẠC MỞ ĐẦU Bài toán về những cây cầu ở Konigsber Năm 1736 Euler, cha đẻ của lý thuyết đồ thị, đã giải được bài toán hóc búa nổi tiếng thời đó về những cây cầu ở Konigberg. Thành phố Königsberg, Đức (nay là Kaliningrad, Nga) nằm trên sông Pregel, bao gồm hai hòn đảo lớn nối với nhau và với đất liền bởi bảy cây cầu. Câu hỏi đặt ra là có thể đi theo một tuyến đường mà đi qua mỗi cây cầu đúng một lần rồi quay lại điểm xuất phát hay không. 1 2 3 4 Euler đã chứng minh rằng bài toán không có lời giải bằng ngôn ngữ đồ thị. Ông biểu diễn 2 hòn đảo và 2 bờ sông bằng 4 điểm và 7 cây cầu bằng các cạnh nối các điểm như sau: Việc đi qua 7 cây cầu tương đương với việc vẽ đồ thị trên bằng 1 nét. Sau này ta sẽ thấy đồ thị trên không thể vẽ bằng 1 nét. 1 2 3 4 ĐỒ THỊ EULER Định nghĩa Cho đồ thị vô hướng G = (V, E)  Đường đi Euler: Đường đi đơn trong G đi qua mọi cạnh của nó, mỗi cạnh chỉ đi qua một lần được gọi là đường đi Euler  Chu trình Euler: Chu trình đơn trong đồ thị G đi qua mọi cạnh của nó, mỗi cạnh chỉ đi qua một lần được gọi là chu trình Euler. Cho đồ thị có hướng G = (V, E)  Đường đi có hướng Euler là đường đi đơn có hướng qua mọi cạnh của đồ thị.  Chu trình có hướng Euler là chu trình đơn có hướng qua mọi cạnh đồ thị. Đồ thị chứa chu trình Euler gọi là đồ thị Euler Ví dụ a b c d e f Đồ thị Euler Chu trình Euler: a, b, c, f, e, b, d, c, a Ví dụ Đồ thị về 7 cây cầu của thành phố Konigsberg 1 2 3 4 Không có chu trình và đường đi Euler  Thí dụ: Đồ thị G1 trong hình 1 là đồ thị Euler vì nó có chu trình Euler a, e, c, d, e, b, a. Đồ thị G3 không có chu trình Euler nhưng nó có đường đi Euler a, c, d, e, b, d, a, b, vì thế G3 là đồ thị cửa Euler. Đồ thị G2 không có chu trình cũng như đường đi Euler. Đồ thị G1, G2, G3  Điều kiện cần và đủ để một đồ thị là một đồ thị Euler được Euler tìm ra vào năm 1736 khi ông giải quyết bài toán hóc búa nổi tiếng thế giới thời đó về bảy cái cầu ở thành phố Konigsberg và đây là định lý đầu tiên của lý thuyết đồ thị. Điều kiện cần và đủ để đồ thị có chu trình và đường đi Euler  Đồ thị G có đường đi Euler khi và chỉ khi G liên thông và có không quá 2 đỉnh bậc lẻ.  Đồ thị G có chu trình Euler khi và chỉ khi G liên thông và mọi đỉnh đều có bậc (chẵn khác 0). Đồ thị vô hướng:  Đồ thị có hướng G có chu trình có hướng Euler khi và chỉ khi G liên thông mạnh và mọi đỉnh đều có nửa bậc ra bằng nửa bậc vào. Chú thích: Đồ thị liên thông mạnh là đồ thị có hướng mà mọi cặp đỉnh của nó đều có đường đi có hướng nối chúng với nhau. Đồ thị có hướng: dv(v) = dr(v) Ví dụ Đồ thị nào sau đây có chu trình Euler? Nếu không, liệu có đường đi Euler không? a b c ed a b c def a b c d e Đồ thị nào sau đây có chu trình có hướng Euler? Nếu không, liệu có đường đi có hướng Euler không? Ví dụ a b cd a b c d e f ĐỒ THỊ HAMINTON Định nghĩa Cho đồ thị G = (V, E)  Đường đi Haminton là đường đi qua tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần được gọi là đường đi Hamilton.  Chu trình Hamintơn là chu trình bắt đầu từ một đỉnh v nào đó qua tất cả các đỉnh còn lại mỗi đỉnh đúng một lần rồi quay trở về v được gọi là chu trình Hamilton. Đồ thị chứa chu trình Hamintơn gọi là đồ thị Hamintơn Định nghĩa tương tự đối với đồ thị có hướng Ví dụ Cho đồ thị: e d c ba f g Đồ thị trên không có chu trình và đường đi Euler nhưng có chu trình Hamintơn. Đồ thị Hamintơn Chu trình Hamintơn có độ dài bằng số đỉnh và mọi đường đi Hamintơn có độ dài bằng số cạnh. Chú ý Xét đồ thị: a b c de Đồ thị trên có chu trình Hamintơn không? Vì sao? Định lý (Dirak). Đơn đồ thị vô hướng G với n>2 đỉnh, mỗi đỉnh có bậc không nhỏ hơn n/2 là đồ thị Hamilton. Đồ thị Hamilton G3, đường đi Hamilton trong G2 , và G1. Cho G là đơn đồ thị n đỉnh (n  3). Nếu: Gv, 2 n )v(d  thì G có chu trình Hamintơn Cho G là đơn đồ thị n đỉnh (n  3). Nếu: Gv, 2 1n )v(d    thì G có chu trình Hamintơn Định lí 1 Định lí 2 Định lí 3 Nếu G là đồ thị có hướng liên thông mạnh và: Gv, 2 n )v(d& 2 n )v(d vr  thì G có chu trình có hướng Hamintơn Ví dụ Các đồ thị sau có chu trình hay đường đi Hamintơn không? Nếu có hãy chỉ ra chu trình hay đường đi Hamintơn.   1 2 3 456 78 a. 1 2 3 4 5 67 8 11 12 13 14 15 910 b. TÌM ĐƯỜNG ĐI NGẮN NHẤT 4.5.1 Đồ thị có trọng số: Là đồ thị mà mỗi cạnh của nó được gán 1 số. Trong đồ thị có trọng số, độ dài trọng số của đường đi  là tổng các trọng số trên đường đi đó. 4.5.2 Phát biểu bài toán: Cho đồ thị có trọng số G = (V, E). Tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z của đồ thị Thuật toán Dijkstra: Tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z trong đồ thị có trọng số. Trọng số của cạnh (i,j) là w(i,j) > 0 và đỉnh x sẽ mang nhãn L(x). Khi kết thúc thuật giải L(z) chính là chiều dài đường đi ngắn nhất từ a đến z. Đầu vào: Đồ thị liên thông G = (V, E) có trọng số w(i, j) > 0 với mọi cạnh (i, j), đỉnh a và đỉnh z. Đầu ra: Chiều dài đường đi ngắn nhất và đường đi ngắn nhất. Phương pháp: (1) Gán L(a)  0. Với mọi đỉnh x  a gán L(x) = . Kí hiệu T  V (2) Chọn v T sao cho L(v) có giá trị nhỏ nhất. Đặt: T  T – {v} (3) Nếu z  T  Kết thúc. L(z) là đường đi ngắn nhất từ a đến z. Từ z lần ngược theo các đỉnh được ghi nhớ ta có đường đi ngắn nhất. Ngược lại sang bước 4. (4) Với mỗi x  T kề với v gán: L(x)  min{L(x), L(v) + w(v, x)} Nếu L(x) này thay đổi thì ghi nhớ đỉnh v cạnh x để sau này xây dựng đường đi ngắn nhất. Quay về bước 2. Ví dụ: Tìm đường đi ngắn nhất từ đỉnh a đến z trong đồ thị sau: a f ed cb g z 2 1 2 14 3 4 2 67 5 3 Ví dụ trên đồ thị vô hướng Nguồn: ThS. Trịnh Thanh Đèo 28 Ví dụ trên đồ thị có hướng Nguồn: ThS. Trịnh Thanh Đèo 29 Hết chương