Rèn luyện kỹ năng vận dụng lý thuyết đồ thị vào giải toán cho học sinh chuyên tin

iệm vụ nghiên cứu 2 IV. Giả thuyết khoa học 2 V. Phƣơng pháp nghiên cứu 3 1. Nghiên cứu lý luận 3 2. Thực nghiệm sƣ phạm 3 CẤU TRÚC LUẬN VĂN 4 Chƣơng 1: NHỮNG NỘI DUNG CƠ BẢN CỦA LÝ THUYẾT ĐỒ THỊ TRONG CHƢƠNG TRÌNH ĐÀO TẠO CHO HỌC SINH CHUYÊN TIN 5 1.1 Phƣơng pháp dạy học phát hiện và giải quyết vấn đề 5 1.1.1 Cơ sở lý luận 5 1.1.1.1 Cơ sở triết học 5 1.1.1.2 Cơ sở tâm lý học 5 1.1.1.3 Cơ sở giáo dục học 6 1.1.2 Những khái niệm cơ bản 6 1.1.2.1 Vấn đề 6 1.1.2.2 Tình huống gợi vấn đề 7 1.1.2.3 Đặc điểm của dạy học phát hiện và giải quyết vấn đề 8 1.1.3 Thực hiện dạy học phát hiện và giải quyết vấn đề 9 1.2 Dạy học giải bài tập toán 10 1.2.1 Vai trò của bài tập trong quá trình dạy học 10 1.2.2 Các yêu cầu đối với lời giải 12 1.2.3 Phƣơng pháp chung để giải bài toán 13 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1.3 Thực trạng dạy học giải bài tập ở trƣờng THPT 15 1.3.1 Thực trạng 15 1.3.2 Nguyên nhân 16 1.4 Những nội dung cơ bản của lý thuyết đồ thị 17 1.4.1. Khái niệm đồ thị (trong tin học) 17 1.4.2. Các đơn đồ thị đặc biệt 20 1.4.3. Tính liên thông của đồ thị 22 1.4.4 Đồ thị Euler và đồ thị Hamilton 23 1.4.5.Cây 24 1.4.5.1 Định nghĩa và các tính chất cơ bản 24 1.4.5.2. Cây khung 25 1.4.5.3. Bài toán tìm cây khung nhỏ nhất 26 1.4.5.4. Cây có gốc 27 1.4.6 Đồ thị phẳng và tô màu đồ thị 28 1.4.6.1 Bài toán mở đầu 28 1.4.6.2. Đồ thị phẳng 28 1.4.6.3 Tô màu đồ thị 29 1.4.6.3.1. Định nghĩa 30 1.4.6.3.2. Một số định lý 31 Kết luận chương 1: 32 Chƣơng 2 KHAI THÁC LÝ THUYẾT ĐỒ THỊ VÀO GIẢI BÀI TẬP TOÁN 33 2.1.Quy trình chuyển đổi từ bài toán thông thƣờng sang ngôn ngữ lý thuyết đồ thị 33 2.1.1 Một số bài toán tiềm ẩn các yếu tố của lý thuyết đồ thị 33 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2.1.2. Quy trình chuyển đổi từ bài toán thông thƣờng sang ngôn ngữ lý thuyết đồ thị 34 2.1.2.1. Dấu hiệu chung 35 2.1.2.2 Dấu hiệu nhận dạng bài tập có thể sử dụng đồ thị có hƣớng 38 2.1.2.3 Dấu hiệu nhận dạng bài tập có thể sử dụng đồ thị màu 41 2.2. Các phƣơng án vận dụng lý thuyết đồ thị trong dạy học giải bài tập 43 2.2.1 Vai trò và định hƣớng của dạy học giải bài tập 43 2.2.2 Quy trình Polya trong giải bài tập 43 2.2.3 Phƣơng án 1 (khai thác lý thuyết đồ thị ở bƣớc 1) 44 2.2.4 Phƣơng án 2 (khai thác lý thuyết đồ thị ở bƣớc 2) 46 2.2.5 Phƣơng án 3 (khai thác lý thuyết đồ thị ở bƣớc 4) 48 2.3. Các biện pháp nhằm góp phần rèn luyện khả năng vận dụng lý thuyết đồ thị vào giải toán cho học sinh THPT chuyên Tin 55 2.3.1 Hệ thống hóa một số yếu tố trong lý thuyết đồ thị 55 2.3.2 Xây dựng một hệ thống bài tập từ dễ đến khó để học sinh tiếp cận từng bƣớc với việc vận dụng lý thuyết đồ thị vào giải toán 58 2.3.2.1 Một số bài toán liên quan đến bậc và cạnh của đồ thị 58 2.3.2.2 Một số bài toán liên quan đến đồ thị có hƣớng 61 2.3.2.3 Một số bài toán liên quan đến đồ thị màu 63 2.3.2.4 Một số bài toán liên quan đến đƣờng đi 65 2.3.2.5 Bài toán về cây 67 2.3.2.6 Bài toán liên quan đến đồ thị phẳng 68 2.3.2.7 Một số bài tập về cạnh, đỉnh, bậc và một số kiến thức có liên quan 70 Chƣơng III Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên THỰC NGHIỆM SƢ PHẠM 77 3.1. Mục đích, nhiệm vụ, nguyên tắc, nội dung thực nghiệm 3.1.1. Mục đích thực nghiệm 77 3.1.2. Nhiệm vụ thực nghiệm 77 3.1.3. Nguyên tắc thực nghiệm 77 3.1.4. Nội dung thực nghiệm 77 3.1.5. Đối tƣợng thực nghiệm 77 3.2. Hình thức và kế hoạch tiến hành thực nghiệm 78 3.2.1 Hình thức 78 3.2.2. Kế hoạch tiến hành thực nghiệm 78 3.3. Đánh giá kết quả thực nghiệm 79 3.3.1. Về nội dung tài liệu thực nghiệm 79 3.3.2. Về phƣơng pháp tiến hành kiểm tra 79 3.3.3. Về kết quả kiểm tra thực nghiệm 79 3.4. Kết luận chung về thực nghiệm sƣ phạm 82 MỘT SỐ ĐỀ BÀI TẬP 84 KẾT LUẬN ĐỀ TÀI 88 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên BẢNG CÁC KÝ HIỆU VIẾT TẮT GV: Giáo viên LTĐT: Lý thuyết đồ thị THPT: Trung học phổ thông SGK: Sách giáo khoa Đ thẳng: Đƣờng thẳng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên TÀI LIỆU THAM KHẢO [1] Hoàng Chúng (1992), Graph và giải toán phổ thông, Nhà xuất bản giáo dục, Hà Nội. [2] Nguyễn Bá Kim (2007), Phương pháp dạy học môn toán, Nhà xuất bản Đại học Sƣ phạm, Hà Nội. [3] Nguyễn Văn Mậu (2007), Toán rời rạc và một số vấn đề liên quan, Đại học Khoa học tự nhiên, Hà Nội. [4] Nguyễn Hữu Ngự (2001), Lý thuyết đồ thị, Nhà xuất bản Đại học Quốc Gia Hà Nội. [5] Đặng Huy Ruận (2004), Lý thuyết đồ thị và ứng dụng, Nhà xuất bản Khoa học và Kỹ thuật Hà Nội. [6] Các đề thi vô địch toán 19 nƣớc trong đó có Việt Nam (Tập 2), Nhà xuất bản trẻ. [7] Tuyển tập 30 năm tạp trí toán học và tuổi trẻ (2000), Nhà xuất bản giáo dục. SGK và tài liệu tham khảo môn toán chƣơng trình phổ thông. [8] Claude Berge (1967), Théorie des Graphes et ses applicacations, Dunod Paris. Nguyễn Hữu Nguyên và Nguyễn Văn Vỵ dịch (1971): Lý thuyết đồ thị và ứng dụng, NXB Khoa học kỹ thuật, Hà Nội. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1 MỞ ĐẦU I. Lý do chọn đề tài: - Đổi mới phương pháp dạy học là một nhiệm vụ quan trọng của ngành giáo dục nhằm nâng cao chất lượng đào tạo, góp phần thực hiện công nghiệp hoá hiện đại hóa đất nước. - Lý thuyết đồ thị 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ý 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ác mối quan hệ của các đối tượng được nghiên cứu. - Vận dụng lý thuyết đồ thị trong dạy học để mô hình hóa các mối quan hệ chuyển thành phương pháp dạy học đặc thù 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. - Trong chương trình học tập học sinh chuyên Tin ở trường THPT được trang bị các kiến thức về lý thuyết đồ thị để nhằm phục vụ cho việc lập trình giải toán, do đó có thể khai thác tri thức về lý thuyết đồ thị vào quá trình dạy học môn toán. - Trong dạy học toán thì giải bài tập đóng vai trò quan trọng. Bởi điều căn bản là bài tập toán có vai trò giá mang hoạt động của học sinh. Thông qua giải bài tập, học sinh phải thực hiện những hoạt động nhất định bao gồm cả nhận dạng và thể hiện định nghĩa, định lý, quy tắc hay phương pháp, những hoạt động toán học phức hợp, những hoạt động trí tuệ phổ biến trong toán học, những hoạt động trí tuệ chung và những hoạt động ngôn ngữ. Vai trò của bài tập toán được thể hiện trên cả 3 phương diện: mục tiêu, nội dung và phương pháp dạy học. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2 - Việc cung cấp thêm một phương pháp giải bài tập cho học sinh chuyên Tin là một nhu cầu cần thiết. Mặt khác việc vận dụng lý thuyết đồ thị vào giải toán giúp ta đạt được hai mục tiêu: 1. Giải được một lớp bài tập. 2. Hỗ trợ cho việc lập trình. - Hiện nay việc nghiên cứu khai thác một số yếu tố của lý thuyết đồ thị vào giải toán cũng được một số tác giả quan tâm nhưng chưa có những công bố có tính chất hệ thống, xuất phát từ những lý do trên chúng tôi lựa chọn đề tài: “Khai thác lý thuyết đồ thị trong dạy học toán ở trƣờng THPT Chuyên”. II. Mục đích nghiên cứu Chỉ ra hướng vận dụng lý thuyết đồ thị vào giải toán và tìm ra các biện pháp để giúp học sinh chuyên Tin trung học phổ thông hình thành và phát triển năng lực vận dụng lý thuyết đồ thị vào giải bài tập toán. III. Nhiệm vụ nghiên cứu - Tìm hiểu những nội dung cơ bản của lý thuyết đồ thị được trang bị cho học sinh chuyên Tin. - Chỉ ra hệ thống bài tập trong chương trình toán có thể vận dụng lý thuyết đồ thị để giải. - Chỉ ra được những dấu hiệu cụ thể để nhận dạng “Bài toán” có thể khai thác lý thuyết đồ thị trong quá trình giải bài toán. - Chỉ ra các phương án vận dụng lý thuyết đồ thị vào giải toán. - Kiểm tra hiệu quả của các biện pháp, phương án lý thuyết đồ thị vào giải toán trong thực tế. IV. Giả thuyết khoa học Nếu ta có các phương pháp giúp học sinh chuyên Tin trung học phổ thông vận dụng kiến thức về lý thuyết đồ thị vào giải toán thì sẽ giúp học sinh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 3 giải quyết được một số lớp bài toán góp phần nâng cao chất lượng dạy học giải bài tập nói riêng dạy học toán nói chung cho học sinh chuyên Tin. V. Phƣơng pháp nghiên cứu 1. Nghiên cứu lý luận - Nghiên cứu các văn bản, tài liệu chỉ đạo của Bộ GD & ĐT liên quan đến đổi mới phương pháp dạy học, đổi mới ra đề kiểm tra, danh mục thiết bị dạy học toán. - SGK, phân phối chương trình, sách GV, chuẩn của bộ môn toán ở trung học phổ thông, sách nâng cao, sách chuyên đề. - Các tài liệu về lý thuyết đồ thị và những ứng dụng của nó trong thực tiễn cuộc sống và trong dạy học. - Các công trình nghiên cứu các vấn đề liên quan trực tiếp đến phương pháp đồ thị. 2. Thực nghiệm sƣ phạm - Chỉ ra cho học sinh các dấu hiệu "nhận dạng" và cách thức vận dụng lý thuyết đồ thị vào giải bài tập toán. - Biên soạn hệ thống bài tập luyện tập cho học sinh và một số đề bài kiểm tra để đánh giá khả năng vận dụng lý thuyết đồ thị vào giải toán. - Tiến hành thực nghiệm và đánh giá kết quả thực nghiệm. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 4 CẤU TRÚC LUẬN VĂN Mở đầu Chƣơng 1: Những nội dung cơ bản của lý thuyết đồ thị trong chương trình đào tạo cho học sinh chuyên Chƣơng 2: Khai thác lý thuyết đồ thị vào giải bài tập toán Chƣơng 3: Thực nghiệm sư phạm Kết luận Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 5 Chƣơng 1 NHỮNG NỘI DUNG CƠ BẢN CỦA LÝ THUYẾT ĐỒ THỊ TRONG CHƢƠNG TRÌNH ĐÀO TẠO CHO HỌC SINH CHUYÊN TIN Trong hệ thống các trường Chuyên thì thời gian gần đây các lớp chuyên Tin phát triển khá mạnh. Học sinh chuyên Tin được trang bị các kiến thức về toán rời rạc, lý thuyết đồ thị, tối ưu hoá… nhằm tạo nền tảng cho học sinh nắm được các thuật toán, vận dụng vào lập trình và giải bài tập toán. Để giúp học sinh chuyên tin có thể tiếp cận được với một phương pháp giải bài tập mới đó là áp dụng lý thuyết đồ thị vào giải bài tập toán, giáo viên có thể sử dụng nhiều phương pháp dạy học khác nhau. Ở đây chúng tôi lựa chọn phương pháp phát hiện và giải quyết vấn đề kết hợp sử dụng hình vẽ trực quan. 1.1 Phƣơng pháp dạy học phát hiện và giải quyết vấn đề 1.1.1 Cơ sở lý luận 1.1.1.1 Cơ sở triết học Theo triết học duy vật biện chứng, mâu thuẫn là động lực thúc đẩy quá trình phát triển. Một vấn đề được gợi ra cho học sinh học tập chính là một mâu thuẫn giữa yêu cầu nhiệm vụ nhận thức với tri thức và kinh nghiệm sẵn có. Tình huống này phản ánh một cách lôgic và biện chứng quan hệ bên trong giữa tri thức cũ, kỹ năng cũ và kinh nghiệm cũ đối với yêu cầu giải thích sự kiện mới hoặc đổi mới tình thế. 1.1.1.2 Cơ sở tâm lý học Theo các nhà tâm lý học, con người chỉ bắt đầu tư duy tích cực khi nảy sinh nhu cầu tư duy, tức là khi đứng trước một khó khăn về nhận thức cần phải khắc phục, một tình huống gợi vấn đề. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 6 Theo tâm lý học kiến tạo, học tập chủ yếu là một quá trình trong đó người học xây dựng tri thức cho mình bằng cách liên hệ những cảm nghiệm mới với những tri thức đã có. Dạy học phát hiện và giải quyết vấn đề phù hợp với quan điểm này. 1.1.1.3 Cơ sở giáo dục học Dạy học phát hiện và giải quyết vấn đề phù hợp với nguyên tắc tính tự giác và tích cực, vì nó khêu gợi được hoạt động học tập mà chủ thể được hướng đích, gợi động cơ trong quá trình phát hiện và giải quyết vấn đề. Dạy học phát hiện và giải quyết vấn đề cũng biểu hiện sự thống nhất giữa kiến tạo tri thức, phát triển năng lực trí tuệ và bồi dưỡng phẩm chất. Những tri thức mới (đối với học sinh) được kiến tạo nhờ quá trình phát hiện và giải quyết vấn đề. Tác dụng phát triển năng lực trí tuệ của kiểu dạy học này là ở chỗ học sinh học được cách khám phá, tức là rèn luyện cho họ cách thức phát hiện tiếp cận và giải quyết vấn đề một cách khoa học. Đồng thời, dạy học phát hiện và giải quyết vấn đề cũng góp phần bồi dưỡng cho người học những đức tính cần thiết của người lao động sáng tạo như tính chủ động, tích cực, tính kiên trì vượt khó, tính kế hoạch và thói quen tự kiểm tra... 1.1.2 Những khái niệm cơ bản 1.1.2.1 Vấn đề Để hiểu đúng thế nào là một vấn đề và đồng thời làm rõ một vài khái niệm khác có liên quan, ta bắt đầu từ khái niệm hệ thống. Hệ thống được hiểu là một tập hợp những phần tử cùng với những quan hệ giữa những phần tử của tập hợp đó. Một tình huống được hiểu là một hệ thống phức tạp gồm chủ thể và khách thể, trong đó chủ thể có thể là người, còn khách thể lại là một hệ thống nào đó. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 7 Nếu trong một tình huống, chủ thể còn chưa biết ít nhất một phần tử của khách thể thì tình huống này được gọi là một tình huống bài toán đối với chủ thể. Trong một tình huống bài toán, nếu trước chủ thể đặt ra mục tiêu tìm phần tử chưa biết nào đó dựa vào một số những phần tử cho trước ở trong khách thể thì ta có một bài toán. Một bài toán được gọi là vấn đề nếu chủ thể chưa biết một thuật giải nào có thể áp dụng để tìm ra phần tử chưa biết. 1.1.2.2 Tình huống gợi vấn đề Tình huống gợi vấn đề, còn gọi là tình huống vấn đề, là một tình huống gợi ra cho học sinh những khó khăn về lý luận hay thực tiễn mà họ thấy cần thiết và có khả năng vượt qua, nhưng không phải ngay tức khắc nhờ một thuật giải mà phải trải qua một quá trình tích cực suy nghĩ, hoạt động để biến đổi đối tượng hoạt động hoặc điều chỉnh kiến thức sẵn có. Như vậy tình huống gợi vấn đề là một tình huống thoả mãn các điều kiện sau: + Tồn tại một vấn đề: Tình huống phải bộc lộ mâu thuẫn giữa thực tiễn với trình độ nhận thức, chủ thể phải ý thức được một khó khăn trong tư duy hoặc hành động mà vốn hiểu biết sẵn có chưa đủ để vượt qua. Nói cách khác, có ít nhất một phần tử của khách thể mà học sinh chưa biết và cũng chưa có trong tay một thuật giải để tìm phần tử đó. + Gợi nhu cầu nhận thức: Nếu tình huống có một vấn đề nhưng vì lý do nào đó học sinh không thấy có nhu cầu tìm hiểu, giải quyết, chẳng hạn họ thấy vấn đề xa lạ, không liên quan gì tới mình thì đó cũng chưa phải là một tình huống gợi vấn đề. Điều quan trọng là tình huống phải gợi nhu cầu nhận thức, chẳng hạn phải làm bộc lộ sự khiếm khuyết về kiến thức và kỹ năng của Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 8 học sinh để họ cảm thấy cần thiết phải bổ sung, điều chỉnh, hoàn thiện tri thức, kỹ năng bằng cách tham gia giải quyết vấn đề nảy sinh. + Khơi dậy niềm tin ở khả năng bản thân: Nếu một tình huống tuy có vấn đề và học sinh tuy có nhu cầu giải quyết vấn đề, nhưng nếu họ cảm thấy vấn đề vượt quá so với khả năng của mình thì họ cũng không sẵn sàng tham gia giải quyết vấn đề. Tình huống cần khơi dậy ở học sinh cảm nghĩ là tuy họ chưa có ngay lời giải, nhưng đã có một số tri thức, kỹ năng liên quan đến vấn đề đặt ra và nếu họ tích cực suy nghĩ thì có nhiều hy vọng giải quyết dược vấn đề đó. Như vậy là học sinh có được niềm tin ở khả năng huy động tri thức và kỹ năng sẵn có để giải quyết hoặc tham gia giải quyết vấn đề. 1.1.2.3 Đặc điểm của dạy học phát hiện và giải quyết vấn đề Trong dạy học phát hiện và giải quyết vấn đề, thầy giáo tạo ra những tình huống gợi vấn đề, điều khiển học sinh phát hiện vấn đề, hoạt động tự giác, tích cực, chủ động, sáng tạo để giải quyết vấn đề, thông qua đó mà kiến tạo tri thức, rèn luyện kỹ năng và đạt được những mục tiêu học tập khác. Dạy học phát hiện và giải quyết vấn đề có những đặc điểm sau: + Học sinh được đặt vào một tình huống gợi vấn đề chứ không phải là được thông báo tri thức dưới dạng có sẵn. + Học sinh hoạt động tự giác, tích cực, chủ động, sáng tạo, tận lực huy động tri thức và khả năng của mình để phát hiện và giải quyết vấn đề chứ không phải chỉ nghe thầy giảng một cách thụ động. + Mục tiêu dạy học không phải chỉ là làm cho học sinh lĩnh hội kết quả của quá trình phát hiện và giải quyết vấn đề, mà còn ở chỗ làm cho họ phát triển khả năng tiến hành những quá trình như vậy. Nói cách khác, học sinh được học bản thân việc học. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 9 1.1.3 Thực hiện dạy học phát hiện và giải quyết vấn đề Hạt nhân của cách dạy học phát hiện và giải quyết vấn đề là việc điều khiển học sinh tự thực hiện hoặc hoà nhập vào quá trình nghiên cứu vấn đề. Quá trình này có thể chia thành các bước dưới đây, trong đó bước nào, khâu nào do học trò tự làm hoặc có sự gợi ý của thầy hoặc chỉ theo dõi thầy trình bày là tuỳ thuộc sự lựa chọn một cấp độ thích hợp. Bước 1: Phát hiện hoặc thâm nhập vấn đề. - Phát hiện vấn đề từ một tình huống gợi vấn đề thường là do thầy tạo ra. Có thể liên tưởng những cách suy nghĩ tìm tòi, dự đoán. - Giải thích và chính xác hoá tình huống (khi cần thiết) để hiểu đúng vấn đề được đặt ra. - Phát biểu vấn đề và đặt mục tiêu giải quyết vấn đề đó. Bước 2: Tìm giải pháp. - Tìm một cách giải quyết vấn đề. - Sau khi đã tìm ra một giải pháp, có thể tiếp tục tìm thêm những giải pháp khác, so sánh chúng với nhau để tìm ra giải pháp hợp lý nhất. Bước 3: Trình bày giải pháp. Khi đã giải quyết được vấn đề đặt ra, người học trình bày lại toàn bộ từ việc phát biểu vấn đề cho tới giải pháp. Nếu vấn đề là một đề bài cho sẵn thì có thể không cần phát biểu lại vấn đề. Trong khi trình bày, cần tuân thủ các chuẩn mực đề ra trong nhà trường như ghi rõ giả thiết, kết luận đối với bài toán chứng minh, phân biệt các phần: phân tích, cách dựng, chứng minh, biện luận đối với bài toán dựng hình, giữ gìn vở sạch chữ đẹp... Bước 4: Nghiên cứu sâu giải pháp - Tìm hiểu những khả năng ứng dụng kết quả. - Đề xuất những vấn đề mới có liên quan nhờ xét tương tự, khái quát hoá, lật ngược vấn đề... và giải quyết nếu có thể. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 10 Như vậy giáo viên có thể sử dụng phương pháp phát hiện và giải quyết vấn đề vào việc dạy cho học sinh một phương pháp giải bài tập toán đó là áp dụng lý thuyết đồ thị. Giáo viên bám sát vào bốn bước của phương pháp dạy học đã nêu ở trên. Cụ thể: + Đứng trước một bài toán vấn đề đặt ra là liệu có thể chuyển đổi hay sử dụng lý thuyết đồ thị để giải hay không? Đây chính là bước phát hiện và thâm nhập vấn đề (bước1). + Khi xác định được bài toán có thể áp dụng lý thuyết đồ thị để giải ta tiếp tục tìm kiến thức nào có liên quan trong lý thuyết đồ thị sẽ áp dụng để giải hay đây chính là đi tìm giải pháp (bước 2). + Trình bày lời giải (bước 3) + Nghiên cứu sâu lời giải. Xét xem liệu rằng bài toán có thể khái quát hoá được không và có thể xét một lớp bài toán tương tự hay không... Như vậy có thể thấy phương pháp dạy học lựa chọn là phù hợp. 1.2 Dạy học giải bài tập toán 1.2.1 Vai trò của bài tập trong quá trình dạy học Ở trường phổ thông, dạy toán là dạy hoạt động toán học. Đối với học sinh có thể xem việc giải toán là hình thức chủ yếu của hoạt động toán học. Trong dạy học toán, mỗi bài tập toán học được sử dụng với những dụng ý khác nhau, có thể dùng để tạo tiền đề xuất phát, để gợi động cơ, để làm việc với nội dung mới, để củng cố hoặc kiểm tra,... Ở thời điểm cụ thể nào đó mỗi bài tập chứa đựng tường minh hay ẩn tàng những chức năng khác nhau (chức năng dạy học, chức năng giáo dục, chức năng phát triển, chức năng kiểm tra), những chức năng này đều hướng tới việc thực hiện các mục đích dạy học. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 11 Tuy nhiên trên thực tế các chức năng này không bộc lộ một cách riêng lẻ và tách rời nhau, khi nói đến chức năng này hay chức năng khác của một bài tập cụ thể tức là có ý nói chức năng ấy được thực hiện một cách tường minh, công khai. Bài tập toán học có vai trò quan trọng trong môn toán. Điều căn bản là bài tập có vai trò giá mang hoạt động của học sinh. Thông qua giải bài tập, học sinh phải thực hiện những hoạt động nhất định bao gồm cả nhận dạng và thể hiện định nghĩa, định lý, quy tắc hay phương pháp, những hoạt động toán học phức hợp, những hoạt động trí tuệ phổ biến trong toán học, những hoạt động trí tuệ chung và những hoạt động ngôn ngữ. Hoạt động của học sinh liên hệ mật thiết với mục tiêu, nội dung và phương pháp dạy học, vì vậy vai trò của bài tập toán học được thể hiện cả trên 3 bình diện này. Trên bình diện mục tiêu dạy học, bài tập toán học ở trường phổ thông là giá mang những hoạt động mà việc thực hiện các hoạt động đó thể hiện mức độ đạt mục tiêu. Mặt khác, những bài tập cũng thể hiện những chức năng khác nhau hướng đến việc thực hiện các mục tiêu dạy học môn toán, cụ thể là: + Hình thành, củng cố tri thức, kỹ năng, kỹ xảo ở những khâu khác nhau của quá trình dạy học, kể cả kỹ năng ứng dụng toán học vào thực tiễn. + Phát triển năng lực trí tuệ: rèn luyện những hoạt động tư duy hình thành những phẩm chất trí tuệ. +Bồi dưỡng thế giới quan duy vật biện chứng, hình thành những phẩm chất đạo đức của người lao động. Trên bình diện nội dung dạy học, những bài tập toán học là giá mang hoạt động liên hệ với những nội dung nhất định, một phương tiện cài đặt nội dung để hoàn chỉnh hay bổ sung cho những tri thức nào đó đã được trình bày trong phần lý thuyết. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 12 Trên bình diện phương pháp dạy học, bài tập toán học là giá mang hoạt động để người học kiến tạo những tri thức nhất định và trên cơ sở đó thực hiện các mục tiêu dạy học khác. Khai thác tốt những bài tập như vậy sẽ góp phần tổ chức cho học sinh học tập trong hoạt động và bằng hoạt động tự giác, tích cực, chủ động và sáng tạo được thực hiện độc lập hoặc trong giao lưu. Trong thực tiễn dạy học, bài tập được sử dụng với những dụng ý khác nhau về phương pháp dạy học: Đảm bảo trình độ xuất phát, gợi động cơ, làm việc với nội dung mới, củng cố hoặc kiểm tra…Đặc biệt là về mặt kiểm tra, bài tập là phương tiện để đánh giá mức độ, kết quả dạy và học, khả năng làm việc độc lập và trình độ phát triển của học sinh,... Một bài tập cụ thể có thể nhằm vào một hay nhiều dụng ý trên. 1.2.2 Các yêu cầu đối với lời giải Để phát huy tác dụng của bài tập toán học, trước hết cần nắm vững các yêu cầu của lời giải. Nói một cách vắn tắt, lời giải phải đúng và tốt. Nói như vậy là bao hàm đủ các ý cần thiết, nhưng quá cô đọng. Để thuận tiện cho việc thực hiện các yêu cầu của lời giải trong quá trình dạy học và đánh giá học sinh, có thể cụ thể hoá các yêu cầu, đương nhiên phải chấp nhận những yếu tố trùng lặp nhất định trong các yêu cầu chi tiết: + Kết quả đúng, kể cả ở các bước chung gian. Kết quả cuối cùng phải là một đáp số đúng, một biểu thức, một hàm số, một hình vẽ,... thoã mãn các yêu cầu đề ra. Kết quả các bước chung gian cũng phải đúng. Như vậy, lời giải không thể chứa những sai lầm tính toán, vẽ hình, biến đổi biểu thức,… + Lập luận chặt chẽ, đặc biệt là lời giải phải tuân thủ các yêu cầu sau: Luận đề phải nhất quán, luận cứ phải đúng, luận chứng phải hợp logic. + Lời giải đầy đủ. Yêu cầu này có nghĩa là lời giải không được bỏ sót một trường hợp, một chi tiết cần thiết nào. Cụ thể là giải phương trình không Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 13 được thiếu nghiệm, phân chia trường hợp không được thiếu một khả năng nào... + Ngôn ngữ chính xác. Đây là một yêu cầu về giáo dục tiếng mẹ đẻ đặt ra cho tất cả các bộ môn. Việc dạy học môn toán cũng phải tuân thủ yêu cầu này. + Trình bày rõ ràng, đảm bảo mỹ thuật. Yêu cầu này đặt ra đối với cả lời văn, chữ viết, hình vẽ, cách sắp xếp các yếu tố (chữ, số, hình, ký hiệu...) trong lời giải. + Tìm ra nhiều cách giải, chọn cách giải ngắn gọn, hợp lý nhất. + Nghiên cứu giải những bài toán tương tự, mở rộng hay lật ngược vấn đề. Tìm được một lời giải hay của một bài toán tức là đã khai thác được những đặc điểm riêng của bài toán, điều dó làm cho học sinh “có thể biết được cái quyến rũ của sự sáng tạo cùng niềm vui thắng lợi” (Pôlia – 1975). 1.2.3 Phƣơng pháp chung để giải bài toán Một số người có tham vọng muốn có một thuật giải tổng quát để giải mọi bài toán. Đó là điều ảo tưởng. Ngay cả đối với những lớp bài toán riêng biệt cũng có trường hợp có, có trường hợp không có thuật giải. Tuy nhiên trang bị những hướng dẫn chung, gợi ý các suy nghĩ tìm tòi, phát hiện cách giải bài toán lại là có thể và cần thiết. Dựa trên những tư tưởng tổng quát cùng với những gợi ý chi tiết của Polya (1975) về cách thức giải bài toán đã được kiểm nghiệm trong thực tiễn dạy học, có thể nêu lên phương pháp chung để giải bài toán như sau: Bước 1: Tìm hiểu nội dung đề bài. Phát biểu đề bài dưới những dạng thức khác nhau để hiểu rõ nội dung bài toán. Phân biệt cái đã cho và cái phải tìm, phải chứng minh. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 14 Có thể dùng công thức, ký hiệu, hình vẽ để hỗ trợ cho việc diễn tả đề bài. Bước 2: Tìm cách giải. Tìm tòi, phát hiện cách giải nhờ những suy nghĩ có tính chất tìm đoán: biến đổi cái đã cho, biến đổi cái phải tìm hay phải chứng minh, liên hệ cái đã cho hoặc cái phải tìm với những tri thức đã biết, liên hệ bài toán cần giải với một bài toán cũ tương tự, một trường hợp riêng, một bài toán tổng quát hơn hay một bài toán nào đó có liên quan, sử dụng những phương pháp đặc thù với từng dạng toán như chứng minh phản chứng, quy nạp toán học, toán dựng hình, toán quỹ tích... Kiểm tra lời giải bằng cách xem lại kỹ từng bước thực hiện hoặc đặc biệt hoá kết quả tìm được hoặc đối chiếu kết quả với một số tri thức có liên quan,... Tìm tòi những cách giải khác, so sánh chúng để chọn được cách giải hợp lý nhất. Bước 3: Trình bày lời giải. Từ cách giải đã được phát hiện, sắp xếp các việc phải làm thành một chương trình gồm các bước theo một trình tự thích hợp và thực hiện các bước đó. Bước 4: Nghiên cứu sâu lời giải. Nghiên cứu khả năng ứng dụng kết quả của lời giải. Nghiên cứu giải những bài toán tương tự, mở rộng hay lật ngược vấn đề. Như vậy bằng phương nói chung và phương pháp dạy học phát hiện và giải quyết vấn đề, giáo viên dựa trên phương pháp chung để giải một bài toán để từ đó cung cấp thêm cho học sinh chuyên tin một phương pháp giải bài tập toán đó là áp dụng lý thuyết đồ thị để giải. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 15 1.3 Thực trạng dạy học giải bài tập ở trƣờng THPT Thực trạng phương pháp dạy học môn toán ở trường THPT nói chung và phương pháp dạy học giải bài tập nói riêng hiện nay. 1.3.1 Thực trạng Qua thực tế giảng dạy và tìm hiểu tham khảo ở một số đồng nghiệp cho thấy: Không ít giáo viên có tâm huyết với nghề, có hiểu biết sâu sắc về bộ môn, có tay nghề vững, có nhiều giờ dạy tốt. Song phải thừa nhận rằng GV vẫn dạy theo cách như đã dạy mấy chục năm trước đây. Đó là kiểu thầy đọc trò chép; thầy viết lên bảng trò ghi chép vào vở, thầy nói trò ghi. Việc thực hiện đổi mới PPDH môn toán có một số chuyển biến bước đầu như: + Đối với bài giảng kiến thức mới: GV có quan tâm đặt vấn đề, dùng hệ thống câu hỏi dẫn dắt học sinh thông qua đàm thoại, gợi mở củng cố kiến thức bằng bài tập, chú trọng câu hỏi và hướng dẫn học sinh học ở nhà. + Đối với giờ luyện tập, dạy học sinh giải bài tập: học sinh được chuẩn bị trước ở nhà, một vài học sinh trình bày trên bảng cách giải, giáo viên hướng dẫn cả lớp nhận xét; GV tổng kết ưu khuyết điểm về lời giải và đưa ra lời giải mẫu. + Hình thức giờ dạy toán có sinh động hơn. Song về bản chất các giờ dạy đó vẫn theo kiểu thầy truyền đạt trò tiếp nhận. Cách dạy đó chưa phản ánh được những đặc thù trong dạy học toán, chưa phản ánh được các hoạt động toán học trong quá trình hình thành khái niệm, định lý cũng như vận dụng kiến thức trong giải toán, trong thực tiễn. Khi học, học sinh chủ yếu là nghe giảng, xem giáo viên làm mẫu, học sinh học thụ động, luôn luôn phụ thuộc vào giáo viên. Học sinh chưa được tự giác, tự do, tự khám phá kiến thức. Không ít giáo viên dạy theo kiểu áp đặt, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 16 kiểu luyện thi, nên học sinh chỉ quen nói theo và làm theo sự áp đặt đó. Như vậy, rất nhiều học sinh sau khi học, hiểu kiến thức một cách máy móc, hình thức. 1.3.2 Nguyên nhân Công tác quản lý chỉ đạo chưa kịp thời, trong một thời gian khá dài, với thời lượng và điều kiện lên lớp không đủ, không ổn định, quy mô mỗi lớp thường trên 60 học sinh nên giáo viên rất khó khăn trong thực hiện đổi mới PPDH. Cơ sở vật chất trường lớp và phương tiện giảng dạy tuy có khá hơn trước nhưng tình hình đó không phải là phổ biến, đời sống giáo viên và học sinh nhìn chung còn khó khăn, đã ảnh hưởng không nhỏ đến nề nếp chuyên môn và chất lượng giảng dạy, tạo nên trạng thái giáo viên giảng dạy xơ cứng dập khuôn theo sách giáo khoa. Việc đánh giá giờ giảng còn nặng hình thức, cứng nhắc theo các điều đã quy định, đã có sẵn, (chẳng hạn dạy phải đúng như sách giáo khoa...) đã làm mất đi tính sáng tạo của giáo viên. Nội dung, chương trình, sách giáo khoa chưa hỗ trợ cho giáo viên đổi mới phương pháp dạy học, một số nội dung có tính chất kinh viên, yêu cầu chặt chẽ (tiên đề hoá...). Tồn tại quá nhiều loại sách, nhiều bài tập khó, bài tập nâng cao, ít những bài tập liên quan đến thực tiễn, liên môn. Từ đó giáo viên chủ yếu dùng phương pháp thuyết trình, tập trung chủ yếu vào truyền thụ cho đủ kiến thức có trong sách giáo khoa với thời lượng 45 phút. Tạo ra hiện tượng dạy khoán cho xong nội dung... Hiện tượng dạy học bình quân rất phổ biến, yêu cầu cả lớp như nhau, bằng lòng với cách giải quyết có sẵn trong sách giáo khoa. Tình trạng._. này chẳng những không khuyến khích học sinh nỗ lực cá nhân mà còn tạo sự nhàm chán trong học tập, tạo sự trì trệ trong hoạt động của giáo viên. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 17 Dạy học hiện đang theo lối dạy nhồi nhét, dạy luyện thi, đối phó với thi, kiểm tra sao cho có điểm số cao mà chưa quan tâm đến sự phát triển trí tuệ, năng lực cá nhân học sinh. Việc chậm đổi mới phương pháp dạy học phải kể thêm các nguyên nhân: Giáo viên cũng như học sinh chưa khắc phục được nhận thức, thói quen dạy học truyền thống, nặng về lý thuyết coi nhẹ thực hành ứng dụng. Việc bồi dưỡng giáo viên chưa sát với yêu cầu nâng cao tri thức cũng như nghiệp vụ sư phạm, chưa theo hướng đổi mới phương pháp dạy học. Mối quan hệ giữa đào tạo tại các trường sư phạm với việc sử dụng ở trường phổ thông cũng như chỉ đạo của các cấp quản lý còn nhiều bất cập. Đánh giá , thi cử chủ yếu vẫn theo nội dung và hình thức truyền thống, nặng về lý thuyết coi nhẹ thực hành ứng dụng, làm hạn chế việc đổi mới phương pháp dạy học. Thông tin chưa cập nhật theo khu vực và thế giới. Có thể coi lối dạy học hiện nay là lối dạy “hộp đen”, tức là không quan tâm đến học sinh học ra sao, hiểu bài thế nào, học tập tích cực hay không, sự tham gia vào quá trình dạy của học sinh có thật sự là nỗ lực cá nhân vươn tới nắm bắt kiến thức hay không thì giáo viên không thể biết được, không kiểm soát được tư duy học sinh. Với cách dạy học đó học sinh càng học càng thu nhận thêm vốn tri thức của mình ngày một nhiều “kiến thức mới” (rất cụ thể), dẫn đến một thời điểm nào đó học sinh sẽ không đủ sức tải, cho dù đã học suốt ngày, một thực trạng thường thấy như hiện nay. 1.3 Những nội dung cơ bản của lý thuyết đồ thị 1.3.1 Khái niệm đồ thị (trong tin học) Xét theo góc độ trực quan, đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh (vô hướng hoặc có hướng) nối các đỉnh đó. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 18 Hay đồ thị là một cặp G=(V, E) trong đó V (Vertex) là tập các đỉnh, và E (Edge) là tập các cạnh nối các đỉnh (cạnh được hiểu là một cung nối hai đỉnh bất kỳ). Một số hình ảnh của đồ thị: Trong đó: +H1 có tập đỉnh V={Đường thẳng a, Đường thẳng b, Đường thẳng c, Đường thẳng d, Đường thẳng e} và tập cạnh E={(Đường thẳng a, Đường thẳng d), ( Đường thẳng b, Đường thẳng e), (Đường thẳng a, Đường thẳng c), (Đường thẳng c, Đường thẳng d), (Đường thẳng c, Đường thẳng e)} +H2 có tập đỉnh V={2, 3, 5, 6, 7, 10} Và tập cạnh là E={(2, 3), (2, 5), (2, 7), (3, 5), (3, 7), (3, 10), (6, 5), (6, 7), (7, 5), (7, 10)} Có thể phân loại đồ thị theo đặc tính và số lượng của tập các cạnh E. Cho đồ thị G=(V, E) gồm một tập V ≠  mà các phần tử của nó gọi là các đỉnh và một tập E mà các phần tử của nó gọi là các cạnh, ta có các khái niệm sau: + Đồ thị G được gọi là đơn đồ thị nếu giữa hai đỉnh bất kỳ được nối với nhau bởi không quá một cung (H3). Đ thẳng c Đ thẳng a Đ thẳng e Đ thẳng d Đ thẳng b Quan hệ song song song H1 3 5 10 7 2 6 Quan hệ nguyên tố cùng nhau H2 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 19 + Đồ thị G được gọi là đa đồ thị nếu giữa hai đỉnh bất kỳ được nối với nhau bởi hai cung trở lên, nhưng không thể có khuyên (H4). + Đồ thị G được gọi là đồ thị có hướng nếu các cạnh được xác định là có hướng (H5). + Đồ thị G được gọi là đồ thị vô hướng nếu các cạnh không xác định hướng (H6). + Đồ thị G được gọi là giả đồ thị nếu trong G tồn tại một cạnh nối một đỉnh với chính nó gọi là khuyên. Hai đỉnh u và v trong đồ thị (vô hướng) được gọi là liền kề nếu (u, v)E. Nếu e=(u, v) thì e gọi là cạnh liên thuộc với các đỉnh u và v. Cạnh e cũng được gọi là cạnh nối các đỉnh u và v. Các đỉnh u và v gọi là các điểm đầu mút của cạnh e. Giữa hai đỉnh chỉ tồn tại duy nhất một đường đi gọi là cầu. H3 H4 H5 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 20 Bậc của đỉnh v trong đồ thị G=(V, E), ký hiệu deg(v) là số cạnh liên thuộc với nó. Nếu cạnh là khuyên thì được tính là 2. Đỉnh v gọi là đỉnh treo nếu deg(v)=1 và gọi là đỉnh cô lập nếu deg(v)= 0. Đỉnh u được gọi là nối tới v hay v được gọi là nối từ u trong đồ thị có hướng G nếu (u, v) là một cạnh của G. Đỉnh u gọi là đỉnh đầu và đỉnh v gọi là đỉnh cuối của cung này. 1.3.2. Các đơn đồ thị đặc biệt Đồ thị đầy đủ n đỉnh, ký hiệu là Kn , là đơn đồ thị mà hai đỉnh phân biệt bất kỳ của nó luôn liền kề. Như vậy Kn có 2 )1( nn cạnh và mỗi đỉnh của Kn có bậc là n-1 (H7). Đơn đồ thị n đỉnh v1, v2,...vn (n ≥ 3) và n cạnh (v1, v2), (v2, v3),..... , (vn-1, vn), (vn, v1) được gọi là đồ thị vòng, ký hiệu là Cn. Như vậy mỗi đỉnh của Cn có bậc là 2 (H8). Từ đồ thị vòng Cn thêm vào đỉnh vn+1 và các cạnh (vn+1, v1), (vn+1, v2),...,(vn+1, vn) ta nhận được đơn đồ thị gọi là đồ thị bánh xe. Ký hiệu là V1 V1 V2 K1 K2 V2 V3 V1 V3 V4 V1 V2 K3 K4 H7 H6 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 21 Wn. Như vậy đồ thị Wn có n+1 đỉnh, 2n cạnh, 1 đỉnh bậc n, và n đỉnh bậc 3 (H9). Đơn đồ thị 2n đỉnh tương ứng với 2n xâu nhị phân độ dài n và hai đỉnh kề nhau khi và chỉ khi hai xâu nhị phân tương ứng với hai đỉnh này chỉ khác nhau đúng 1 bit được gọi là đồ thị lập phương, ký hiệu Qn. Như vậy mỗi đỉnh của Qn có bậc là n và số cạnh của Qn là n.2 n-1 (H9) Đơn đồ thị G=(V, E) sao cho V=V1  V2, V1 ∩ V2 = , V1 ≠ , V2 ≠  và mỗi cạnh của G được nối một đỉnh trong V1 và một đỉnh trong V2 được gọi là đồ thị phân đôi (H10). Nếu đồ thị phân đôi G=(V1UV2, E) sao cho mọi v1V1, v2V2; (v1, v2)E thì G được gọi là đồ thị phân đôi đầy đủ. Nếu V1=m, V2=n thì đồ thị phân đôi đầy đủ G ký hiệu là Km,n. Vậy Km,n có m.n cạnh, các đỉnh V1 có bậc n và các đỉnh V2 có bậc m. V2 V3 V1 V4 H9 V2 V3 V1 C3 V3 V4 V1 V2 C4 H8 10 11 00 01 V1 V2 Q1 H10 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 22 1.3.3 Tính liên thông của đồ thị Giả sử G=(V, E) là đồ thị vô hướng (hoặc có hướng). Một đường đi trong đồ thị là một dãy vi1ei1vi2ei2...vijeij...vikeikvik+1, trong đó các vij là các đỉnh còn các eij là các cạnh sao cho với j{1, 2, ...,k} thì đỉnh vij và đỉnh vij+1 là hai đỉnhkề nhau của cạnh eij. Đường đi đó xuất phát từ đỉnh vi1 và kết thúc tại đỉnh vik+1. Đường đi gọi là chu trình nếu nó bắt đầu và kết thúc tại cùng một đỉnh Đường đi hoặc chu trình gọi là chu trình đơn nếu nó đi qua mỗi cạnh đúng một lần (H12). YZ WXVUY là chu trình sơ cấp độ dài 6 Một đường đi hoặc chu trình đi qua mỗi đỉnh đúng một lần (trừ đỉnh đầu và đỉnh cuối của chu trình là trùng nhau) được gọi là đường đi hoặc chu trình sơ cấp. Đường đi (chu trình) sơ cấp là đường đi (chu trình) đơn. Một đồ thị (vô hướng) được gọi là liên thông nếu có đường đi giữa mọi cặp đỉnh phân biệt của đồ thị (H13). V3 V4 V1 V2 V5 H11 Y V W Z X U H12 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 23 Một đồ thị không liên thông là hợp của hai hay nhiều đồ thị con liên thông mỗi cặp các đồ thị con này không có đỉnh chung. Các đồ thị con liên thông rời nhau như vậy được gọi là các thành phần liên thông của đồ thị đang xét. Vậy một đồ thị là liên thông khi và chỉ khi nó chỉ có một thành phần liên thông (H14). Đồ thị có hướng G được gọi là liên thông mạnh nếu với hai đỉnh phân biệt bất kỳ u và v của G đều có đường đi từ u đến v và đường đi từ v đến u. Đồ thị có hướng G được gọi là liên thông yếu nếu đồ thị vô hướng nền của nó là đồ thị liên thông. 1.3.4 Đồ thị Euler và đồ thị Hamilton Chu trình đơn chứa tất cả các cạnh (hoặc cung) của đồ thị (có hướng hoặc vô hướng) G được gọi là chu trình Euler. §ường đi đơn chứa tất cả các cạnh (hoặc cung) của đồ thị (có hướng hoặc vô hướng) G được gọi là đường đi Euler. Một đồ thị liên thông có chứa một chu trình (đường đi) Euler được gọi là đồ thị Euler. Y U T Z X V H13 C D B G A H I H14 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 24 Ví dụ: Chu trình (đường đi) sơ cấp chứa tất cả các đỉnh của đồ thị (vô hướng hoặc có hướng) G được gọi là chu trình (đường đi) Hamilton. Một đồ thị có chứa một chu trình (đường đi) Hamilton được gọi là đồ thị Hamilton (nửa Hamilton). Ví dụ: Đồ thị Hamilton (hình thập nhị diện đều biểu diễn trong mặt phẳng) với chu trình Hamilton A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, A (đường tô đậm) (H16). 1.3.5 Cây 1.3.5.1 Định nghĩa và các tính chất cơ bản Cây là một đồ thị vô hướng liên thông, không chứa chu trình. H15 C C B B D F A F E F J F L L H F T F K K I F O F P P F F M F G F S S R F N F Q Q H16 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 25 Một đồ thị vô hướng không chứa chu trình gọi là một rừng. Trong một rừng, mỗi thành phần liên thông là một cây. Ví dụ: Rừng có 3 cây (H17): Định lý 6 mệnh đề tƣơng đƣơng: Cho T là một đồ thị có n đỉnh. Các điều kiện sau tương đương: 1)T là một cây. 2)T liên thông và có n-1 cạnh. 3)T không chứa chu trình và có n-1 cạnh. 4)T liên thông và mỗi cạnh là cầu. 5)Giữa hai đỉnh phân biệt bất kỳ của T luôn có duy nhất một đường đi sơ cấp. 6)T không chứa chu trình nhưng khi thêm một cạnh mới thì có được một chu trình duy nhất. 1.3.5.2 Cây khung Trong đồ thị liên thông G, nếu ta loại bỏ cạnh nằm trên chu trình nào đó thì ta sẽ được đồ thị vẫn là liên thông. Nếu cứ loại bỏ các cạnh ở các chu trình khác cho đến khi nào đồ thị không còn chu trình (vẫn liên thông) thì thu được một cây nối các đỉnh của G. Cây đó gọi là cây khung của đồ thị G. C E B A G F D N M L J I H K H17 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 26 Ví dụ: Cho đồ thị G như sau (H18): Ta có cây khung sau (H19): Tổng quát, nếu G là đồ thị có n đỉnh, m cạnh và k thành phần liên thông thì áp dụng thủ tục vừa mô tả đối với mỗi thành phần liên thông của G, ta thu được đồ thị gọi là rừng khung của G. 1.3.5.3 Bài toán tìm cây khung nhỏ nhất Đây là một trong những bài toán tối ưu trên đồ thị tìm được ứng dụng trong nhiều lĩnh vực khác nhau của đời sống. Cho G=(V,E) là đồ thị vô hướng liên thông có trọng số, mỗi cạnh eE có trọng số m(e)≥0. Giả sử T=(VT, ET) là cây khung của đồ thị G(VT=V). Ta gọi độ dài m(T) của cây khung T là tổng trọng số của các cạnh của nó. Bài toán đặt ra là trong số tất cả các cây khung của đồ thị G, hãy tìm cây khung có Y U T Z X V H18 Y U T Z X V H19 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 27 độ dài nhỏ nhất. Cây khung như vậy được gọi là cây khung nhỏ nhất của đồ thị và bài toán đặt ra gọi là bài toán tìm cây khung nhỏ nhất. 1.3.5.4 Cây có gốc Cây (tree) là một grap vô hướng liên thông, không chứa chu trình. Cây có gốc là một cây có hướng, trong đó có một đỉnh đặc biệt gọi là gốc, từ gốc có đường đi đến mọi đỉnh khác của cây. Trong cây có gốc thì gốc R có bậc vào bằng 0, còn tất cả các đỉnh khác đều có bậc vào bằng 1. Một cây có gốc thường được vẽ với gốc r ở trên cùng và cây phát triển từ trên xuống, gốc r gọi là đỉnh mức 0. Các đỉnh kề với r được xếp ở phía dưới và gọi là đỉnh mức 1. Đỉnh ngay dưới mức 1 là đỉnh mức 2,...(H20). Tổng quát trong một cây có gốc thì v là đỉnh mức k khi và chỉ khi đường đi từ r đến v có độ dài bằng k. Mức lớn nhất của một đỉnh bất kỳ trong cây gọi là chiều cao của cây. Cho cây T có gốc r=v0. Giả sử v0, v1,...vn-1, vn là một đường đi trong T. Ta gọi: vi+1 là con của vi và vi là cha của vi+1. v0, v1,...vn-1 là các tổ tiên của vn và vn là dòng dõi của v0, v1,...vn-1. Đỉnh treo vn là đỉnh không có con; Đỉnh treo cũng gọi là lá hay đỉnh ngoài; Một đỉnh không phải lá là một đỉnh trong. 4 3 1 2 7 6 5 9 8 H20 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 28 Một cây có gốc T được gọi là cây m-phân nếu mỗi đỉnh của T có nhiều nhất là m con. Với m=2, ta có cây nhị phân. Trong một cây nhị phân, mỗi con được chỉ rõ là con bên trái hay con bên phải; Con bên trái (tương ứng phải) được vẽ phía dưới về bên trái (tương ứng phải) của cha. Cây có gốc T được gọi là một cây m-phân đầy đủ nếu mỗi đỉnh trong của T đều có m con. Một cây m - phân đầy đủ có i đỉnh trong thì có mi+1 đỉnh và (m-1)i+1 lá. 1.3.6 Đồ thị phẳng và tô màu đồ thị 1.3.6.1 Bài toán mở đầu Bài toán ba làng và ba nhà máy. Ta có 3 làng L1, L2, L3, mà ta muốn đặt đường nối với 3 nhà máy: một nhà máy cung cấp điện Đ, một nhà máy cung cấp nước N và nhà máy cung cấp thực phẩm rau sạch R. Vấn đề đặt ra là, ta có thể đặt trên một mặt phẳng sao cho các đường đi không giao nhau ngoài các đỉnh cực biên hay không? (H21) Đồ thị biểu diễn 3 làng và 3 nhà máy cho phép định nghĩa một lớp các đồ thị gọi là lớp đồ thị không phẳng. 1.3.6.2 Đồ thị phẳng Một đồ thị được gọi là phẳng nếu nó có thể vẽ được trên một mặt phẳng mà không có các cạnh nào cắt nhau (ở một điểm không phải là điểm mút của các cạnh) Hình vẽ như thế gọi là một biểu diễn phẳng của đồ thị. Một đồ thị có thể là phẳng ngay cả khi nó được vẽ với những cạnh cắt nhau vì có thể vẽ nó bằng cách khác không có các cạnh cắt nhau. L1 Đ N R L3 L2 H21 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 29 Cho G là một đồ thị phẳng. Mỗi phần mặt phẳng giới hạn bởi một chu trình đơn không chứa bên trong một chu trình đơn khác gọi là miền (hữu hạn) của đồ thị G. Chu trình giới hạn miền là biên của miền. Mỗi đồ thị phẳng liên thông có một miền vô hạn duy nhất (là phần mặt phẳng bên ngoài tất cả các miền hữu hạn). Số cạnh ít nhất tạo thành biên gọi là đai của G. Trường hợp nếu G không có chu trình thì đai chính là số cạnh của G. Ví dụ: Đồ thị trên (H22) có 4 miền (M1, M2, M3, M4), và đồ thị có đai là 8. Định lý: Nếu một đồ thị phẳng liên thông có n đỉnh, p cạnh, và d miền thì ta có hệ thức: n - p + d = 2 Hệ thức n – p + d = 2 được gọi là “hệ thức Euler cho hình đa diện”. Mỗi hình đa diện có thể coi là một đồ thị phẳng. Hệ quả: Trong một đồ thị phẳng liên thông tuỳ ý, luôn tồn tại ít nhất một đỉnh có bậc không vượt quá 5. 1.3.6.3 Tô màu đồ thị Bài toán mở đầu: Bài toán được đặt ra xuất phát từ bài toán tô màu bản đồ như sau: Ta coi mỗi bản đồ là một ®ồ thị phẳng. Trong một bản đồ ta coi hai miền có chung nhau một đường biên là hai miền kề nhau. (Hai miền chỉ có B A C F D E M2 M3 M1 M4 H22 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 30 chung nhau một điểm biên là hai miền không kề nhau). Một bản đồ thường được tô màu sao cho hai miền kề nhau được tô hai màu khác nhau. Và bài toán đặt ra là: “xác định số màu tối thiểu cần có để tô màu một bản đồ sao cho 2 miền kề nhau có màu khác nhau”. Ví dụ: Ta có bản đồ (H23) sau: Với bản đồ này ta cần 3 màu là đủ (2 màu không đủ để có thể tô được theo yêu cầu nói trên) Mỗi bản đồ trên mặt phẳng có thể biểu diễn bằng một đồ thị, trong đó mỗi miền của bản đồ được biểu diễn bằng một đỉnh, các cạnh nối hai đỉnh nếu các miền được biểu diễn bằng hai đỉnh này là kề nhau. Đồ thị nhận được bằng cách này gọi là đồ thị đối ngẫu của bản đồ đang xét. Tô màu một đơn đồ thị là việc gán màu cho các đỉnh của nó sao cho hai đỉnh liền kề có màu khác nhau. Mỗi đồ thị có thể có nhiều cách tô màu khác nhau. Số màu hay sắc số (Chromatic number) của một đồ thị G là số màu tối thiểu cần thiết để tô màu G. Ký hiệu: (G). 1.3.6.3.1 Định nghĩa A B C D E F G H23 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 31 Định lý 1: Mọi đơn đồ thị đầy đủ Kn đều có: (Kn) = n. Định lý 2: Mọi chu trình độ dài lẻ đều có sắc số là 3. Định lý 3: Nếu G có chứa một đồ thị con đẳng cấu với Kn thì (G)  n. Chú ý: Nếu G' là một đồ thị con của G thì (G)  (G'). Nếu dùng k màu để tô màu G thì không cần quan tâm đến những đỉnh có bậc nhỏ hơn k. Định lý 4: Một đơn đồ thị G = (V, E) có thể tô bằng 2 màu khi và chỉ khi nó không có chu trình độ dài lẻ. Định lý 5 (Định lý 5 màu của Kempe-Heawood): Mọi đồ thị phẳng đều có thể tô đúng 5 màu. Định lý 6 (Định lý bốn màu) (định lý Appel-Haken, 1976): Mọi đồ thị phẳng đều có sắc số không lớn hơn 4. Định lý này là định lý đầu tiên được chứng minh với sự hỗ trợ của máy vi tính. 1.3.6.3.2 Một số định lý Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 32 Kết luận chương 1: Việc học toán, giải bài tập toán muốn đạt được các yêu cầu trên và khắc phục được những vấn đề tồn tại đã đưa ra trong phần thực trạng thì phải cần một giải pháp đồng bộ, hệ thống. Một trong những hướng đó là dạy học theo quan điểm tích hợp (khai thác nội dung của các nội dung khác một cách hợp lý...). Chương trình học tập của học sinh chuyên Tin được trang bị tri thức về lý thuyết đồ thị một cách hệ thống nhằm phục vụ cho việc lập trình giải toán. Tuy nhiên với kiến thức có được về lý thuyết đồ thị thì việc khai thác chúng dạy học giải bài tập nói riêng, dạy học toán nói chung sẽ góp phần không nhỏ vào việc bồi dưỡng cho HS năng lực giải bài tập và rèn luyện kỹ năng vận dụng lý thuyết vào thực tiễn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 33 Chƣơng 2 KHAI THÁC LÝ THUYẾT ĐỒ THỊ VÀO GIẢI BÀI TẬP TOÁN 2.1. Quy trình chuyển đổi từ bài toán thông thƣờng sang ngôn ngữ lý thuyết đồ thị 2.1.1 Một số bài toán tiềm ẩn các yếu tố của lý thuyết đồ thị Trong chương trình toán và trong một số các chuyên đề bồi dưỡng HS ở trường trung học phổ thông chuyên, học sinh đã gặp nhiều bài toán tiềm ẩn các yếu tố của lý thuyết đồ thị. Ví dụ: Ví dụ 1 Một cuộc họp có ít nhất 3 đại biểu. Khi đến họp mỗi đại biểu đã bắt tay ít nhất 2 đại biểu đến dự họp. Chứng minh rằng ta luôn có thể xếp 1 số đại biểu ngồi xung quanh 1 bàn tròn để mỗi người ngồi giữa 2 người mà anh (chị) ta đã bắt tay. Ví dụ 2 Có 10 đội bóng thi đấu với nhau mỗi đội phải đấu 1 trận với các đội khác. Chứng minh rằng vào bất kỳ lúc nào cũng có 2 đội đã đấu được một số trận như nhau. Ví dụ 3 Một nhóm gồm 5 thành viên trong đó mỗi bộ ba đều có 2 người quen nhau và 2 người không quen nhau. Chứng minh rằng có thể xếp cả nhóm ngồi xung quanh 1 bàn tròn để mỗi người ngồi giữa 2 người mà thành viên đó quen. Ví dụ 4 Trong phòng có n người (n  3) mỗi người quen với ít nhất 2 người khác. Chứng minh rằng có thể chọn ra một số người để xếp ngồi quanh một bàn tròn sao cho mỗi người đều ngồi giữa 2 người quen. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 34 Ví dụ 5 Có 6 đội bóng thi đấu vòng tròn một lượt với nhau (mỗi đội phải đấu 1 trận với 5 đội khác). Chứng minh rằng vào bất kỳ lúc nào cũng có 3 đội trong đó từng cặp đã đấu với nhau rồi hoặc chưa đấu với nhau trận nào. Ví dụ 6 Cho 5 số nguyên dương tuỳ ý, mà cứ 3 số bất kỳ đều có 2 số có ước chung và 2 số nguyên tố cùng nhau. Chứng minh rằng có thể ghi 5 số trên một đường tròn, để mỗi số đều đứng giữa 2 số mà nó có ước chung. Ví dụ 7 Chứng minh rằng trong 6 góc nhọn bao giờ cũng tìm được 3 góc A, B, C sao cho các tổng A+B, A+C, B+C đồng thời lớn hơn 900 hoặc đồng thời không lớn hơn 900. Ví dụ 8 Cho n mặt phẳng phân biệt đôi một, phân biệt cắt nhau, trong đó không có 3 mặt phẳng nào cùng thuộc một chùm. Hãy tìm số giao tuyến của các cặp mặt phẳng. Ví dụ 9 Chứng minh rằng trong 6 số nguyên dương khác nhau tuỳ ý luôn luôn chọn được 2 số có ước chung hoặc nguyên tố cùng nhau. 2.1.2. Quy trình chuyển đổi từ bài toán thông thƣờng sang ngôn ngữ lý thuyết đồ thị Với các dạng bài toán trên (2.1.1) ngoài cách giải thông thường đã biết thì có thể vận dụng lý thuyết đồ thị để giải quyết các bài toán. Để sử dụng được kiến thức lý thuyết đồ thị để giải thì công việc đầu tiên là phải chuyển đổi được bài tập này sang ngôn ngữ lý thuyết đồ thị. Sau đó đưa ra dấu hiệu nhận dạng các bài toán có thể vận dụng lý thuyết đồ thị để giải quyết. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 35 2.1.2.1. Dấu hiệu chung Không phải bất kỳ một bài toán nào ta cũng có thể vận dụng lý thuyết đồ thị để giải điều đó còn tùy thuộc vào các yếu tố cho của bài toán. Vấn đề đặt ra là đứng trước một bài toán ta phải xác định được bài toán này có thể khai thác kiến thức của lý thuyết đồ thị để giải quyết hay không? Một đồ thị luôn xác định với 2 yếu tố đó là đỉnh và cạnh. Như vậy muốn áp dụng đồ thị để giải bất kỳ một bài toán nào ta cũng phải xác định xem liệu bài toán có thể chuyển được về một đồ thị hay không? (Hay nói cách khác ta phải chuyển bài toán sang cách biểu diễn mới là đồ thị). Giáo viên tổ chức cho học sinh hoạt động nhận dạng ra các yếu tố của lý thuyết đồ thị tiềm ẩn trong bài toán. Cụ thể: Yếu tố nào của bài toán sẽ là đỉnh của đồ thị Yếu tố nào sẽ là cạnh của đồ thị? Nếu xác định được thì ta sẽ nghĩ tới phương án áp dụng lý thuyết đồ thị để giải bài toán này? Qua nghiên cứu ta thấy yếu tố được xác định trong đồ thị thường như sau: +Đỉnh tương ứng với các đối tượng +Cạnh tương ứng với các quan hệ Vậy nếu học sinh nhận dạng được trong bài toán hàm chứa 2 yếu tố các đối tượng và các quan hệ giữa chúng thì có thể sẽ đưa về mô hình đồ thị được. Mấu chốt của vấn đề là ở chỗ giáo viên giúp học sinh nhận dạng và định hướng 1 bài toán có thể áp dụng lý thuyết đồ thị để giải hay không? Ví dụ 11: Ta xét ví dụ 3 (2.1.1). Một nhóm gồm 5 thành viên trong đó mỗi bộ ba đều có 2 người quen nhau và 2 người không quen nhau. Chứng minh rằng có thể xếp cả nhóm ngồi Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 36 xung quanh 1 bàn tròn để mỗi người ngồi giữa 2 người mà thành viên đó quen. Nhận xét: Với bài toán trên, nếu không biết lý thuyết đồ thị thì sẽ thực hiện giải nó như thế nào? Với các yếu tố của bài toán đã cho ta nhận thấy số người đối tượng là hữu hạn do đó số khả năng xảy ra cũng là hữu hạn. Vì vậy ta có thể xét lần lượt hết các khả năng có thể xảy ra bằng lý thuyết tổ hợp. Tuy nhiên vấn đề đặt ra là ở đây chỉ có 5 đối tượng ta có thể liệt kê được còn nếu số đối tượng nhiều hơn thì sẽ gặp khó khăn. Khó khăn về cách thực hiện có thể bỏ sót các trường hợp dẫn đến kết quả thiếu chính xác. Từ đó ta có thể nghĩ đến một phương pháp giải khác để có thể khắc phục nhược điểm trên đó là áp dụng lý thuyết đồ thị để giải. Giải: Xác định hai yếu tố theo dấu hiệu chung từ đó ta xây dựng đồ thị mô tả lại bài toán theo ngôn ngữ lý thuyết đồ thị. - Đối tượng trong bài toán là thành viên tương ứng đỉnh của đồ thị. Có 5 thành viên tương ứng với 5 đỉnh của đồ thị. Dùng tên các thành viên để ghi tên các đỉnh tương ứng. - Quan hệ tương ứng giữa các đỉnh là cạnh của đồ thị. Trong bài toán này quan hệ ở đây có 2 mối quan hệ giữa các thành viên: quen nhau hoặc không quen nhau. Ta quy ước như sau: + Cạnh nét liền để nối giữa 2 đỉnh tương ứng với 2 người quen nhau. + Cạnh nét chấm để nối giữa 2 đỉnh tương ứng với 2 người không quen nhau. Vậy ta có bài toán tương ứng bằng ngôn ngữ lý thuyết đồ thị như sau: Cho đồ thị G với 5 đỉnh, các cạnh được nối bởi cạnh nét liền và cạnh nét đứt sao cho không có “tam giác nào có các cạnh cùng loại”. Chứng minh rằng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 37 luôn có hình 5 cạnh với các cạnh cùng loại và các đường chéo được vẽ khác loại. Ở đây “tam giác có các cạnh cùng loại” được hiểu theo nghĩa tam giác được tạo bởi 3 đỉnh và các cạnh của tam giác được vẽ cùng loại hoặc nét đứt hoặc nét liền. Đồ thị G là đa giác 5 cạnh với các cạnh nét đứt và các đường chéo là nét liền hoặc ngược lại. Khi đó dựa theo đường gấp khúc khép kín nét đứt mà sắp xếp các thành viên tương ứng ngồi xung quanh 1 bàn tròn, thì mỗi thành viên sẽ ngồi giữa 2 người mà thành viên có quen (H24). Phân tích bài toán: Bài toán có chứa hai mối quan hệ là quen và không quen. Coi 5 người là 5 đỉnh A, B, C, D, E của một đồ thị, hai người quen nhau tương ứng với cạnh nối hai đỉnh được vẽ bằng nét liền và hai người không quen nhau tương ứng với cạnh nối hai đỉnh được vẽ bằng nét đứt. Do giữa 3 người bất kỳ luôn tìm được hai người quen nhau và hai người không quen nhau suy ra không có tam giác nào có 3 cạnh cùng loại. Khi đó chuyển về bài toán đồ thị màu: Cho đồ thị đầy đủ 5 đỉnh và các cạnh trong đó không có tam giác nào có 3 cạnh cùng loại. Chứng minh có một chu trình Euler trong đồ thị đó. B C D E A H24 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 38 Ta chứng minh như sau: Trước hết ta chứng minh mỗi đỉnh là đầu mút của đúng hai cạnh cùng loại. Thật vậy, xét đỉnh A bất kỳ, A có bậc là 4 suy ra A là đầu mút của ít nhất hai cạnh cùng loại. Giả sử A là đầu mút của 2 cạnh nét liền AB, AC suy ra BC nét đứt. Giả sử AD nét liền khi đó DC nét đứt suy ra nếu BD nét liền thì tam giác ABD có 3 cạnh nét liền, nếu BD nét đứt thì tam giác BCD có các cạnh nét đứt, cả hai trường hợp đều trái với giả thiết . Vậy AD nét đứt. Giả sử AB, AC nét liền suy ra BC nét đứt và giả sử BD nét liền khi đó nếu DC nét liền thì EC, EA, EB, ED đều nét đứt (vô lý). Vậy BC nét đứt, lại có AD nét đứt, BC nét đứt suy ra CE nét liền, DE nét liền. Vậy ta được cách xếp 5 người thành một vòng tròn như hình H24. 2.1.2.2 Dấu hiệu nhận dạng bài tập có thể sử dụng đồ thị có hƣớng Từ dấu hiệu chung ta có nhận xét sau: Trong thực tế chúng ta hay gặp những mối quan hệ giữa các đối tượng như A thắng B, A giỏi hơn B, A nhanh hơn B…Những quan hệ này theo kiểu một chiều nghĩa là A thắng B thì không thể suy ra B thắng A được. Vì vậy khi gặp những bài toán có mối những quan hệ một chiều như vậy ta nghĩ ngay tới việc liệu có thể chuyển bài toán đó về bài toán đồ thị có hướng và từ đó sử dụng những tính chất của đồ thị có hướng mà ta đã biết hay không? Nếu được thì bài toán sẽ trở nên dễ hiểu và việc giải quyết yêu cầu bài toán sẽ dễ dàng hơn. Ví dụ 12 Có 5 đội bóng chuyền thi đấu với nhau để tranh giải cúp quốc gia. Biết rằng hai đội chỉ đấu với nhau đúng một trận và mỗi đội phải đấu với đúng 4 đội khác, đồng thời không có trận hòa. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 39 Chứng tỏ rằng căn cứ vào kết quả thi đấu có thể xếp đội trưởng các đội đứng theo một hàng dọc để đội đứng sau thắng đội đứng ngay trước. Nhận xét: Một cách giải thông thường ở phổ thông hay sử dụng để giải bài tập dạng trên đó là: lập bảng trạng thái vì có thể xét hữu hạn các khả năng. Nhưng khi số đối tượng lớn thì khó khăn nếu ta cũng xét hét các khả năng như vậy. Vậy ta cũng lại đi tìm một phương pháp giải khác cho phù hợp đó là áp dụng lý thuyết đồ thị để giải Ta sẽ chỉ ra 2 yếu tố: Đối tượng và quan hệ tương ứng với đỉnh và cạnh của đồ thị. Đối tượng: các đội bóng. Quan hệ: thắng thua. Vì ở đây có quan hệ một chiều do đó ta sử dụng đồ thị có hướng để biểu diễn. Coi mỗi đội bóng là một đỉnh của đồ thị, mũi tên nối hai đỉnh biểu thị mối quan hệ từ đội thắng sang đội thua, khi đó ta được một đồ thị có hướng. Do mỗi đội phải đấu với 4 đội khác và không có trận hòa nên được một đồ thị đầy đủ có hướng với 5 đỉnh. Như vậy việc “xếp đội trưởng các đội đứng theo một hàng dọc để đội đứng sau thắng đội đứng ngay trước” tương đương với một chu trình Hamilton trong đồ thị xây dựng ở trên. Bài toán đã cho trở thành bài toán đồ thị như sau: “ Cho đồ thị đầy đủ có hướng với 5 đỉnh, chứng minh rằng có thể tìm được một chu trình Hamilton trong đồ thị đó” Áp dụng định lý của lý thuyết đồ thị: “ Trong đồ thị có hướng đầy đủ luôn luôn có đường Hamilton”, sẽ tìm được lời giải bài toán (H25). Giả sử ta có kết quả thi đấu như sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 40 A B C D E A 0 + + + + B - 0 - - - C - + 0 + - D - + - 0 - E - + + + 0 Từ đó ta có đồ thị: Kết quả của bài toán như sau: A → E → C → D → B E D C B A H26 E D C B A H25 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 41 2.1.2.3 Dấu hiệu nhận dạng bài tập có thể sử dụng đồ thị màu Với bài toán trong đó có chứa những mối quan hệ đối lập nhau giữa các đối tượng như: “quen và không quen”, “nói cùng thứ tiếng và khác thứ tiếng”, “có đường đi và không có đường đi”, đồng thời yêu cầu của bài toán thường là chứng minh có ít nhất 3 đối tượng có cùng mối quan hệ hoặc sẽ tạo thành một vòng tròn. Ta liên hệ tới đồ thị có cạnh được tô màu và giải bài toán bằng đồ thị với các cạnh (đỉnh) được tô màu. Ví dụ 13: Chứng minh rằng trong 6 góc nhọn bao giờ cũng tìm được 3 góc A, B, C sao cho các tổng A+B, A+C, B+C đồng thời lớn hơn 900 hoặc đồng thời không lớn hơn 900. Nhận xét: Ở phổ thông học sinh biết và vận dụng lý thuyết về tổng ba góc trong một tam giác bằng 1800, hiệu hai góc nhỏ hơn hai góc còn lại...Tuy nhiên để vận dụng các lý thuyết đó để xét các trường hợp đối với bài toán này là khó vì liệt kê hết các khả năng có thể dẫn đến bỏ sót, lời giải không hoàn chỉnh hoặc sai. Vì vậy ta cũng nghĩ tới áp dụng phương pháp khác để giải bài toán đó là dựa vào lý thuyết đồ thị. Giải: Ta xác định hai yếu tố: Đối tượng tương ứng là đỉnh của đồ thị và quan hệ là cạnh của đồ thị. Đối tượng ở đây là các góc, quan hệ tổng hai góc lớn hơn 900 hay tổng hai góc nhỏ hơn 900 . Ta thấy trong bài toán có hai mối quan hệ trái ngược nhau đó là: tổng hai góc lớn hơn 900 hay tổng hai góc nhỏ hơn 900 . Vì vậy ta sẽ áp dụng giải bài toán bằng đồ thị với các cạnh được tô màu. Như vậy: Có 6 góc tương ứng là 6 đỉnh của đồ thị. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 42 Cạnh của đồ thị được xác định: Nếu tổng hai góc lớn hơn 900 thì cạnh nối 2 đỉnh tương ứng nối bằng nét liền, ngược lại tô bằng nét đứt. Ta phải chứng minh trong đồ thị G xây dựng như trên luôn có một tam giác có 3 cạnh cùng dạng. (Ở đây tam giác được hiểu theo nghĩa thông thường là hình được nối 3 đỉnh tương._.