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=1, 2, ..., 2n+1). Với giá trị nào của n ta có thể gán cho mỗi phần tử của B giá trị 0 hoặc 1 sao cho trong mỗi tập hợp Ai có đúng n phần tử được gán giá trị 0? Nhận xét: Bài toán trên có yêú tố liên quan đến lý thuyết tập hợp. Trên cơ sở học sinh đã biết về lý thuyết tập hợp (thông thường hay sử dụng biểu diễn bằng biểu đồ ven). Tuy nhiên bằng phương pháp đó không thể vẽ được trong trường hợp có số tập hợp lớn. Như vậy ta phải nghĩ tới một phương pháp khác để biểu diễn nó. Giải: Ta xác định 2 yếu tố đối tượng và quan hệ để xây dựng đồ thị tương ứng mô tả bài toán theo dấu hiệu chung. Đối tượng: Các tập hợp. Quan hệ: Quan hệ giao nhau của các tập hợp. Như vậy: Ta cho tương ứng mỗi tập hợp A1, A2, ..., A2n+1 với mỗi đỉnh của đồ thị; giao của Ai và Aj tương ứng với cạnh AiAj. Dễ thấy rằng các tính chất a, b, c nêu trong bài toán tương ứng với các tính chất của một đồ thị đầy đủ có 2n+1 đỉnh. Việc gán cho mỗi phần tử của B giá trị 0 hoặc 1có thể cho tương ứng với việc tô mỗi cạnh của đồ thị bằng màu đỏ hoặc xanh. Ta phải giải bài toán theo lý thuyết đồ thị như sau: Cho một đồ thị đầy đủ có 2n+1 đỉnh. Với những giá trị nào của n ta có thể tô mỗi cạnh của G bằng màu xanh hoặc đỏ sao cho tại mỗi đỉnh của G có đúng n cạnh màu đỏ. 46 Nếu tại mỗi đỉnh của G có đúng n cạnh màu đỏ thì tổng số cạnh màu đỏ sẽ là 2 )12( nn (do mỗi cạnh nối 2 đỉnh và có tất cả 2n+1 đỉnh), do đó n phải chẵn. Ngược lại, giả sử n chẵn (n=2k). Khi đó ta có thể tô màu các cạnh như sau: Tô màu đỏ tất cả các cạnh AiAi+m (i+m theo mod 2n+1), i=1, ..., 2n+1 và 1≤ m ≤ k; tất cả các cạnh còn lại được tô màu xanh. Vì với mỗi giá trị của m, ta tô màu đỏ được hai cạnh xuất phát từ mỗi đỉnh nên với k giá trị của m, ta tô đỏ được 2k=n cạnh. Hay khẳng định của bài toán được chứng minh. Ví dụ với n=4=2.2 Ta tô đỏ (nét liền) tất cả các cạnh AiAi+1, tức là các cạnh A1A2, A2A3,..., và các cạnh AiAi+2, tức là các cạnh A1A3, A2A4, A3A5, A4A6...., (H27) 2.2.4 Phƣơng án 2 (khai thác lý thuyết đồ thị ở bƣớc 2) Chuyển bài toán gốc sang bài tập dạng lý thuyết đồ thị, dựa vào lý thuyết đồ thị để dự đoán kết quả sau đó dùng kiến thức toán học để giải quyết bài toán gốc. A1 A2 A3 A4 A5 A6 A7 A8 A9 H27 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 47 Ví dụ 15 : 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. Giải: Tương tự ta cũng nghĩ đến việc xét xem có thể áp dụng được lý thuyết đồ thị để giải hay không? Muốn vậy ta cho học sinh nhận dạng 2 yếu tố để có thể đưa bài toán về mô hình đồ thị là đối tượng và quan hệ. Đối tượng ở đây là mặt phẳng do đó n mặt phẳng cho tương ứng n đỉnh. Quan hệ là cắt nhau do đó cứ 2 mặt phẳng cắt nhau thì ta được một cạnh của đồ thị. Như vậy ta được một đồ thị đầy đủ bậc n (do các mặt phẳng đôi một cắt nhau). Theo tính chất của đồ thị đầy đủ ta xác định được ngay số cạnh của đồ thị là 2 )1( nn . Từ kết quả này ta đi chứng minh bằng suy luận toán học. Ta giải bằng lý luận như sau: Cứ hai mặt phẳng tạo ra một giao tuyến, một mặt phẳng cắt n-1 mặt phẳng còn lại tạo ra n-1 giao tuyến. Như vậy một giao tuyến được tính 2 lần.  Số giao tuyến là: 2 )1( nn Vậy số giao tuyến của các cặp mặt phẳng chính là số cạnh của đồ thị đó là: 2 )1( nn cạnh. Với trường hợp n=3, 4, 5 ta có: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 48 Số mặt phẳng 3 4 5 Số giao tuyến 32 )13(3   3 2 )14(4   3 2 )15(5   2.2.5 Phƣơng án 3 (khai thác lý thuyết đồ thị ở bƣớc 4) Ta thực hiện giải bài toán bình thường sau đó đưa về đồ thị để mở rộng và phát triển bài toán. Ví dụ 16: 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. Bài toán tổng quát: Chứng minh rằng trong n (n>=6) số nguyên dương tuỳ ý luôn luôn chọn được n-4 bộ ba mà trong mỗi bộ ba này từng cặp số có ước chung hoặc nguyên tố cùng nhau. Để giải được bài toán ta có khẳng định sau: Đồ thị đầy đủ gồm n (n>=6) và được tô bằng không quá 2 màu cạnh thì luôn có ít nhất n-4 tam giác cùng màu. Để giải bài toán đã cho trước tiên ta chứng minh khẳng định trên: Trường hợp 1: Đồ thị đầy đủ Gn có n đỉnh ( n ≥ 6 ) được tô bằng một màu cạnh. Khẳng định dễ dàng được chứng minh. Trường hợp 2: Đồ thị đầy đủ Gn có n đỉnh ( n ≥ 6 ) với 2 màu cạnh (chẳng hạn xanh, đỏ). Ta phải khảng định Gn có ít nhất n-4 tam giác cùng màu. Điều này được chứng minh bằng quy nạp theo số đỉnh của đồ thị. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 49 1. Cơ sở quy nạp: n = 6 thì đồ thị tương ứng G6 đầy đủ với 2 màu cạnh (xanh, đỏ). Ta phải chứng minh G6 có ít nhất (6-4)= 2 tam giác cùng màu. Ta có G6 luôn có ít nhất một tam giác cùng màu. Do đó ta phải chứng minh trong G6 có thêm ít nhất một tam giác cùng màu nữa. Không mất tính tổng quát, ta gọi các đỉnh của G6 là A, B, C, D, E, F và tam giác cùng màu là tam giác ABC với các cạnh màu đỏ (nét liền), (H28). Ta xét các trường hợp sau có thể xảy ra: 1 0 ) Cả ba cạnh AD, AE, AF đều được tô màu đỏ (H29). Khi đó, nếu có ít nhất một trong ba cạnh DE, EF, DF đỏ thì trong G6 có thêm ít nhất một tam giác cùng màu nữa (tam giác đỏ). Ngược lại, nếu cả ba cạnh DE, EF, DF xanh (nét đứt) thì trong G6 có tam giác cùng màu thứ hai (tam giác xanh). A B C D E F H28 A B C D E F H29 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 50 2 0 ) Cả ba cạnh AD, AE, AF đều được tô màu xanh (H30). Chứng minh tương tự trường hợp 10) Nếu có ít nhất một trong ba cạnh DE, EF, DF xanh thì trong G6 có thêm ít nhất một tam giác nữa cùng màu (tam giác xanh). Ngược lại, cả ba cạnh DE, EF, DF đỏ thì trong G6 có tam giác cùng màu thứ hai (tam giác đỏ). 3 0 ) Trong ba cạnh AD, AE, AF có hai cạnh đỏ, chẳng hạn AD, AE được tô màu đỏ (H31). Khi đó, nếu có ít nhất một trong ba cạnh CD, DE, CE đỏ thì trong G6 có thêm ít nhất một tam giác nữa cùng màu (tam giác đỏ). Ngược lại, cả ba cạnh CD, DE, CE xanh thì trong G6 có tam giác cùng màu thứ hai (tam giác xanh). 4 0 ) Trong ba cạnh AD, AE, AF có đúng một cạnh đỏ, chẳng hạn AD được tô màu đỏ (H32 ). A B C D E F H30 A B C D E F H31 A B C D E F H32 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 51 a) Một trong hai cạnh BD, CD đỏ. Khi đó trong G6 có tam giác cùng màu thứ hai (tam giác đỏ). b) Cả hai cạnh BD, CD xanh (H33 ). b1) EF xanh: Khi đó trong G6 có tam giác cùng màu thứ hai (tam giác AEF xanh). b2) EF đỏ: b2.1) BE đỏ (H34 ) b2.1.1) Hoặc BF hoặc CE đỏ, ta có tam giác cùng màu thứ hai (tam giác đỏ). b2.1.2) Cả hai cạnh BF và CE xanh (H35). A B C D E F H33 A B C D E F H34 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 52 b2.1.2.1) Hoặc DE hoặc DF xanh, ta có tam giác cùng màu thứ hai (tam giác xanh). b2.1.2.2) Cả hai cạnh DE và DF đều đỏ, ta có tam giác cùng màu thứ hai (tam giác DEF đỏ). b2.2) BE xanh (H36 ) b2.2.1) DE xanh ta có tam giác cùng màu thứ hai (tam giác BDE xanh). b2.2.2) DE đỏ (H37 ) A B C D E F H35 A B C D E F H36 A B C D E F H37 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 53 b2.2.2.1) DF đỏ ta có tam giác cùng màu thứ hai (tam giác DEF đỏ). b2.2.2.2) DF xanh (H38). b2.2.2.2.1) Hoặc BF hoặc CF xanh ta có tam giác cùng màu thứ hai (tam giác xanh). b2.2.2.2.2) Cả BF và CF đều đỏ ta có tam giác cùng màu thứ hai (tam giác BCF đỏ). Vậy trong mọi trường hợp, G6 đều có ít nhất hai tam giác cùng màu. 2. Quy nạp: Giả sử định lý đúng với n=k. Xét đồ thị Gk+1 đầy đủ với (k+1) đỉnh, được tô bằng hai màu xanh, đỏ. Ta phải chứng minh Gk+1 có ít nhất (k+1-4)= k-3 tam giác cùng màu. Thật vậy: Vì Gk+1 đầy đủ gồm (k+1) đỉnh (k+1≥7) với hai màu cạnh nên có ít nhất một tam giác cùng màu. Giả sử các đỉnh của Gk+1 là A1, A2,...,Ak+1 và tam giác cùng màu là tam giác A1A2A3 (chẳng hạn màu đỏ) (H39). A B C D E F H38 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 54 Loại A1 và các cạnh xuất phát từ A1 ra khỏi đồ thị Gk+1 ta có đồ thị Gk với hai màu cạnh (xanh, đỏ). Nên theo giả thiết quy nạp trong Gk luôn có ít nhất (k-4) tam giác cùng màu. Khôi phục đỉnh A1 cùng các cạnh thuộc A1 ta được đồ thị Gk+1 với hai màu cạnh (xanh, đỏ) và Gk+1 có ít nhất (k-4+1) hay (k-3) tam giác cùng màu. Khẳng định được chứng minh. Giải bài toán 1: Xét tất cả các tam giác có đỉnh là các điểm đã cho. Vì khoảng cách giữa các cặp điểm đã cho khác nhau từng đôi một nên mỗi tam giác có đỉnh là các điểm đã cho đều có cạnh ngắn nhất và cạnh dài nhất. Đối với mỗi tam giác này ta dùng màu xanh để tô cạnh ngắn nhất. Sau khi tất cả các đoạn thẳng nối giữa các cặp điểm đã cho được phép tô màu xanh đã tô xong, phần đoạn thẳng còn lại tô màu đỏ. Đồ thị G nhận được là đồ thị đầy đủ gồm 6 đỉnh với các cạnh được tô bằng hai màu (xanh, đỏ) nên theo khẳng định trên trong G có ít nhất hai tam giác cùng màu. Vì tam giác nào cũng có cạnh ngắn nhất được tô màu xanh trước, nên các tam giác cùng màu đều là tam giác xanh. Khi đó cạnh dài nhất trong mỗi tam giác này là đoạn thẳng cần tìm. Bởi vì trong tam giác này ta xét nó đóng vai trò cạnh dài nhất, nhưng vì đoạn thẳng này có màu xanh nên nó đã là cạnh ngắn nhất của một tam giác nào đó trong các tam giác có đỉnh là các điểm đã cho. A1 A2 A3 Ak+1 Ak A4 H 39 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 55 Giải bài toán 2,3: Xây dựng đồ thị mô tả quan hệ. Đỉnh: Lấy n điểm (n≥6) tương ứng với n người (n số nguyên, n đối tượng) đã chọn ra. Dùng ngay tên người (các số, ký hiệu các đối tượng) để ghi trên các điểm tương ứng. Cạnh: Dùng: Cạnh đỏ để nối giữa hai điểm tương ứng với hai người quen nhau (hai số có ước số chung, hai đối tượng có quan hệ t1). Cạnh xanh để nối giữa hai điểm tương ứng với hai người không quen nhau (hai số nguyên tố cùng nhau, hai đối tượng có quan hệ t2). Đồ thị Gi nhận được mô tả toàn bộ quan hệ được cho trong bài toán và thoả mãn điều kiện của khẳng định trên. Vậy theo khẳng định trên trong Gi có ít nhất n-4 tam giác cùng màu 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 Để học sinh có thể hiểu và vận dụng được lý thuyết đồ thị vào giải toán ta có thể thực hiện các biện pháp sau: 2.3.1 Hệ thống hóa một số yếu tố trong lý thuyết đồ thị Đây là biện pháp đầu tiên và hết sức cần thiết bởi muốn học sinh vận dụng được lý thuyết đồ thị vào giải toán thì người giáo viên phải yêu cầu học sinh nhớ lại kiến thức về lý thuyết đồ thị học sinh đã được học trong bộ môn Tin học một cách tường minh. Khi học sinh nắm được vững vàng, đầy đủ và sâu sắc lý thuyết đồ thị từ đó sẽ có định hướng giải bài toán thông thường thông qua bài toán lý thuyết đồ thị tương ứng ở phần đơn vị kiến thức nào. Như vậy phải hiểu về chúng thì mới có thể biết vận dụng chúng. Việc cung cấp kiến thức về lý thuyết đồ thị cho học sinh, giáo viên có thể truyền thụ một cách tường minh hay thông báo trong quá trình dạy học từ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 56 đó để hình thành các khái niệm cho học sinh. Điều này khiến cho học sinh dễ dàng nắm bắt được khái niệm và cũng dễ tiếp cận với mối quan hệ qua lại giữa bài toán thông thường chuyển sang ngôn ngữ lý thuyết đồ thị. Ví dụ 17 : Xét các số trong tập hợp sau: { 1, 2, 3, 4, 5, 6 } với quan hệ không nguyên tố cùng nhau. Hãy biểu thị mối quan hệ đó. Giáo viên cho học sinh đặt mỗi số tương ứng với một điểm trên mặt phẳng, nếu 2 số không nguyên tố cùng nhau thì nối 2 điểm tương ứng bằng 1 cạnh. Như vậy ta có đồ thị sau (H40): Nhìn hình vẽ ta thấy ngay rằng có 4 cặp số không nguyên tố cùng nhau. Trong ví dụ này đề cập tới một số khái niệm của lý thuyết đồ thị đó là: Đồ thị, đỉnh, cạnh, bậc của đỉnh, tính liên thông,... Ví dụ 18 : Xét bài toán sau: Có thể vẽ hình phong bì thư chỉ bằng 1 nét hay không? (H41). 5 2 4 6 3 1 H40 H41 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 57 Bài toán này được mô tả trong đồ thị như sau: Gọi những nơi có phân nhánh là các đỉnh, còn các đoạn thẳng nối trực tiếp các đỉnh là cạnh của đồ thị. Với đồ thị đơn giản này ta có thể dùng cách thử và thấy có thể vẽ được như sau: Sau ví dụ này giáo viên tiếp tục nhắc lại các khái niệm đường đi, đường đi Euler và các kiến thức có liên quan. Ví dụ 19 : Phân tích số 300 thành tích các thừa số nguyên tố. Thông thường ta vẽ như sau (H43): Với cách phân tích theo sơ đồ trên cho ta mô hình về cây trong lý thuyết đồ thị qua đó giáo viên phân tích và dạy cho học sinh khái niệm về cây và những kiến thức có liên quan như mỗi quan hệ giữa số đỉnh và số cạnh… H42 5 300 50 6 2 25 3 2 5 5 300 100 3 4 25 2 2 5 H43 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 58 Sau khi học sinh hiểu được kiến thức về cây trong lý thuyết đồ thị giáo viên có thể đưa ra một vài ví dụ tương tự. Cụ thể: Hãy tìm tất cả các ước của 126 Gợi ý: Mỗi đỉnh của cây là một ước của 126 (H44). Như vậy từ những bài toán thông thường mà các em đã biết giáo viên cho các em tái hiện, hệ thống hóa lại những lý thuyết đồ thị, các khái niệm của nó và khái niệm liên quan. Từ đó giáo viên cũng có thể giới thiệu thêm các tính chất để giúp các em có thể vận dụng chúng vào làm bài tập toán. 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 3.2.1 Một số bài toán liên quan đến bậc và cạnh của đồ thị Học sinh được làm quen với khái niệm điểm và đường thẳng từ rất sớm. Đó là các yếu tố cơ bản của lý thuyết đồ thị. Như vậy với những bài toán yêu cầu tìm tất cả các đường thẳng đi qua một điểm cho trước ta có thể qui về bài toán đồ thị. Ví dụ 20: Một tổ học sinh lớp 10 chuyên toán có 11 học sinh. Buổi họp đầu tiên của tổ vào dịp đầu năm học. Bạn tổ trưởng đã phát hiện ra điều thú vị rằng 126 9 14 3 3 7 2 H44 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 59 mỗi bạn trong tổ đã quen đúng 3 bạn khác. Ngay lập tức bạn Chi đứng lên bác bỏ phát hiện đó. Vậy trong hai bạn ai nói đúng? Vì sao? Giải: Ý tưởng: Phải nhận dạng đỉnh (Đối tượng), cạnh (Quan hệ). Sau đó xét xem sẽ áp dụng được lý thuyết đồ thị như thế nào? Ta có: Đối tượng: Các bạn học sinh và cụ thể có 11 học sinh đặt tương ứng với 11 đỉnh của đồ thị. Quan hệ: có 2 quan hệ quen và không quen, vậy ta cho tương ứng: nếu hai bạn quen nhau nối 2 đỉnh tương ứng bởi 1 cạnh. Vậy từ đó ta có đồ thị tương ứng với bài toán đã cho (H45): Theo giả thiết của bài toán ta thấy mỗi học sinh đều có quan hệ quen với 3 bạn khác điều đó ứng với trong đồ thị tại mỗi đỉnh đều có cạnh nối tới 3 đỉnh khác hay tất cả các đỉnh đều có bậc 3. Vậy ta sẽ áp dụng các lý thuyết về bậc của đồ thị. 2 4 8 7 3 1 5 6 9 1 1 1 0 0 H45 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 60 Trong đồ thị đó ta thấy mỗi đỉnh của đồ thị đều có bậc là 3 (do theo bài toán mỗi bạn đều quen đúng 3 bạn ). Với số đỉnh bằng 7 thì chỉ có thể có bậc 2 và khi đó số cạnh của đồ thị là 12 cạnh. Nếu theo đúng giả thiết tất cả các đỉnh của đồ thị đều có bậc là 3 thì số cạnh của đồ thị là 33/2  N điều này vô lý. Vậy phát hiện của bạn tổ trưởng về số người quen của mỗi bạn trong tổ là không đúng, do đó bạn Chi nói đúng. Ví dụ 21: Cho 2n điểm A1, A2,..., A2n (n>1) trong không gian không có 3 điểm nào thẳng hàng. Gọi M là tập hợp gồm (n2+1) đoạn thẳng có đầu mút tại các điểm đã cho. Chứng minh rằng có ít nhất một tam giác có đỉnh tại những điểm Ar, As, At nào đó và các cạnh đều thuộc M. Chứng minh rằng nếu số phần tử của M không vượt quá n2 thì có thể không tồn tại một tam giác như vậy. Giải: Chứng minh bằng quy nạp theo n: Nếu trong đồ thị có 2n đỉnh không có ba cạnh nào lập thành một tam giác thì số cạnh của đồ thị không vượt quá n2. Mệnh đề đúng với n=1, lúc đó đồ thị có 2 đỉnh và số cạnh không vượt quá 1=n 2 . Giả sử mệnh đề đúng với n, ta chứng minh nó cũng đúng với n+1. Thật vậy, xét một đồ thị G có 2(n+1) đỉnh, trong đó không có ba cạnh nào lập thành một tam giác. Ta lấy một cạnh bất kỳ của G gọi cạnh đó là AB (H46). Mỗi đỉnh trong n đỉnh còn lại chỉ có thể nối nhiều nhất là một trong 2 đỉnh A, B (vì trong G không có tam giác nào) do đó số cạnh trong G có đỉnh tại A hoặc B nhiều nhất là 2n+1 (kể cả AB). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 61 Theo giả thiết quy nạp, đồ thị với 2n đỉnh (trong đó không có 3 cạnh nào lập thành một tam giác) có không quá n2 cạnh. Vậy đồ thị G có nhiều nhất là: 1+2n+n 2 = (n+1) 2 cạnh. Điều phải chứng minh. Trong trường hợp G có số cạnh ≤n2: Xét hai tập hợp con rời nhau M1, M2 mỗi tập này chứa không quá n phần tử. Mỗi đỉnh thuộc M1 nối với các đỉnh thuộc M2 và ngược lại (H47). Ta có đồ thị với số cạnh ≤n2 và không có ba cạnh nào lập thành một tam giác. (Điều phải chứng minh). 3.2.2 Một số bài toán liên quan đến đồ thị có hƣớng Ví dụ 22: (Thi học sinh giỏi Anh, 1972) Trên tập hợp S, cho quan hệ → giữa các cặp phần tử của S với các tính chất sau: A B H46 M1 M2 H47 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 62 1. Với mọi phần tử khác nhau a, bS có đúng một quan hệ: a→b hoặc b→a 2. Với mọi bộ ba phần tử khác nhau a, b, cS nếu có a→b và b→c thì cũng có c→a. Hỏi tập hợp S có thể chứa nhiều nhất là bao nhiêu phần tử? Giải: Xây dựng đồ thị theo dấu hiệu chung. Ta xác định 2 yếu tố đối tượng và quan hệ để xác định đồ thị mô tả lại bài toán. Đối tượng: Các phân tử của S. Quan hệ: quan hệ → giữa các cặp phần tử của S. Từ đó ta có đồ thị với các đỉnh là các phần tử của S (H37). Theo giả thiết, với bất cứ ba đỉnh a, b, c nào ta cũng có đồ thị con như trong hình 36 (a hoặc b). Ở đó mỗi đỉnh là điểm đi ra (điểm đầu) của một cung (mũi tên) và là điểm đi tới (điểm cuối) của một cung (mũi tên) khác. Từ đó, nếu có đỉnh thứ tư là d (H48) và xét ba đỉnh a, b , d thì ta phải có b→d. Nhưng nếu xét 3 đỉnh b, c, d thì ta phải có d→b, điều đó mâu thuẫn với giả thiết là có một và chỉ một trong hai quan hệ b→d hoặc d→b. Vậy S có thể có nhiều nhất là 3 phân tử. a b c a b c a b c H48 d Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 63 Ngoài các bài toán kể trên thì có nhiều bài toán mà lời giải hoặc chu trình lời giải cũng có thể biểu diễn dưới dạng đồ thị. Ví dụ như sau: Ví dụ 23: Các bước giải phương trình bậc hai: 3.2.3 Một số bài toán liên quan đến đồ thị màu Ví dụ 24: Chứng minh rằng trong không gian có 6 đường thẳng, trong đó không có 3 đường thẳng nào đồng quy tại một điểm, không có 3 đường thẳng nào đồng phẳng và không có 3 đường thẳng nào song song thì nhất định có ba đường thẳng đôi một chéo nhau. ax 2 +bx +c=0 ∆=b2 -4ac ∆>0 ∆=0 ∆<0 Phương trình có 2 nghiệm phân biệt: x1= a b 2  x2= a b 2  Phương trình có nghiệm kép: x1=x2= a b 2  Phương trình vô nghiệm Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 64 Giải: Ta sẽ chỉ ra 2 yếu tố: Đối tượng: Các đường thẳng. Quan hệ: Quan hệ đồng phẳng, quan hệ song song, quan hệ chéo nhau. Như vậy theo dấu hiệu chung đối tượng ta chọn tương ứng là đỉnh của đồ thị (có 6 đỉnh). Vì ở đây có nhiều quan hệ vậy để phân biệt các quan hệ này ta sử dụng biện pháp tô màu các cạnh của đồ thị. Ta thấy trong bài toán này chứa những mối quan hệ khác nhau, mỗi một đối tượng có quan hệ khác nhau với các đối tượng còn lại và nếu ta biểu thị quan hệ đó theo các cạnh của đồ thị thì các cạnh nối một đối tượng với các đối tượng còn lại không giống nhau, do đó ta sử dụng đồ thị tô màu các cạnh. Có thể chuyển bài toán trên về đồ thị như sau: + Coi 6 đường thẳng tương ứng là 6 điểm trong đó không có 3 điểm nào thẳng hàng. Như vậy đồ thị có 6 đỉnh tương ứng. + Các cạnh của đồ thị được xây dựng như sau: Nếu các đoạn thẳng chéo nhau thì mỗi cặp điểm tương ứng được nối với nhau bằng nét liền, còn lại thì các cặp điểm nối với nhau bằng cạnh nét đứt. Như vậy ta được một đồ thị đầy đủ gồm 6 đỉnh và các cạnh được nối bằng nét đứt hoặc nét liền. Do đó để giải quyết yêu cầu của bài toán ta chỉ cần chứng minh G có tam giác có 3 cạnh cùng dạng. Lập luận tương tự ví dụ 13 ta thấy theo điều kiện đầu bài ba đường thẳng bất kỳ đều có hai đường thẳng chéo nhau, nên tam giác tùy ý có đỉnh là các điểm đã chọn đều có ít nhất một cạnh nét liền, vậy tam giác cùng màu phải là tam giác có các cạnh nét liền. Ta suy ra ba đường thẳng tương ứng với 3 đỉnh của tam giác có các cạnh cùng dạng sẽ chéo nhau từng đôi một. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 65 3.2.4 Một số bài toán liên quan đến đƣờng đi a, Dạng 1: Bài toán tìm đường đi từ đỉnh A đến đỉnh B cho trước Với những bài toán này ta có thể áp dụng một số thuật toán sau: * Thuật toán Tarry: với 2 qui tắc - Qui tắc 1 (T1): Không bao giờ đi trở lại trên một cạnh theo cùng một chiều. - Qui tắc 2 (T2): Khi đi đến một đỉnh E (ngã ba hoặc ngã tư…) thì chỉ được chọn cạnh đã dẫn tới E lần đầu tiên khi không còn cạnh nào khác. * Qui tắc “Luật giao thông ”: Luôn đi bên phải hoặc luôn luôn đi bên trái mặt đường. b, Dạng 2: Bài toán đường đi Euler Một đường đi đơn giản từ đỉnh A đến đỉnh B và chứa mọi cạnh của G gọi là một đường đi Euler từ A đến B. Trường hợp đặc biệt A trùng với B thì ta có một chu trình Euler. Như vậy một chu trình đơn giản và chứa mọi cạnh của G được gọi là một chu trình Euler của G. Dạng bài toán vẽ hình bằng một nét liền chính là tìm chu trình Euler trong một đồ thị. Sử dụng định lý sau: Một đơn đồ thị G có một chu trình Euler khi và chỉ khi G liên thông và mọi đỉnh của nó đều bậc chẵn. Khi đó áp dụng thuật toán: Chọn đỉnh xuất phát, vạch một chu trình đơn giản p1 và đánh số tất cả các cạnh của p1. Sau đó vạch tiếp một chu trình p2 và đánh số 2 tất cả các cạnh của p2. Tiếp tục quá trình trên cho tới khi tất cả các cạnh của G đều được đánh số, sau đó đi theo qui tắc sau: mỗi khi ra khỏi đỉnh nào thì đi theo một cạnh đánh số cao nhất trong tất cả các cạnh chưa dùng. Khi đó ta được một chu trình Euler. c, Dạng 3: Bài toán đường đi Hamiltơn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 66 Đường đi sơ cấp từ A đến B qua mọi đỉnh của đồ thị (tức là đường đi qua mọi đỉnh của đồ thị và mỗi đỉnh chỉ đi qua một lần) gọi là đường đi Hamiltơn, trường hợp đặc biệt khi A trùng B ta được chu trình Hamiltơn. Để tìm đường đi Hamiltơn ta dựa vào các nhận xét và định lý: - Đường đi (chu trình) Hamiltơn phải đi qua các cạnh có đầu mút tại các đỉnh có bậc 2. - Nếu đường đi (chu trình) đã qua hai cạnh có đầu mút tại một đỉnh có bậc lớn hơn 2 thì nó không thể đi qua các cạnh khác có đầu mút tại đỉnh đó. - Định lý 1: Một đồ thị G có n đỉnh và bất kỳ hai đỉnh nào cũng có tổng các bậc không nhỏ hơn n thì G là đồ thị có chu trình Hamiltơn. - Định lý 2: Trong đồ thị có hướng đầy đủ luôn luôn tồn tại đường Hamiltơn. d, Dạng 4: Đường đi ngắn nhất. Ví dụ 25: Có 6 hộ gia đình (a, b, c, d, e, z) mắc điện. Từ a đến b mất 40m dây, từ b đến c mất 30m dây, từ c đến z mất 20m dây, từ a đến d mất 20m dây, từ d đến e mất 30m dây, từ e đến z mất 10m dây, từ b đến e mất 30m dây. Hỏi muốn mắc điện từ a đến z phải mắc qua những gia đình nào để mất chi phí dây ít nhất. z b c e d a 30 40 10 20 30 20 30 H49 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 67 Giải: Áp dụng thuật toán trên ta dễ dàng tìm được đường đi ngắn nhất từ a đến z: a, d, e, z. Với bài toán đơn giản trên ta có thể kiểm tra được bằng thử trực tiếp nhưng với bài có mạng đường đi phức tạp hơn thì việc thử được là rất khó vì khối lượng lớn. 3.2.5 Bài toán về cây Ta có thể vận dụng Lý thuyết đồ thị vào giải các bài toán đếm, tổ hợp, chỉnh hợp và xác suất. Với cách giải bằng Lý thuyết đồ thị sẽ có kết quả cụ thể liệt kê dễ hiểu. Ví dụ 26: Bốn bạn A, B, C, D đứng thành một hàng để chụp ảnh. Có bao nhiêu cách sắp xếp khác nhau. Giải: Với bài toán trên ta sử dụng kiến thức về phép đếm, tổ hợp, chỉnh hợp sẽ có ngay kết quả là 4!=24 cách sắp xếp. Tuy nhiên việc sắp xếp cụ thể ra sao thì chưa có. Chính vì vậy ta có thể sử dụng việc biểu diễn qua cây sẽ rõ ràng, tường minh và cụ thể dễ hiểu hơn, có thể liệt kê chính xác được. Kể từ trái sang phải nếu A đứng ở vị trí đầu tiên thì các cách sắp xếp các bạn được làm rõ qua cây như trong hình (H50): A C C D B B D D C B B C B D C D H50 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 68 Có 6 cách sắp xếp ABCD, ABDC, ACBD, ACDB, ADBC, ADCB. Mỗi bạn đứng ở vị trí đầu tiên thì có 6 cách sắp xếp, do đó ta có tất cả 24 cách sắp xếp khác nhau. Ví dụ 27: Trong một cuộc thi đấu bóng bàn giữa Ất và Bính, kẻ thắng là người đầu tiên thắng ba ván hoặc thắng hai ván liên tiếp. Có bao nhiêu trường hợp có thể xảy ra? Giải: Kí hiệu: A: Ất thắng B: Bính thắng Ta có sơ đồ sau: Trong sơ đồ cây (H51), số đỉnh treo trên chính là số trường hợp có thể xảy ra. Vậy có 10 trường hợp xảy ra. 3.2.6 Bài toán liên quan đến đồ thị phẳng Ví dụ 28: Bài toán ba nhà ba giếng: Ngày xưa, có ba nhà ở gần ba cái giếng, từ mỗi nhà có đường đi thẳng đến mỗi giếng (H52). Có lần bất hòa với nhau họ tìm cách làm các con đường A B A B A B B A B A A B A B A B A B H51 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 69 khác đến giếng sao cho các đường này không cắt nhau, nhưng họ không thể thực hiện được ý định đó. Vì sao? Giải: Nếu tương ứng mỗi nhà, mỗi cái giếng với một đỉnh của graph đường đi từ nhà đến mỗi giếng là một cạnh của graph. Ta được đồ thị (H52). Giả sử các con đường nối các nhà (A, B, C) và các giếng (M, N, P) không cắt nhau ở chỗ nào khác ngoài nơi đầu đường và cuối đường. Thế thì ta được một đồ thị phẳng với 6 đỉnh (m=6) và 9 cạnh (n=9). Theo định lý Euler graph có số diện tích là: d= m-n+2 = 5. Ở đây mỗi cạnh chung cho hai diện mà mỗi diện có ít nhất 4 cạnh (nếu có diện nào chỉ có 3 cạnh thì trong 3 cạnh ấy phải có một cạnh nối hai nhà hoặc hai giếng với nhau, điều này trái với giả thiết). Do đó 4d ≤ 2m 45 ≤ 29 (vô lý). Vậy ý định của các nhà là không thể thực hiện được. Đồ thị phẳng có tính chất: trong một đồ thị phẳng liên thông tùy ý luôn luôn tồn tại ít nhất một đỉnh có bậc không vượt quá 5. Thật vậy, trong đồ thị phẳng mỗi diện có ít nhất 3 cạnh. Mặt khác mỗi cạnh lại chung cho hai diện nên ta có 3.f ≤ 2m . Nếu mỗi đỉnh đều có bậc ≥ 6 thì vì mỗi cạnh có đầu mút ở hai đỉnh, nên 6  n ≤ 2m hay 3 n ≤ m .  3d + 3n ≤ 2m +m hay d+n ≤ m, trái với công thức Euler. Vậy đồ thị phẳng phải có ít nhất một đỉnh có bậc không vượt quá 5. P N M C B A H52 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 70 Như vậy trong đồ thị phẳng có một định lý rất mạnh biểu thị mối quan hệ giữa số đỉnh, số cạnh, số diện của graph đó là: n-m +d = 2 (định lý Euler). Chứng minh định lý này dựa vào tính chất của cây (một cây có n đỉnh có n-1 cạnh). Cho G là đa đồ thị liên thông có n đỉnh, m cạnh và d diện. Khi đó có thể bỏ một số cạnh của G để được một cây. Mỗi lần bỏ một cạnh (m giảm 1) thì số diện của G cũng giảm 1(d giảm 1 vì hoặc bớt đi một chu trình đơn giản, hoặc biến 2 chu trình đơn giản thành một), số đỉnh của G không thay đổi. Như vậy, giá trị của biểu thức n-m+d không thay đổi trong suốt quá trình bỏ bớt cạnh của G để được một cây. Cây này có n đỉnh, do đó có n-1 cạnh và cây luôn chỉ có một diện, vì vậy: n-m+d = n-(n-1) +2 =2 ( điều phải chứng minh). Như ta đã biết, trong toán học ngoài chứng minh tính đúng đắn còn có thể chứng minh phủ định vấn đề (chứng minh phản chứng). Qua ví dụ 28 bằng lý thuyết đồ thị đã giúp gợi ý cho giáo viên định hướng lời giải cho bài toán bằng phương pháp chứng minh phản chứng. Một cách cụ thể người giáo viên có thể giúp học sinh có được những dấu hiệu nhận dạng bài toán áp dụng đơn vị kiến thức nào của lý thuyết đồ thị. Chẳng hạn như: 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 Ở trung học cơ sở, học sinh bắt đầu làm quen với khái niệm điểm, đường thẳng. Đó là các yếu tố cơ bản của đồ thị. Như vậy với những bài toán yêu cầu tìm tất cả các đường thẳng đi qua một điểm cho trước ta có thể qui về bài toán đồ thị. Ví dụ 29: Lấy 4 điểm A, B, C, D trong đó không có 3 điểm nào thẳng hàng, kẻ các đường thẳng đi qua các cặp điểm. Có tất cả bao nhiêu đường thẳng? Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 71 Phân tích bài toán: Coi mỗi điểm A, B, C, D là một đỉnh của đồ thị, mỗi đoạn thẳng nối hai đỉnh là một cạnh của đồ thị thì số đường thẳng đi qua các cặp điểm chính là số đoạn thẳng nối hai đỉnh hay số cạnh của đồ thị. Khi đó bài toán trở thành tìm tất cả các cạnh của một đồ thị đầy đủ 4 đỉnh và sử dụng định lý: “ Trong mọi đồ thị G tổng tất cả các bậc của đỉnh là một số chẵn và bằng hai lần tổng tất cả các cạnh của G ”. Giải: Mỗi đỉnh của đồ thị có bậc là 3 Suy ra tổng số bậc của đồ thị là : 4 x 3 = 12 Suy ra tổng tất cả các cạnh của G là: 12 : 2 = 6 Vậy có 6 đường thẳng đi qua các cặp điểm. Ở THPT bên cạnh việc sử dụng lý thuyết chỉnh hợp, tổ hợp ta có thể sử dụng kiến thức về đồ thị để giải quyết một số bài toán. Ví dụ 29: Có 20 đội bóng đá tham gia thi đấu tính điểm thể lệ cuộc thi là bất kỳ hai đội nào cũng chỉ gặp nhau một lần. Hỏi phải tổ chức bao nhiêu trận đấu? Giải: Coi mỗi đội bóng là một đỉnh, do hai đội nào cũng chỉ gặp nhau một lần nên ta được đồ thị đầy đủ với 20 đỉnh. Mỗi đỉnh có bậc là 19 Suy ra tổng số bậc là: 20x19 Suy ra tổng số cạnh là: (20.19) : 2 = 190 (cạnh) Vậy phải tổ chức 190 trận đấu. Ví dụ 30: Có bao nhiêu đường chéo trong một hình thập giác lồi? Giải: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 72 Coi mỗi đỉnh của hình thập giác lồi là một cạnh của đồ thị, khi đó mỗi đỉnh có bậc là 9.  Tổng tất cả các bậc là: 10 x 9 = 90  Tổng tất cả các cạnh của đồ thị là: 90 : 2 = 45  Tổng tất cả các đường chéo của hình thập giác lồi là: 45-10=35 Bài toán tổng quát: Trong mặt phẳng cho n điểm trong đó 3 điểm phân biệt không thẳng hàng. Hỏi có bao nhiêu đường thẳng đi qua các cặp điểm? Coi n điểm là n đỉnh của đồ thị, khi đó một đường thẳng nối 2 điểm tương ứng với một cạnh của đồ thị. Bài toán quy về tính số cạnh của một đồ thị n đỉnh. Ta làm như sau: Mỗi đỉnh của đồ thị có bậc là n-1. Tổng số bậc của đỉnh là: n.(n-1).  Tổng số cạnh là: 2 )1( nn Vậy có 2 )1( nn đường thẳng đi qua các cặp điểm. Xét bài toán sau: Cho n đường thẳng đôi một phân biệt và không có 3 đường nào đồng qui. Tìm số giao điểm của n đường thẳng trên. Bài toán trên có thể giải bằng lý luận sau: cứ hai đường thẳng tạo ra một giao điểm, một đường thẳng cắt n-1 đường thẳng còn lại tạo ra n-1 giao điểm. Như vậy một giao điểm được tính 2 lần.  Số giao điểm là: 2 )1( nn Tuy nhiên nếu chuyển về ngôn ngữ đồ thị thì bài toán trở lên rất dễ hiểu: Nếu coi mỗi đường thẳng là một điểm, khi đó cạnh nối 2 điểm biểu thị giao điểm của 2 đường thẳng đó. Vậy ta chỉ việc đi tính số cạnh của đồ thị n đỉnh. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 73 Dễ thấy mỗi đỉnh có bậc là n-1. Tổng số bậc của G là n.(n-1) Tổng số cạnh của G là 2 )1( nn Vậy có 2 )1( nn giao điểm. Như ta đã biết khái niệm đa giác lồi chính là một trường hợp đặc biệt của đồ thị phẳng giúp ta dễ dàng giải quyết các yêu cầu của bài toán xung quanh các vấn đề về số cạnh, số đường chéo. Ví dụ 31: Tính số mặt của chóp ngũ giác? Ta có số đỉnh là : n=6 Tổng số bậc của đỉnh là 5+5x3 = 20 Tổng số cạnh bằng 20:2 = 10 Số mặt f = m-n+2 = 10-6+2 = 6 Trường hợp tổng quát với hình chóp có đáy là đa giác n cạnh. Ta có tổng số bậc của đỉnh là (n-1) + (n-1).3 =4.(n-1) Tổng số cạnh là: m=2(n-1) Tổng số mặt f = 2.(n-1) –n+2 = n Nhận xét: hình chóp có bao nhiêu đỉnh thì có bấy nhiêu mặt. Nhận xét: Như vậy ta có thể thấy quy trình để thực hiện việc giải một bài toán bằng phương pháp áp dụng lý thuyết đồ thị phải qua một chu trình sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 74 Vậy vấn đề chuyển từ đồ thị về bài toán thông thường được thực hiện như sau: Để học sinh hiểu rõ mối liên hệ qua lại giữa bài toán đồ thị và bài toán thông thường giáo viên hướng dẫn học sinh chuyển từ bài toán đồ thị về bài toán thông thường. Ví dụ 32: Cho đồ thị đầy đủ G với n đỉnh. Tính số cạnh của đồ thị G. Ta có thể chuyển về một số bài toán thông thường như sau: a, Cho n điểm ( n  N, n≥ 2 ) trong đó không có ba điểm nào thẳng hàng. Hỏi có bao nhiêu đường thẳng đi qua các cặp điểm? b, Cho n đường thẳng phân biệt cắt nhau và không có ba đường thẳng nào đồng qui. Tìm số giao điểm của tất cả các cặp đường thẳng. Bài toán Nhận dạng (thuộc loại đồ thị nào) Chuyển về mô hình đồ thị Giải ( bằng lý thuyết đồ thị ) chuyển kết quả giải được về kết quả phổ thông Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 75 c, Cho n mặt phẳng phân biệt đôi một phân biệt cắt nhau, trong đó không có ba mặt phẳng nào cùng thuộc một chùm. Tìm số giao tuyến của các cặp mặt phẳng. Dễ kiểm tra được 3 bài toán trên đều quy về được bài toán đồ thị ban đầu bằng cách coi mỗi một điểm ( đường thẳng hoặc mặt phẳng ) là một đỉnh của đồ thị, ta sẽ được một đồ thị đầy đủ. Và việc giải quyết bài toán là tính số cạnh của đồ thị đầy đủ đó. Từ bài toán ta có thể khai thác theo khía cạnh tính số đỉnh của đồ thị đầy đủ nếu biết số cạnh của đồ thị đó. Ví dụ 33: Cho đồ thị đầy đủ G với 300 cạnh. Tính số đỉnh của đồ thị G đó. Chuyển về bài toán thông thường như sau: Cho một số con đường đôi một cắt nhau và không có 3 con đường nào đồng quy. Các con đường tạo thành 300 ngã tư. Hỏi có tất cả bao nhiêu con đường? Thực chất việc chuyển bài toán dạng 1 về bài toán thông thường là ta đã căn cứ mối quan hệ giữa đỉnh và cạnh của đồ thị để thể hiện mối quan hệ giữa các đối tượng. Đặc biệt ta đã sử dụng định lí: “ Trong mọi đồ thị G, tổng tất cả các bậc của các đỉnh là một số chẵn, bằng hai lần tổng tất cả các cạnh của G” để giải quyết bài toán đồ thị dạng trên. Ví dụ 34: Xét bài toán đồ thị sau: “ Cho đồ thị đầy đủ G với 6 đỉnh và các cạnh được tô hai màu xanh đỏ. Chứng minh bao giờ cũng tìm được một tam giác có các cạnh cùng màu”. Ta đưa về bài toán thông thường như sau: a, Chứng minh rằng trong 6 góc nhọn bao giờ cũng tìm được 3 góc nhọn 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 76 b, Chứng minh rằng trong không gian có 6 đường thẳng trong đó không có ba đường thẳng nào đồng quy tại một điểm, không có đường thẳng nào đồng phẳng và không có 3 đường thẳng nào song song thì nhất định có 3 đường thẳng đôi một chéo nhau. c, Sáu đội bóng tham gia đợt thi đấu. Mỗi đội gặp từng đội khác đúng một trận. Chứng minh rằng vào bất kỳ thời điểm nào cũng có ba đội, mà hoặc các đội đã gặp nhau từng đôi một hoặc chưa thi đấu với nhau trận nào. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 77 Chƣơng III THỰC NGHIỆM SƢ PHẠM 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 - Kiểm nghiệm tính khả thi của việc áp dụng lý thuyết đồ thị vào dạy học giải toán cho học sinh chuyên Tin ở trường THPT và hiệu quả của nó. - Tìm hiểu khả năng triển khai của đề tài trong thực tiễn giáo dục hiện nay ở Việt Nam. 3.1.2. Nhiệm vụ thực nghiệm - Đưa ra một hệ thống bài tập thể hiện việc sử dụng lý thuyết đồ thị vào giải. - Đưa ra đề kiểm tra và đáp án để kiểm tra quá trình vận dụng lý thuyết đồ thị của học sinh chuyên Tin và một số lớp chuyên khác được dạy giải toán bằng lý thuyết đại số tổ hợp để đối chứng. - Phân tích kết quả thực nghiệm. 3.1.3. Nguyên tắc thực nghiệm - Đảm bảo kiến thức cơ bản của chương trình THPT. - Phù hợp với đối tượng học sinh. - Trình độ nhận thức toán học của lớp thực nghiệm và lớp đối chứng tương đương nhau. - Kết quả thực nghiệm phải được xử lý một cách khách quan, khoa học. 3.1.4. Nội dung thực nghiệm Nội dung dạy học là phạm vi kiến thức toán lớp 10 chương trình chuyên. 3.1.5. Đối tƣợng thực nghiệm Học sinh 10 chuyên tin và học sinh lớp 10 chuyên toán trường THPT Chuyên Thái Nguyên. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 78 3.2. Hình thức và kế hoạch tiến hành thực nghiệm 3.2.1 Hình thức: Ta tiến hành dạy ngoại khoá cho hai lớp 10 chuyên tin và 10 chuyên toán. Với số tiết học bằng nhau, cùng một hệ thống bài tập. Trong đó lớp 10 chuyên tin học lý thuyết đồ thị và vận dụng nó vào giải bài tập còn lớp 10 chuyên toán vận dụng lý thuyết đại số tổ hợp vào giải bài tập. Kiểm tra trên đối tượng lớp thực nghiệm là lớp chuyên Tin 10 và lớp đối chứng là toán 10. Cả 2 lớp chuyên này đều có điểm trung bình môn toán tương đương nhau về các tỷ lệ điểm giỏi, khá, trung bình. Về kiến thức môn toán cũng được truyền thụ chung một chương trình. - Tiến hành kiểm tra trên lớp thực nghiệm và lớp đối chứng với nội dung thực nghiệm như sau: + Ra đề bài tập kiểm tra với nội dung trong chương trình chuyên 10 trong đó vừa có thể áp dụng lý thuyết đồ thị để giải và cũng có thể vận dụng lý thuyết tổ hợp để giải. + Đối tượng làm bài học sinh lớp 10 chuyên Tin và học sinh lớp 10 chuyên toán. - Các lớp thực nghiệm và lớp đối chứng đều kiểm tra cùng một đề, các bài kiểm tra được chấm cùng một biểu điểm. 3.2.2. Kế hoạch tiến hành thực nghiệm - Chuẩn bị tài liệu thực nghiệm: Soạn đề bài tập kiểm tra, làm đáp án và biểu điểm chi tiết, phiếu học tập. - Tổ chức kiểm tra thực nghiệm và kiểm tra đối chứng. - Đánh giá sơ bộ. - Điều chỉnh, bổ sung (nếu có), đánh giá tổng hợp kết quả thực nghiệm. - Thời gian tiến hành thực nghiệm sư phạm: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 79 3.3. Đánh giá kết quả thực nghiệm 3.3.1. Về nội dung tài liệu thực nghiệm Hệ thống các phương pháp được đề cập đến trong tài liệu về việc vận dụng lý thuyết đồ thị vào giải toán đã giúp cho học sinh có thêm một phương pháp mới vận dụng giải toán. Nội dung của tài liệu thực nghiệm có những ý nghĩa nhất định. Thông qua các bài kiểm tra đánh giá chúng tôi nhận thấy: Việc sử dụng các kiến thức về lý thuyết đồ thị vào giải toán đã giúp học sinh giải quyết được những lớp bài toán đặc biệt là các bài toán khó thi học sinh giỏi. Giải bài toán bằng phương pháp này dễ hiểu và cũng dễ dàng nhìn nhận được hướng giải quyết. 3.3.2. Về phƣơng pháp tiến hành kiểm tra - Với mục tiêu là cung cấp thêm cho học sinh ngày càng nhiều phương pháp để giải quyết các bài toán, giúp học sinh phát triển tư duy. - Giúp học sinh thấy được mối quan hệ qua lại giữa các môn học, thấy được sự hỗ trợ của môn này đối với môn khác để có được ý thức học đều tất cả các môn học. - Nội dung các phiếu học tập do các em thực hiện cho các kết quả khả quan và các em sẽ tự so sánh được kết quả học tập của hai lớp, việc phân tích các kết quả này giúp các em hiểu hơn về ý nghĩa của các nội dung kiến thức. 3.3.3. Về kết quả kiểm tra thực nghiệm Sau đợt thực nghiệm, thông qua việc cho học sinh làm bài kiểm tra trong 45 phút đối với các lớp 10 chuyên Tin và lớp 10 chuyên toán: - Về mặt định tính: Thái độ làm bài của học sinh nghiêm túc, ý thức tốt, tập trung cao. a) Đề kiểm tra 45 phút: Mục tiêu cần đạt: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 80 Đề bài: Mức độ Câu Nhận biết Thông hiểu Vận dụng Tổng TNKQ TL TNKQ TL TNKQ TL 1 1đ 2đ 3đ 2 1đ 2đ 3đ 3 1đ 1đ 2đ 4đ Tổng 1đ 3đ 6đ 10đ Đề bài: Câu 1: Chứng minh rằng trong 9 số nguyên dương tuỳ ý mà 3 số bất kỳ đều có 2 số nguyên tố cùng nhau luôn luôn tìm được 4 số nguyên tố cùng nhau (từng cặp nguyên tố cùng nhau). Câu 2: Để mừng người con đoạt giải trong kỳ thi Toán Quốc tế lần thứ 48, một gia đình dự định mời bạn đến dự tiệc. Trong số khách mời: A, Người vợ muốn có ít nhất 3 người từng đôi một quen nhau. Người chồng lại muốn có ít nhất 4 người từng đôi một chưa quen nhau. Hỏi họ phải mời ít nhất bao nhiêu bạn để ít nhất mong muốn của chồng hoặc của vợ được thoả mãn? Câu 3: Cho tập hợp n>3 điểm trong mặt phẳng, trong đó không có 3 điểm nào thẳng hàng và một số tự nhiên k < n. Chứng minh các mệnh đề sau đây: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 81 1. Nếu k≤n/2 thì từ mỗi điểm của tập hợp đã cho ta có thể vẽ các đoạn thẳng nối với ít nhất k điểm khác sao cho trong các đoạn thẳng đó không có ba cạnh của một tam giác. 2. Nếu k > n/2 và mỗi điểm của tập hợp đã cho được nối bằng những đoạn thẳng với k điểm khác thì trong các đoạn thẳng đó bao giờ cũng có ba cạnh của một tam giác. Đáp án: Câu 1 + câu 2 (6 điểm): Áp dụng tính chất trong lý thuyết đồ thị: “ Đồ thị gồm 9 đỉnh với 2 màu cạnh xanh, đỏ luôn luôn hoặc có tam giác xanh hoặc tứ giác mà các cạnh và các đường chéo đều màu đỏ”. Nếu đồ thị đầy đủ chỉ gồm 8 đỉnh thì không còn đúng nữa. Câu 3 (4 điểm): Chứng minh bằng quy nạp theo n. b) Dụng ý sư phạm: Bài kiểm tra được thực hiện sau khi học sinh hai lớp 10 chuyên toán và tin học xong đợt học ngoại khoá. Cùng một hệ thống bài tập, với số giờ ngoại khoá là như nhau và so sánh khả năng giải lớp bài toán này trên hai lớp đó. a) Kết quả bài kiểm tra như sau: Lớp Kết quả kiểm tra (điểm) Dưới 5 5 6 7 8 9 10 Tin 10 0% 0% 10,1% 24% 24,1% 14,5% 27,3% Toán 10 0% 46% 15,3% 27% 11,7% 0% 0% Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 82 d) Đánh giá sơ bộ về khả năng lĩnh hội kiến thức của học sinh lớp 10 chuyên tin. - Học sinh nắm được nội dung các kiến thức về lý thuyết đồ thị đã học, biết vận dụng nó để giải các bài tập cụ thể, tuy nhiên còn một số học sinh còn mắc sai lầm khi xác định cạnh thông qua việc xác định quan hệ ở một số bài toán phức tạp. - Biết vận dụng lý thuyết đồ thị vào bài giải của mình, trình bày lời giải rõ ràng . Điều đó thể hiện tính tích cực của tư duy và thể hiện năng lực nắm chắc bài học của các em. - Tỷ lệ % ở bài kiểm tra đối với 2 lớp tin 10 và toán 10 cho thấy kết quả ở lớp chuyên tin cao hơn nhiều vì có được hệ thống kiến thức lý thuyết đồ thị biết áp dụng nó vào bài toán đã cho, còn đối ví lớp chuyên toán bằng sự thông minh và sử dụng lý thuyết đại số tổ hợp để giải tuy nhiên không đạt được hiệu quả cao. Như vậy các lớp thực nghiệm và các lớp đối chứng cho thấy học sinh các lớp thực nghiệm có bước tiến rõ rệt trong việc nắm chắc các nội dung đã học, có kỹ năng giải quyết bài toán tốt hơn. Điều đó phản ánh hệ thống phương pháp sư phạm trong khi được sử dụng trong khi giảng dạy nội dung phương pháp vận dụng lý thuyết đồ thị vào giải toán có tác động tích cực đến việc phát huy tính tích cực của học sinh, nâng cao một bước hiệu quả dạy học giải toán ở trường phổ thông. Với lớp thực nghiệm việc áp dụng lý thuyết đồ thị vào giải bài tập toán đã giúp các em lập trình, cài đặt bài tập liên quan đến đồ thị tốt hơn vì đã làm tốt bước chuyển bài tập sang dạng đồ thị. 4. Kết luận chung về thực nghiệm sƣ phạm Kết quả khả quan bước đầu trong đợt thực nghiệm sư phạm theo định hướng trên đã cho phép chúng tôi đưa ra nhận xét: Chúng ta hoàn toàn có thể Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 83 vận dụng được lý thuyết đồ thị vào dạy học giải toán cho lớp chuyên tin ở trường THPT chuyên đem lại những kết quả tích cực hơn bằng việc khai thác triệt để mối quan hệ qua lại giữa toán và tin, phát huy được khả năng tư duy, cung cấp thêm một phương pháp giải toán cho học sinh khá giỏi khi làm toán. Tin học đóng vai trò không nhỏ giúp học sinh có hướng nhìn rộng hơn trong việc tìm lời giải cho các bài toán. Một cách cụ thể lý thuyết đồ thị đã giúp học sinh giải quyết được một lớp các bài toán. Trong tin học các lý thuyết đồ thị thường được cài đặt dưới dạng ma trận nên học sinh có cảm giác “rời rạc”. Tuy nhiên thông qua dạy toán “kiểu” lý thuyết đồ thị giúp học sinh có nhìn tổng quan, liên hoàn của nó. Những nghiên cứu lý luận và thực nghiệm đã chứng tỏ rằng giả thiết khoa học mà đề tài đã đề ra là chấp nhận được. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 84 MỘT SỐ ĐỀ BÀI TẬP Bài 1 Có 18 điểm khác nhau trong mặt phẳng, từng đôi một được nối với nhau bởi những đoạn thẳng màu đỏ hoặc màu xanh. Chứng minh rằng có một tứ giác mà các cạnh và các đường chéo đều cùng màu. Bài 2 Có 17 nhà bác học, mỗi người trao đổi thư từ với 16 người khác. Trong thư, họ chỉ bàn về ba đề tài, nhưng bất cứ hai nhà bác học nào cũng chỉ bàn với nhau chỉ về một đề tài. Chứng minh rằng có không ít hơn ba nhà bác học đã bàn với nhau về cùng một đề tài. (Đề thi toán quốc tế lần thứ VI, 1964) Bài 3 Cho hình vẽ gồm 16 đoạn thẳng. Chứng minh rằng không thể vạch một đường cong cắt mỗi đoạn thẳng đó vừa đúng một lần (đầu mút cả đường cong không được nằm trên các đoạn thẳng và đường cong không được đi qua đỉnh của các đoạn thẳng). (Đề thi học sinh giỏi toán toàn Nga, lần thứ nhất, 1961) Bài 4 Một cơ quan cần tuyển ba người để lập thành một nhóm có đủ năng lực biên dịch các tài liệu từ 6 thứ tiếng Anh, Pháp, Nga, Đức, Trung Quốc và Bồ Đào Nha sang tiếng Việt. Có 7 người đến dự tuyển, trong đó mỗi người đều Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 85 biết 2 và chỉ 2 trong 6 thứ tiếng đó và bất cứ hai người nào cũng cùng biết nhiều nhất một thứ tiếng chung trong 6 thứ tiếng đó. Biết rằng thứ tiếng nào cũng có ít nhất hai người biết. Hỏi có thể xảy ra trường hợp không thể tuyển chọn được như yêu cầu đã nêu không, tại sao? (Đề thi học sinh giỏi toán lớp 11 của Hà Nội năm học 1987 – 1988) Bài 5 Ở một làng nọ có 10 người dân, mỗi người có 3 người quen. Ngày 1 – 1, một người dân biết một tin lạ và báo cho 3 người quen mình. Ngày 2-1, những người quen này lại báo tin cho tất cả những người quen mình… Có thể xảy ra trường hợp ngày 5-3 thì còn một số dân làng chưa biết tin tức đó, nhưng đến ngày 1-3 thì nọ người đều đã biết tin. (Thi học sinh giỏi Matscơva, 1978) Bài 6 Có 1982 người, trong đó bất kỳ 4 người nào cũng có ít nhất 1 người quen với 3 người kia. Vậy trong 1982 người đó, có ít nhất là bao nhiêu người từng đôi một quen nhau? (Thi học sinh giỏi Mỹ, 1982) Bài 7 a) Trong phòng có 10 người, trong đó bất kỳ 3 người nào cũng có 2 người quen nhau. Chứng minh rằng có 4 người từng đôi một quen nhau. (Thi học sinh gỏi Anh, 1980) b) Nếu trong phòng có 9 người thì kết luận trên đây có còn đúng không? (Theo đề dự tuyển thi toán quốc tế 1977, do Balan đề nghị) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 86 Bài 8 Cho n>2 điểm trên đường tròn, từng cặp điểm được nối bằng một đoạn thẳng. Có thể nào vạch được một cách nhanh chóng tất cả các đoạn thẳng đó sao cho điểm cuối của đoạn thẳng thứ nhất trùng với điểm đầu của đoạn thẳng thứ hai, điểm cuối của đoạn thẳng thứ hai trùng với điểm đầu đoạn thẳng thứ ba…và điểm cuối của đoạn thẳng cuối cùng trùng với điểm đầu của đoạn thẳng đầu tiên. (Thi học sinh giỏi Balan, 1964 – 1965) Bài 9 Cho G là một đồ thị liên thông gồm k cạnh. Chứng minh rằng có thể đánh số các cạnh bằng tất cả các số 1, 2, …, k sao cho tại mỗi đỉnh mà ở đó có ít nhất hai cạnh của đồ thị, ta đều có ước chung lớn nhất của các số nguyên viết trên các cạnh của đỉnh này bằng 1. (Thi toán quốc tế lần thứ 32, 1991) Bài 10 Cho n điểm trong không gian trong đó không có 4 điểm nào đồng phẳng. Tất cả những điểm này được nối nhau từng cặp bằng các đoạn thẳng. Mỗi đoạn thẳng được tô màu xanh hoặc màu đỏ hoặc không tô màu. Tìm giá trị nhỏ nhất của n sao cho với mọi cách tô màu tồn tại một tam giác có các cạnh cùng màu. (Thi toán quốc tế lần thứ 33, 1992) Bài 11 Cho 6 điểm trong mặt phẳng sao cho bất kỳ 3 điểm nào cũng là đỉnh của một tam giác có các cạnh có chiều dài khác nhau. Chứng minh rằng cạnh nhỏ nhất của một trong các tam giác đó đồng thời là cạnh lớn nhất của một tam giác khác. (Thi học sinh giỏi Ba Lan, 1976) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 87 Bài 12 Cho 6 đường thẳng trong không gian, trong đó không có 3 đường thẳng nào song song, không có 3 đường thẳng nào đồng quy và không có 3 đường thẳng nào cùng nằm trong một mặt phẳng. Chứng minh rằng từ 6 đường thẳng đó bao giờ cũng lấy ra được 3 đường thẳng từng đôi một chéo nhau. (Thi học sinh giỏi Ba Lan, 1970) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 88 KẾT LUẬN ĐỀ TÀI Qua quá trình nghiên cứu đề tài đã nhận được một số kết quả sau: 1. Hệ thống hoá các khái niệm cơ bản của lý thuyết đồ thị. 2. Chỉ ra dấu hiệu nhận dạng bài tập có thể áp dụng lý thuyết đồ thị để giải. 3. Đưa ra được quy trình để chuyển đổi từ bài toán thông thường sang ngôn ngữ lý thuyết đồ thị. 4. Đưa ra được các phương án vận dụng. 5. Đề xuất một số biện pháp để giúp học sinh hình thành, rèn luyện khả năng vận dụng lý thuyết đồ thị vào giải toán. 6. Lựa chọn được một hệ thống các ví dụ điển hình cho học sinh giải quyết. Nhiệm vụ nghiên cứu đã hoàn thành, giả thuyết khoa học được sáng tỏ Hướng phát triển của đề tài: Tiếp tục nghiên cứu vận dụng lý luận và kết quả của lý thuyết đồ thị và việc bồi dưỡng học sinh giỏi toán, tin.