- CÁC BÀI TOÁN CƠ BẢN CỦA LÝ THUYẾT TỔ HỢP. - Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 60.46.0113. - LUẬN VĂN THẠC SỸ TOÁN HỌC. - 1 Bài toán tồn tại 6. - 1.1 Giới thiệu bài toán. - 1.2 Các phương pháp chứng minh sự tồn tại. - 1.2.1 Phương pháp chứng minh phản chứng. - 2 Bài toán liệt kê 39 2.1 Giới thiệu bài toán. - 2.3 Phương pháp sinh. - 3 Bài toán đếm 52 3.1 Các bài toán đếm cơ bản. - 3.1.1 Giới thiệu bài toán. - 3.2 Phân loại các bài toán đếm. - 3.2.1 Bài toán đếm có sử dụng hai quy tắc đếm cơ bản. - 3.2.2 Bài toán đếm các số tự nhiên thỏa mãn điều kiện cho trước. - 3.2.3 Phương trình, hệ phương trình, bất phương trình và đẳng thức chứa công thức tổ hợp. - 3.2.4 Bài toán đếm các đối tượng hình học. - 3.2.5 Bài toán phân chia (hoặc lấy ra) các đồ vật vào (hoặc ra khỏi) các hộp. - 4 Bài toán tối ưu 108 4.1 Giới thiệu bài toán. - 4.2 Bài toán tối ưu trong đồ thị. - 4.2.3 Bài toán tìm cây bao trùm có trọng số nhỏ nhất. - 4.2.4 Bài toán tìm đường đi có trọng số nhỏ nhất. - Các vấn đề liên quan đến lý thuyết tổ hợp là một bộ phận quan trọng, hấp dẫn và lý thú của Toán học nói chung và Toán học rời rạc nói riêng.. - Tư duy về tổ hợp đã xuất hiện từ rất sớm trong lịch sử phát triển của nhân loại và đến thế kỉ thứ 17 nó được hình thành như một ngành toán học bằng một loạt các công trình nổi tiếng của các nhà toán học như Pascal, Fermat, Lenibniz, Euler. - Kể từ sau khi tin học ra đời, lý thuyết tổ hợp phát triển ngày càng mạnh mẽ, có nội dung phong phú và được ứng dụng nhiều trong thực tế đời sống.. - Trong toán học sơ cấp, tổ hợp cũng xuất hiện với nhiều bài toán hay với độ khó cao. - Những ai mới bắt đầu làm quen với khái niệm tổ hợp thường khó hình dung hết độ phức tạp về về cấu trúc trên các tập đặc biệt. - Do vậy tôi đã chọn đề tài "bài toán cơ bản của lý thuyết tổ hợp". - Luận văn đã trình bày bốn bài toán cơ bản của lý thuyết tổ hợp, xây dựng một số bài toán áp dụng.. - Chương 1: Bài toán tồn tại. - Trong chương này tác giả đã giới thiệu bài toán tồn tại bằng ba bài toán cổ nổi tiếng là bài toán về bẩy cây cầu của Euler, bài toán bốn màu và bài toán chọn 2n điểm trên lưới n.n điểm.. - Trong chương này tác giả cũng nêu được hai phương pháp chứng minh sự tồn tại là phương pháp chứng minh bằng phản chứng và phương pháp sử dụng nguyên lý Diriclet.. - Chương 2: Bài toán liệt kê. - Chương 2 được trình bày theo bốn mục bao gồm: giới thiệu bài toán, thuật toán và độ phức tạp tính toán cùng với phương pháp sinh và thuật toán quay lui.. - Chương 3: Bài toán đếm. - Trong chương này tác giả đã nêu được các bài toán đếm cơ bản, phân loại các. - thị bằng ma trận và trình bày hai bài toán cơ bản là: Bài toán tìm cây bao trùm có trọng số nhỏ nhất và bài toán tìm đường đi có trọng số nhỏ nhất.. - Bài toán tồn tại. - Trong rất nhiều bài toán tổ hợp, việc chỉ ra sự tồn tại của một cấu hình thoả mãn các tính chất cho trước là hết sức khó khăn. - Bài toán về bẩy cây cầu của nhà toán học Euler vào thể kỉ XVIII đã khiến người dân thành phố Konigsberg và các nhà toán học thời bấy giờ mất bao công tìm kiếm lời giải. - Như vậy, trong tổ hợp xuất hiện một vấn đề rất quan trọng là xét sự tồn tại của các cấu hình tổ hợp với các tính chất cho trước. - Các bài toán thuộc dạng này được gọi là các bài toán tồn tại tổ hợp.. - Một bài toán tồn tại tổ hợp xem như giải xong nếu chỉ ra một cách xây dựng cấu hình hoặc chứng minh rằng chúng không tồn tại. - Để thấy rõ được sự phức tạp của vấn đề, dưới đây xin được xét một số bài toán tồn tại cổ điển nổi tiếng.. - a, Bài toán về bẩy cây cầu của Euler. - Nhà toán học Thụy Sĩ, Leonhard Euler, đã giải bài toán này.. - Ông đã chứng minh được rằng không có được đường đi nào thoả mãn yêu cầu bài toán (lời giải chi tiết của bài xin được trình bày rõ ở chương IV). - b, Bài toán bốn màu. - Có những bài toán mà nội dung của nó có thể giải thích cho bất kì ai, tuy lời giải của nó thì ai cũng có thể tự tìm nhưng mà khó có thể tìm được.. - Ngoài định lý Fermat thì bài toán bốn màu là một trong những bài toán như vậy. - Bài toán có thể phát biểu trực quan như sau: Chứng minh rằng mọi bản đồ trên mặt phẳng đều có thể tô bằng bốn màu sao cho không có hai nước láng giềng nào được tô bởi cùng một màu. - Con số 4 không phải là ngẫu nhiên, người ta đã chứng minh được rằng mọi bản đồ đều được tô với số màu lớn hơn 4 , còn với số màu ít hơn 4 thì không tô được, chẳng hạn bản đồ gồm bốn nước ở hình dưới đây không thể tô được với số màu ít hơn 4.. - Bài toán này xuất hiện vào khoảng những năm 1850 - 1852 từ một nhà buôn người Anh là Gazri, khi tô bản đồ hành chính nước Anh đã cố gắng chứng minh rằng có thể tô bằng 4 màu. - Năm 1878, Keli trong một bài báo đăng ở tuyển tập các công trình của Hội toán học Anh có hỏi rằng bài toán này đã được giải quyết hay chưa? Từ đó bài toán này trở thành nổi tiếng và trong hơn một thế kỉ, có rất nhiều người làm toán nghiệp dư cũng như chuyên nghiệp đã cố gắng chứng minh giả thuyết này. - Tuy nhiên, mãi đến năm 1976 hai nhà toán học Mỹ là K.Appel và W.Haken mới chứng minh được giả thuyết này bằng máy tính điện tử.. - c, Bài toán chọn 2n điểm trên lưới n × n điểm. - Hình dưới đây cho một lời giải bài toán với n = 12. - Phương pháp chứng minh phản chứng có lẽ là một trong những phương pháp chứng minh sớm nhất mà loài người đã biết đến, đặc biệt trong nghệ thuật diễn thuyết và tranh luận. - Trong toán học, phương pháp chứng minh phản chứng thường được sử dụng, đặc biệt khi cần chứng minh tính duy nhất của một đối tượng T nào đó thoả mãn điều kiện cho trước (mà sự tồn tại của T đã được chứng minh trước đó) ta thường giả sử còn ∀T 0 6= T . - Giả sử ta phải chứng minh một mệnh đề có dạng P. - Ta có thể dùng phương pháp chứng minh phản chứng để chứng minh nguyên lý Diriclet. - Do đó, với nhiều bài toán ta có thể chứng minh bằng nguyên lý Diriclet hoặc phương pháp chứng minh phản chứng.. - b, Phương pháp giải toán qua các ví dụ. - [1] Nguyễn Văn Mậu (2008), Chuyên đề chọn lọc tổ hợp và toán rời rạc, NXB Giáo Dục.. - [5] Nguyễn Đức Nghĩa(2001), Toán học rời rạc, NXB Đại học Quốc gia Hà Nội.. - [6] Ngô Đắc Tân(2004), Lý thuyết tổ hợp và đồ thị, NXB Đại học Quốc gia Hà Nội.. - [7] Tạp chí toán học và tuổi trẻ, Tuyển tập 30 năm, NXB Giáo Dục, 1997.. - [8] Kenneth H Rosen, Toán học rời rạc ứng dụng trong tin học, NXB khoa học và kĩ thuật, 1998.