Tài liệu Bồi dưỡng học sinh giỏi môn tin học thpt chuyên đề phân loại bài toán đồ thị

PHÂN LOẠI BÀI TOÁN ĐỒ THỊ 1. LỜI MỞ ĐẦU................................................................................................................................................2 2. MỘT SỐ KHÁI NIỆM CƠ BẢN...................................................................................................................2 2.1. cấu trúc đồ thị..........................................................................................................................................2 2.2. Phép duyệt đồ thị.....................................................................................................................................3 2.3. Đồ thị và hàm chi phí...............................................................................................................................4 2.4. Đồ thị và quan hệ.....................................................................................................................................6 2.5. Cây và cây có gốc....................................................................................................................................8 2.6. Biểu diễn đồ thị và cây..........................................................................................................................10 3. TÌM HIỂU MỘT SỐ CÁCH PHÂN LOẠI BÀI TOÁN ĐỒ THỊ.................................................................11 3.1. Một số cách phân loại bài toán đồ thị.........................................................................................................11 3.1.1. Phân loại theo chương trình khung của Bộ GD&ĐT..........................................................................11 3.1.2. Phân loại theo logic lý thuyết đồ thị....................................................................................................12 3.1.3. Phân loại bài toán theo nhóm các thuật toán trên đồ thị......................................................................13 3.2. Nhận xét và lựa chọn của chúng tôi...........................................................................................................14 1 1. LỜI MỞ ĐẦU Bài toán trên đồ thị là một chủ đề truyền thống trong các kỳ thi HSG Quốc gia, Olympic Tin học Quốc tế và khu vực. Không những thế mà số lượng các bài toán đồ thị được đưa vào các đề thi chiếm tỷ lệ khá lớn. Là những giáo viên dạy Chuyên Tin THPT, chúng tôi luôn cố gắng tích cực tìm tòi, nghiên cứu, sưu tầm tài liệu để nâng cao kiến thức về chủ đề này, với mong muốn truyền thụ được nhiều kiến thức hữu ích cho học sinh. Nhiệm vụ đặt ra là, trong điều kiện tài liệu dạy Chuyên Tin khan hiếm, trình độ học sinh không đồng đều, kinh nghiệm bản thân còn ít, chúng ta nên dạy toán đồ thị cho học sinh như thế nào? Gồm những chủ đề gì? Phân loại bài toán như thế nào? Đây chỉ là vài trong số nhiều câu hỏi phát sinh trong quá trình giảng dạy toán đồ thị. Trong bài viết này, chúng tôi sẽ cố gắng đưa ra một số câu trả lời trong số đó, với kinh nghiệm giảng dạy toán trên đồ thị, cũng như kiến thức sưu tầm được của mình. Chắc chắn rằng còn nhiều thiếu sót, rất mong được các đồng nghiệp đóng góp cho bài viết. Trong phần 2, chúng tôi xin nhắc lại một số khái niệm cơ bản về đồ thị, không phải vì người đọc không quen thuộc với chúng mà chỉ để tránh sự hiểu lầm bởi cách sử dụng thuật ngữ khác nhau. Trong phần 3, chúng tôi xin nêu một số cách phân loại các bài toán trên đồ thị trong các tài liệu hiện hành, một số nhận xét và cách vận dụng của đơn vị chúng tôi trong quá trình giảng dạy. 2. MỘT SỐ KHÁI NIỆM CƠ BẢN 2.1. Cấu trúc đồ thị Một cấu trúc đồ thị G(V,E) được xác định bởi một tập hữu hạn V gồm các đỉnh và tập hữu hạn E các liên kết mà mỗi liên kết nối một cặp đỉnh với nhau. Một liên kết là có hướng khi cặp đỉnh tương ứng là có thứ tự và liên kết là vô hướng khi cặp đỉnh không có thứ tự. Ta gọi liên kết không có thứ tự là cạnh và liên kết có thứ tự là cung. 2 Nếu E là tập cạnh (cung) có sự lặp lại ta gọi đồ thị đó là đa đồ thị, nếu không có cạnh lặp ta gọi đồ thị đó là đơn đồ thị như vậy có thể chia ra bốn loại đồ thị: đơn đồ thị vô hướng, đơn đồ thị có hướng, đa đồ thị vô hướng, đa đồ thị có hướng. Và với mỗi loại đồ thị này, thuật toán giải quyết các bài toán tương tự là khác nhau. Ví dụ với thủ tục hiển thị cấu trúc đồ thị dưới dạng ma trận liên thuộc g[][]. Với một cấu trúc cho trước từ tệp tin đầu vào dưới dạng danh sách cạnh (cung) ta có thể gán g[v][w] = 1 ứng với cung (v,w), nhưng với cạnh (v,w) thì cần phải gán g[v][w] = 1 và g[w][v] = 1. Với các liên kết (v,v) ta gọi là khuyên, và người ta thường chỉ cho phép khuyên có mặt trong đồ thị có hướng. 1 2 1 2 1 2 4 3 4 3 4 3 a. Đa đồồ thị có hướng b. Đơn đồồ thị có hướng c. Đơn đồồ thị vồ hướng Hình 1: Minh họa đồ thị 2.2. Phép duyệt đồ thị Ý tưởng "di chuyển" trong một cấu trúc đồ thị, đi từ một đỉnh tới một đỉnh khác qua cạnh (cung) nối giữa chúng là một trong những thao tác cơ bản khi làm việc với đồ thị và ta gọi đó là duyệt đồ thị. Ta gọi một dãy các đỉnh v0, v1, ..., vm của một đồ thị có hướng là đường đi độ dài m từ đỉnh v0 đến đỉnh vm, nếu cung (vi, vi+1)E với i = 0,1,..., m-1. Khi v0 = vm ta gọi đường đi đó là một chu trình. Ta cũng gọi một dãy các đỉnh v0, v1, ..., vm của một đồ thị vô hướng là đường đi độ dài m từ đỉnh v0 đến đỉnh vm, nếu cạnh(vi, vi+1)E và vi-1 ≠ vi+1 với i = 0,1,..., m-1. Khi v0 = vm ta gọi đường đi đó là một chu trình. 3 Điều kiện vi-1 ≠ vi+1 là quan trọng nếu không sẽ xảy ra loại chu trình kiểu 1,2,1 hoặc 1,1, 2, 1 (với cạnh (1,2) của đồ thị). Trong một đồ thị, nếu giữa hai đỉnh bất kỳ luôn có đường đi, ta nói đồ thị đó liên thông. Trong đồ thị có hướng, giữa hai đỉnh bất kỳ có ít nhất một đường đi theo một hướng nào đó, thì gọi là liên thông yếu. Khi một đồ thị không liên thông, nó sẽ được phân chia thành một số đồ thị con liên thông ta gọi chúng là những thành phần liên thông. Ngoài ra còn có các khái niệm đường đi không có đỉnh nào (hoặc cạnh nào) lặp lại. Đường đi mà mỗi cạnh (cung) chỉ xuất hiện đúng một lần gọi là đường đi Euler. Đường đi mà mỗi đỉnh chỉ xuất hiện đúng một lần gọi là đường đi Hamilton. 2.3. Đồ thị và hàm chi phí Mỗi cấu trúc đồ thị có thể xác định hàm chi phí trên các đỉnh cV: V  C, hàm chi phí trên các cạnh(cung) cE: E  C, hoặc cả hai, với C là một tập các số nào đó (số nguyên, số hữu tỷ, số thực, v.v... hoặc tập con của các tập đó). Giá trị của các hàm chi phí, bên cạnh từ chi phí có các tên gọi khác như độ dài, trọng số, độ ưu tiên, v.v... tùy theo ngữ cảnh. Nếu một đồ thị không định nghĩa hàm chi phí thì ta coi như chi phí của mỗi đỉnh hoặc mỗi cạnh (cung) là 1. Hàm chi phí thường được mở rộng theo cách tự nhiên trên các đồ thị con hoặc các cấu trúc con trong đồ thị. Ví dụ chi phí của một đường đi trong đồ thị thường là tổng chi phí của các đỉnh (hoặc cách cạnh, hoặc cả hai) của đồ thị. Khái niệm đường đi có chi phí nhỏ nhất, hay được gọi là đường đi ngắn nhất là khái niệm cơ bản trên đồ thị với nhiều thuật toán liên quan. Ví dụ một số bài toán dưới đây có hàm chứa bài toán tìm đường đi ngắn nhất đã đề cập. Bài toán 1: Thành phố có N bến xe buýt được gán nhãn 1, 2, ..., N và R tuyến xe buýt: M1(i1,1, i1,2, ..., i1,m1), M2(i2,1, i2,2, ..., i2,m2), ..., Mr(ir,1, ir,2, ..., ir,m1), i  ij,k  N, ij,k ≠ ij,l với k ≠ l. Mỗi xe buýt xuất phát từ một bến ở đầu mút của tuyến, đi qua tất cả các bến thuộc tuyến theo trật tự đã cho và khi đến bến đầu mút còn lại nó quay lại với hành trình đảo ngược. Viết chương trình: 4 (i) Kiểm tra một người nào đó có thể đi xe buýt từ một bến i đến một bến j cho trước hay không? (ii) Với hai bến i và j cho trước, hãy in ra tất cả các đường đi có thể để đi từ bến i đến bến j? (iii) Với hai bến i và j cho trước, hãy tìm đường đi nhanh nhất có thể để đi từ bến i đến bến j, nếu thời gian đi từ bến này sang bến khác là như nhau và nhỏ hơn 3 lần so với thời gian đổi tuyến xe buýt? Bài toán 2: Cho tập V gồm các xâu ký tự độ dài 2N gồm N-1 chữ cái 'A', N-1 chữ cái 'B' và 2 chữ cái 'O'. Với hai xâu X và Y thuộc V (hai đỉnh thuộc V), xâu Y được gọi là biến đổi từ xâu X (đỉnh X có cạnh nối với đỉnh Y) nếu, ta đổi chỗ hai ký tự 'O' với hai ký tự liền kề nào đó (giữ nguyên thứ tự của chúng) trong X thì được Y. Xâu có các chữ cái 'A' nằm hoàn toàn ở phía trái các chữ cái 'B' (không quan tâm vị trí của các chữ cái 'O') gọi là xâu cuối cùng. Viết chương trình với xâu S cho trước hãy tìm và in ra chi phí nhỏ nhất để từ S ta biến đổi được xâu cuối cùng (tìm và in ra đường đi ngắn nhất từ đỉnh S đến đỉnh cuối cùng, chi phí mỗi cạnh là 1) . Nếu không có cách biến đổi (không có đường đi) thì thông báo 'NOSOLUTION'. Bài toán 3: Cho đồ thị G(V = {1, 2, ..., n}, E). Có r đường đi độ dài tương ứng là m1, m2, ..., mr, mỗi cạnh của G thuộc ít nhất một trong các đường đi đã cho. Chi phí của mỗi đỉnh là 3 và chi phí của mỗi cạnh là 1. Viết một chương trình: (i) Kiểm tra xem đồ thị có liên thông hay không, (ii) cho cho hai đỉnh v và w, in ra tất cả các đường đi giữa v và w, (iii) cho hai đỉnh v và w, để tìm đường đi giữa v và w với chi phí tối thiểu. Cho đồ thị G (V, E) với hàm chi phí cE: E → C, trong đó C là tập các số không âm. Thì hàm d: V × V → C, trong đó d(v, w) là chi phí của đường đi ngắn nhất từ v đến w là khoảng cách theo ý nghĩa toán học cổ điển, bởi vì: (i) ∀ v, w ∀ V, d(v, w) ≥ 0 và d (v, w) = 0  v = w, 5 (ii) ∀ v, w ∀ V, d(v, w) = d (w, v), (iii) ∀ v, w, u ∀ V, d(v, w)  d(v, u) + d(u, w). Hàm khoảng cách cho ta khả năng xem xét đồ thị G (V, E) là một đối tượng hình học và xác định các khái niệm tương ứng. Ví dụ, tâm của đồ thị G là mỗi đỉnh v, trong đó giá trị nhỏ nhất D(v) = max {d(v,w) | w ∀ V} và đường kính của đồ thị G là D(G) = max {d (v, w) | v, w ∀ V}. Sự tương tự giữa tính chất "hình học" của một đồ thị và hình học không gian Euclid cũng được biết đến như là nguồn gốc của bài toán thú vị trên đồ thị. 2.4. Đồ thị và quan hệ Cho A và B là tập tùy ý. Mỗi tập con R của tích Đề các A × B được gọi là một quan hệ. Trong toán học, người ta dạy học sinh một số lượng lớn các mối quan hệ hữu ích: trong đại số ta nói ("x nhỏ hơn y", "x nhỏ hơn hoặc bằng y", "x bằng y", v.v...), trong hình học ta nói ("điểm p nằm trên đường thẳng l", "đường thẳng l đi qua điểm p", "đường thẳng l và m song song", v.v...), trong lý thuyết tập hợp nói chung, ta nói ("A là tập con của B","A và B giao nhau", v.v...). Rất nhiều mối quan hệ chúng ta có thể tìm thấy bên ngoài toán học, trong thế giới xung quanh chúng ta. Ví dụ, quan hệ giữa con người - "x là con trai của y", "x giống y", "x và y cùng một lớp", v.v..., hoặc mối quan hệ phổ biến giữa các làng, "làng x được nối với y làng bằng một con đường" (các quan hệ tương tự có thể được thiết lập giữa các ngã tư đường phố nối với nhau bằng đường phố, các nhà ga kết nối bằng đường xe lửa; nguồn điện, trung tâm phân phối điện và khách hàng liên kết bởi đường điện, v.v...). Đó là lý do tại sao có nhiều bài toán khác nhau có thể xảy ra. Ta cần quan tâm đến các tính chất đặc biệt của quan hệ trên tích Descartes A×A - phản xạ, đối xứng, phản đối xứng, bắc cầu. Một số mối quan hệ cụ thể trên tích Descartes - tương đương (phản xạ, đối xứng và bắc cầu), thứ tự bộ phận (phản xạ, phản đối xứng và bắc cầu) và thứ tự toàn phần (phản xạ, phản đối xứng mạnh và bắc cầu) có ý nghĩa cả về toán học và thuật toán. 6 Khái niệm quan hệ hữu hạn trùng với khái niệm đồ thị có hướng. Thật vậy, mỗi đồ thị có hướng G(V, E) có thể được coi như một quan hệ E ∀ V × V và ngược lại. Một mối quan hệ hữu hạn E ∀ V × V có tính đối xứng (tùy trường hợp có thêm tính phản xạ) thực sự là một đồ thị. Đó là lý do tại sao, mỗi bài toán liên quan với một quan hệ nào đó có thể coi như một bài toán trên đồ thị có hướng hoặc đồ thị vô hướng. Chúng ta hãy xem xét một số ví dụ, với giả sử tập đỉnh V là {1, 2, ..., n}. Bài toán 4: Cho E ∀ V×V là quan hệ tương đương. Tìm số lượng các lớp tương đương của E. Số này có bằng 1 hay không? Nếu số lượng các lớp tương đương lớn hơn 1, hãy tìm các lớp tương đương của E. Bài toán này (thực ra là một tập các bài toán tương tự) là bài toán cổ điển về quan hệ tương đương. Vì quan hệ tương đương có tính phản xạ và đối xứng, G (V, E) là một đồ thị. Từ quan điểm của đồ thị, bài toán này có thể được phát biểu như sau: "Có bao nhiêu thành phần liên thông trong đồ thị G(V, E)? Đồ thị có liên thông không? Nếu không, hãy liệt kê các đỉnh của mỗi thành phần liên thông của G?". Bài toán 5: Cho E ∀ V×V là tập quan hệ thứ tự toàn phần (chúng ta biểu thị (x, y) ∀ E bằng x  y) và V'∀ V, |V'|= M. Tìm một dãy a1, a2, ..., aM gồm tất cả các phần tử của V' thỏa mãn a1  a2  ...  aM. Tất nhiên, đây là bài toán sắp xếp một tập hợp các phần tử của một dãy thứ tự toàn phần cho trước. Có một nhánh cụ thể của Lý thuyết Thuật toán được dành riêng cho nó. Bài toán có thể được xây dựng như một bài toán trên đồ thị có hướng. Có thể hiểu quan hệ thứ tự như đồ thị có hướng không có chu trình. Vì vậy, bài toán sắp xếp một tập con cho trước theo trật tự toàn phần có thể phát biểu như sau: "Cho đồ thị có hướng G(V', E') không có chu trình. Tìm đường đi có độ dài cực đại trong G". Quan hệ E' trong công thức này là, rõ ràng, hạn chế E trên V'. Đồ thị có hướng không có chu trình rất phổ biến và có tên là dag (viết tắt của Directed Acyclic Graphs). 7 Bài toán 6: Cho E ∀ V×V là tập quan hệ thứ tự bộ phận (chúng ta cũng biểu thị (x, y) ∀ E với x  y). Tìm một dãy a1, a2, ..., aM gồm các phần tử của V với chiều dài cực đại, thỏa mãn a1  a2  ...  aM. Phát biểu bài toán này dưới dạng một bài toán đồ thị có hướng như sau: "Cho một dag G(V,E). Tìm đường đi có độ dài cực đại trong G". Bài toán 7: Cho R1∀ A × B và R2∀ B × A, như vậy (a, b) ∀ R1 khi và chỉ khi (b,a) ∀ R2. Tìm một tập hợp {(a1, b1), (a2, b2), ..., (aM, bM)} của R1 (hoặc {(b1, a1), (b2, a2), ..., (bM, aM)} của R2) với số lượng phần tử tối đa, thỏa mãn ai = aj và bi = bj, 1  i < j  M. Quan hệ giữa R1 và R2 với đề cập ở trên được gọi là đảo ngược lẫn nhau. Ví dụ về quan hệ cặp đôi đảo ngược là "điểm p nằm trên đường thẳng l" và "đường thẳng l qua điểm p". Một ví dụ thực tế cuộc sống là "người p có thể làm công việc w" và "công việc w có thể được thực hiện bởi người p". Đối với mỗi quan hệ cặp đôi đảo ngược, chúng ta có thể xây dựng một đồ thị G(V = A ∪ B, R1) (hoặc G (V = A ∪ B, R2)) coi các phần tử của R1 (hoặc R2) là không có thứ tự. Đồ thị như vậy được gọi là đồ thị hai phía. Việc tìm tập con có M cạnh, mà mỗi đỉnh là một đầu mút của nhiều nhất một cạnh trong M được gọi là cặp ghép. Trong đồ thị bài toán có thể phát biểu như sau: "Cho đồ thị hai phía G(V = A ∪ B, R1). Tìm cặp ghép cực đại của G". 2.5. Cây và cây có gốc Khi nói về các bài toán trên đồ thị, ta không thể không giới thiệu khái niệm cây. Theo định nghĩa cổ điển, đồ thị T(V, E) là một cây nếu nó liên thông và không có chu trình. Hai định nghĩa quy nạp tương đương của cây được phát biểu như sau: Định nghĩa 1. (i) Đồ thị T ({r}, ∀) là một cây có gốc. r là gốc và r là lá của T; (ii) Cho T(V, E) là một cây có gốc r và các lá L = {v1, v2, ..., vk}. Cho v ∀ V và w  V; 8 (iii) thì, T''(V '= V∪{w}, E' = E∪{(v, w)}) cũng là một cây có gốc là r và lá của T' là (L {v}) ∪ {w}, (xem minh họa hình 2a). Định nghĩa 2. (i) Đồ thị T({r}, ∀) là một cây có gốc là r và r cũng là lá của T; (ii) Cho T1(V1, E1), T2(V2, E2), ..., Tk(Vk, Ek), là các cây có gốc tương ứng là r1, r2, ..., rk, và lá L1, L2, ..., Lc. Cho r  V1 ∪ V2 ∪ ... ∪ Vk; (iii) thì, T'(V' = V1 ∪ V2 ∪ ... ∪ Vk ∪ {r}, E' = E1 ∪ E2 ∪ ... ∪ Ek ∪ {(r, r1), (r, r2), ..., (r, rk)}) cũng là một cây có gốc r và lá của T' là L1 ∪ L2 ∪ ... ∪ Lc. Các cây có gốc T1, T2, ..., Tk được gọi là cây con của T', (xem minh họa hình 2b). Các khái niệm cây con dẫn đến các thủ tục đệ quy tự nhiên. Bởi cây bắt nguồn từ định nghĩa là đồ thị vô hướng. Định nghĩa 1 giới thiệu một hướng tiềm ẩn trên các cạnh của cây có gốc. Chúng ta có thể nói rằng v là cha của w và w là con của v. Rõ ràng mỗi cây có gốc là một cây và mỗi cây có thể được xây dựng lại như một cây có gốc khi ta chọn một trong các đỉnh là gốc của nó. Nếu G(V,E) là một đồ thị và T(V, E') là một cây (có gốc) thỏa mãn E'∀ E thì T được gọi là cây khung của G. Đồ thị G liên thông khi và chỉ khi nó có một cây khung. Như vậy, một cách tự nhiên nhất để kiểm tra tính liên thông của đồ thị G là xây dựng một cây khung của G. Nếu c: E → C là một hàm chi phí trên các cạnh của G(V, E), chúng ta có thể mở rộng nó thành hàm chi phí của cây khung của G, c (T (V , E ' ))  định nghĩa  c(e) . Mỗi cây khung T của G với c(T) tối thiểu hoặc tối đa) gọi là eE ' cây khung tối thiểu (tối đa) của G. 9 r r T r1 r2 T1 T2 ... rk v w Tk Hình 2. Minh họa hai định nghĩa tương đương về cây có gốc 2.6. Biểu diễn đồ thị và cây Trong từng lĩnh vực khác nhau, việc biểu diễn các kiểu dữ liệu trừu tượng như đơn đồ thị vô hướng, đơn đồ thị có hướng, đa đồ thị vô hướng, đa đồ thị có hướng và cây bằng cấu trúc dữ liệu là rất quan trọng trong việc xây dựng các thuật toán hiệu quả. Theo truyền thống, đồ thị được đưa vào qua tập tin đầu vào, như đã đề cập ở trên, dưới hình thức một danh sách cạnh (cung) và đi trước đó là số n - số đỉnh của nó và số m - số cạnh (cung) của đồ thị và phần hướng dẫn phải chỉ rõ là đồ thị vô hướng (cạnh) hoặc có hướng (cung). Nếu một phần quan trọng của thuật toán được thực hiện trên cấu trúc đồ thị G(V, E) là lệnh lặp dạng: for e ∀ G do{...} thì danh sách cạnh (cung) sẽ được biểu diễn với chi phí thời gian O(m). Nếu cùng một thuật toán biểu diễn đồ thị G với một ma trận kề (ví dụ, mảng hai chiều g thỏa mãn g[v] [w] là số cạnh (cung) nối giữa v và w) chi phí thời gian sẽ là O(n 2) và việc thờì gian thi hành sẽ chậm hơn với các đồ thị thưa. Nếu một phần quan trọng của thuật toán là một lệnh lặp dạng: for v ∀ V'∀ V do {for w∀V''∀ V do{...if (v, w) ∀ E {...}}} 10 thì khi thực hiện với cấu trúc danh sách cạnh (cung) sẽ có chi phí thời gian O(|V'||V'' |.m) và với cấu trúc ma trận kề có chi phí thời gian O(|V'||V''|), tốt hơn so với việc dùng cấu danh sách cạnh (cung). Nếu một phần quan trọng của thuật toán là một lệnh lặp dạng: for v ∀ V do {for w|(v, w) ∀ E do {...}} thì khi thực hiện với cấu trúc ma trận kề sẽ có chi phí thời gian O(n2). Trong trường hợp này, sử dụng cấu trúc danh sách kề sẽ cho bạn chi phí thời gian O(m). Đặc biệt là với những cây có gốc, chúng ta biểu diễn danh sách cha g[] với g[i] là cha của i cho mỗi đỉnh không phải gốc r và g[r] = 0. Cách biểu diễn này với những cây có gốc là rất thuận tiện khi cần xây dựng một cây có gốc (cây khung, cây khung tối thiểu, v.v...) hoặc để duyệt cây. 3. TÌM HIỂU MỘT SỐ CÁCH PHÂN LOẠI BÀI TOÁN ĐỒ THỊ Phân loại các bài toán trên đồ thị là điều rất quan trọng vì những lý do khác nhau. Phân loại tốt có thể rất hữu ích cho việc chuẩn bị chương trình đào tạo và tổ chức quá trình đào tạo - cho việc quyết định thứ tự các chuyên đề được giảng dạy theo trật tự nhất định. Ngoài ra việc phân loại bài toán đồ thị, rất hữu ích để chuẩn bị cho cuộc thi. Trong phần này chúng tôi xin đề nêu ra một số cách phân loại các bài toán trên đồ thị mà chúng tôi sưu tầm được qua các tài liệu và quan điểm lựa chọn của chúng tôi. 3.1. Một số cách phân loại bài toán đồ thị 3.1.1. Phân loại theo chương trình khung của Bộ GD&ĐT * Lớp 10: + Chuyên đề 2: PHÂN TÍCH, THIẾT KẾ VÀ CÀI ĐẶT THUẬT TOÁN Nội dung 7: Mô hình đồ thị không có và có trọng số, cây Nội dung 8: Bài toán tìm đường đi ngắn nhất Nội dung 9: Bài toán tìm cây khung nhỏ nhất 11 * Lớp 11: + Chuyên đề 2. LÝ THUYẾT TRÒ CHƠI + Chuyên đề 4: BÀI TOÁN LUỒNG CỰC ĐẠI TRONG MẠNG VÀ ỨNG DỤNG Nội dung 1: Biểu diễn đồ thị, duyệt đồ thị Nội dung 2: Bài toán luồng cực đại Nội dung 3: Lát cắt. Đường tăng luồng. Định lý Ford – Fulkerson Nội dung 4: Thuật toán Ford - Fulkerson tìm luồng cực đại trong mạng Nội dung 5: Một số bài toán luồng tổng quát Nội dung 6: Một số ứng dụng + Chuyên đề 5. BÀI TOÁN LẬP LỊCH: Đề cập đến một số bài toán lập lịch có ứng dụng mô hình bài toán đồ thị * Lớp 12: + Chuyên đề 3. CÁC CẤU TRÚC DỮ LIỆU NÂNG CAO Đề cập đến ứng dụng của kiểu dữ liệu heap vào bài toán đồ thị 3.1.2. Phân loại theo logic lý thuyết đồ thị Tài liệu Giải thuật và lập trình (TS Lê Minh Hoàng), Tài liệu giáo khoa chuyên Tin quyển 1 và 2 (TS Hồ Sĩ Đàm chủ biên), Toán rời rạc (TS Nguyễn Đức Nghĩa và TS Nguyễn Tô Thành) đều có bố cục kiến thức lý thuyết đồ thị tương tự như sau: 1. Các khái niệm cơ bản 2. Biểu diễn đồ thị trên máy tính 3. Các thuật toán tìm kiếm trên đồ thị (DFS, BFS) 4. Tính liên thông của đồ thị 5. Vài ứng dụng của DFS và BFS 6. Chu trình Euler, đường đi Euler, đồ thị Euler 12 7. Chu trình Hamilton, đường đi Hamilton, đồ thị Hamilton 8. Bài toán tìm đường đi ngắn nhất 9. Bài toán cây khung nhỏ nhất 10. Bài toán luồng cực đại trên mạng 11. Bài toán tìm bộ ghép cực đại trên mạng 12. Bài toán tìm bộ ghép cực đại với trọng số cực tiểu trên đồ thị hai phía 13. Bài toán tìm bộ ghép cực đại trên đồ thị 3.1.3. Phân loại bài toán theo nhóm các thuật toán trên đồ thị + Tài liệu Algorithms (Robert Sedgewick) Phần 6: Các thuật toán đồ thị có bố cục như sau: 1. Các thuật toán cơ bản về đồ thị: Thuật ngữ, Biểu diễn đồ thị, Tìm kiếm DFS và BFS, Mê cung. 2. Đồ thị liên thông: Các thành phần liên thông, Song liên thông, Các thuật toán tìm phần hợp. 3. Đồ thị có trọng số: Cây khung tối thiểu, Đường đi ngắn nhất, Đồ thị dày, Các bài toán hình học 4. Đồ thị có hướng: Tìm kiếm DFS, Bao đóng bắc cầu, Sắp xếp tô pô, Tìm tất cả các đường đi ngắn nhất, các thành phần liên thông mạnh. 5. Luồng trong mạng: Bài toán luồng trong mạng, Phương pháp Ford-Fulkerson, Tìm kiếm trên mạng 6. Cặp ghép: Đồ thị hai phía, Bài toán hôn nhân bền vững, các thuật toán nâng cao. + Tài liệu Introduction to Algorithms (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein) Phần 6: Các thuật toán đồ thị của tài liệu này phân chia bài toán đồ thị như sau: 13 1. Các thuật toán cơ bản về đồ thị: Biểu diễn đồ thị, Tìm kiếm DFS và BFS, sắp xếp topo, các thành phần liên thông mạnh. 2. Cây khung tối thiểu: Xây dựng cây khung tối thiểu, các thuật toán Prim, Kruskal. 3. Đường đi đơn ngắn nhất: Thuật toán Bellman-Ford, đường đi đơn ngắn nhất trong đồ thị không có chu trình, thuật toán Dijkstra. 4. Đường đi ngắn nhất giữa tất cả các cặp đỉnh: Các đường đi ngắn nhất và phép nhân ma trận, Thuật toán Floyd-Warshall, Thuật toán Johnson với đồ thị thưa. 5. Luồng cực đại: Luồng trong mạng, Phương pháp Ford-Fulkerson, Cặp ghép cực đại. 3.2. Nhận xét và lựa chọn của chúng tôi Cách phân loại các bài toán đồ thị theo logic lý thuyết đồ thị như các tài liệu nêu trong phần 3.2.1 có thể coi là các phân loại truyền thống trong hầu hết các giáo trình dạy lý thuyết đồ thị cho học sinh và sinh viên. Đơn vị chúng tôi cũng thực hiện phân phối chương trình dạy toán đồ thị cho học sinh theo cách phân loại trên. Chúng tôi thường chọn giáo trình Toán rời rạc của Nguyễn Đức Nghĩa và Nguyễn Tô Thành làm tài liệu tham khảo chính để dạy phần Lý thuyết đồ thị và giáo trình Giải thuật và Lập trình của TS Lê Minh Hoàng làm tài liệu tham khảo cho học sinh khi thực hành cài đặt các giải thuật trên máy tính. Bên cạnh đó, chúng tôi cũng thấy các mô đun trong phân phối chương trình Tin của Bộ GD&ĐT chưa cụ thể, chưa khoa học và logic. Phân loại các bài toán trên cơ sở các thuật toán được sử dụng là một cách tiếp cận điển hình cho các cuốn sách về thuật toán. Những quyển sách này không nhằm mục đích xem xét các bài toán thuộc một miền toán học cụ thể nhưng nó giới thiệu các nguyên tắc và phương pháp tiếp cận thiết kế và phân tích các thuật toán. Bài toán đồ thị trong cuốn tài liệu Introduction to Algorithms nêu trong phần 3.2 bắt đầu với chương "Các thuật toán cơ bản của đồ thị", trong đó thảo luận các phép duyệt đỉnh đồ thị là BFS và DFS. Cả hai phương pháp được áp dụng để giải quyết các bài toán khác nhau liên quan đến tính liên thông của đồ thị và đường đi giữa hai đỉnh khác nhau. Nhưng hai thuật toán này cũng được sử dụng để giải quyết một số bài toán cụ thể. Ví dụ, 14 BFS, xây dựng một cây đường đi ngắn nhất trong đồ thị không có hàm chi phí trên các cạnh và DFS là một bước cơ bản để sắp xếp topo hiệu quả, tìm kiếm các thành phần liên thông mạnh, các điểm khớp và các cầu, v.v... Chương thứ hai, dành riêng cho các thuật toán tìm cây khung tối thiểu của đồ thị (MSP). Các thuật toán tìm MST còn được đề cập đến trong chương nói về thuật toán tham lam trong một phần đặc biệt dành riêng cho việc áp dụng thuật toán tham lam trên đồ thị. Hai chương kế tiếp là "Đường đi đơn ngắn nhất" và "Đường đi ngắn nhất giữa tất cả các cặp đỉnh". Thực ra hai chương này có thể dồn thành một như trong các tài liệu thuật toán khác. Ta cũng có thêm hai nhận xét. Đầu tiên, từ "ngắn nhất" phải được xem xét trong một nghĩa rộng hơn - bài toán tìm đường đi lớn nhất, đường đi tin cậy hơn, v.v..., được giải quyết với phương pháp tương tự - phương pháp làm tốt dần. Và thứ hai, bài toán tìm kiếm tâm, điểm giữa, bán kính (hoặc đường kính), v.v... của đồ thị cũng giải được bằng phương pháp làm tốt dần. Chương cuối cùng là "Luồng cực đại". Bên cạnh một số thuật toán cơ bản để tìm luồng cực đại trong một mạng lưới, chương này cũng xem xét các bài toán liên quan đến việc tìm bộ ghép cực đại trong đồ thị hai phía. Cách phân chia các bài toán đồ thị theo nhóm các thuật toán như một số cuốn tài liệu, đã nêu trong phần 3.2 lại khá hữu dụng khi ôn tập kiến thức cho học sinh tham gia đội tuyển thi Học sinh giỏi. Chúng tôi đã chọn sử dụng cách phân chia này trong quá trình ôn luyện, hướng dẫn học sinh phát hiện dạng bài toán đồ thị và qua đó các em có thể nhanh chóng chọn được thuật toán phù hợp để áp dụng vào giải bài tập. Trong quá trình ôn tập cho học sinh, chúng tôi cũng tham khảo thêm các chủ đề bài tập được liệt kê trong các tài liệu như: Art of programming contest, The Programming Contest Training Manual. Trước khi kết thúc bài viết này, với mong muốn nêu ra một vấn đề nhỏ trong chủ đề các bài toán đồ thị, nhằm trao đổi suy nghĩ với các đồng nghiệp. Với kinh nghiệm chưa 15 nhiều, trình độ còn có hạn chế, chúng tôi mong rằng sẽ nhận được sự góp ý của các đồng chí. Xin chân trọng cảm ơn! 16 TÀI LIỆU THAM KHẢO [1] Bộ GD&ĐT, Chương trình chuyên sâu môn Tin học trường THPT chuyên. [2] Nguyễn Đức Nghĩa, Nguyễn Tô Thành, Toán rời rạc, NXB Đại học Quốc gia Hà Nội, 2007. [3] Lê Minh Hoàng, Giải thuật và lập trình, Ebook. [4] Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, Introduction to Algorithms, The MIT Press, 2001. [5] Robert Sedgetwick, Algorithms, Addison-Wesley Publishing Co, 1984. [6] Krassimir Manev, Tasks on Graphs, 2008. [7] http://en.wikipedia.org. 17