Thạc Sĩ Lý thuyết đồ thị với các bài toán phổ thông

LỜI NÓI ĐẦU
Lý thuyết đồ thị là một trong những ngành khoa học ra đời khá sớm. Lý thuyết đồ thị giúp mô tả hình học và giải quyết nhiều bài toán thựctế phức tạp. Khái niệm lý thuyết đồ thị được nhiều nhà khoa học độc lập nghiêncứu và có nhiều đóng góp trong lĩnh vực toán học ứng dụng. Năm 2001, Bộ Giáo Dục và Đào Tạo có quy định các chuyên đề bồi dưỡng học sinh giỏi thống nhất trên toàn quốc, trong đó có chuyên đề lý thuyết đồ thị. Như vậy, việc học chuyên đề Lý Thuyết Đồ Thị đối với học sinh khá và giỏi đang là nhu cầu thực tế trong dạy học toán ở phổthông. Tuy nhiên, việc dạy học chuyên đề này còn tồn tại một số khókhăn vì những lý do khác nhau. Một trong các lý do đó là sự mới mẻ, độc đáo và khó của chủ đề kiến thức này.

Luận văn "Lý thuyết đồ thị với các bài toán phổ thông" đưa đến sự sáng tạo trong cách nhìn nhận bài toán và lập luận cách giải dưới con mắt của lý thuyết đồ thị.
Ngoài phần mở đầu và kết luận luận văn gồm 3 chương:
Chương 1 Đại cương về đồ thị.
Chương 2 Một số bài toán đồ thị cơ bản.
Chương 3 Ứng dụng lý thuyết đồ thị vào giải toán phổ thông.
Luận văn được hoàn thành dưới sự hướng dẫn, giúp đỡ tận tình của GS.TS Đặng Huy Ruận, tác giả xin bày tỏ sự kính trọng và lòng biết ơn sâu sắc tới thầy.
Tác giả cũng xin gửi lời cảm ơn chân thành đến Ban giám hiệu cùng các thầy cô giáo khoa Toán - Cơ - Tin, Trường Đại học Khoa Học Tự Nhiên
- Đại Học Quốc Gia Hà Nội đã tạo điều kiện, dạy bảo và dìu dắt tác giả trong những năm học vừa qua.
Xin chân thành cảm ơn sự giúp đỡ của bạn bè, người thân trong thời gian học tập và làm luận văn.
Do khả năng nhận thức của bản thân tác giả, luận văn còn nhiều hạn chế, thiếu sót. Tác giả kính mong các ý kiến chỉ bảo của quý thầy cô cùng sự đóng góp của các bạn đọc.

Mục lục
Lời nói đầu 3
1 Đại cương về đồ thị 4
1.1 Định nghĩa đồ thị 4
1.2 Một số dạng đồ thị đặc biệt 6
1.3 Bậc của đỉnh đồ thị . 8
1.3.1 Bậc của đỉnh 8
1.3.2 Nửa bậc . 8
1.3.3 Một số tính chất 9
1.4 Xích, chu trình, đường, vòng 13
1.4.1 Xích, chu trình . 13
1.4.2 Đường, vòng . 14
1.4.3 Một số tính chất 15
1.5 Đồ thị liên thông 16
1.5.1 Định nghĩa . 16
1.5.2 Tính chất 17
1.6 Số ổn định trong, số ổn định ngoài 18
1.6.1 Số ổn định trong 18
1.6.2 Số ổn định ngoài 19
1.6.3 Các thuật toán tìm số ổn định trong, số ổn định
ngoài . 20
1.7 Nhân của đồ thị và ứng dụng vào trò chơi 21
1.7.1 Định nghĩa . 21
1.7.2 Tính chất 22
1.7.3 Trò chơi Nim 23
1.7.4 Trò chơi bốc các vật 24
1.8 Cây và bụi 29
1.8.1 Định nghĩa . 29
1.8.2 Đặc điểm của cây và bụi 30
1
2 Một số bài toán đồ thị cơ bản 33
2.1 Bài toán về đường đi 33
2.1.1 Đường đi Euler - Chu trình Euler 33
2.1.2 Đường đi Hamilton - Chu trình Hamilton . 40
2.2 Bài toán tô màu đồ thị . 43
2.2.1 Định nghĩa . 43
2.2.2 Một số tính chất 43
2.2.3 Thuật toán tô màu đỉnh . 53
3 Ứng dụng lý thuyết đồ thị vào giải toán phổ thông. 54
3.1 Quy trình giải bài toán bằng phương pháp đồ thị . 54
3.1.1 Xây dựng đồ thị G mô tả các quan hệ . 54
3.1.2 Dựa vào các kết quả của lý thuyết đồ thị hoặc lý
luận trực tiếp suy ra đáp án của bài toán D 54
3.2 Bài toán về đỉnh - cạnh của đồ thị . 55
3.3 Bài toán về xích, chu trình, đường, vòng và tính liên thông
của đồ thị 58
3.4 Bài toán về tô màu đồ thị . 63
3.5 Bài toán liên quan đến số ổn định trong, số ổn định ngoài. 74
3.6 Bài toán liên quan đến đường đi 76
3.6.1 Bài toán tìm đường đi trong mê cung . 76
3.6.2 Bài toán liên quan đến đường và chu trình Euler . 80
3.6.3 Bài toán liên quan đến đường và chu trình Hamilton 82
3.7 Bài toán liên quan đến cây . 84
Kết luận 89
Tài liệu tham khảo 90