Luận văn Thạc sĩ Toán học: Một số bài toán đếm trong lý thuyết đồ thị

Luận văn tìm hiểu về số cây trên tập đỉnh cho trước, số cây có n đỉnh cho trước, với n là một số nguyên dương. Luận văn cũng tìm hiểu cách tính số cây khung bằng ma trận Laplacian. Việc đánh giá số đỉnh, số cạnh của đồ thị phẳng cũng được xem là bài toán đếm. Cuối cùng luận văn trình bày một số đánh giá về việc đếm số tam giác trong đồ thị, bài toán này cũng thường xuất hiện trong các đề thi học sinh giỏi. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Toán học: Một số bài toán đếm trong lý thuyết đồ thị ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NINH THỊ NỤ MỘT SỐ BÀI TOÁN ĐẾMTRONG LÝ THUYẾT ĐỒ THỊLUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2019 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NINH THỊ NỤ MỘT SỐ BÀI TOÁN ĐẾMTRONG LÝ THUYẾT ĐỒ THỊChuyên ngành: Phương pháp Toán sơ cấpMã số: 8 46 01 13 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC TS. TRẦN NGUYÊN AN THÁI NGUYÊN - 2019Mục lụcMở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1Chương 1. Mở đầu đại số tổ hợp và lý thuyết đồ thị . . . . . . . . . 3 1.1. Đại số tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2. Công thức đa thức . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3. Mở đầu lý thuyết đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14Chương 2. Bài toán đếm trên đồ thị . . . . . . . . . . . . . . . . . . . . . . . . 23 2.1. Cây và các bài toán đếm cây . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2. Công thức tính số cây khung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.3. Đánh giá số cạnh của một đồ thị phẳng. . . . . . . . . . . . . . . . . . . . . . . . . 34 2.4. Số tam giác trong đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 iMở đầu Cùng với sự phát triển với tốc độ nhanh của công nghệ thông tin, lýthuyết tổ hợp và đồ thị đã trờ thành các lĩnh 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ý thuyết tổ hợp là chiếccầu nối giữa các bài toán cần được giải quyết với công cụ tính toán, còn đồthị là mô hình trực quan để mô tả các quan hệ hai ngôi. Trong những thập kỷ gần đâỵ, 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ìnhhữu hiệu cho tính toán và tối ưu. Ngày nay khái niệm đồ thị đã xâm nhậpkhông chỉ vào các lĩnh vực khoa học tự nhiên truyền thống như toán học,vật lý học hay hoá học, mà còn vào nhiều lĩnh vực khoa học tự nhiên và xãhội khác. Có nhiều bài toán toán về lý thuyết đồ thị cần được tìm hiểu như bàitoán tối ưu trên đồ thị, bài toán tô màu đồ thị, cấu trúc đồ thị, ... Các bàitoán về đồ thị cũng thường xuất hiện trong các đề thi học sinh giỏi các cấp.Luận văn tìm hiểu về một số bài toán đếm trên lý thuyết đồ thị như bài toánđếm cây; tính số cây khung; tìm mối liên hệ giữa một số yếu tố trong đồ thịnhư cạnh, đỉnh; đếm số tam giác trên đồ thị. Luận văn được chia làm hai chương. Chương 1 trình bày một số kiếnthức chuẩn bị về đại số tổ hợp, công thức đa thức và mở đầu về lý thuyết đồthị. Tuy là kiến thức chuẩn bị cho Chương 2 nhưng đối với tác giả nhiều kiếnthức của chương là kiến thức mới và có nhiều ứng dụng trong giải toán phổthông. Chương này chủ yếu tham khảo theo các tài liệu [1, 2, 4]. Chương 2trình bày về một số bài toán đếm cơ bản trong lý thuyết đồ thị. Bắt đầu làbài toán đếm về cây. Việc đếm số đỉnh, số cảnh của cây cũng cho ta một sốđặc trưng của cây (Định lý móc xích kiểu hoa cúc). Tiếp theo luận văn tìmhiểu về số cây trên tập đỉnh cho trước, số cây có n đỉnh cho trước, với n là 1một số nguyên dương. Luận văn cũng tìm hiểu cách tính số cây khung bằngma trận Laplacian. Việc đánh giá số đỉnh, số cạnh của đồ thị phẳng cũngđược xem là bài toán đếm. Cuối cùng luận văn trình bày một số đánh giávề việc đếm số tam giác trong đồ thị, bài toán này cũng thường xuất hiệntrong các đề thi học sinh giỏi. Chương 2 tham khảo chính theo các tài liệu[4, 6, 7, 8, 9]]. Trong quá trình làm luận văn, tôi nhận được sự hướng dẫn và giúp đỡtận tình của TS. Trần Nguyên An - Trường Đại học Sư phạm - Đại học TháiNguyên. Tôi xin được bày tỏ lòng biết ơn sâu sắc đến thầy. Tôi xin gửi lời cảm ơn chân thành đến quý thầy cô giảng dạy lớp Caohọc khóa Cao học Toán khóa 11E (2017-2019) - trường Đại học Khoa học- Đại học Thái Nguyên, đã truyền thụ đến cho tôi nhiều kiến thức và kinhnghiệm nghiên cứu khoa học. Lời cuối cùng, tác giả muốn dành để tri â ...