MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ PHẦN 4

Chia sẻ: Nguyễn Thông | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST

Báo xấu

122
lượt xem 14
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo tài liệu 'một số bài toán tối ưu trên đồ thị phần 4', 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ả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ PHẦN 4

MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ - PHẦN 4 1. Dùng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh a đến các đỉnh khác trong đồ thị sau: d 2 3 4 2 k 7 b 12 4 1 e 2 5 4 c h 3 a g 5 7 11 1 b 2. Dùng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh a đến các đỉnh khác 4 f trong đồ thị sau: c g d h
1 10 2 5 4 k 2 10 1 6 3 a 4 i5 8 3 e 5 6 2 3 8 3. Cho đồ thị có trọng số nh ư hình dưới đây. Hãy tìm đường đi ngắn nhất từ đỉnh A đến đỉnh N. 7 3 3 8 A 2 4 2 2 B C D E F3 G 6H2 5 J K L M 3 2 2 9 1 I 2 4 2 5 4 3 3 2 3 4 7 5
N 4. Tìm đường đi ngắn nhất từ B đến các đỉnh khác của đồ thị có ma trận trọng số A FG CD là (các ô trống là ): B E A  36    B 3 24  6 2 142 C   D  41 2 4  2 1 42 E    4 2 2 F   414 G   5. Tìm W* bằng cách áp dụng thuật toán Floyd vào đồ thị sau: 8 B C 3 2 6 5 13 20 F A D 8 3 4 E 1 v1
6. Giải bài toán mạng vận tải sau bằng thuật toán Ford-Fulkerson với luồng vận tải khởi đầu bằng 0. v5 4 2 4 8 2 2 4 v2 6 v0 v4 v7 4 3 4 8 v3 v6 6 7. Giải bài toán mạng vận tải sau bằng thuật toán Ford-Fulkerson với luồng vận tải khởi đầu được cho kèm theo. 66 10 v1 10 8 6 15 0 8 2 v0 88 20 16 10 v7
v2 v3 v4 28 16 0 3 25 6 4 v6 3 6 v5 10 2 15 10 0 5 7 30 0 0 0 7 0 8 6 15 1 2 2 v10 2 2 v8 v11 4 12 2 v9 0 20 8. Hãy giải bài toán người du lịch với 6 thành phố, có số liệu cho trong ma trận trọng số sau:  25 45 14 32 24     9 16 2 34 23   22 0  11 33 7  .   23 14 27 20 21  14 3  44 29 46    25  3 4 7 8  