Khác biệt giữa bản sửa đổi của “Sắp xếp tô pô”
Nội dung được xóa Nội dung được thêm vào
Không có tóm lược sửa đổi |
n Đã lùi lại sửa đổi của 2001:EE0:4FCD:3770:7992:AA7A:B259:6605 (Thảo luận) quay về phiên bản cuối của Ngomanh123 Thẻ: Lùi tất cả |
||
Dòng 1:
Trong [[khoa học máy tính]], '''thứ tự tô pô''' của một [[đồ thị (lý thuyết đồ thị)#đồ thị có hướng|đồ 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ị [[đồ thị có hướng không có chu trình|không có chu trình]] (viết tắt là DAG - [[tiếng Anh]] directed acyclic graph). Đồ 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.
=== Ví dụ ===
| |||