MỤc lục mục lụC 1 MỞ ĐẦu lý do chọn đề tài

MỞ ĐẦU

Trong nền giáo dục hiện đại, đổi mới phương pháp dạy học là một nhiệm vụ hết sức quan trọng, cấp thiết nhằm nâng cao chất lượng giáo dục đào tạo và góp phần thực hiện công nghiệp hóa, hiện đại hóa đất nước. Theo đó, phương pháp dạy học phát huy tính tích cực, chủ động, sáng tạo của học sinh được đề cao hơn bao giờ hết. Việc áp dụng những phương pháp tiến bộ để bồi dưỡng, phát triển cho người học những phẩm chất tốt đẹp của người lao động mới, có năng lực, chủ động, sáng tạo, dám nghĩ, dám làm trong tương lai, đặc biệt là khả năng tư duy, sáng tạo là vô cùng cần thiết.

Tư duy của học sinh tiểu học đang trong giai đoạn “tư duy cụ thể”, chưa hoàn chỉnh. Vì vậy việc nhận thức các kiến thức toán học trừu tượng là vấn đề khó khăn đối với các em. Cho nên muốn phát triển tư duy thì trẻ cần có một công cụ trung gian như là một biểu tượng, một mô hình toán học cụ thể, trực quan để tường minh hóa và làm sáng rõ những giả thiết của vấn đề. Từ đó trẻ dễ dàng nắm được các giả thiết, xâu chuỗi các sự kiện và tìm hướng giải quyết thích hợp. Thực tế cho thấy việc áp dụng lý thuyết cây đồ thị vào trong lớp học là phương pháp khoa học vừa có tính khái quát cao vừa có tính ổn định vững chắc để mã hóa các mối quan hệ phức tạp giữa các đối tượng, giúp học sinh dễ dàng tri giác được vấn đề. Vận dụng cây đồ thị vào trong dạy học sẽ nâng cao được hiệu quả dạy học, thúc đẩy quá trình tự học, tự nghiên cứu của học sinh theo hướng tối ưu hóa đặc biệt nhằm rèn luyện năng lực hệ thống hóa kiến thức và năng lực sáng tạo của học sinh.

Hơn nữa trong dạy học toán ở tiểu học có một số bài học, một số bài toán mà việc sử dụng các phương pháp truyền thống là vô cùng phức tạp và khó hiểu đối với học sinh. Ngược lại, nhờ khả năng biểu diễn đồ thị bằng hình vẽ hiển hiện mà vấn đề trở nên rõ ràng, logic hơn, đồng thời người học tự mình giải quyết các bài toán một cách nhanh chóng, chính xác. Do đó 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ư graph là một giải pháp tốt.

Song trên thực tế hiện nay việc dạy – học toán bằng cây đồ thị chưa đạt được hiệu quả như mong muốn. Điều này chịu tác động của nhiều lý do. Song trở ngại lớn nhất là rất ít giáo viên sử dụng cây đồ thị để dạy học toán. Hay nói cách khác là người dạy chưa thực hiện tốt nhiệm vụ của mình. Tôi cho rằng dạy học theo sơ đồ là rất cần thiết trong việc nâng cao chất lượng giáo dục theo hướng đổi mới.

Xuất phát từ những lí do trên và nhằm để nâng cao chất lượng giảng dạy môn Toán trong trường tiểu học, tôi chọn đề tài “Dùng cây đồ thị trong dạy học toán tiểu học”.

Lý thuyết đồ thị là một lĩnh vực nghiên cứu của toán học đã có từ lâu nhưng lại có nhiều ứng dụng hiện đại. Những tư tưởng cơ bản của lý thuyết đồ thị được đưa ra từ thế kỷ XVIII bởi nhà toán học lỗi lạc người Thụy Sĩ Leonhard Euler. Ông là người đã dùng mô hình đồ thị để giải bài toán về những cây cầu nổi tiếng ở thành phố Konigsberg. Có thể coi đây là ứng dụng đầu tiên của lý thuyết đồ thị.

