CHUYÊN ĐỀ TIN HỌC THPT NĂM 2021 - 2022: sắp xếp topo c++, thuật toán sắp xếp topo, sắp xếp topo toán rời rạc

[Yopovn]

CHUYÊN ĐỀ TIN HỌC THPT NĂM 2021 - 2022: sắp xếp topo c++, thuật toán sắp xếp topo, sắp xếp topo toán rời rạc

SẮP XẾP TOPO - MỘT BÀI TOÁN CỔ ĐIỂN
​

1. Sắp xếp topo:

Sắp xếp topo (topological sorting) là một trong những bài toán có tính ứng dụng cao cả trong Tin học lẫn Toán học và đời sống thường ngày. Đây là quá trình sắp xếp một dãy các phần tử sao cho thứ tự mới vẫn đảm bảo được thứ tự cục bộ (một cách nôm na có nghĩa là thứ tự được xác định đối với một vài cặp phần tử chứ không phải là tất cả các phần tử) vốn có của chúng. Một số ví dụ sẽ minh hoạ điều này

Ví dụ 1:

i) Một đề án có thể được chia thành nhiều nhiều công việc nhỏ khác nhau, tuy nhiên trong đó có những công việc chỉ có thể thực hiện được sau khi một số công việc khác đã hoàn thành. Nếu việc v buộc phải hoàn thành trước việc w (khi ấy việc w mới có thể thực hiện), ta kí hiệu v w. Sắp xếp topo trong trường hợp này nghĩa là đưa ra một thứ tự thực hiện các công việc hợp lý để có thể hoàn thành đề án.

ii) Trong một số trường ĐH ở VN hiện nay, có những học phần gọi là học phần tiên quyết mà sinh viên buộc phải hoàn thành trước khi học các học phần khác. Nếu học phần v là học phần tiên quyết đối với học phần w, ta viết v w. Sắp xếp topo ở đây có nghĩa là đưa ra thứ tự học các học phần sao cho mọi học phần phải được học sau các học phần tiên quyết của nó.

Một thứ tự cục bộ trên tập S thực chất là một quan hệ giữa các phần tử trên tập S, và khi đó S được gọi là tập được sắp xếp cục bộ (1). Thông thường thứ tự cục bộ được kí hiệu là (2), và phải thoả các tính chất (xem như tiên đề) sau với mọi x, y, z S:

i) Tính phản xạ: x ≤ x,
ii) Tính phản xứng: nếu x ≤ y và y ≤ x thì x=y, và
iii) Tính bắc cầu: nếu x ≤ y, y ≤ z thì x ≤ z.

Ví dụ 2:

i) Quan hệ chia hết trên Z+ là một thứ tự cục bộ.
ii) Quan hệ “nhỏ hơn hay bằng” (≤) trên tập các số nguyên là một thứ tự cục bộ.
iii) Quan hệ “nhỏ hơn” (<) trên Z không phải là thứ tự cục bộ, vì nó phản xứng, bắc cầu nhưng không phản xạ. (bạn đọc có thể tự kiểm chứng một cách dễ dàng).

Trong một tập được sắp xếp cục bộ, kí hiệu x y cũng được dùng để chỉ x ≤ y mà x ≠ y.

Một cách hiển nhiên, ta giả sử tập S cần sắp xếp topo là tập hữu hạn. Do đó một thứ tự cục bộ có thể được biểu diễn bởi một đồ thị có hướng mà các đỉnh của đồ thị biểu diễn các phần tử của S, đồng thời các cạnh có hướng biểu diễn thứ tự giữa các phần tử.

Để tiện theo dõi, giả sử có 10 công việc cần thực hiện (đây chính là tập S) được đánh số từ 1 đến 10, với thứ tự cục bộ như sau:

​

Khi đó, đồ thị biểu diễn của tập S có dạng như hình 1:

​

Sắp xếp topo phải xây dựng được thứ tự toàn bộ từ thứ tự cục bộ đã cho (3). Một cách trực quan, đó là quá trình vẽ lại đồ thị ở hình 1 thành một đồ thị mới sao cho tất cả các đỉnh đều nằm trên một hàng và tất cả các cạnh đều hướng sang phải (xem hình 2)