Luận văn Thạc sĩ Khoa học: Lý thuyết đồ thị với các bài toán phổ thông

Luận văn "Lý thuyết đồ thị với các bài toán phổ thông" đưa đến sự sáng tạo trong cách nhìn nhận bài toán và lập luận cách giải dưới con mắt của lý thuyết đồ thị. Ngoài phần mở đầu và kết luận luận văn gồm 3 chương: Chương 1 Đại cương về đồ thị, Chương 2 Một số bài toán đồ thị cơ bản, Chương 3 Ứng dụng lý thuyết đồ thị vào giải toán phổ thông.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Khoa học: Lý thuyết đồ thị với các bài toán phổ thông ĐẠI HỌC QUỐC GIA HÀ NỘITRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ———– NGUYỄN THỊ MINH THƯƠNG LÝ THUYẾT ĐỒ THỊ VỚI CÁC BÀI TOÁN PHỔ THÔNGLUẬN VĂN THẠC SĨ KHOA HỌC HÀ NỘI - 2015 ĐẠI HỌC QUỐC GIA HÀ NỘITRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ———– NGUYỄN THỊ MINH THƯƠNG LÝ THUYẾT ĐỒ THỊ VỚI CÁC BÀI TOÁN PHỔ THÔNG Chuyên ngành: Phương pháp toán sơ cấp Mã số: 60.46.01.13LUẬN VĂN THẠC SĨ KHOA HỌC Người hướng dẫn khoa học: GS.TS Đặng Huy Ruận HÀ NỘI - 2015Mục lụcLời nói đầu 31 Đại cương về đồ thị 4 1.1 Định nghĩa đồ thị . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Một số dạng đồ thị đặc biệt . . . . . . . . . . . . . . . . 6 1.3 Bậc của đỉnh đồ thị . . . . . . . . . . . . . . . . . . . . . 8 1.3.1 Bậc của đỉnh . . . . . . . . . . . . . . . . . . . . 8 1.3.2 Nửa bậc . . . . . . . . . . . . . . . . . . . . . . . 8 1.3.3 Một số tính chất . . . . . . . . . . . . . . . . . . 9 1.4 Xích, chu trình, đường, vòng . . . . . . . . . . . . . . . . 13 1.4.1 Xích, chu trình . . . . . . . . . . . . . . . . . . . 13 1.4.2 Đường, vòng . . . . . . . . . . . . . . . . . . . . . 14 1.4.3 Một số tính chất . . . . . . . . . . . . . . . . . . 15 1.5 Đồ thị liên thông . . . . . . . . . . . . . . . . . . . . . . 16 1.5.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . 16 1.5.2 Tính chất . . . . . . . . . . . . . . . . . . . . . . 17 1.6 Số ổn định trong, số ổn định ngoài . . . . . . . . . . . . 18 1.6.1 Số ổn định trong . . . . . . . . . . . . . . . . . . 18 1.6.2 Số ổn định ngoài . . . . . . . . . . . . . . . . . . 19 1.6.3 Các thuật toán tìm số ổn định trong, số ổn định ngoài. . . . . . . . . . . . . . . . . . . . . . . . . 20 1.7 Nhân của đồ thị và ứng dụng vào trò chơi . . . . . . . . 21 1.7.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . 21 1.7.2 Tính chất . . . . . . . . . . . . . . . . . . . . . . 22 1.7.3 Trò chơi Nim . . . . . . . . . . . . . . . . . . . . 23 1.7.4 Trò chơi bốc các vật . . . . . . . . . . . . . . . . 24 1.8 Cây và bụi . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.8.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . 29 1.8.2 Đặc điểm của cây và bụi . . . . . . . . . . . . . . 30 12 Một số bài toán đồ thị cơ bản 33 2.1 Bài toán về đường đi . . . . . . . . . . . . . . . . . . . . 33 2.1.1 Đường đi Euler - Chu trình Euler. . . . . . . . . . 33 2.1.2 Đường đi Hamilton - Chu trình Hamilton. . . . . 40 2.2 Bài toán tô màu đồ thị . . . . . . . . . . . . . . . . . . . 43 2.2.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . 43 2.2.2 Một số tính chất . . . . . . . . . . . . . . . . . . 43 2.2.3 Thuật toán tô màu đỉnh. . . . . . . . . . . . . . . 533 Ứng dụng lý thuyết đồ thị vào giải toán phổ thông. 54 3.1 Quy trình giải bài toán bằng phương pháp đồ thị. . . . . 54 3.1.1 Xây dựng đồ thị G mô tả các quan hệ. . . . . . . 54 3.1.2 Dựa vào các kết quả của lý thuyết đồ thị hoặc lý luận trực tiếp suy ra đáp án của bài toán D. . . . 54 3.2 Bài toán về đỉnh - cạnh của đồ thị. . . . . . . . . . . . . 55 3.3 Bài toán về xích, chu trình, đường, vòng và tính liên thông của đồ thị. . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.4 Bài toán về tô màu đồ thị. . . . . . . . . . . . . . . . . 63 3.5 Bài toán liên quan đến số ổn định trong, số ổn định ngoài. 74 3.6 Bài toán liên quan đến đường đi. . . . . . . . . . . . . . 76 3.6.1 Bài toán tìm đường đi trong mê cung . . . . . . . 76 3.6.2 Bài toán liên quan đến đường và chu trình Euler . 80 3.6.3 Bài toán liên quan đến đường và chu trình Hamilton 82 3.7 Bài toán liên quan đến cây. . . . . . . . . . . . . . . . . 84Kết luận 89Tài liệu tham khảo 90 2 LỜI NÓI ĐẦU Lý thuyết ...