Năm 1852, Francis Guthrie đưa ra bài toán bốn màu về vấn đề: Liệu chỉ với bốn màu có thể tô màu một bản đồ bất kỳ sao cho không có 2 nước nào cùng biên giới được tô cùng màu. Bài toán này được xem như đã khai sinh ra lý thuyết đồ thị và nó chỉ được giải đáp sau một thế kỷ vào năm 1976 bởi Kenneth Appel và Wolfgang Haken. Trong khi cố gắng giải quyết bài toán này, các nhà toán học đã phát minh ra nhiều thuật ngữ và khái niệm nền tảng cho lý thuyết đồ thị. Từ đó lý thuyết đồ thị ngày càng khẳng định được vị trí quan trọng, trở thành công cụ đắc lực, hữu hiệu cho nhiều nghành khoa học khác nhau.

Cây là một khái niệm quan trọng và là một trường hợp riêng trong lý thuyết đồ thị. Khái niệm Cây đã được dùng từ năm 1857 khi nhà toán học người Anh tên là Arthur Cayley sử dụng chúng để xác định những dạng khác nhau của các hợp chất hóa học. Sau đó Cây được ứng dụng rộng rãi trong rất nhiều lĩnh vực khác nhau của cuộc sống.

Từ khi xuất hiện đến nay lý thuyết cây đồ thị và việc áp dụng lý thuyết đó vào nhiều ngành khoa học nói chung và vào việc dạy học nói riêng cũng đã được không ít người trong và ngoài nước quan tâm, nghiên cứu. Một số trong các công trình nghiên cứu đó là:

1. Claude Berge, Théorie des Graphes et ses aplications, Dunod, Paris 1967.

(Người dịch: Nguyễn Hữu Nguyên - Nguyễn Văn Vỵ, Lý thuyết đồ thị và ứng dụng, Nxb Khoa học và kỹ thuật, Hà Nội, 1971)

2. Đặng Huy Ruận, Lý thuyết đồ thị và ứng dụng, Nxb Khoa học và kỹ thuật, Hà Nội, 2000.

3. Đặng Huy Ruận, Bảy phương pháp giải các bài toán Logic, Nxb Khoa học và kỹ thuật, Hà Nội, 2002.

4. Hoàng Chúng, Graph và giải toán phổ thông, Nxb Giáo dục, 1997.

Mục đích chính của đề tài là:

- Nghiên cứu một số khái niệm cơ bản về lý thuyết cây đồ thị, từ đó đưa ra cách dạy – học toán sử dụng cây đồ thị. Cụ thể là xây dựng một số bài dạy về hình thành kiến thức mới, giải quyết các bài toán trong chương trình tiểu học. Đồng thời vận dụng vào việc sáng tác đề toán nhằm nâng cao chất lượng dạy và học môn toán ở tiểu học.

- Góp phần phát triển trí tưởng tượng, khả năng khái quát hóa, tự mình diễn tả được vấn đề cần giải quyết bằng ngôn ngữ trực quan cho học sinh tiểu học, kích thích sự sáng tạo, gây hứng thú học tập cho các em.

Đối tượng nghiên cứu của đề tài là:

- Cây đồ thị.

- Dạy học toán theo cách dùng cây đồ thị.

Với thời gian và điều kiện cho phép đề tài chỉ đề cập đến một số vấn đề về cây đồ thị, sau đó chọn một số nội dung, một số bài toán ở tiểu học và biên soạn bài dạy cho các nội dung đó theo cách dùng cây đồ thị.

Đề tài nhằm thực hiện những nhiệm vụ sau:

- Nghiên cứu các vấn đề về cây đồ thị.

- Biên soạn một số bài dạy có nội dung toán ở tiểu học theo hướng sử dụng cây đồ thị.

- Tìm hiểu một số bài toán ở tiểu học có thể giải theo phương pháp sử dụng cây đồ thị, sáng tác một số đề toán dựa vào cây đồ thị.

