Thạc Sĩ 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

MỤC LỤC
MỞ ĐẦU 1
I. Lý do chọn đề tài 1
II. Mục đích nghiên cứu 2
III. Nhiệ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
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ữngnộidung cơbảncủalý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
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 : 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