TAILIEUCHUNG - Bài giảng Lý thuyết đồ thị: Chương 7 - Bài toán luồng cực đại trong mạng

Bài giảng Lý thuyết đồ thị: Chương 7 - Bài toán luồng cực đại trong mạng giới thiệu tới các bạn những nội dung về khái niệm mạng; luồng trên mạng; lát cắt; đồ thị tăng luồng; thuật toán tìm luồng cực đại và một số nội dung khác. Mời các bạn tham khảo. | Chương 7 Bài toán luồng cực đại trong mạng Khái niệm mạng Định nghĩa. Mạng là một đồ thị có hướng G = , trong đó: Có duy nhất một đỉnh s không có cạnh đi vào, gọi là điểm phát. Có duy nhất một đỉnh t không có cung đi ra, gọi là điểm thu. Mỗi cạnh của đồ thị được gán với một con số không âm gọi là khả năng thông qua (băng thông) của cạnh đó. 5/14/2020 4:53:09 AM Lý thuyết đồ thị s t 1 2 3 4 4 3 3 2 3 1 4 3 Luồng trên mạng Định nghĩa. Xét mạng G = . Ta gọi luồng f trong mạng là ánh xạ f: E R+, gán cho mỗi cạnh e = (u,v) một số thực không âm f(e), gọi là luồng trên cung e, thỏa mãn các điều kiện sau: Luồng trên mỗi cung không đượt vượt quá khả năng thông qua của nó: f(e) c(e). Tại mỗi đỉnh, tổng luồng đi vào phải bằng tổng luồng đi ra (trừ tại s và t). Giá trị của mỗi luồng f được tính bằng tổng luồng đi ra tại s (cũng chính là tổng luồng đi vào tại t). 5/14/2020 4:53:09 AM Lý thuyết đồ thị Luồng trên mạng (tt) VD: Ký hiệu Điều kiện cân bằng luồng: Giá trị của luồng

• Toán học
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Bài toán luồng cực đại
• Luồng trên mạng
• Đồ thị tăng luồng
• Thuật toán tìm luồng cực đại
• Giới thiệu Lý thuyết đồ thị
• Môn học Lý thuyết đồ thị
• Đại cương Lý thuyết đồ thị
• Hình thức thi Lý thuyết đồ thị
• tài liệu về lý thuyết đồ thị
• học lý thuyết đồ thị tốt
• phương pháp học lý thuyết đồ thị
• hàm trên đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Euler
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị