Toán rời rạc là một lĩnh vực của toán học nghiên cứu về các đối tượng rời rạc. Mặc dù các đối tượng là rời rạc, không có ý nghĩa nhưng khi chúng ta liên kết các đối tượng rời rạc lại với nhau ta lại có được những thông tin rất lý thú và mang nhiều ý nghĩa. | BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC CẦN THƠ KHOA SƯ PHẠM BỘ MÔN TOÁN HỌC GIÁO TRÌNH TOÁN RỜI RẠC Discrete mathematics Biên soạn Bùi Anh Kiệt Trương Quốc Bảo Năm 2003 LỜI NÓI ĐẦU Toán rời rạc là một lĩnh vực của toán học nghiên cứu về các đối tượng rời rạc. Mặc dù các đối tượng là rời rạc không có ý nghĩa nhưng khi chúng ta liên kết các đối tượng rời rạc lại với nhau ta lại có được những thông tin rất lý thú và mang nhiều ý nghĩa. Chúng ta sẽ sử dụng công cụ của toán học rời rạc khi phải đếm các đối tượng nghiên cứu mối quan hệ giữa các tập rời rạc khi nghiên cứu các quá trình hữu hạn. Một trong những nguyên nhân chủ yếu làm tăng tầm quan trọng của toán rời rạc là việc lưu trữ và xử lý thông tin trên máy tính điện tử mà bản chất là các quá trình rời rạc. Ba lĩnh vực có nhiều ứng dụng của toán học rời rạc là lý thuyết tổ hợp hàm đại số logic đại số Boole và lý thuyết đồ thị. Các vấn đề về lý thuyết tổ hợp hàm đại số logic đại số Boole sẽ được trình bày trong các giáo trình khác. Trong phạm vi giáo trình này chúng tôi chỉ trình bày lĩnh vực có thể xem là quan trọng nhất và có nhiều ứng dụng nhất của toán học rời rạc là Lý thuyết đồ thị. Lý thuyết đồ thị được khai sinh kể từ công trình nghiên cứu về bài toán 7 cây cầu Konigsberg của nhà toán học Leonhard Euler 1707 - 1783 được công bố vào năm 1736. Từ đó đến nay đã có nhiều nhà toán học trên thế giới nghiên cứu làm cho lý thuyết đồ thị ngày càng phong phú và có nhiều ứng dụng trong các lĩnh vực khác nhau như mạng điện tử lý thuyết mã vận trù học kinh tế học . Đặc biệt trong khoảng vài chục năm trở lại đây cùng với sự ra đời của máy tính điện tử và sự phát triển nhanh chóng của Tin học Lý thuyết đồ thị càng được quan tâm nhiều hơn đặc biệt là các thuật toán và ứng dụng trên đồ thị. Hiện nay môn học này đã được xem là kiến thức cơ sở của khoa học máy tính. Giáo trình này được biên soạn từ bài giảng của các tác giả trong các năm qua ở Trường Đại học Cần thơ và các trung tâm đào tạo liên kết trong vùng Đồng .