Danh mục

Bài giảng Toán rời rạc (Discrete Mathematics) - Bài 2: Xếp hạng đồ thị

Số trang: 99      Loại file: pdf      Dung lượng: 1.70 MB      Lượt xem: 18      Lượt tải: 0    
Jamona

Xem trước 10 trang đầu tiên của tài liệu này:

Thông tin tài liệu:

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.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc (Discrete Mathematics) - Bài 2: Xếp hạng đồ thịTRƯỜNG ĐẠI HỌC CẦN THƠKHOA CNTT & TRUYỀN THÔNGBỘ MÔN KHOA HỌC MÁY TÍNH1TOÁN RỜI RẠC(DISCRETE MATHEMATICS)08/2013GV: Trần Nguyễn Minh Thư (tnmthu@ctu.edu.vn)2XẾ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 vtrong đồ 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ắpxế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ôncó í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ạng1)- 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) = kVới mỗi j là ảnh của i (đỉnh đi từ i) thực hiện:d  d 1jjNếu d  0 thì gán Sk+1 = Sk+1 + {j}jk = k+1Nế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 hạng2471356

Tài liệu được xem nhiều: