TAILIEUCHUNG - GIÁO TRÌNH TOÁN RỜI RẠC - CHƯƠNG V MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ_3

. Định nghĩa: Cho A V là tập con tuỳ ý không chứa lối vào v0 và chứa lối ra vn. Tập (A) được gọi là một thiết diện của mạng vận tải G. Đại lượng m( (A))= thiết diện (A). | CHƯƠNG V MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐÒ THỊ . Định nghĩa Cho A c V là tập con tuỳ ý không chứa lối vào v0 và chứa lối ra vn. Tập r- A được gọi là một thiết diện của mạng vận tải G. Đại lượng m r- A m e được gọi là khả năng thông qua của eíl A thiết diện r- A . Từ định nghĩa thiết diện và khả năng thông qua của nó ta nhận thấy rằng mỗi đơn vị hàng hoá được chuyển từ v0 đến vn ít nhất cũng phải một lần qua một cung nào đó của thiết diện r- A . Vì vậy dù luồng ọ và thiết diện r- A như thế nào đi nữa cũng vẫn thoả mãn quan hệ Ọn m r- A . Do đó nếu đối với luồng ọ và thiết diện W mà có Ọn m W thì chắc chắn rằng luồng ọ đạt giá trị lớn nhất và thiết diện W có khả năng thông qua nhỏ nhất. . Định nghĩa Cung e trong mạng vận tải G với luồng vận tải ọ được goi là cung bão hoà nếu ọ e m e . Luồng ọ của mạng vận tải G được gọi là luồng đầy nếu mỗi đường đi từ v0 đến vn đều chứa ít nhất một cung bão hoà. Từ định nghĩa trên ta thấy rằng nếu luồng ọ trong mạng vận tải G chưa đầy thì nhất định tìm được đường đi a từ lối vào v0 đến lối ra vn không chứa cung bão hoà. Khi đó ta nâng luồng ọ thành ọ như sau p e p e 1 khi e a p e khi e Ẻa. Khi đó ọ cũng là một luồng mà giá trị của nó là ọ n Ọn 1 Ọn. Như vậy đối với mỗi luồng không đầy ta có thể nâng giá trị của nó và nâng cho tới khi nhận được một luồng đầy. Tuy vậy thực tế cho thấy rằng có thể có một luồng đầy nhưng vẫn chưa đạt tới giá trị cực đại. Bởi vậy cần phải dùng thuật toán Ford-Fulkerson để tìm giá trị cực đại của luồng. . Thuật toán Ford-Fulkerson Để tìm luồng cực đại của mạng vận tải G ta xuất phát từ luồng tuỳ ý ọ của G rồi nâng luồng lên đầy sau đó áp dụng thuật toán Ford-Fulkerson hoặc ta có thể áp dụng thuật toán Ford-Fulkerson trực tiếp đối với luồng ọ. Thuật toán gồm 3 bước Bước 1 đánh dấu ở đỉnh của mạng Lối vào v0 được đánh dấu bằng 0. 1 Nếu đỉnh vi đã được đánh dấu thì ta dùng chỉ số i để đánh dấu cho mọi đỉnh y chưa được đánh dấu mà vi y eE và cung này chưa bão hoà ọ v y m vi y . 2 Nếu đỉnh vi

