Luận văn thạc sĩ lý thuyết đồ thị với các bài toán phổ thông - Lê Thị Thu Hiền

Đại học Quốc gia Hà Nội Trường Đại học Khoa học Tự nhiên Lê Thị Thu Hiền LÝ THUYẾT ĐỒ THỊ VỚI CÁC BÀI TOÁN PHỔ THÔNG Chuyên ngành : Phương pháp toán sơ cấp Mã số : 60.13 Người hướng dẫn khoa học: GS. Đặng Huy Ruận Hà Nội- 2013 TIEU LUAN MOI download : skknchat@gmail.com Mục lục Mở đầu 4 1 Lý thuyết đồ thị 5 1.1 Các khái niệm cơ bản.2 Bậc của đồ thị.3 Xích, chu trình, đường, vòng .4 Đồ thị liên thông .5 Sắc số và đồ thị tô màu .6 Số ổn định trong, số ổn định ngoài .7 Nhân của đồ thị và ứng dụng vào trò chơi. 26 2 Khai thác lý thuyết đồ thị vào giải toán trung học phổ thông 30 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 Bài toán liên quan đến đồ thị có hướng.3 Bài toán liên quan đến đồ thị màu .4 Bài toán có liên quan đến bậc và cạnh của đồ thị.5 Bài toán liên quan đến đường đi.6 Bài toán liên quan đến đồ thị liên thông.7 Bài toán liên quan đến cây. 60 Kết luận 72 Tài liệu tham khảo 73 2 TIEU LUAN MOI download : skknchat@gmail.com Mở đầu Phương pháp lý thuyết đồ thị là môn khoa học có tính khái quát cao giúp nghiên cứu và tối ưu các mối liên hệ giữa các đỉnh, nút, cạnh hoặc cung để chuyển thành phương pháp giải bài toán.

Đặc biệt là đối với trung học phổ thông phương pháp đồ thị giải được nhiều bài toán hay và bổ ích. Vận dụng lý thuyết đồ thị vào giải bài tập cho học sinh sẽ giúp rèn luyện năng lực hệ thống hóa kiến thức và thúc đẩy quá trình sáng tạo cũng như quá trình tự học nghiên cứu trong mỗi học sinh. Qua các bài toán sơ cấp logic, lý thuyết đồ thị giúp phân tích các yếu tố, cấu trúc, đưa ra cách chọn lựa hợp lý cho từng trường hợp và bài toán. Lý thuyết đồ thị phát triển trong khoảng hơn 1 thế kỉ trước.

Đánh dấu sự xuất hiện của lý thuyết đồ thị chính là kết quả ứng dụng của nó vào năm 1736 trong bài báo của Leonhard Euler về “Bảy cây cầu Euler”. Cho đến ngày nay nó mang lại nhiều ứng dụng quan trọng trong khoa học, kĩ thuật như : Tin học, vật lý, hóa học, mạng lưới giao thông, điều khiển học, cấu trúc máy tính,. Để hiểu sâu hơn về lý thuyết đồ thị và phương pháp này, trước hết cần nắm bắt được tính chất cơ bản của đồ thị : Đồ thị là một tập các đối tượng được gọi là các đỉnh (hoặc nút) nối với nhau bởi các cạnh (hoặc cung). Cạnh có thể có hướng hoặc vô hướng.

