nhOx_hon3y
New Member
[Free] 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
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ữ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
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
Để tải bản DOC Đầy Đủ thì Trả lời bài viết này, mình sẽ gửi Link download cho
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 hay 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 hay đồ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 hay 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...
Download 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 miễn phí
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ữ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
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
Để tải bản DOC Đầy Đủ thì Trả lời bài viết này, mình sẽ gửi Link download cho
Tóm tắt nội dung:
đầ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 hay 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 hay đồ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 hay 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...