CHƯƠNG 1 CƠ SỞ LÝ LUẬN VÀ THỰC TIỄN CỦA ĐỀ TÀI 1. Lược sử vấn đề nghiên cứu 1. Trên Thế giới Lí thuyết Graph là một chuyên ngành của toán học được khai sinh từ công trình về bài toán Bảy cây cầu ở Konigsburg (1736) của nhà toán học người Thụy Sĩ – Leonhard Euler (1707 – 1783). Lúc đầu, lý thuyết graph là một bộ phận nhỏ của toán học, chủ yếu nghiên cứu giải quyết những bài toán có tính chất giải trí.
Trong những năm cuối thế kỉ XX, cùng với sự phát triển của toán học và nhất là toán học ứng dụng, những nghiên cứu về vận dụng lý thuyết graph đã có những bước tiến nhảy vọt. Sau đó nó đã được nghiên cứu trong các lĩnh vực khoa học khác. [7] Năm 1965, tại Liên Xô cũ, A. Xokos là người đầu tiên đã vận dụng một số quan điểm của lí thuyết Graph để mô hình hóa nội dung tài liệu sách giáo khoa môn hóa học.
Poloxin mô tả trình tự các thao tác dạy học trong một tình huống dạy học bằng Graph.Garkunov đã sử dụng phương pháp graph để lập mô hình các tình huống dạy học của phương pháp dạy học nêu vấn đề. Trên cơ sở đó, ông phân loại ra các tình huống khác nhau trong dạy học nêu vấn đề. Tuy nhiên, phương pháp graph do Xokhor, Polosin, Garkunov và những người khác đã xuất mới chỉ dừng lại ở mức độ là phương pháp nghiên cứu khoa học trong lý luận dạy học. Sau này, các nhà nghiên cứu và các giáo viên có kinh nghiệm lâu năm trong nghề đã đưa graph vào kiểm nghiệm trong thực tiễn giảng dạy và thấy rõ hiệu quả của giờ lên lớp khi dạy bằng graph.
Tiêu biểu có một số tác giả : Công trình graph và ứng dụng của nó với bố cục 8 chương, L.Berezina đã dành những chương đầu cho việc nêu khái niệm garph và ứng dụng có tính 6 z chất riêng biệt để minh họa cho lý thuyết này. Những chương sau, tác giả đã dành sự chú ý cho những ứng dụng cuả graph trong lĩnh vực kinh tế và điều khiển. Ông khẳng định mục đích chính khi viết cuốn sách là giúp đỡ giáo viên, kể cả học sinh, nắm vững khái niệm cơ bản của lý thuyết đồ thị. và làm quen với một vài ứng dụng của nó dưới dạng phổ cập.
Ngoài ra, có thể kể đến một số công trình khác như : graph và mạng lưới hữu hạn của R.Xachi; lý thuyết graph của V.đều nêu những định hướng cho việc ứng dụng graph vào nghiên cứu, giảng dạy các bộ môn trong nhà trường như: văn học, vật lí, hoá học, sinh học,. Năm 1973 tại Liên Xô (cũ) tác giả Nguyễn Như Ất đã vận dụng phương pháp graph kết hợp với phương pháp ma trận như một phương pháp hỗ trợ để xây dựng logic cấu trúc các khái niệm Tế bào học trong giáo trình môn Sinh học đại cương trường phổ thông của nước Việt Nam. Hiện nay, nhiều nước khác nhau trên thế giới, các công trình nghiên cứu về lý thuyết graph cũng như tìm hiểu ứng dụng graph trong dạy học ở tất cả các môn học, các cấp học số lượng ngày càng lớn với chất lượng ngày càng sâu sắc. Ở Việt Nam Ở Việt Nam, nhà sư phạm đầu tiên đề xuất việc nghiên cứu và vận dụng phương pháp graph trong khoa học thành phương pháp graph dạy học, mở ra một hướng đi mới cho những nhà nghiên cứu lí luận dạy học là GS.
Nguyễn Ngọc Quang. GS đã cùng với các cộng sự tiến hành thực nghiệm đưa lý thuyết graph vào dạy học trong nhà trường phổ thông và đại học. Năm 1979, giáo sư viết cuốn sách lí luận dạy học - khoa học về trí dục và dạy học như một lời tuyên ngôn cho việc tìm cách vận dụng những phương pháp thâm nhập khoa học (như thực nghiệm, dự đoán, mô hình, algorit, sơ đồ mạng .) vào thực tiễn dạy học ở trường phổ thông. Sau đó vào năm 1981 ông công bố bài báo:phương pháp graph trong dạy học; năm 1982 ông công bố bài: 7 z phương pháp graph và lí bài toán hoá học; năm 1983 ông công bố bài: Sự chuyển hoá phương pháp khoa học thành phương pháp dạy học.
Qua những nghiên cứu của mình, giáo sư khẳng định việc sử dụng phương pháp graph trong dạy học có giá trị rất lớn về mặt trí dục, vì: khi lập được graph nội dung của một vấn đề có nghĩa là nắm vững được cả cấu trúc và lôgic phát triển của nội dung vấn đề đó, đồng thời graph nội dung của vấn đề chính là điểm tựa cho sự lĩnh hội, tái hiện nội dung đó. Song song với giá trị trí dục, phương pháp này có giá trị rất lớn về mặt đức dục, vì:graph nội dung của một bài lên lớp là công cụ cho cả giáo viên và học sinh nhằm đạt được chất lượng cao của dạy và học đặc biệt là của tự học. Trên cơ sở tiếp thu những thành tựu nghiên cứu khoa học của GS.Nguyễn Ngọc Quang, năm 1984 nhà giáo Phạm Tư đã nghiên cứu: Dùng graph nội dung của bài lên lớp để dạy học chương Nitơ-Phốtpho ở lớp 11- THPT, tác giả đã nghiên cứu việc dùng phương pháp graph với tư cách là phương pháp dạy học (biến phương pháp graph trong toán học thành phương pháp dạy học hoá học). Phạm Tư một lần nữa khẳng định hiệu quả của graph trong việc nâng cao chất lượng dạy học và đổi mới phương pháp dạy học qua hai bài báo Dạy học bằng phương pháp graph nâng cao chất lượng giờ giảng và Dạy học bằng phương pháp graph góp phần nâng cao chất lượng học tập, tự học.
Năm 1987, Nguyễn Chính Trung đã nghiên cứu Dùng phương pháp graph lập chương trình tối ưu và dạy môn sử dụng thông tin trong chiến dịch. Trong công trình này tác giả đã nghiên cứu chuyển hoá graph toán học vào lĩnh vực giảng dạy khoa học quân sự. Năm 1993, Hoàng Việt Anh đã nghiên cứu Vận dụng phương pháp sơ đồ - graph vào giảng dạy địa lý các lớp 6 và 8 ở trường trung học cơ sở. Tác giả đã tìm hiểu và vận dụng phương pháp graph trong quy trình dạy học môn địa lý ở trường trung học cơ sở và đã bổ sung một phương pháp dạy học cho những bài thích hợp, trong tất cả các khâu lên lớp (chuẩn bị bài, nghe giảng, 8 z ôn tập, kiểm tra) nhằm nâng cao năng lực lĩnh hội tri thức, nâng cao chất l- ượng dạy học bộ môn địa lý.
Trong những năm gần đây, nhất là sau khi thực hiện chương trình cải cách giáo dục, các bài viết về việc dùng graph trong dạy học đã có những bước chuyển nhất định. Các vấn đề nghiên cứu trở nên đa dạng, phong phú và đội ngũ tác giả ngày một đông đảo hơn. Việc ứng dụng lý thuyết graph cũng được mở rộng ở nhiều môn khác nhau trong nhà trường. Có thể kể đến các tác giả sau: Phạm Thị My (2000) nghiên cứu “ứng dụng lý thuyết Graph xây dựng và sử dụng sơ đồ để tổ chức hoạt động nhận thức của học sinh trong dạy học sinh học ở THPT”.
[12] Trịnh Quang Từ:Sử dụng graph trong thiết kế phương pháp dạy học. Nguyễn Phúc Chỉnh với: Sử dụng Graph nhằm tích cực hoá hoạt động nhận thức của học sinh trong dạy học sinh thái học và Sử dụng Graph trong dạy học sinh học góp phần phát triển tư duy hệ thống. Năm 2005 tác giả nghiên cứu: Nâng cao hiệu quả dạy học giải phẫu sinh lý người ở trung học cơ sở bằng áp dụng phương pháp graph. Trong lĩnh vực 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 một cách hệ thống về lý thuyết graph và ứng dụng lý thuyết graph trong dạy học Giải phẫu sinh lý người.
Trong lĩnh vực dạy học Sinh học ở trường phổ thông, phó giáo sư - tiến sĩ Lê Đình Trung cũng là một trong số những người đi sâu nghiên cứu một cách hệ thống về lý thuyết graph và ứng dụng lý thuyết graph trong dạy học Sinh học. Một số vấn đề cơ bản của lí thuyết graph 1. Khái niệm Graph Theo từ điển Anh - Việt, graph (danh từ) có nghĩa là sơ đồ, đồ thị, mạch, mạng; khi là động từ, graph có nghĩa là vẽ sơ đồ, vẽ đồ thị, minh hoạ 9 z bằng đồ thị, vẽ mạng, vẽ mạch; còn khi là tính từ, graphic có nghĩa là thuộc về sơ đồ, thuộc về đồ thị, thuộc về mạng mạch. Hiện nay để tránh một cách hiểu máy móc mang tính chất toán học, khi sử dụng lý thuyết này để nghiên cứu và giảng dạy các môn khoa học khác người ta vẫn giữ nguyên tên gọi của nó là “graph” chứ không dịch sang tiếng Việt.
Về mặt hình thức biểu hiện thì graph được hiểu là sơ đồ, gồm những điểm biểu thị các đối tượng được xem xét và các đường nối các điểm với nhau tượng trưng cho một quan hệ nào đó giữa các đối tượng - đó chính là các graph. Theo lý thuyết toán: Một graph gồm một tập hợp điểm gọi là đỉnh của graph cùng với một tập hợp đoạn thẳng hay đường cong gọi là cạnh (cung) của graph, mỗi cạnh nối hai đỉnh khác nhau và hai đỉnh khác nhau được nối bằng nhiều nhất là một cạnh. Như vậy, điều kiện để lập một graph phải có hai yếu tố: tập hợp các đỉnh và tập hợp các cung. Mỗi cung lại là tập hợp của một cặp đỉnh có quan hệ với nhau.
Mỗi cặp đỉnh không quan hệ với nhau không lập thành một cung của graph. Đỉnh của graph biểu thị một nội dung hoặc một đối tượng nghiên cứu theo quy ước của chúng ta. Các đỉnh của graph có thể được ký hiệu bằng một chữ cái (A, B, C.), một dấu chấm, một hình chữ nhật, một hình vuông, hay một hình tròn, .Đỉnh được kí hiệu theo cách nào không quan trọng, không quyết định bản chất của graph. Các cung của graph: Là đường nối các đỉnh của graph, biểu thị mối quan hệ giữa các đỉnh trong graph.
Các cung của graph được thể hiện bằng những hình thức đa dạng: đoạn thẳng, đường gấp khúc, đường cong,. Cung có thể dài ngắn, to nhỏ, đậm nhạt khác nhau. Tuy nhiên việc thể hiện cung bằng hình thức nào hoàn toàn không ảnh hưởng đến nội dung của graph. Hình dạng của các cung không thể hiện mối liên hệ kiến thức nên người lập graph có thể chọn cho mình kiểu dáng cung graph phù hợp để có một graph vừa thể hiện được các đơn vị kiến thức, mối liên hệ giữa các kiến thức, vừa có hình thức đẹp sắc nét.
10 z Cách kí hiệu các đỉnh và cách biểu diễn các cung không làm thay đổi bản chất của graph.