Bài giảng Toán rời rạc (Discrete Mathematics) - Bài 2: Xếp hạng đồ thị được biên soạn nhằm trang bị cho các bạn những kiến thức về sắp xếp tôpô (xếp hạng), giải thuật xếp hạng. Đặc biệt, với những bài tập được đưa ra ở cuối bài giảng sẽ giúp cho các bạn nắm bắt kiến thức một cách tốt hơn. | TRƯỜNG ĐẠI HỌC CẦN THƠ KHOA CNTT & TRUYỀN THÔNG BỘ MÔN KHOA HỌC MÁY TÍNH 1 TOÁN RỜI RẠC (DISCRETE MATHEMATICS) 08/2013 GV: Trần Nguyễn Minh Thư (tnmthu@) 2 XẾP HẠNG ĐỒ THỊ Sắp xếp tôpô (xếp hạng) 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. Giải thuật xếp hạng 1)- Khởi tạo: i là tập hợp các ảnh của i (các đỉnh đi từ i) d i là số tạo ảnh của i ( i X), (tổng số đỉnh đến i) k=0 Sk= {s} 2)- Với mỗi k thực hiện: Sk+1 = Với mỗi i Sk thực hiện : r(i) = k Với mỗi j là ảnh của i (đỉnh đi từ i) thực hiện: d d 1 j j Nếu d 0 thì gán Sk+1 = Sk+1 + {j} j k = k+1 Nếu Sk = thì giải thuật kết thúc, ngược lại thì quay về (2). Giải thuật xếp .
