Luận văn 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

đầ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 ứng bởi 3 cạnh. Tam giác có các cạnh cùng loại là tam giác có 3 cạnh cùng là nét liền hoặc là nét đứt với cách xác định ở trên). Thật vậy, mỗi đỉnh của đồ thị là đầu mút của 5 cạnh, vì mỗi cạnh có thể là nét đứt hoặc nét liền nên mỗi đỉnh của G phải là đầu mút của ít nhất 3 cạnh cùng dạng. Giả sử đỉnh A là đầu mút của 3 cạnh nét liền AB, AC, AD. Xét 3 cạnh BC, BD, CD: - Nếu có ít nhất 1 cạnh nét liền, thí dụ là BD thì ∆ABC có các cạnh cùng là nét liền. - Nếu không có cạnh nào là nét liền, tức là cả 3 cạnh nét đứt thì ∆BCD là tam giác có 3 cạnh cùng dạng. Như vậy trong mọi trường hợp ta đều có một tam giác có các cạnh cùng loại. Tuy nhiên tùy mối quan hệ trong từng bài đã cho mà xác định đầy đủ và chính xác tương ứng giữa các đỉnh (hoặc các cạnh) khi chuyển về bài toán đồ thị màu. Chẳng hạn với mối quan hệ A quen B, B quen C thì chưa chắc A D C B A D C B A D C B A H26 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 43 đã quen C nên khi đó nếu tô màu đỏ biểu thị mối quan hệ quen biết thì AB đỏ, BC đỏ nhưng chưa chắc AC đỏ. Nhưng nếu A nói cùng thứ tiếng α với B, B nói cùng thứ tiếng α với C thì suy ra A nói cùng thứ tiếng α với C. Tức nếu AB đỏ, BC đỏ suy ra AC đỏ. 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 2.2.1 Vai trò và định hƣớng của dạy học giải bài tập 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 đượ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. 2.2.2 Quy trình Polya trong giải bài tập 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. + 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. + 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 liên quan. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 44 + 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ước 1: Ta có thể cho học sinh phát biểu bài toán theo ngôn ngữ lý thuyết đồ thị và tìm hiểu rõ bài tập đã cho. Bước 2: Vận dụng kết quả của lý thuyết đồ thị để tìm và dự đoán kết quả của bài toán. Bước 4: Nghiên cứu sâu lời giải bằng cách chuyển về bài toán ở dạng lý thuyết đồ thị. Vậy trên cơ sở lý luận đó ta có thể chỉ ra 3 phương án khai thác lý thuyết đồ thị trong giải bài tập. 2.2.3 Phƣơng án 1 (khai thác lý thuyết đồ thị ở bƣớc 1) Thực hiện chuyển bài toán gốc sang bài tập dạng đồ thị sau đó giải bài tập bằng lý thuyết đồ thị và dùng kết quả đó để khẳng định luôn kết quả của bài toán gốc. Ví dụ 14: Cho n là số nguyên dương và A1, A2, ..., A2n+1 là 2n+1 tập hợp con của tập hợp B. Giả sử các tính chất sau đây được thực hiện: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 45 a. Mỗi tập hợp Ai (i=1, 2, ..., 2n+1) chứa đúng 2n phần tử; b. Với mỗi cặp (i, j), 1 ≤ i < j ≤ 2n+1, Ai∩Aj chứa đúng một phần tử; c. Mỗi phần tử của B thuộc ít nhất hai tập hợp Ai (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 đỏ. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 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 r