Bài giảng Toán rời rạc (Phần 2) - Trần Nguyễn Minh Thư

Thứ tự tôpô của một đồ thị có hướng là một thứ tự sắp xếp của các đỉnh sao cho với mọi cung từ u đến v

trong đồ thị, u luôn nằm trước v.

Thuật toán để tìm thứ tự tôpô gọi là thuật toán sắp xếp tôpô.

Thứ tự tôpô tồn tại khi và chỉ khi đồ thị không có

chu trình. Đồ thị có hướng không có chu trình luôn

có ít nhất một thứ tự tôpô, và có thuật toán để tìm thứ

tự tô pô trong thời gian tuyến tính.