7. Phương pháp nghiên cứu

Để hoàn thành được đề tài này tôi đã sử dụng các phương pháp sau:

- Phương pháp nghiên cứu tài liệu: tìm tòi, thu thập, phân tích , tổng hợp và khái quát những nguồn tài liệu liên quan đến đề tài, làm cơ sở cho việc nghiên cứu. Tham khảo một số sách ở thư viện, nhà sách, tài liệu tìm được trên internet… Nghiên cứu để tìm hiểu về cây đồ thị, nội dung toán tiểu học dạy theo hướng sử dụng cây đồ thị.

- Phương pháp phỏng vấn: Trò chuyện, tham khảo ý kiến giáo viên hướng dẫn, một số giáo viên tiểu học và các em học sinh trong quá trình thực tập sư phạm 2, để thu thập thông tin liên quan nhằm hổ trợ cho việc nghiên cứu, tìm hiểu.

- Phương pháp quan sát: Xem một số giờ dạy của giáo viên tiểu học từ các băng hình, bài giảng trên internet.

Việc nghiên cứu xây dựng đề tài được tiến hành theo các bước cơ bản sau:

 Bước 1: Đọc kỹ và tìm hiểu đề tài.

 Bước 2: Hoàn thiện đề cương.

 Bước 3: Sưu tầm các loại sách và tài liệu có liên quan để tham khảo.

 Bước 4: Phỏng vấn.

 Bước 5: Tiến hành xây dựng đề tài cho đến hoàn chỉnh.

8. Cấu trúc đề tài

Đề tài gồm 3 phần: Mở đầu, Nội dung, Kết luận.

Ngoài phần Mở đầu và Kết luận toàn bộ nội dung của đề tài được chia thành 2 chương:

Chương 1: Cây đồ thị.

Chương 2: Cây đồ thị trong dạy học toán tiểu học.

NỘI DUNG





1.1. Đồ thị

1.1.1. Định nghĩa đồ thị

Một đồ thị (Graph) gồm có tập hợp X (≠ ) các đối tượng nào đấy và tập hợp E xác định các quan hệ giữa các phần tử trong X. Kí hiệu G = (X, E) hoặc G (X, E).

Mỗi phần tử của X được gọi là một đỉnh, tập X gọi là tập đỉnh.

Mỗi phần tử (cặp không sắp thứ tự) trong E gọi là một cạnh, còn E được gọi là tập cạnh của đồ thị G. Cạnh đặc biệt có hai đầu mút trùng nhau gọi là khuyên.

Đồ thị là một khái niệm trừu tượng chỉ các đối tượng và quan hệ giữa chúng. Ta có nhiều cách để biểu diễn một đồ thị, song để phục vụ cho mục đích của đề tài này ta có thể dùng cách biểu diễn trực quan nhất, đó là biểu diễn đồ thị bằng hình học.

Giả sử G = (X, E) là một đồ thị, khi đó ta biểu diễn đồ thị G bằng hình học như sau:

- Biểu diễn đỉnh: Ta cho ứng mỗi đỉnh trong X bởi một điểm (tùy ý) trong mặt phẳng hoặc trong không gian, thường lấy tên của đỉnh đặt làm tên cho điểm và khoanh điểm đó lại. Các điểm được phân bố ở các vị trí tùy theo cách của người sử dụng.

- Biểu diễn cạnh: Ta nối hai điểm là hai đầu mút của cạnh tương ứng bởi một đoạn thẳng hay một đoạn cong tùy thích.

Hoàn tất việc biểu diễn đỉnh và cạnh, hình nhận được từ cách biểu diễn trên được gọi là sơ đồ biểu diễn đồ thị G, đôi khi ta cũng gọi nó là đồ thị.

Cho đồ thị G. Bậc của đỉnh A là số cạnh có đầu mút tại A, với khuyên được tính 2 lần. Kí hiệu là m (A).

Nếu m (A) = k thì A được gọi là đỉnh bậc k.

