tailieunhanh - Ebook Lý thuyết tổ hợp và đồ thị: Phần 1

Phần 1 cuốn sách "Lý thuyết tổ hợp và đồ thị" cung cấp cho người học các kiến thức: Các bài toán và kết quả tổ hợp cơ bản, phương pháp đếm dùng hàm sinh, một số phương pháp và kỹ thuật đếm cơ bản khác, lý thuyết Polya. . | BỘ SÁCH CAO HỌC - VIỆN TOÁN HỌC NGÔ ĐẮC TÂN Vỉện Tòán học Trung tâm Khoa học Tự nhiên và Công nghệ Quốc gia LÝ THUYẾT TO Hộp VÀ ĐỒ THI i 1 1138 ƯỒNQ LẲNG ữ 0Q69Jề8t744 W NHÀ XUẤT BẢN ĐẠI HỌC QUỐC GIA HÀ NỘI DAYKEM. HỘI ĐỔNG BIÊN TẬP GS Trần Đức Vân Chủ tịch PGS Phan Huy Khải Thư ký GS Hà Huy Khoái GS Phạm Hữu Sách GS Ngô Việt Trưng GS Hoàng Tụy GS ĐỖ Long Vân DAYKEM. Lời nói đầu Cùng vớỉ sự phát triển với tốc độ nhanh cùa công nghệ thông tin ỉý thuyểt tổ hợp và đồ thi đã trở thành các nhh vực toán học quan trọng và cần thiết cho nhiều lĩnh vực khoa học và ứng dụng. Đó là do lý thuyết tổ hợp là chiếc cầu nối giữa các bài toán cần được giảỉ quyết với công cụ tính toán còn đb thí ỉà mô hình trực quan để mô tầ các quan hệ hai ngôi. Nhiều bài toán hiện nạy được giải quyết bằng cách qụi chúng về các bài toán tổ hợp. Việc giài quyết được các bài toán to hợp này thường có sự hỗ trợ của máy tính sẽ dẫn tới lời giải cho. bài toán ban đầu. Có thể dẫn sự chứng minh giả thuyết bốn màu rá dâỹ để minh hoạ. Từ 1850 Guthrie đã có nhận xét rằng có thể dùng bốn màu khác nhau đề tô các tỉnh của vương quốc Anh sao cho không có hai tỉnh kề nhau nào cùng màu. Với nhận xét này người ta dặt giả thuyết rằng có thể dùng bốn mảụ khác nhau đề tô màu mọi bản đồ bao gồm các quốc gia sao cho không có hai quốc gia kề nhau-nào có cùng màu. Giả thuyết này đã thách thức các nhà toán học hơĩi 100 nam. Mãi tới tận nằm 1977 Appel và Haken mới qui được bài toán tô màu bản đồ về việc xem xét trên 1900 cấu hình tổ hợp. Với việc sử dụng trên 1200 giờ mấy tính để xem xét các cấu hình tổ hợp trên Appel và Haken đã chứng minh được giả thuyết bốn màu. Trong khoảng mấy chục năm gần đầy người ta đã quan tâm nhiều tới đồ thị và các ứng dụng của nó. Đó là do đồ thị đã chứng tỏ được là một mô hình hữu hiệu cho tính toán và tối ưu. Ngày nay khái niệm đồ thị đã xâm nhập không chi vào các lĩnh vực khoa học tự nhiên truyền .