Bài giảng môn Toán rời rạc - Chương 5: Đường đi trên đồ thị

Nội dung text: Bài giảng môn Toán rời rạc - Chương 5: Đường đi trên đồ thị

1. TRƯỜNG CAO ĐẲNG CƠNG NGHỆ THƠNG TIN TP.HCM MƠN TỐN RỜI RẠC Company L/O/G/O Chương 5 ĐƯỜNG ĐI TRÊN ĐỒ THỊ GV: Võ Tấn Dũng
2. MỞ ĐẦU Bài tố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 tốn hĩc búa nổi tiếng thời đĩ về những cây cầu ở Konigberg.
3. 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. 3 1 2 4 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.
4. Euler đã chứng minh rằng bài tố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: 3 Việc đi qua 7 cây cầu tương 1 2 đương với việc vẽ đồ thị trên bằng 1 nét. 4 Sau này ta sẽ thấy đồ thị trên khơng thể vẽ bằng 1 nét.
5. ĐỒ 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.
6. 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
7. Ví dụ a b c d e f Đồ thị Euler Chu trình Euler: a, b, c, f, e, b, d, c, a
8. Ví dụ Đồ thị về 7 cây cầu của thành phố Konigsberg 3 1 2 4 Khơng cĩ chu trình và đường đi Euler
9. Đồ thị G1, G2, G3  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.
10.  Đ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 tố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ị.
11. Điều kiện cần và đủ để đồ thị cĩ chu trình và đường đi Euler Đồ thị vơ hướng: Đồ 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ị G cĩ đường đi Euler khi và chỉ khi G liên thơng và cĩ khơng quá 2 đỉnh bậc lẻ.
12. Đồ thị cĩ 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. dv(v) = dr(v) 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.
13. 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 b c a e d e d c f b d a e
14. Ví dụ Đồ 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? b a b a c c d f d e
15. ĐỒ 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. Định nghĩa tương tự đối với đồ thị cĩ hướng Đồ thị chứa chu trình Hamintơn gọi là đồ thị Hamintơn
16. Ví dụ Cho đồ thị: a b f d c g e Đồ thị Hamintơn Đồ thị trên khơng cĩ chu trình và đường đi Euler nhưng cĩ chu trình Hamintơn. Chú ý 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.
17. Đị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. Xét đồ thị: a d e b c Đồ thị trên cĩ chu trình Hamintơn khơng? Vì sao?
18. Đồ thị Hamilton G3, đường đi Hamilton trong G2 , và G1.
19. Định lí 1 Cho G là đơn đồ thị n đỉnh (n 3). Nếu: n d(v) , v G 2 thì G cĩ chu trình Hamintơn Định lí 2 Cho G là đơn đồ thị n đỉnh (n 3). Nếu: n 1 d(v) , v G 2 thì G cĩ chu trình Hamintơn
20. Định lí 3 Nếu G là đồ thị cĩ hướng liên thơng mạnh và: n n d (v) & d (v) ,v G r 2 v 2 thì G cĩ chu trình cĩ hướng Hamintơn
21. 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. 2 a. 1 3 8 7 6 5 4
22. b. 1 2 3 4 5 8 10 9 7 6 11 12 13 14 15
23. 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 tố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ị
24. Thuật tố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.
25. 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.
26. (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.
27. Ví dụ: Tìm đường đi ngắn nhất từ đỉnh a đến z trong đồ thị sau: b 2 c 4 2 2 3 1 4 z a d e 1 3 7 6 f 5 g
28. Ví dụ trên đồ thị vơ hướng Nguồn: ThS. Trịnh Thanh Đèo 28
29. Ví dụ trên đồ thị cĩ hướng Nguồn: ThS. Trịnh Thanh Đèo 29
30. Hết chương