Đồ thị thường được vẽ dưới dạng một tập các điểm (các đỉnh nối với nhau bằng các đoạn thẳng (các cạnh). Đồ thị biểu diễn được rất nhiều cấu trúc. Nhiều bài toán thực tế có thể biểu diễn bằng đồ thị. Do vậy, sự phát triển của các thuật toán xử lý đồ thị là một trong các mối quan tâm chính của phương pháp đồ thị.

Ngoài ra, Cấu trúc đồ thị có thể được mở rộng bằng cách gán trọng số cho mỗi cạnh. Có thể sử dụng đồ thị có trọng số để biểu diễn nhiều khái niệm khác nhau. Luận văn : “Lý thuyết đồ thị với các bài toán trung học phổ thông” nghiên cứu cấu trúc bài toán được biểu diễn bằng đồ thị, đưa ra các phương pháp nhận dạng bài toán và phát triển năng lực vận dụng lý thuyết đồ thị vào giải bài tập toán. Đồng thời làm nổi bật các ưu thế của lý thuyết đồ thị qua bài toán ứng dụng thực tế.

Cấu trúc luận văn Luận văn gồm phần mở đầu và ba chương. Chương 1 : Giới thiệu nội dung của lý thuyết đồ thị, các khái niệm, định lý, tính chất hệ quả được chứng minh. Chương 2 : Tập trung khai thác lý thuyết đồ thị vào giải toán trung học phổ 3 TIEU LUAN MOI download : skknchat@gmail.com thông qua các dạng bài toán cụ thể. Đưa ra phương pháp giải dạng toán liên quan đến đồ thị, đồ thị tô màu, đồ thị liên thông, cây, bậc, đường đi cùng bài toán tổng hợp.

Chương 3 : Hướng dẫn giải một số bài toán có thể quy về phương pháp đồ thị, và một số bài toán áp dụng. Luận văn được hoàn thành dưới sự hướng dẫn khoa học của GS. Đặng Huy Ruận, trường Đại học Khoa học Tự Nhiên, Đại học Quốc gia Hà Nội, người Thầy đã tận tình giúp đỡ tác giả trong quá trình nguyên cứu và soạn thảo luận văn này. Tác giả xin bày tỏ lòng biết ơn chân thành và kính trọng sâu sắc tới Giáo sư.

Hà Nội, tháng 9 năm 2013 Tác giả Lê Thị Thu Hiền 4 TIEU LUAN MOI download : skknchat@gmail.com Chương 1 Lý thuyết đồ thị 1.1 Các khái niệm cơ bản. Định nghĩa đồ thị và các yếu tố liên quan. + Tập hợp X 6= ∅ các đối tượng tùy ý và bộ E các cặp được sắp thứ tự và không được sắp thứ tự các phần tử của X được gọi là một đồ thị, đồng thời được kí hiệu hoặc bằng G(X, E) hoặc bằng G = (X, E) hoặc bằng G(X). Các phần tử của tập X được gọi là các đỉnh còn các phần tử của tập E được gọi là các cạnh của đồ thị G.

Hình ảnh về đồ thị: Trong (H1) có: Tập đỉnh là X = {2, 3, 5, 6, 7, 10} Tập cạnh là E = {(2, 3), (2, 7), (3, 5), (3, 7), (3, 10), (6, 5), (6, 7), (7, 5), (7, 10)} + Cặp đỉnh không sắp thứ tự a = (x, y) được gọi là cạnh hay cạnh vô hướng, còn x, y được gọi là các đỉnh đầu của cạnh a; cặp đỉnh được sắp thứ tự b = (u, v) được gọi là cạnh có hướng hay cung. Đỉnh u được gọi là đỉnh đầu, còn đỉnh v được gọi là đỉnh cuối của cung b. Người ta còn nói rằng: cung b đi từ đỉnh u đến đỉnh v. 5 TIEU LUAN MOI download : skknchat@gmail.com Trong hình (H2) có: Tập cạnh là (3, 5), (5, 7), (7, 10) Cung là (3,10), trong đó 3 là đỉnh đầu, 10 là đỉnh cuối.

+ Đồ thị chỉ chứa các cạnh được gọi là đồ thị vô hướng. Đồ thị chỉ chứa các cung gọi là đồ thị có hướng. Nếu đồ thị chứa cả cạnh lẫn cung, thì gọi là đồ thị hỗn hợp hay đồ thị hỗn tạp. + Một cặp đỉnh có thể được nối với nhau bằng hai hoặc nhiều hơn hai cạnh ( hai hoặc nhiều hơn hai cung cùng một hướng).

+ Một cạnh (hay một cung) có thể bắt đầu và kết thúc tại một đỉnh. 6 TIEU LUAN MOI download : skknchat@gmail.com Trong hình (H4) có: Cạnh bội là cạnh (3, 5). Cung bội là cung (3, 10). + Cặp đỉnh x, y được gọi là hai đỉnh kề nhau, nếu x 6= y và là hai đầu của cùng một cạnh hay cùng một cung.

+ Đối với mỗi đỉnh x dùng D(x) để kí hiệu tập đỉnh, mà mỗi đỉnh này được nối với x bằng ít nhất một cạnh. D+ (x) để chỉ tập đỉnh, mà mỗi đỉnh này từ x có cung đi tới. D− (x) để chỉ tập đỉnh, mà mỗi đỉnh này có cung đi tới x. Trong hình (H4) có: D(3) = {5, 7}; D+ (3) = {10}; D− (3) = ∅ + Hai cạnh (cung) a, b được gọi là kề nhau, nếu: 1.

Chúng khác nhau. Chúng có đỉnh chung (nếu a, b thì không phụ thuộc vào đỉnh chung đó là đỉnh đầu hay đỉnh cuối của cung a, đỉnh đầu hay đỉnh cuối của cung b ). Biểu diễn đồ thị bằng hình học. Đồ thị có nhiều cách để biểu diễn nhưng trong phần này chỉ trình bày cách biểu diễn bằng hình học.

Giả sử có đồ thị G = (X, E). Để có dạng biểu diễn hình học của G ta cần biểu diễn đỉnh và cạnh. Biểu diễn đỉnh: Lấy các điểm trên mặt phẳng hay trong không gian tương ứng với các phần tử của tập X và dùng ngay kí hiệu các phần tử này để ghi trên các điểm tương ứng. Biểu diễn cạnh: Nếu cạnh a với hai đỉnh đầu là x, y thì nó được biểu diễn bằng một đoạn thẳng hay một đoạn cong nối giữa hai điểm x, y và không đi qua các điểm tương ứng chung gian khác.

Biểu diễn cung: Cung b có đỉnh đầu là u, đỉnh cuối là v , thì nó được biểu diễn bằng một đoạn thẳng hay một đoạn cong được định hướng từ u sang v và không đi qua các điểm tương ứng chung gian khác. Hình nhận được gọi là dạng biểu diễn hình học của đồ thị G = (X, E). Đôi khi người ta cũng gọi dạng biểu diễn hình học là đồ thị. Giả sử đồ thị G có tập đỉnh X = {x1 , x2 , x3 , x4 , x5 , x6 , x7 , x8 } và tập cạnh E gồm các cạnh a1 = (x1 , x2 ), a2 = (x2 , x3 ), a3 = (x4 , x5 ), a4 = (x5 , x6 ), khuyên vô hướng a5 = (x7 , x7 ), khuyên có hướng (x6 , x6 ) và cung b1 = (x1 , x8 ).

Khi đó đồ thị G = (X, E) có dạng biểu diễn hình học sau: 7 TIEU LUAN MOI download : skknchat@gmail. Một số dạng đồ thị đặc biệt. Trong những trường hợp không cần phân biệt cạnh và cung ta quy ước dùng cạnh thay cho cả cung. + Đồ thị G = (X, E) không có khuyên và mỗi cặp đỉnh được nối với nhau bằng không quá một cạnh, được gọi là đồ thị đơn hay đơn đồ thị và thông thường gọi là đồ thị.

Hình ảnh về đơn đồ thị. + Đồ thị G = (X, E) không có khuyên và có ít nhất một cặp đỉnh được nối với nhau bằng từ hai cạnh trở lên được gọi là đa đồ thị. Hình ảnh về đa đồ thị. + Đồ thị vô hướng (có hướng) G = (X, E) được gọi là đồ thị đầy đủ nếu mỗi cặp đỉnh được nối với nhau bằng đúng một cạnh (một cung với chiều tùy ý).

+ Đồ thị (đa đồ thị) G = (X, E) được gọi là hữu hạn, nếu số đỉnh của nó là hữu hạn, tức tập X có lực lượng hữu hạn. + Đồ thị G được gọi là giả đồ thị nếu trong G tồn tại một cạnh nối một đỉnh 8 TIEU LUAN MOI download : skknchat@gmail.com với chính nó. Cạnh này được gọi là khuyên. + Đồ thị (đa đồ thị) G = (X, E) được gọi là đồ thị (đa đồ thị) hai mảng, nếu tập đỉnh X được phân thành hai tập con rời nhau X1 , X2 , (X1 ∪ X2 = X và X1 ∩ X2 = ∅) và mỗi cạnh đều có một đầu thuộc X1 , còn đầu kia thuộc X2 .