tailieunhanh - Cẩm nang thuật toán tập 2 part 6

Tham khảo tài liệu 'cẩm nang thuật toán tập 2 part 6', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | tXỈTHỊCỎ ỈỊƯỚNG 169 BÀI TẬP 1. Hãy cho biết ma trân kê của bao đóng của dag trong Hình . 2. Nếu áp dụng thuật toán tìm bao đóng vào một đô thị vô hướng biểu diẾn băng ma trận kè thì kết quả như thế nào 3. Hãy viết một chường trình để tìm số cạnh của bao đóng cùa một đô thị có hưởng bang cách dùng biểu diễn xâu kê. 4. Hãy so sanh thuật toán Warshall với thuật toán tìm bao đóng bằng cách dùng kỹ thuật tìm kiếm ưu tiên độ sâu nhưng sử dụng dạng ma trận kê cho thủ tục visit và khử bỏ đè quy. 5. Hãy cho biết thứ tự tôpố có được đối với DAG trong Hình khi dùng phương pháp đã nói vối biểu diễn ma trận kê nhưng thủ tục quét qua các đỉnh theo thứ tự đảo ngược từ V xuống 1 trong quá trình tìm kiếm các đỉnh chưa dược viếng. 6. Thuật toán tim đường đi ngán nhất trong Chương 31 có đúng đối với đô thị có hướng hay không Giâi thích tại sao và cho một ví dụ nếu nó sai. 7. Viết một chương trình để kiểm tra xem một đô thị đã cho có là một DAG hay không. 8. Có hao nhiêu thành phàn liên thòng mạnh trong một DAG Có bao nhiêu thành phàn lièn thông mạnh trong một đô thị có một chu trình có hướng kích thước V 9. Sử dụng chương trình trong Chương 29 và Chương 30 để tìm ra các đô thị có hướng ngẫu nhiên vởi V đỉnh. Có bao nhiêu thành phán liên thòng mạnh trong các đô thị như thế 10. Viết mốt chương trinh có chức năng tương tự như thù tục find trong Chương 30 nhưng chú ý các thành phần liên thông mạnh của dò t hị có hướng bài tập này không dễ chác chán bạn sẽ không thể có được một chương trình hiệu quâ như thủ tục find. 33 DÒNG CHẢY TRONG MẠNG LƯỚI Các đô thị có hướng và có trọng số ỉà các mô hình hữu dụng cho các ứng dụng càn đến sự di chuyển trong một mạng lưới. Một ví dụ là mạng lưới gôm các ống dẫn dâu với nhiều kích cỡ khác nhau được nối lại rất đa dạng với các còng tắc điêu khiển hướng đi của đâu trong ống tại các điểm nối. Giả sử mạng lưới có một nơi bắt ngũôn chằng hạn bể chứa dâu và một nơi kết thúc đủ lớn cho tất cã các ống đản nối tói chúng. Làm thê nào để lượng dâu