Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Giới thiệu
Đăng ký
Đăng nhập
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Thông tin
Điều khoản sử dụng
Quy định bảo mật
Quy chế hoạt động
Chính sách bản quyền
Giới thiệu
Đăng ký
Đăng nhập
0
Trang chủ
Khoa Học Tự Nhiên
Toán học
MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ PHẦN 2
Đang chuẩn bị liên kết để tải về tài liệu:
MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ PHẦN 2
Hồng Xuân
96
16
pdf
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Định nghĩa: Mạng vận tải là một đồ thị có hướng, không có khuyên và có trọng số G=(V,E) với V={v0, v1, ., vn} thoả mãn: 1) Mỗi cung e E có trọng số m(e) là một số nguyên không âm và được gọi là khả năng thông qua của cung e. 2) Có một và chỉ một đỉnh v0 không có cung đi vào, tức là degt(v0)=0. Đỉnh v0 được gọi là lối vào hay đỉnh phát của mạng. 3) Có một và chỉ một đỉnh vn không có cung đi ra, tức là dego(vn)=0. Đỉnh vn được gọi là. | MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐÒ THỊ - PHẦN 2 BÀI TOÁN LUÒNG CựC ĐẠI. 5.2.1. Luồng vận tải 5.2.1.1. Định nghĩa Mạng vận tải là một đồ thị có hướng không có khuyên và có trọng số G V E với V v0 v1 . vn thoả mãn 1 Mỗi cung e e E có trọng số m e là một số nguyên không âm và được gọi là khả năng thông qua của cung e. 2 Có một và chỉ một đỉnh v0 không có cung đi vào tức là degt v0 0. Đỉnh v0 được gọi là lối vào hay đỉnh phát của mạng. 3 Có một và chỉ một đỉnh vn không có cung đi ra tức là dego vn 0. Đỉnh vn được gọi là lối ra hay đỉnh thu của mạng. 5.2.I.2. Định nghĩa Để định lượng khai thác tức là xác định lượng vật chất chuyển qua mạng vận tải G V E người ta đưa ra khái niệm luồng vận tải và nó được định nghĩa như sau. Hàm ọ xác định trên tập cung E và nhận giá trị nguyên được gọi là luồng vận tải của mạng vận tải G nếu ọ thoả mãn 1 ọ e 0 Ve e E. 2 e e Vv eV Wv0 v vn. Ở đây r- v eeE e có đỉnh cuối eel v eer v là v r v eeE e có đỉnh đầu là v . 3 ọ e m e Ve e E. Ta xem ọ e như là lượng hàng chuyển trên cung e u v từ đỉnh u đến đỉnh v và không vượt quá khả năng thông qua của cung này. Ngoài ra từ điều kiện 2 ta thấy rằng nếu v không phải là lối vào v0 hay lối ra vn thì lượng hàng chuyển tới v bằng lượng hàng chuyển khỏi v. Từ quan hệ 2 suy ra 4 E e E e v . eer V0 eel vn Đại lượng ọv ta còn ký hiệu là pn được gọi là luồng qua mạng hay cường độ luồng tại điểm vn hay giá trị của luồng ọ. Bài toán đặt ra ở đây là tìm ọ để ọv đạt giá trị lớn nhất tức là tìm giá trị lớn nhất của luồng. 5.2.I.3. Định nghĩa Cho mạng vận tải G V E và A G V. Ký hiệu r A u v eE veA u A r A u v eE ueA v A . Đối với tập cung M tuỳ ý đại lượng ọ M p e được gọi là luồng của e M tập cung M. Từ điều kiện 2 dễ dàng suy ra hệ quả sau. 5.2.I.4. Hệ quả Cho ọ là luồng của mạng vận tải G V E và A G V v0 vn . Khi đó ọ r- A ọ r A . 5.2.2. Bài toán luồng cực đại Cho mạng vận tải G V E . Hãy tìm luồng ọ để đạt pv max trên mạng G. Nguyên lý của các thuật toán giải bài toán tìm luồng cực đại là như sau. 5.2.2.I. Định
TÀI LIỆU LIÊN QUAN
Luận văn Thạc sĩ Toán học: Một số bài toán tối ưu trên đồ thị và ứng dụng
Giáo trình toán rời rạc - MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ
Tà liệu tham khảo: Một số bài toán tối ưu trên đồ thị
Toán rời rạc - Chương V: Một số bài toán tối ưu trên đồ thị
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Ị_2
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
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Ị_4
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Ị_5
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Ị_1
[Giáo trình Toán rời rạc] - Chương5 - Một số bài toán Tối ưu trên Đồ thị
crossorigin="anonymous">
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.