Đỉnh chẵn là đỉnh có bậc là số chẵn. Đỉnh chẵn bậc 0 là đỉnh cô lập.

Đỉnh lẻ là đỉnh có bậc là số lẻ. Đỉnh lẻ bậc 1 là đỉnh treo.

Ví dụ 1.4. Bậc của các đỉnh trong đồ thị G = (X, E) với X = [x₁, x₂, x₃, x­₄, x₅, x₆, x₇] và E = [x₁ x₂, x₂ x₃, x₄ x₆, x₅ x₆, x₃ x₃, x₁ x₆, x₁ x₅] là:

m (x₁) = m (x₃) = m (x₆) = 3  x₁, x₃, x₆ gọi là đỉnh bậc 3.

m (x₂) = m (x₅) = 2  x₂, x₅ gọi là đỉnh bậc 2.

m (x₄) = 1  x₄ gọi là đỉnh treo.

m (x₇) = 0  x₇ gọi là đỉnh cô lập.


1.1.3.2. Tính chất về bậc

 Định lý: Trong một đồ thị G = (X, E) tổng số bậc của các đỉnh gấp hai lần số cạnh.

Gọi |X| là số đỉnh của đồ thị. Gọi |E| là số cạnh của đồ thị.

Vì tổng số bậc của các đỉnh của đồ thị bằng tổng số cạnh thuộc mỗi đỉnh, mà mỗi cạnh thuộc hai đỉnh, do đó: |X| = 2|E|

 Hệ quả: Trong một đồ thị G = (X, E) có hai đỉnh trở lên số đỉnh bậc lẻ là một số chẵn.

 Bài tập áp dụng tính chất về bậc

Hỏi bạn Bình đếm đúng hay sai? Vì sao?

Bạn Bình đếm sai bởi vì:

Ta lấy các điểm trong không gian tương ứng với những người tham dự hội nghị và lấy tên của những người đó để ghi tên các điểm tương ứng. Khi đó có 20 đại biểu tương ứng với 20 đỉnh. Các đại biểu bắt tay một số lần là một số đường cong bất kỳ để nối các đỉnh.

Cho nên theo cách đếm của bạn Bình sẽ có 4 đỉnh bậc 4, 7 đỉnh bậc 7, 8 đỉnh bậc 8. Áp dụng hệ quả ở trên ta suy ra bạn Bình đếm sai.

- Trong một đồ thị, cặp đỉnh x, y được gọi là hai đỉnh kề nhau nếu x ≠ y và là hai đầu mút của một cạnh.

- Hai cạnh a, b trong đồ thị G = (X, E) được gọi là kề nhau nếu a ≠ b và có chung đầu mút.

1.1.4.2. Khái niệm đường đi

Dãy α các đỉnh của đồ thị G = (X, E), α = [A­₁, A₂,…A_i, A_{i +1},…,A_{n - 1}, A_n] được gọi là một đường đi nếu với mọi i (1 ≤ i ≤ n – 1), cặp đỉnh A_i và A_{i +1} kề nhau.

A₁, A_n gọi là đỉnh đầu, đỉnh cuối của đường đi.

Ví dụ 1.6. Với đồ thị G cho ở hình sau ( hình H - 1.4) ta có đường đi đó là α = [GF, FD, DE, ED, DA, AC, CD].


1.1.4.3. Độ dài của đường đi

Tổng số vị trí của các cạnh xuất hiện trong đường đi α được gọi là độ dài của α và kí hiệu: |α|.

Đồ thị G được gọi là liên thông nếu mọi cặp đỉnh của nó đều có đường đi đến nhau.

Đường đi α trong đồ thị G được gọi là đường đi Euler nếu nó đi qua tất cả các cạnh của G và qua mỗi cạnh đúng một lần. Như vậy đồ thị G = (X, E) có đường đi Euler có nghĩa là ta có thể vẽ hình tương ứng của đồ thị chỉ bằng một nét.

