Bài giảng Toán rời rạc: Bài tập Luồng trên mạng cung cấp cho người học những nội dung kiến thức như: Tìm luồng cực đại và lát cắt cực tiểu, tìm ghép cặp cực đại trên đồ thị hai phần, tìm tập đỉnh phủ tối tiểu của đồ thị hai phần, tìm số đường đi không chung cạnh lớn nhất, Mời các bạn cùng tham khảo. | Bài tập Luồng trên mạng Trần Vĩnh Đức HUST Ngày 21 tháng 11 năm 2019 https tailieudientucntt 1 19 Tài liệu Tham khảo Nguyễn Đức Nghĩa Slides Toán rời rạc Fall 2005. Jeff Erickson Algorithms 2015. https tailieudientucntt 2 19 Tìm luồng cực đại và lát cắt cực tiểu https tailieudientucntt 3 19 Tìm luồng cực đại và lát cắt cực tiểu 2 https tailieudientucntt 4 19 Tìm luồng cực đại và lát cắt cực tiểu 3 https tailieudientucntt 5 19 Mạng với nhiều điểm phát và nhiều điểm thu Mạng với p điểm phát s1 . . . sp và q điểm thu t1 . . . tq . Tìm luồng cực đại từ các điểm phát đến các điểm thu. https tailieudientucntt 6 19 Tìm ghép cặp cực đại trên đồ thị hai phần https tailieudientucntt 7 19 Tìm tập đỉnh phủ tối tiểu của đồ thị hai phần Tập đỉnh phủ là một tập đỉnh C V sao cho mọi cạnh của đồ thị đều có ít nhất một đầu mút trong C. https tailieudientucntt 8 19 Phủ bàn cờ Cho bàn cờ n n đã bị xóa đi một số ô. Tìm thuật toán để xác định xem liệu có thể phủ kín bàn cờ này bằng các quân dominos biết rằng mỗi quân domino chỉ phủ đúng hai ô trên bàn cờ. https tailieudientucntt 9 19 Tìm số đường đi không chung cạnh lớn nhất Cho đồ thị có hướng G V E và hai đỉnh s t. Hãy tìm số lượng lớn nhất các đường đi không chung cạnh từ s đến t. https tailieudientucntt 10 19 Bài toán vượt ngục Cho một lưới m n và m đỉnh phân biệt x1 y1 x2 y2 xm ym . Hãy xác định xem liệu có hay không m đường đi không chung đỉnh nối m điểm này với các biên. https tailieudientucntt 11 19 Xếp lịch thi học kỳ Mỗi học kỳ có n lớp học có r phòng học và t ca thi. Bạn có danh sách hai danh sách E i số sinh viên đăng ký học lớp i S j số chỗ ngồi của phòng j Lớp i có thể thi ở phòng j nếu E i lt S j . Trong mỗi ca thi mỗi
