Đang chuẩn bị liên kết để tải về tài liệu:
Luận văn Thạc sĩ Toán học: Bài toán luồng lớn nhất và luồng chi phí nhỏ nhất trên mạng

Mục đích chính của luận văn là tìm hiểu và trình bày về hai bài toán nói trên và các thuật toán giải hai bài toán đó. Luận văn được viết dựa chủ yếu trên các tài liệu tham khảo hiện có. Mời các bạn tham khảo! | ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC HOÀNG THỊ CÚC BÀI TOÁN LUỒNG LỚN NHẤT VÀ LUỒNG CHI PHÍ NHỎ NHẤT TRÊN MẠNG LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2016 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC HOÀNG THỊ CÚC BÀI TOÁN LUỒNG LỚN NHẤT VÀ LUỒNG CHI PHÍ NHỎ NHẤT TRÊN MẠNG LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành Toán ứng dụng Mã số 60 46 01 12 NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TS. TRẦN VŨ THIỆU Thái Nguyên - 2016 i Mục lục Danh sách kí hiệu iii Danh sách hình vẽ v Lời nói đầu 1 Chương 1. Kiến thức chuẩn bị 4 1.1 Khái niệm cơ bản về đồ thị . . . . . . . . . . . . . . . . . . . . . 4 1.1.1 Định nghĩa và ký hiệu . . . . . . . . . . . . . . . . . . . 4 1.1.2 Đồ thị đẳng cấu . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.3 Đồ thị liên thông . . . . . . . . . . . . . . . . . . . . . . 8 1.1.4 Đường và chu trình trong đồ thị . . . . . . . . . . . . . . 8 1.1.5 Một số dạng đồ thị đặc biệt . . . . . . . . . . . . . . . . . 9 1.2 Mạng và luồng . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3 Một số bài toán tối ưu trên đồ thị . . . . . . . . . . . . . . . . . . 13 1.3.1 Ghép cặp phủ cạnh phủ đỉnh tập ổn định và clique . . . 13 1.3.2 Bài toán phủ đỉnh phủ cạnh và ghép cặp . . . . . . . . . 14 1.4 Kết luận Chương 1 . . . . . . . . . . . . . . . . . . . . . . . . . 15 Chương 2. Bài toán luồng lớn nhất trên mạng 17 2.1 Nội dung bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.1.1 Mạng và luồng . . . . . . . . . . . . . . . . . . . . . . . 17 ii 2.1.2 Luồng tương thích lớn nhất . . . . . . . . . . . . . . . . . 19 2.1.3 Bài toán luồng lớn nhất trên mạng . . . . . . . . . . . . . 19 2.1.4 Tiêu chuẩn tối ưu . . . . . . . . . . . . . . . . . . . . . . 20 2.2 Thuật toán tìm luồng lớn nhất . . . . . . . . . . . . . . . . . . . . 22 2.3 Luồng lớn nhất và thiết diện nhỏ nhất . . . . . . . . . . . . . . . 25 2.3.1 Khả năng của một mạng . . . . . . . . . . . . . . . . . . 25 2.3.2 Thiết diện nhỏ nhất . . . . . . . . . . . . . . . . . . . . . 27 2.4 Kết .