• Toán học
• thuật toán
• khái niệm thuật toán
• toán rời rạc
• giáo trình toán rời rạc
• tài liệu toán rời rạc
• Thuật toán và tư duy thuật toán
• Đặc trưng cơ bản về thuật toán
• Thiết kế thuật toán
• Hiệu quả giảng dạy thuật toán
• Cài đặt thuật toán
• Vấn đề tư duy thuật toán
• Ngôn ngữ lập trình
• Bài giảng thuật toán
• Biểu diễn thuật toán
• Kỹ thuật thiết kế thuật toán
• Phân tích thuật toán
• Đáng giá thuật toán
• Thuật toán máy tính
• Thuật toán tham lam
• Đánh giá thuật toán
• Bài giảng đánh giá thuật toán
• Bài giảng thiết kế thuật toán
• Bài toán sắp xếp
• Sắp xếp chèn
• Tự học lập trình
• Bài giảng Tin học 10
• Bài giảng Tin học 10 Bài 4
• Bài 4 Bài toán và thuật toán
• Bài giảng Bài toán và thuật toán
• Khái niệm bài toán
• Thuật toán tìm Max của một dãy số
• Cẩm nang thuật toán
• Phương pháp giải thuật toán
• Thuật toán thông dụng
• Thuật toán sắp xếp
• Thuật toán tìm kiếm
• Thuật toán xử lý chuỗi
• Thuật toán chuyên dụng
• Một số vấn đề về thuật toán
• Độ phức tạp thuật toán
• Phương pháp trong thuật toán
• Tính đúng đắn của thuật toán
• thuật toán DDA
• thuật toán bresenham
• thuật toán đường tròn
• thuật toán MidPoint
• thuật toán vẽ Ellipse
• Thuật toán tô màu
• Bài giảng Phân tích thuật toán
• Tính chất cơ bản của thuật toán
• Độ phức tạp của thuật toán
• Ước lượng tiệm cận
• Thuật toán Google
• Thuật toán Sand
• Thuật toán chim ruồi
• Thuật toán ngựa vằn Zebra Box
• Thuật toán Chim cánh cụt
• Thuật toán Gấu trúc Panda
• Đề thi cuối kì môn Toán kỹ thuật
• Bài thi môn Toán kỹ thuật
• Ôn thi Toán kỹ thuật
• Luyện thi Toán kỹ thuật
• Tài liệu thi Toán kỹ thuật
• Hướng dẫn thi Toán kỹ thuật
• Lý thuyết thuật toán tìm đường
• Thuật toán tìm đường
• Thuật toán tìm đường đi ngắn nhất
• Thuật toán tìm đường đi
• Xây dựng thuật toán
• Thuật toán xử lý thông tin
• Đặc trưng của thuật toán
• Thuật toán Euclid cải tiến
• Ngôn ngữ thuật toán
• Diễn tả thuật toán
• Phân tích thiết kế thuật toán
• Đề thi Phân tích thiết kế thuật toán
• Câu hỏi Phân tích thiết kế thuật toán
• Ôn tập Phân tích thiết kế thuật toán
• Trình diễn thuật toán
• Thuật toán nâng cao
• Bài giảng Thuật toán nâng cao
• Tính chất của thuật toán
• Đặc tả thuật toán
• Bài giảng Thuật toán Ứng dụng
• Thuật toán Ứng dụng
• Quy hoạch động
• Bài giảng Phân tích thiết kế thuật toán
• Kỹ thuật phân tích thuật toán
• Đánh giá một giải thuật
• Khóa luận tốt nghiệp
• Khóa luận tốt nghiệp Kế toán Kiểm toán
• Kế toán Kiểm toán
• Kế toán thanh toán
• Nguyên tắc kế toán thanh toán với người mua
• Nguyên tắc kế toán thanh toán với người bán
• Thuật toán gần đúng
• Bài toán tối ưu tổ hợp
• Tối ưu tổ hợp
• Toán tối ưu tổ hợp
• Ứng dụng thuật toán gần đúng
• Tìm hiểu thuật toán gần đúng
• Tài liệu thuật toán gần đúng
• Sáng kiến kinh nghiệm
• Bài tập xây dựng thuật toán giải bài toán
• Thuật toán giải bài toán
• Xây dựng thuật toán máy tính
• Kỹ thuật kiểm toán
• tài liệu Kỹ thuật kiểm toán
• bài giảng Kỹ thuật kiểm toán
• kế toán kiểm toán
• nghiệp vụ kế toán
• kế toán tài chính
• kế toán doanh nghiệp