Lý thuyết Graph và ứng dụng

Nhiệm vụ đổi mới phương pháp dạy học theo hướng tích cực hóa hoạt động học tập của học sinh không chỉ là định hướng mà còn đòi hỏi cần nghiên cứu xác định nguyên tắc, quy trình vận dụng của những phương pháp dạy học tích cực. Việc kết hợp các phương pháp truyền thống với các phương pháp dạy học đặc thù như phương pháp Graph là một giải pháp tốt.Lý thuyết đồ thị (Graph) là một chuyên ngành toán học hiện đại đã được ứng dụng vào nhiều ngành khoa học, kĩ thuật khác nhau vì lý...
Nội dung trích xuất từ tài liệu:
Lý thuyết Graph và ứng dụngNhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốt LỜI MỞ ĐẦU Nhiệm vụ đổi mới phương pháp dạy học theo hướng tích cực hóa hoạt đ ộnghọc tập của học sinh không chỉ là định hướng mà còn đòi hỏi cần nghiên cứu xácđịnh nguyên tắc, quy trình vận dụng của những phương pháp dạy học tích cực. Việckết hợp các phương pháp truyền thống với các phương pháp dạy học đ ặc thù nhưphương pháp Graph là một giải pháp tốt. Lý thuyết đồ thị (Graph) là một chuyên ngành toán học hiện đại đã đ ược ứngdụng vào nhiều ngành khoa học, kĩ thuật khác nhau vì lý thuyết đ ồ thị toán học làphương pháp khoa học có tính khái quát cao, có tính ổn định vững chắc để mã hóa cácmối quan hệ của các đối tượng được nghiên cứu. Có thể nói Graph là một phép Toánthần kì kích thích sự hoạt đông, óc tư duy, suy luận của trí não thậm chí còn là mộtcâu trả lời thông minh, logic cho các câu đố hốc búa. Việc vận dụng phương pháp graph trong dạy học Toán nhằm nâng cao chấtlượng dạy học môn học này ở trường THPT (nhất là các trường chuyên Tin) và đượcxem như là một trong những hành trang mới vừa tiếp cận vừa bổ sung vào hệ thốngcác phương pháp dạy học truyền thống song đó còn làm phong phú thêm kho tàng cácphương pháp dạy học Toán . Theo hướng này, có nhiều tác giả đã thành công trongviệc nghiên cứu và vận dụng lý thuyết Graph vào dạy học một số môn học ở trườngphổ thông và đã có những kết quả bước đầu. Năm 1980, tác giả Trần Tr ọngDương đã nghiên cứu đề tài: “Áp dụng phương pháp Graph và algorit hoá để nghiêncứu cấu trúc và phương pháp giải, xây dựng hệ thống về lập công thức hoá học ởtrường phổ thông”. Năm 1984, Phạm Tư vớisự hướng dẫn của giáo sư NguyễnNgọc Quang đã nghiên cứu đề tài: “Dùng Graph nội dung của bài lên l ớp đ ể dạy vàhọc chương Nitơ- Phôtpho ở lớp 11 trường trung học phổ thông”. Năm 1987, NguyễnChính Trung đã nghiên cứu: “Dùng phương pháp Graph lập chương trình tối ưu đ ểdạy môn sử”. Trong dạy học sinh học ở trường phổ thông, Nguyễn Phúc Chỉnh làngười đầu tiên đi sâu nghiên cứu về lý thuyết Graph và ứng dụng lý thuyết Graphtrong dạy học Giải phẫu - Sinh lý người (năm 2005). Đối với phương pháp Graphtrong dạy học ttoán cácchuyên gia Hoàng Chúng và Vũ Đình Hoà đã có một số địnhhướng nhưng chưa có học viên cao học nào nghiên cứu một cách chi tiết. Với mong muốn được tiệp cận chuyên sâu về Graph, nhóm tác giả mạnh dạnlàm bài thu hoạch “Lý thuyết đồ thị Graph”. Nội dung bài viết là những kinh nghiệmmà nhóm tác giả đã học hỏi được, bám sát vào những dạng cơ bản mà học sinhthường gặp trong học tập hay đời sống hàng ngày để từ đó vận dụng lí thuyết đồ thịvà giúp ta đạt được hai mục tiêu: - Giải được một lớp bài tập - Hỗ trợ cho việc lập trình Trong bài thu hoạch, tác giả đưa ra một số khái niệm cơ bản về đồ thị kèmtheo những hình ảnh minh họa sinh động kết hợp với xây dựng hệ thống phươngpháp phân tích, trình bày cách giải đối với các bài tập, ví dụ cụ thể dựa theo các vấnđề được đề cập. Bên cạnh đó chúng tôi còn cung cấp đáp án và hướng dẫn giải sơGVBM: Dư Quang Anh Huy Trang 1Nhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốtlược một số bài tập tiêu biểu nhằm giúp độc giả có thể thông hiểu, vận dụng, kiểmtra kiến thức và rèn luyện kĩ năng phân tích đồ thị. Mong rằng với bài thu hoạch “Lý thuyết đồ thị Graph” sẽ giúp độc giả có cáinhìn và tầm hiểu biết khái quát, sâu và rộng hơn về dạng Toán vô cùng quan trọngnày. Nhân đây, nhóm tác giả xin được bày tỏ lòng cảm ơn sâu sắc tới thầy DưQuang Anh Huy (giáo viên toán trường THPT Thốt Nốt, TP Cần Thơ) đã nhiệt tìnhgiúp đỡ, chỉ dẫn chúng tôi trong quá trình biên soạn bài thu họạch này. Tuy bài thu hoạch được biên soạn khá kĩ và công phu nhưng việc thiếu sót làkhó tránh khỏi. Nếu có điều chi sơ suất rất mong quí độc giả thông cảm! Xin chânthành cảm ơn!GVBM: Dư Quang Anh Huy Trang 2Nhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốt ĐỒ THỊ TRONG ĐỜI SỐNG Trong đời sống, chúng ta phải giải quyết nhiều vấn đề mà ta có thể coi mộtđường cong là cạnh và đầu mút của chúng được coi là đỉnh của cạnh. Để làm rõ điềunày, chúng ta có thể xem xét những ví dụ sau đây. Ví dụ 1: Hãy xác định một con đường đi bộ từ nhà đến trường tối ưu nhất(hiểu theo nghĩa khoảng cách ngắn nhất). - Khi giải quyết bài toán này bạn phải quan sát trên bản đồ, bỏ qua độ rộnghẹp của các đường phố và chỉ còn chú ý tới độ dài của các con đ ường cũng như cácđầu mút giao thông để phát hiện một con đường ngắn nhất. Trong vấn đề tìm đườngđi ngắn nhất này chúng ta đã coi các phố là các cạnh và các đầu mút giao thông (cácngã tư chẳng hạn) là các đỉnh của các cạnh. - Trong nhiều vấn đề phải ...