Phân loại Topo có cố gắng sắp xếp các đỉnh hoặc cạnh không?

Question

Chúc mừng đông dân, mọi người.

Tôi hiện đang học loại topo và có câu hỏi về loại phân loại topo nào thực sự sắp xếp.

Các Algorithm Design Manual mô tả loại topo theo cách này:

phân loại tôpô là hoạt động quan trọng nhất trên đồ thị không chu trình có hướng (DAG). Nó ra lệnh cho các đỉnh trên một dòng sao cho tất cả các cạnh được chỉ đạo đi từ trái sang phải.

Phần táo bạo này làm tôi bối rối. Vì vậy, các đỉnh phân loại topo phân loại hoặc tất cả các cạnh đạo diễn?

Hãy lấy một ví dụ cũng có trong sách.

Vì vậy, đối với trên DAG, chúng tôi có thể nhận được một loại topo (G, A, B, C, F, E, D).

Tôi có thể hiểu loại này. Không chỉ các đỉnh được sắp xếp, mà các cạnh cũng được sắp xếp, tức là, G-> A-> B-> C-> F-> E-> D, điều này khớp với mô tả sách ADM ở trên: all directed edges go from left to right

Nhưng nếu tôi loại bỏ các cạnh của B-> C thì sao? Biểu đồ kết quả vẫn là một DAG, nhưng kiểu tôpô vẫn là (G, A, B, C, F, E, D)?

Nếu có, thì tôi nghĩ các cạnh không được sắp xếp, vì A-> B-> C không tồn tại nữa, thay vào đó, nó là A-> B và A-> C. Vì vậy, nó trường hợp này vẫn là một loại topo hợp lệ? Chúng ta có thể vẫn còn suy nghĩ (G, A, B, C, F, E, D) là một loại hợp lệ ngay cả khi A là cha mẹ của B và C?

Cảm ơn

Answer 1

Bạn có thể coi đó là thứ tự các yếu tố.

let v1, v2, ..., vn là các phần tử. và để một cạnh (vi,vj) biểu thị rằng vi<vj. topo loại đảm bảo rằng sau khi phân loại: cho mỗi vi, và cho mỗi vj mà i < j, vj là không lớn hơn sau đó vi

Hoặc trong ký hiệu khác: giả (vi,vj) chỉ ra rằng vj phụ thuộc vào vi, loại topo đảm bảo rằng mỗi phần tử "không phụ thuộc" vào bất kỳ phần tử nào xuất hiện sau khi sắp xếp.

Vì vậy, các đỉnh sắp xếp topo phân loại hoặc tất cả các cạnh được chỉ định?

sắp xếp topo sắp xếp các đỉnh, chứ không phải cạnh. Nó sử dụng các cạnh như các ràng buộc để phân loại các đỉnh.

Nhưng nếu tôi loại bỏ cạnh của B-> C thì sao?

có, mọi cạnh bạn thêm, chỉ thêm một ràng buộc.Lưu ý rằng có thể có nhiều hơn thì một giải pháp khả thi cho việc sắp xếp topo [ví dụ, đối với một đồ thị không có cạnh, bất kỳ hoán vị nào là một giải pháp khả thi]. loại bỏ một ràng buộc, làm cho bất kỳ giải pháp trước đó, mà "giải quyết một vấn đề khó khăn hơn" vẫn còn khả thi.

Chúng ta vẫn có thể nghĩ (G, A, B, C, F, E, D) là một loại hợp lệ ngay cả khi A là cha mẹ của B và C?

Không có vấn đề gì với điều đó! A xuất hiện trước B, C trong loại topo, do đó không có vấn đề gì là cha của họ.

Hy vọng điều đó sẽ rõ ràng hơn một chút.