Khái niệm

Mạng AOV (Activity On Vertex)

1. Một dự án lớn thường được chia thành nhiều công việc con, chúng được gọi là hoạt động. Trong toàn bộ dự án, một số công việc con (hoạt động) chỉ có thể bắt đầu sau khi các công việc con trước đó hoàn thành. Để phản ánh mối quan hệ giữa các hoạt động, ta sử dụng đồ thị có hướng, trong đó các đỉnh đại diện cho hoạt động và cạnh có hướng đại diện cho mối quan hệ trước-sau giữa các hoạt động. Đồ thị này được gọi là mạng AOV (Activity On Vertex).
2. Mạng AOV phải là đồ thị có hướng không chứa chu trình, vì nếu có chu trình, các hoạt động trong chu trình sẽ không thể thực hiện. Nếu xuất hiện chu trình, điều này dẫn đến tình trạng deadlock hoặc vòng lặp vô tận.
3. Trong mạng AOV, nếu không tồn tại chu trình, tất cả các hoạt động có thể sắp xếp thành một dãy tuyến tính, sao cho mỗi hoạt động đều có tất cả các hoạt động tiền nhiệm đứng trước nó. Dãy này được gọi là dãy topo (topological order). Quá trình tạo ra dãy topo từ mạng AOV được gọi là sắp xếp topo (topological sort).

Cách giải quyết

1. Kiểm tra chu trình: Sử dụng DFS để kiểm tra chu trình. Nếu gặp đỉnh đang được thăm, có nghĩa là có chu trình.

• vis[i] = 0 chưa thăm
• vis[i] = 1 đã thăm
• vis[i] = -1 đang thăm

bool topddfs(int x) {
    vis[x] = -1;
    for (int i = head[x]; i; i = e[i].next) {
        if (vis[e[i].to] == -1) return false;
        if (!vis[e[i].to] && !topddfs(e[i].to)) return false;
    }
    vis[x] = 1;
    return true;
}

2. Sắp xếp topo: Lấy tất cả các đỉnh có bậc vào bằng 0, thêm vào hàng đợi. Mỗi lần lấy một đỉnh từ hàng đợi, giảm bậc vào của các đỉnh kề với đỉnh đó, nếu bậc vào của đỉnh kề bằng 0, thêm vào hàng đợi.

void topsort() {
    for (int i = 1; i <= n; ++i) {
        if (in[i] == 0) q.push(i);
    }
    while (!q.empty()) {
        int x = q.front(); q.pop();
        ans[++top] = x;
        for (int i = head[x]; i; i = e[i].next) {
            --in[e[i].to];
            if (in[e[i].to] == 0) q.push(e[i].to);
        }
    }
}

Tìm đường đi dài nhất/ ngắn nhất

Để tìm đường đi dài nhất/ ngắn nhất, sử dụng phương pháp quy hoạch động:

• Phương trình quy hoạch động: dp[to] = max(dp[to], dp[x])
• Khởi tạo dp[] bằng 0 cho đường đi dài nhất, và bằng giá trị cực đại cho đường đi ngắn nhất.

Ghi nhớ đường đi

void gt(int x) { // đệ quy
    if (x == 0) return;
    gt(pre[x]);
    ans[++top] = x;
}

while (xb) { // vòng lặp
    ans[++top] = xb;
    xb = pre[xb];
}

Đường đi quan trọng (Critical Path)

Khái niệm

1. Đường đi quan trọng (Critical Path) là chuỗi các hoạt động quyết định thời gian hoàn thành dự án. Nó là đường đi dài nhất trong mạng, và bất kỳ sự chậm trễ nào trên đường đi này cũng sẽ ảnh hưởng trực tiếp đến thời gian hoàn thành dự án.
2. Một dự án có thể có nhiều đường đi quan trọng song song. Đường đi có tổng thời gian gần bằng đường đi quan trọng được gọi là đường đi quan trọng thứ cấp.
3. Mạng AOE (Activity On Edge) sử dụng đỉnh để biểu diễn sự kiện và cạnh để biểu diễn hoạt động, với trọng số cạnh là thời gian hoạt động. Mạng AOE thường được sử dụng để ước lượng thời gian hoàn thành dự án.
4. Đường đi quan trọng trong mạng AOE có thể không duy nhất. Chỉ khi sự kiện xảy ra, các hoạt động xuất phát từ đỉnh đó mới có thể bắt đầu. Chỉ khi tất cả các hoạt động kết thúc, sự kiện mới xảy ra. Mạng AOE nên không chứa chu trình và có duy nhất một đỉnh bắt đầu và một đỉnh kết thúc.

Tính chất

1. Phải thực hiện sắp xếp topo trước khi tìm đường đi quan trọng.
2. Chỉ khi giảm thời gian hoạt động quan trọng, thời gian hoàn thành dự án mới có thể giảm.
3. Nếu một hoạt động quan trọng không nằm trên tất cả các đường đi quan trọng, giảm thời gian của nó không làm giảm thời gian hoàn thành dự án.
4. Chỉ khi không thay đổi đường đi quan trọng, giảm thời gian hoạt động quan trọng mới có thể giảm thời gian hoàn thành dự án.

Phân tích

Đường đi quan trọng là đường đi dài nhất từ đầu đến cuối trong mạng AOE, cách tìm tương tự như tìm đường đi dài nhất.