Luận văn Thạc sĩ Khoa học: Lý thuyết đồ thị và ứng dụng để giải toán sơ cấp

Đề tài đưa ra một số bài toán dẫn đến khái niệm đồ thị. Bằng những ví dụ gần gũi với thực tế. Làm rõ khái niệm đồ thị bằng những ví dụ gần gũi với thực tế cuộc sống. Tổng kết một số khái niệm hay dùng trong lý thuyết đồ thị. Ứng dụng một số kết quả của đồ thị vào giải quyết sáu dạng toán hay gặp trong chương trình bồi dưỡng toán trung học 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à ứng dụng để giải toán sơ cấp ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN NGUYỄN NGỌC HẢI LÝ THUYẾT ĐỒ THỊVÀ ỨNG DỤNG ĐỂ GIẢI TOÁN SƠ CẤP LUẬN VĂN THẠC SĨ TOÁN HỌC HÀ NỘI, NĂM 2014 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN NGUYỄN NGỌC HẢI LÝ THUYẾT ĐỒ THỊ VÀỨNG DỤNG ĐỂ GIẢI TOÁN SƠ CẤP LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 60 46 40 NGƯỜI HƯỚNG DẪN KHOA HỌC: GS. TS. ĐẶNG HUY RUẬN HÀ NỘI, NĂM 2014Mục lục Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 Các khái niệm và định lý cơ bản 7 1.1 Các ví dụ về đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Định nghĩa đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3 Biểu diễn đồ thị bằng hình học . . . . . . . . . . . . . . . . . . 12 1.4 Một số dạng đồ thị đặc biệt . . . . . . . . . . . . . . . . . . . . 13 1.5 Phương pháp đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . 142 Đồ thị và một số bài toán phổ thông 16 2.1 Bài toán liên quan đến bậc của đồ thị . . . . . . . . . . . . . . . 16 2.1.1 Bậc của đỉnh . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.2 Nửa bậc . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.3 Một số tính chất . . . . . . . . . . . . . . . . . . . . . . 17 2.1.4 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Bài toán liên quan đến chu trình . . . . . . . . . . . . . . . . . 28 2.2.1 Xích, Chu trình . . . . . . . . . . . . . . . . . . . . . . . 28 2.2.2 Đường, Vòng . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2.3 Một số tính chất . . . . . . . . . . . . . . . . . . . . . . 29 2.2.4 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.3 Bài toán liên quan đến tính liên thông . . . . . . . . . . . . . . 38 2.3.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.3.2 Một số tính chất . . . . . . . . . . . . . . . . . . . . . . 39 2.3.3 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.4 Đồ thị Euler - Đồ thị Hamilton . . . . . . . . . . . . . . . . . . 50 3 2.4.1 Đường đi Euler và đồ thị Euler . . . . . . . . . . . . . . 50 2.4.2 Đường đi Hamilton và đồ thị Hamilton . . . . . . . . . . 55 2.4.3 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 632.5 Bài toán liên quan đến đồ thị tô màu . . . . . . . . . . . . . . . 70 2.5.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . 70 2.5.2 Tính chất . . . . . . . . . . . . . . . . . . . . . . . . . . 71 2.5.3 Thuật toán tìm sắc số . . . . . . . . . . . . . . . . . . . 74 2.5.4 Lớp đồ thị có chu trình tam giác cùng màu . . . . . . . . 75 2.5.5 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 772.6 Bài toán về cây . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 2.6.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . 85 2.6.2 Đặc điểm của cây và bụi . . . . . . . . . . . . . . . . . . 85 2.6.3 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 88Lời kết . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4 Mở đầu Lý thuyết đồ thị (lý thuyết graph) là một ngành toán học hiện đại, một lĩnhvực khá trẻ của toán học mặc dù những vấn đề của lý thuyết đồ thị đã có từvài trăm năm trước đây. Những ý tưởng cơ bản về lý thuyết đồ thị được đưa ra vào năm 1736 bởinhà toán học Thụy Sĩ Leonhard Euler với bài toán nổi tiếng về 7 cây cầu ởthành phố K¨onigsberg. Những công trình nghiên cứu về lý thuyết đồ thị gắnliền với những tên tuổi các nhà toán học lớn như Euler, Hamilton,... Cuốn sáchgiáo khoa đầu tiên về lý thuyết đồ thị được K¨onig viết và xuất bản tại Leipzignăm 1936. Mãi 22 năm sau, cuốn sách giáo khoa thứ hai về đồ thị mới được rađời bởi nhà toán học Berge viết và in tại Paris. Vả lại, do đặc trưng rất “gần gũi” với thực tế của mình, lý thuyết đồ thịngày càng khẳng định được vị trí quan trọng trong việc áp dụng để giải cácbài toán trong cuộc sống. Nó có nhiều ứng dụng quan trọng trong nhiều ngànhkhoa học, kĩ thuật hiện đại: vật lý, hóa học, sinh học, tin học,... Ngày ...