Ta dễ dàng nhận thấy trong đồ thị G có đường đi Euler vì mọi đỉnh của G đều có bậc chẵn.

Đường đi Euler đó là α = [1, 2, 3, 4, 5, 6, 7, 2, 8, 6, 9, 7, 8, 5, 3, 1].

Đường đi này xuất phát ở đỉnh 1 và kết thúc ở đỉnh ấy.

Đường đi này xuất phát ở đỉnh lẻ x₁ và kết thúc ở đỉnh lẻ x₃.

- Nếu đồ thị G có mọi đỉnh đều là đỉnh chẵn thì khi tìm đường đi Euler ta cần xuất phát từ một đỉnh tùy ý và kết thúc tại đỉnh ấy.

- Nếu đồ thị G có đúng 2 đỉnh bậc lẻ thì khi tìm đường đi Euler ta cần xuất phát từ một trong 2 đỉnh bậc lẻ đi qua tất cả các cạnh và mỗi cạnh chỉ một lần rồi kết thúc tại đỉnh kia.

- Nếu đồ thị có số đỉnh lẻ là 0 thì xuất phát từ một điểm bất kỳ, đi qua tất cả các cạnh và mỗi cạnh chỉ đi qua một lần rồi quay về điểm xuất phát.

 Bài toán áp dụng đường đi Euler

Dạng 1: Bài toán tìm đường đi trong sơ đồ đã cho, sao cho phải đi qua hết tất cả các con đường (cái cầu, cánh cửa…) và qua mỗi con đường (cái cầu, cánh cửa…) đúng một lần. Thực chất của bài toán này là tìm đường đi Euler trong đồ thị đã cho.

Bài toán 1. ([10], trang 34)

Hình H – 1.10 là sơ đồ hệ thống các cây cầu nối liền giữa các miền đất. Anh (chị) hãy xem xét xem có thể dạo chơi qua các cây cầu và qua mỗi cây cầu đúng một lần được không? Hãy chỉ ra hành trình để thõa mãn yêu cầu bài toán (nếu có)?

Biểu diễn các miền đất A, B, C, D, E, F, G bởi các điểm A, B, C, D, E, F, G trong mặt phẳng và mỗi cây cầu nối hai miền đất được biểu diễn bởi một cạnh, khi đó ta có đồ thị G (hình H – 1.11)

Xét đồ thị G ta thấy: Trong đồ thị G có 2 đỉnh bậc lẻ là đỉnh C (bậc 3) và D (bậc 3). Do đó ta khẳng định đồ thị G có thể vẽ được bằng một nét (có đường đi Euler). Và để thực hiện được cách vẽ này ta phải xuất phát từ một trong hai đỉnh bậc lẻ C hoặc D và kết thúc ở đỉnh lẻ còn lại. Một trong các cách vẽ một nét là: [C, D, B, A, E, C, B, E, F, G, D].

Từ kết luận vừa nêu ta khẳng định: Có thể dạo chơi qua tất cả các cây cầu có trong hình H – 1.10 và qua mỗi cây cầu đúng một lần. Hơn nữa hành trình để thỏa mãn yêu cầu bài toán là: [CDBAECBEF G D]

