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

Chương 5 trình bày những kiến thức liên quan đến đường đi trên đồ thị. Các nội dung chính trong chương gồm có: Đường đi và chu trình Euler, đường đi và chu trình Hamilton, bài toán đường đi tốt nhất. | Chương 5. Đường đi trên đô thị I. ĐƯỜNG ĐI VÀ CHU TRÌNH EULER Định nghĩa 1. 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. Đườ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. Đồ thị được gọi là đồ thị Euler nếu nó có chu trình Euler và gọi là đồ thị nửa Euler nếu nó có đường đi Euler. Rõ ràng mọi đồ thị Euler luôn là nửa Euler nhưng điều ngược lại không luôn đúng. jThí dụ 1. Đồ 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. Hình 1. Đồ thị Gỉ G2 G3 jThí dụ 2. Đồ thị H2 trong hình 2 là đồ thị Euler vì nó có chu trình Euler a b c d e a. Đồ thị H3 không có chu trình Euler nhưng nó có đường đi Euler c a b c d b vì thế H3 là đồ thị nửa Euler. Đồ thị H1 không có chu trình cũng như đường đi Euler. Hình 2. Đồ thị H1 H2 H3 Đ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ị. Định lý 1 Euler . Đồ thị vô hướng liên thông G là đồ thị Euler khi và chỉ khi mọi đỉnh của G đều có bậc chăn. Hệ quả. Đồ thị vô hướng liên thông G là nửa Euler khi và chỉ khi nó có không quá 2 đỉnh bậc lẻ. Định lý 2 Euler tổng quát . Đồ thị vô hướng liên thông G có k đỉnh bậc lẻ k luôn là số chăn thì cần ít nhất k 2 con đường để đi qua tất cả các cạnh của đồ thị môi cạnh chỉ đi qua đúng 1 lần. Hơn nữa để đi được như vậy môi con đường cần xuất phát từ một đỉnh bậc lẻ và kết thúc ở một đỉnh bậc lẻ khác. Giả sử G là đồ thị Euler thuật toán đơn giản sau đây cho phép xác định chu trình Euler khi làm bằng tay. Thuật toán Flor Xuất phát từ một đỉnh u nào đó của G ta đi theo các cạnh của nó một cách tuỳ ý chỉ cần tuân thủ 2 qui tắc sau 1

• Toán học
• Toán rời rạc
• Lý thuyết đồ thị
• Đường đi trên đồ thị
• Chu trình Euler
• Chu trình Hamilton
• Bài toán đường đi tốt nhất
• Bài giảng toán rời rạc
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Bài tập về toán rời rạc
• Ôn tập toán rời rạc
• Đề thi toán rời rạc