Ví dụ, 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ạn[r]
MỘT SỐ KHÁI NIỆM CƠ BẢN
cấu trúc đồ thị
Cấu trúc đồ thị G(V,E) bao gồm một tập hợp hữu hạn V của các đỉnh và một tập hữu hạn E các liên kết giữa các đỉnh Liên kết có thể được phân loại thành có hướng, khi các đỉnh có thứ tự, và vô hướng, khi không có thứ tự Trong đó, liên kết không có thứ tự được gọi là cạnh, còn liên kết có thứ tự được gọi là cung.
Đồ thị có thể được phân loại thành bốn loại chính: đơn đồ thị vô hướng, đơn đồ thị có hướng, đa đồ thị vô hướng và đa đồ thị có hướng, tùy thuộc vào việc có sự lặp lại của các cạnh hay không Mỗi loại đồ thị yêu cầu thuật toán khác nhau để giải quyết các bài toán liên quan Chẳng hạn, khi hiển thị cấu trúc đồ thị dưới dạng ma trận liên thuộc g[][], nếu có một danh sách cạnh từ tệp tin đầu vào, ta gán g[v][w] = 1 cho cạnh (v,w) Đối với đa đồ thị, cần gán cả g[v][w] = 1 và g[w][v] = 1 Các liên kết (v,v) được gọi là khuyên, và thường chỉ được phép tồn tại trong đồ thị có hướng.
Hình 1: Minh họa đồ thị
Phép duyệt đồ thị
Duyệt đồ thị là một thao tác cơ bản trong lý thuyết đồ thị, cho phép di chuyển từ một đỉnh này sang đỉnh khác qua các cạnh nối Một dãy các đỉnh v0, v1, , vm trong đồ thị có hướng được gọi là đường đi độ dài m từ đỉnh v0 đến v m nếu các cung (vi, vi+1) thuộc tập E với i = 0, 1, , m-1 Nếu v0 = vm, dãy này được gọi là chu trình Tương tự, trong đồ thị vô hướng, một dãy các đỉnh v0, v1, , vm cũng là đường đi độ dài m từ v0 đến vm nếu các cạnh (vi, vi+1) thuộc E và điều kiện vi-1 ≠ vi+1 được thỏa mãn Khi v0 = vm, đây cũng là một chu trình, và điều kiện vi-1 ≠ vi+1 rất quan trọng để tránh các chu trình không hợp lệ như 1,2,1 hoặc 1,1,2,1.
Trong lý thuyết đồ thị, một đồ thị được gọi là liên thông nếu giữa hai đỉnh bất kỳ luôn tồn tại đường đi Đối với đồ thị có hướng, nếu giữa hai đỉnh có ít nhất một đường đi theo một hướng nhất định, nó được xem là liên thông yếu Khi một đồ thị không liên thông, nó sẽ được chia thành các thành phần liên thông Thêm vào đó, khái niệm đường đi không có đỉnh hoặc cạnh nào lặp lại cũng rất quan trọng; đường đi mà mỗi cạnh chỉ xuất hiện một lần được gọi là đường đi đơn.
Đồ thị có hướng và đồ thị vô hướng đều có thể áp dụng cho các khái niệm như đường đi Euler và đường đi Hamilton Đường đi Euler là đường đi qua mỗi cạnh của đồ thị đúng một lần, trong khi đường đi Hamilton là đường đi mà mỗi đỉnh chỉ xuất hiện đúng một lần.
Đồ 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 và cạnh, với các giá trị chi phí có thể là số nguyên, số hữu tỷ, hoặc số thực Các hàm chi phí này có thể được gọi bằng nhiều tên khác nhau như độ dài, trọng số, hay độ ưu tiên, tùy thuộc vào ngữ cảnh Trong trường hợp đồ thị không định nghĩa hàm chi phí, chi phí của mỗi đỉnh hoặc cạnh sẽ được mặc định là 1 Hàm chi phí thường được mở rộng tự nhiên trên các đồ thị con, và 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ạnh liên quan.
Khái niệm đường đi ngắn nhất, hay còn gọi là đường đi có chi phí nhỏ nhất, là một khái niệm cơ bản trong lý thuyết đồ thị, với nhiều thuật toán liên quan Nhiều bài toán trong thực tiễn đều chứa yếu tố tìm đường đi ngắn nhất, cho thấy tầm quan trọng của khái niệm này.
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: M 1 (i 1,1, i 1,2, , i 1,m1), M 2(i 2,1, i 2,2, , i 2,m2), , M r (i r,1, i r,2, , i r,m1), i i j,k N, i j,k
Mỗi xe buýt bắt đầu từ một bến ở đầu tuyến, di chuyển qua tất cả các bến theo thứ tự đã định Khi đến bến đầu tuyến còn lại, xe buýt sẽ quay lại và thực hiện hành trình theo chiều ngược lại Viết chương trình để thực hiện quy trình này.
(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?
Để tìm đường đi nhanh nhất từ bến i đến bến j, cần xác định rằng thời gian di chuyển giữa các bến là đồng nhất và nhỏ hơn 3 lần so với thời gian đổi tuyến xe buýt.
Bài toán 2 yêu cầu cho tập V gồm các xâu ký tự có độ dài 2N, bao gồm N-1 chữ cái 'A', N-1 chữ cái 'B' và 2 chữ cái 'O' Hai xâu X và Y thuộc V được gọi là có mối liên hệ biến đổi nếu xâu Y có thể được tạo ra từ xâu X bằng cách đổi chỗ hai ký tự 'O' với hai ký tự liền kề nào đó trong X, mà không thay đổi thứ tự của chúng.
Để tìm xâu cuối cùng từ xâu S, chúng ta cần đảm bảo rằng tất 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 đến vị trí của các chữ cái 'O' Chương trình sẽ tính toán chi phí nhỏ nhất để thực hiện biến đổi này, với mỗi bước di chuyển có chi phí là 1 Nếu không thể thực hiện biến đổi, chương trình sẽ thông báo 'NOSOLUTION' Hãy chắc chắn rằng các bước thực hiện được in ra rõ ràng để người dùng có thể theo dõi đường đi từ xâu S đến xâu cuối cùng.
Bài toán 3 yêu cầu giải quyết trên đồ thị G với tập đỉnh V = {1, 2, , n} và tập cạnh E Đồ thị này có r đường đi với độ dài tương ứng là m1, m2, , mr, trong đó mỗi cạnh 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 Nhiệm vụ là viết một chương trình để tính toán chi phí tổng thể của đồ thị dựa trên các thông tin trên.
(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 hợp các số không âm Hàm d: V × V → C được định nghĩa sao cho d(v, w) là chi phí của đường đi ngắn nhất từ đỉnh v đến đỉnh w, được coi là khoảng cách theo nghĩa toán học cổ điển.
Hàm khoảng cách cho phép chúng ta xem đồ thị G (V, E) như một đối tượng hình học và xác định các khái niệm liên quan Cụ thể, tâm của đồ thị G là đỉnh v có giá trị D(v) nhỏ nhất, được tính bằng max {d(v,w) | w ∈ V} Đường kính của đồ thị G, ký hiệu là D(G), được xác định là max {d(v, w) | v, w ∈ V} Sự tương đồng giữa các thuộc tính "hình học" của đồ thị và hình học không gian Euclid đã dẫn đến những bài toán thú vị trong lý thuyết đồ thị.
Đồ thị và quan hệ
Trong toán học, tập A và B là hai tập tùy ý, và mỗi tập con R của tích Đề các A × B được gọi là một quan hệ Các mối quan hệ này rất đa dạng và hữu ích, như trong đại số với các khái niệm "x nhỏ hơn y", "x nhỏ hơn hoặc bằng y", và "x bằng y" Trong hình học, ta có thể nói về các mối quan hệ như "điểm p nằm trên đường thẳng l", "đường thẳng l đi qua điểm p", hay "đường thẳng l và m song song" Ngoài ra, trong lý thuyết tập hợp, các quan hệ như "A là tập con của B" và "A và B giao nhau" cũng rất quan trọng.
Trong cuộc sống hàng ngày, chúng ta có thể nhận thấy nhiều mối quan hệ không chỉ trong toán học mà còn trong các tương tác xã hội Ví dụ, các mối quan hệ như "x là con trai của y", "x giống y", hay "x và y cùng học một lớp" thể hiện sự kết nối giữa con người Ngoài ra, còn có những mối quan hệ phổ biến giữa các làng, cho thấy sự liên kết chặt chẽ trong cộng đồng.
Làng X được kết nối với làng Y qua một con đường, tương tự như các ngã tư phố nối liền nhau, các nhà ga được kết nối bằng đường sắt, và nguồn điện liên kết với trung tâm phân phối cùng khách hàng qua hệ thống điện Điều này tạo ra nhiều bài toán khác nhau cần được giải quyết.
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
Trong tích Descartes, có một số mối quan hệ quan trọng như phản xạ, đối xứng và bắc cầu, cùng với thứ tự bộ phận và thứ tự toàn phần Những mối quan hệ này giúp xác định cách các phần tử tương tác và liên kết với nhau trong không gian toán học Phản xạ thể hiện tính chất đối xứng, trong khi bắc cầu kết nối các yếu tố khác nhau, tạo nên một cấu trúc mạch lạc và hợp lý Thứ tự bộ phận và thứ tự toàn phần đóng vai trò quan trọng trong việc phân tích và hiểu rõ hơn về các mối quan hệ này.
Khái niệm quan hệ hữu hạn tương đương với khái niệm đồ thị có hướng Cụ thể, mỗi đồ thị có hướng G(V, E) có thể được xem như một quan hệ E ⊆ V × V và điều này cũng đúng theo chiều ngược lại.
Một mối quan hệ hữu hạn E ⊆ V × V có tính đối xứng, và có thể có tính phản xạ, được xem như một đồ thị Điều này cho phép mỗi bài toán liên quan đến một quan hệ nào đó được chuyển đổi thành bài toán trên đồ thị có hướng hoặc đồ thị vô hướng 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 yêu cầu xác định số lượng các lớp tương đương của quan hệ tương đương E ⊆ V×V Cần kiểm tra xem số lượng này có bằng 1 hay không Nếu số lượng lớp tương đương lớn hơn 1, hãy xác định các lớp tương đương cụ thể của E.
Bài toán này, thuộc nhóm các bài toán tương tự, là một ví dụ điển hình về quan hệ tương đương Quan hệ tương đương có đặc tính phản xạ và đối xứng, và G (V, E) được xem như một đồ thị Từ góc độ đồ thị, bài toán này có thể được diễn đạt một cách rõ ràng.
Trong đồ thị G(V, E), số lượng thành phần liên thông có thể được xác định bằng cách phân tích cấu trúc của đồ thị Đồ thị có thể liên thông hoặc không, tùy thuộc vào việc có tồn tại đường đi giữa mọi cặp đỉnh hay không Nếu đồ thị không liên thông, cần liệt kê các đỉnh của từng thành phần liên thông để hiểu rõ hơn về cấu trúc của nó.
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 a 1, a 2, , a M gồm tất cả các phần tử của V' thỏa mãn a 1 a 2 a M
Bài toán sắp xếp một tập hợp các phần tử theo thứ tự toàn phần là một vấn đề quan trọng trong Lý thuyết Thuật toán Nó có thể được mô hình hóa dưới dạng bài toán trên đồ thị có hướng, trong đó quan hệ thứ tự được hiểu như đồ thị có hướng không có chu trình Do đó, việc sắp xếp một tập con theo trật tự toàn phần có thể được diễn đạt một cách chính xác.
Trong đồ thị có hướng G(V', E') không có chu trình, việc tìm kiếm đường đi có độ dài cực đại là một bài toán quan trọng Quan hệ E' trong công thức này rõ ràng là hạn chế E trên tập hợp đỉnh V' Đồ thị có hướng không có chu trình, hay còn gọi là đồ thị DAG (Directed Acyclic Graphs), rất phổ biến trong nhiều lĩnh vực.
Bài toán 6 yêu cầu tìm một dãy phần tử a1, a2, , aM từ tập hợp V, sao cho dãy này có chiều dài cực đại và thỏa mãn quan hệ thứ tự bộ phận E, tức là 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 R 1⊆ A × B và R 2⊆B × A, như vậy (a, b) ∈R 1 khi và chỉ khi (b,a)
∈R 2 Tìm một tập hợp {(a 1, b 1), (a 2, b 2), , (a M , b M )} của R 1 (hoặc {(b 1, a 1), (b 2, a 2), , (b M , a M )} của R 2) với số lượng phần tử tối đa, thỏa mãn a i = a j và b i = b j, 1 i < j M.
Quan hệ giữa R1 và R2 được gọi là đảo ngược lẫn nhau Một ví dụ cho 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 đi qua điểm p" Trong thực tế, một ví dụ khác là "người p có thể thực hiện công việc w".
"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, R 1 ) (hoặc G (V = A ∪B,
R 2)) coi các phần tử của R 1 (hoặc R 2) là không có thứ tự, tạo thành một đồ thị hai phía Việc xác định tập con có M cạnh, trong đó mỗi đỉnh là đầu mút của tối đa 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,
R 1) Tìm cặp ghép cực đại của G".
Cây và cây có gốc
Khi thảo luận về các bài toán đồ thị, khái niệm cây là rất quan trọng Theo định nghĩa cổ điển, một đồ thị T(V, E) được coi là một cây nếu nó liên thông và không chứa chu trình Hai định nghĩa quy nạp tương đương của cây cũng được đưa ra để làm rõ hơn về khái niệm này.
(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 = {v 1, v 2, , v k } Cho v ∈V và w V;
(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 T 1(V 1, E 1), T 2(V 2, E 2), , T k (V k , E k ), là các cây có gốc tương ứng là r 1, r 2, , r k , và lá L 1, L 2, , Lc Cho r V 1 ∪V 2 ∪ ∪V k ;
(iii) thì, T'(V' = V 1 ∪V 2 ∪ ∪V k {∪ r}, E' = E 1 ∪E 2 ∪ ∪E k {(∪ r, r 1), (r, r 2), , (r, r k )}) cũng là một cây có gốc r và lá của T' là L 1 ∪ L 2 ∪ ∪Lc Các cây có gốc T 1, T 2, , T k đượ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.
Cây được định nghĩa là đồ thị vô hướng, trong đó một đỉnh được chọn làm gốc Khi đó, mỗi đỉnh khác có thể được xác định là con hoặc cha của một đỉnh khác, tạo nên mối quan hệ phân cấp Mỗi cây đều có thể được xây dựng lại từ một đỉnh bất kỳ được chọn làm gốc, khẳng định rằng mọi cây đều có thể trở thành cây có gốc.
Nếu G(V,E) là một đồ thị và T(V, E') là một cây với E' ⊆ E, thì T được gọi là cây khung của G Đồ thị G sẽ được xem là liên thông nếu và chỉ nếu nó tồn tại một cây khung.
Để kiểm tra tính liên thông của đồ thị G một cách tự nhiên, chúng ta có thể xây dựng một cây khung của G Nếu c: E → C là 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í cho cây khung của G.
T c 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à cây khung tối thiểu (tối đa) của G.
Hình 2 Minh họa hai định nghĩa tương đương về cây có gốc
Biểu diễn đồ thị và cây
Trong các lĩnh vực khác nhau, việc sử dụng cấu trúc dữ liệu để biểu diễn các kiểu dữ liệu trừu tượng như đồ thị vô hướng, đồ thị có hướng, đa đồ thị và cây là rất quan trọng cho việc phát triển thuật toán hiệu quả Đồ thị thường được nhập qua tập tin đầu vào dưới dạng danh sách cạnh, kèm theo số đỉnh n và số cạnh m, cùng với hướng dẫn xác định loại đồ thị là vô hướng hay có hướng.
Khi một phần quan trọng của thuật toán thao tác trên cấu trúc đồ thị G(V, E) sử dụng lệnh lặp dạng "for e ∈ G do { }", danh sách cạnh sẽ có chi phí thời gian O(m) Ngược lại, nếu đồ thị G được biểu diễn bằng ma trận kề, chẳng hạn như mảng hai chiều g với g[v][w] là số cạnh nối giữa v và w, chi phí thời gian sẽ tăng lên O(n²), dẫn đến thời gian thực thi chậm hơn, đặc biệt là 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: rvw
Khi thực hiện với cấu trúc danh sách cạnh, chi phí thời gian cho thuật toán là O(|V'| |V''| m), trong khi với cấu trúc ma trận kề, chi phí thời gian giảm xuống còn O(|V'| |V''|) Do đó, việc sử dụng ma trận kề là lựa chọn tối ưu hơn so với danh sách cạnh trong trường hợp này.
Khi thuật toán sử dụng lệnh lặp dạng "for v V do {∈ for w|(v, w) E do { }}∈", chi phí thời gian với cấu trúc ma trận kề sẽ là O(n²), trong khi với danh sách kề, chi phí sẽ giảm xuống còn O(m) Đối với các cây có gốc, danh sách cha g[] được biểu diễn với g[i] là cha của đỉnh i (không phải gốc) và g[r] = 0 cho đỉnh gốc r Cách biểu diễn này rất hữu ích trong việc xây dựng cây có gốc, như cây khung và cây khung tối thiểu, cũng như trong quá trình duyệt cây.
TÌM HIỂU MỘT SỐ CÁCH PHÂN LOẠI BÀI TOÁN ĐỒ THỊ
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
+ 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
+ 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ị
+ 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 của TS Lê Minh Hoàng, Tài liệu giáo khoa chuyên Tin quyển 1 và 2 do TS Hồ Sĩ Đàm chủ biên, cùng với sách Toán rời rạc của TS Nguyễn Đức Nghĩa và TS Nguyễn Tô Thành đều có cấu trúc kiến thức lý thuyết đồ thị tương đồng.
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
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:
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.
Nhận xét và lựa chọn của chúng tôi
Các bài toán đồ thị được phân loại theo logic lý thuyết đồ thị, như đã nêu trong phần 3.2.1, là các phân loại truyền thống thường thấy trong 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 áp dụng cách phân loại này trong chương trình dạy toán đồ thị cho học sinh 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à tài liệu tham khảo hữu ích cho học sinh, giúp làm rõ những mô đun trong phân phối chương trình Tin của Bộ GD&ĐT, vì hiện tại các mô đun này chưa được cụ thể, khoa học và logic.
Phân loại bài toán dựa trên các thuật toán sử dụng là phương pháp phổ biến trong các sách về thuật toán Những cuốn sách này không chỉ tập trung vào các bài toán trong một lĩnh vực toán học cụ thể mà còn giới thiệu các nguyên tắc và phương pháp thiết kế, phân tích thuật toán.
Trong cuốn tài liệu "Introduction to Algorithms", phần 3.2 trình bày về các thuật toán cơ bản của đồ thị, bao gồm hai phương pháp duyệt đỉnh: BFS (Breadth-First Search) và DFS (Depth-First Search) Cả hai thuật toán này được áp dụng để giải quyết các vấn đề liên quan đến tính liên thông của đồ thị và tìm đường đi giữa hai đỉnh Cụ thể, BFS được sử dụng để xây dựng cây đường đi ngắn nhất trong đồ thị không có hàm chi phí trên các cạnh, trong khi DFS là bước cơ bản để thực hiện sắp xếp topo, tìm kiếm các thành phần liên thông mạnh, điểm khớp và cầu trong đồ thị.
Chương hai tập trung vào các thuật toán tìm cây khung tối thiểu (MST) của đồ thị Nội dung chương cũng đề cập đến các thuật toán MST trong bối cảnh thuật toán tham lam, với một phần đặc biệt dành riêng cho việc áp dụng phương pháp này trên đồ thị.
Hai chương tiếp theo tập trung vào "Đường đi đơn ngắn nhất" và "Đường đi ngắn nhất giữa tất cả các cặp đỉnh", có thể gộp lại thành một chương như trong nhiều tài liệu thuật toán khác Đầu tiên, khái niệm "ngắn nhất" cần được mở rộng để bao gồm các bài toán như tìm đường đi lớn nhất và đường đi tin cậy hơn, có thể giải quyết bằng phương pháp làm tốt dần Thứ hai, các bài toán tìm kiếm tâm, điểm giữa, bán kính hoặc đường kính của đồ thị cũng có thể được giải bằng phương pháp tương tự.
Chương cuối cùng mang tên "Luồng cực đại" không chỉ trình bày các thuật toán cơ bản để xác định luồng cực đại trong mạng lưới mà còn khám phá 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.
Việc phân chia các bài toán đồ thị theo nhóm các thuật toán, như đã đề cập trong phần 3.2, là rất hữu ích cho việc ô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 đã áp dụng phương pháp này trong quá trình ôn luyện, giúp học sinh nhận diện dạng bài toán đồ thị và nhanh chóng lựa chọn thuật toán phù hợp để giải quyết bài tập Ngoài ra, trong quá trình ôn tập, chúng tôi cũng tham khảo thêm các chủ đề bài tập từ các tài liệu như "Art of Programming Contest".
The Programming Contest Training Manual
[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
[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
[5] Robert Sedgetwick, Algorithms, Addison-Wesley Publishing Co, 1984.
[6] Krassimir Manev, Tasks on Graphs, 2008.
MỘT SỐ BÀI TOÁN VỀ CÂY KHUNG NHỎ NHẤT
Bài toán cây khung nhỏ nhất là một bài toán tối ưu quan trọng trong lý thuyết đồ thị, với hai thuật toán chính để giải quyết là Prim và Kruskal Cuốn Tài liệu Giáo khoa chuyên Tin (Quyển 2) đã trình bày chi tiết về hai thuật toán này, bao gồm hướng dẫn cài đặt và đánh giá độ phức tạp tính toán Bài viết này sẽ giới thiệu một số bài tập áp dụng các thuật toán trên.
Bài toán 1: Vòng đua F1- Mã bài: NKRACING
Singapore sẽ tổ chức cuộc đua xe Công Thức 1 đầu tiên vào năm 2008, nhưng trước đó đã xuất hiện nhiều cuộc đua đêm trái phép Để kiểm soát tình trạng này, chính quyền đã lên kế hoạch thiết lập một hệ thống giám sát giao thông với nhiều camera đặt trên các tuyến đường Để hệ thống hoạt động hiệu quả, cần đảm bảo có ít nhất một camera dọc theo mỗi vòng đua.
Hệ thống đường ở Singapore bao gồm các nút giao thông và đường hai chiều, tạo thành một vòng đua từ một nút giao thông xuất phát Vòng đua này bao gồm ít nhất 3 tuyến đường, và mỗi tuyến đường chỉ được đi qua một lần và theo đúng một hướng, trước khi quay trở lại điểm xuất phát.
Chi phí lắp đặt camera phụ thuộc vào tuyến đường được chọn, với các số nhỏ trong hình vẽ biểu thị chi phí cho từng tuyến Các số lớn đánh dấu các nút giao thông, nhưng camera sẽ được lắp đặt trên các tuyến đường chứ không phải tại các nút Để tối ưu chi phí, bạn cần lựa chọn các tuyến đường sao cho tổng chi phí lắp đặt là thấp nhất, đồng thời đảm bảo có ít nhất một camera dọc theo mỗi vòng đua.
Viết chương trính tìm cách đặt các camera theo dõi giao thông sao cho tổng chi phí lắp đặt là thấp nhất.
Dòng đầu tiên chứa 2 số nguyên n, m ( 1 ≤ n ≤ 10000, 1 ≤ m ≤ 100000) là số nút giao thông và số đường nối Các nút giao thông được đánh số từ 1 đến n.
Mỗi dòng tiếp theo mô tả các đường nối, bao gồm ba số nguyên dương: hai đầu mút của tuyến đường và chi phí lắp đặt camera Chi phí lắp đặt nằm trong khoảng từ 1 đến 1000.
In ra 1 số nguyên duy nhất là tổng chi phí lắp đặt thất nhất tìm được.
Giả sử chúng ta đã lắp đặt camera ở tất cả các tuyến đường, nhiệm vụ bây giờ là xác định cách loại bỏ một số camera nhằm giảm thiểu tổng chi phí một cách hiệu quả nhất.
Để tối ưu hóa chi phí, cần xác định cây khung lớn nhất của đồ thị từ các tuyến đường bỏ đi, đảm bảo không chứa chu trình để tránh tạo ra vòng đua không được giám sát Việc này cho phép loại bỏ tối đa n-1 camera trên n-1 tuyến đường, giúp giảm thiểu chi phí giám sát hiệu quả.
{$mode objfpc} const fi='nkracing.inp'; fo='nkracing.out'; max000; maxm0000; vc0000000; var f:text; n,m,kq:longint; x,y,c:array[0 maxm+1]of longint;