Bài toán 2. ([10, trang 75)

Hình H - 1.12 là sơ đồ mặt bằng của một khu triển lãm với các phòng trưng bày và các cửa đi. Liệu có thể đi liên tục qua tất cả các cửa đi và mỗi cửa đúng một lần không? Hãy chỉ dẫn đường đi thỏa mãn điều kiện bài toán nếu có thể?

Thực chất bài toán này là tìm đường đi Euler của một đồ thị với các đỉnh là các tâm của phòng trưng bày và một điểm ở ngoài sân của khu triển lãm, còn các cạnh là các đường nối từ ngoài sân vào các phòng và đường nối giữa các phòng với nhau. Dễ dàng nhận thấy đồ thị có đúng 2 đỉnh bậc lẻ, do đó đồ thị có đường đi Euler. Từ đó suy ra cách đi thỏa mãn yêu cầu của bài toán (xem hình H – 1.13).

654211087643210986111312111413

Cây là một đồ thị có n đỉnh (n ≥ 2), n – 1 cạnh và trong đó luôn có đường đi nối 2 đỉnh bất kỳ.

Khái niệm quan trọng này do Cayley đưa ra. Sau này người ta gọi cây đồ thị là sơ đồ cây.

Trong một cây ta luôn xác định được gốc của nó.

Độ cao của cây được xác định bằng quy nạp: Những cạnh xuất phát từ gốc được gọi là cạnh hạng 1. Những cạnh kề với ít nhất một cạnh hạng 1 được gọi là cạnh hạng 2. Giả sử đã xác định đến cạnh hạng k thì khi đó cạnh kề với ít nhất một cạnh hạng k được coi là cạnh hạng k + 1.

Ví dụ 1.12. Đồ thị G cho ở hình H – 1.15 là một cây. Đồ thị G cho ở hình 1.16 không phải là cây.

 Định lý: Một cây có ít nhất hai đỉnh treo.

Giả sử ngược lại, đồ thị G = (X, E) là một cây không quá một đỉnh treo. Gọi P là đỉnh treo của G = (X, E), nếu G = (X, E) không có đỉnh treo thì ta chọn P tùy ý. Xuất phát từ P ta đi dọc theo các cạnh, sao cho mỗi cạnh chỉ đi đúng một lần. Vì đồ thị G = (X, E) là một cây không có đường đi mà có đỉnh đầu trùng với đỉnh cuối, nên ta không đi tới đỉnh nào đã đi qua. Do có hữu hạn đỉnh, nên quá trình phải kết thúc tại Q ≠ P nào đó, và Q rõ ràng có bậc 1. Điều này dẫn đến mâu thuẫn với G = (X, E) không có hoặc chỉ có một đỉnh treo. Vậy G = (X, E) có ít nhất hai đỉnh treo.

Đồ thị không liên thông mà là hợp của các cây được gọi là rừng.

 Tiểu kết chương 1

Chương 1 trình bày ngắn gọn một số khái niệm và tính chất cơ bản về lý thuyết cây đồ thị (không chứng minh). Trong đó đề tài nhấn mạnh phần đường đi của đồ thị vì đây là nội dung cần quan tâm nhất trong cây đồ thị. Các nội dung của chương này được chọn lọc, sắp xếp chặt chẽ, dễ hiểu, phù hợp với mục đích làm nổi bật ưu thế của cây đồ thị trong việc giải quyết các bài toán rắc rối, liên quan đến một tập đối tượng và những mối liên hệ giữa chúng bằng phương pháp hiệu quả. Đồng thời trên cơ sở lý thuyết đã được đưa ra đó sẽ là cầu nối quan trọng để áp dụng lý thuyết cây đồ thị một cách thiết thực và hiệu quả vào quá trình dạy học toán ở tiểu học.

Vậy để biết được việc vận dụng cây đồ thị vào trong dạy học toán tiểu học như thế nào thì chúng ta cùng tìm hiểu qua chương 2.

Lý thuyết cây đồ thị đang phát triển nhanh chóng và ngày càng tìm thấy những ứng dụng hoàn toàn mới mẻ, thiết thực. Để nghiên cứu toàn bộ các tính chất cơ bản của cây và các ứng dụng đã làm được thì đó là cả một khối lượng lớn kiến thức. Cho nên trong khuôn khổ của đề tài này không thể nào liệt kê và chuyển tải hết những nội dung đó. Như đã trình bày ở phần mở đầu, mục đích chính của đề tài là nghiên cứu về cây đồ thị, sau đó vận dụng để xây dựng một số bài dạy về hình thành kiến thức, giải các bài toán trong chương trình tiểu học và sáng tác đề toán. Vì thế trong chương này chỉ tập trung đề cập tới những ứng dụng của cây trong dạy học toán tiểu học.