TAILIEUCHUNG - Đề tài: " BÀI TỐN LUỒNG CỰC ĐẠI VỚI KHẢ NĂNG THÔNG QUA CÁC CUNG – CÁC ĐỈNH "

Chương 2 BÀI TỐN LUỒNG CỰC ĐẠI VỚI KHẢ NĂNG THÔNG QUA CÁC CUNG – CÁC ĐỈNH Bài tốn luồng cực đại trong mạng là một trong số những bài tốn tối ưu trên đồ thị tìm được những ứng dụng rộng rãi trong thực tế cũng như những ứng dụng thú vị trong lý thuyết tổ hợp. | Chương 2 BÀI TỐN LUỒNG CỰC ĐẠI VỚI KHẢ NĂNG THÔNG QUA CÁC CUNG - CÁC ĐỈNH Bài tốn luồng cực đại trong mạng là một trong số những bài tốn tối ưu trên đồ thị tìm được những ứng dụng rộng rãi trong thực tế cũng như những ứng dụng thú vị trong lý thuyết tổ hợp. Bài tốn được đề xuất vào đầu những năm 1950 và gắn liền với tên tuổi của hai nhà bác học Mỹ là Ford và Fulkerson. Bài tốn luồng cực đại trong mạng có nhiều ứng dụng trong thực tế như Bài tốn xác định cường độ dòng lớn nhất của dòng vận tải giữa hai nút của một bản đồ giao thông bài tốn tìm luồng dầu lớn nhất có thể bơm từ tàu chở dầu vào bể chứa của một hệ thống đường ống dẫn dầu. .Ngồi ra ứng dụng của bài tốn còn để giải các bài tốn như Bài tốn đám cưới vùng quê bài tốn về hệ thống đại diện chung bài tốn phân nhóm sinh hoạt bài tốn lập lịch cho hội nghị .Trong phạm vi đề tài này tôi sẽ trình bày bài tốn luồng cực đại trong mạng với khả năng thông qua các cung các đỉnh và phải nhờ thuật tốn của Ford và Fulkerson để giải bài tốn đặt ra và nêu một số ứng dụng của bài tốn. I. PHÁT BIỂU BÀI TỐN 1. Bài tốn Giả xử trong đồ thị G V E ngồi khả năng thông qua của các cung c u v ở mỗi đỉnh v e V còn có khả năng thông qua của đỉnh là d v và đòi hỏi tổng luồng đi vào đỉnh v không còn vượt quá d v tức là ỉ f wv d v weV Cần phải tìm luồng cực đại giữa s và t trong mạng như vậy. Xây dựng một mạng G sao cho mỗi đỉnh v của G tương ứng với hai đỉnh v v trong G mỗi cung u v trong G ứng với cung u v trong G mỗi cung v w trong G ứng với cung v- w trong G . Ngồi ra mỗi cung v v- trong G có khả năng thông qua là d v tức là bằng khả năng thông qua của đỉnh v trong G. 2. Giải quyết bài tốn Từ mạng G VE khả năng thông qua các cung và các đỉnh. Ta sẽ giải quyết theo hai bước sau 10 Xác định mạng G . 20 Tìm luồng cực đại trong mạng G . Bắt đầu từ luồng zero với khả năng thông qua cung. 1 Thí dụ 1. Hình 1a cho ví dụ mạng G với khả năng thông qua ở cung và đỉnh. Hình 1b là mạng G tương ứng chỉ có khả năng thông qua ở các cung. Hình 1 Do .

• Báo cáo khoa học
• Quy định thực hiện báo cáo
• Báo cáo thực tập
• cách trình bày báo cáo
• quy định nội dung báo cáo
• bố cục báo cáo thực tập
• lắp ráp máy tính
• phần cứng máy tính
• kỹ thuật máy tính
• kỹ thuật lắp ráp
• sửa chữa máy tính
• card màn hình
• giáo trình kỹ thuật điện
• mạch điện ứng dụng
• vi mạch điện tử
• qui chuẩn xây dựng
• quy định nhà nước
• phương thức quản lý
• phát triển kinh tế
• thủ thuật máy tính
• quản trị hệ thống
• thiết bị mạng
• lắp đặt mạng
• hệ điều hành mac
• hệ điều hành unix
• kinh nghiệm cài đặt
• kiến thức phần cứng
• cài đặt máy tính
• cấu trúc phần cứng
• Báo cáo tiêu chuẩn trẻ em
• Đánh giá quy định trẻ em
• Tình hình thực hiện quy định trẻ em
• Quy định trẻ em
• Tiêu chuẩn xã với trẻ em
• Tiêu chuẩn phường
• hệ điều hành linux
• hình học giải tích
• hình học không gian
• xây dựng đô thị
• kinh tế thị trường
• phương pháp kế toán
• hoạt động cho vay
• bài tập kiểm toán
• kiểm toán doanh nghiệp
• đề cương vi xử lí
• kỹ thuật mạch điện tử
• linh kiện điện tử
• điện gia dụng
• hệ điều hành windows
• Quy định thực hiện báo cáo Đo Lường
• cách trình bày báo cáo Đo Lường
• quy định nội
• Khóa luận tốt nghiệp
• Hướng dẫn làm báo cáo
• Quy định chung
• Hình thức trình bày
• Nội dung báo cáo
• cách viết báo cáo thực tập
• bảo vệ luận văn
• báo cáo tốt nghiệp
• bài báo cáo thực tập
• Mẫu Báo cáo
• báo cáo sơ kết
• Văn bản hành chính
• mẫu văn bản
• biểu mẫu hành chính
• quyết định mẫu
• biểu mẫu thuế
• Biểu mẫu
• văn bản
• văn bản về giáo dục
• biểu mẫu quy định của nhà nước
• Biểu mẫu Báo cáo triển khai thực hiện đề tài