Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Toán rời rạc: Bài tập Luồng trên mạng - Trần Vĩnh Đức

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 CuuDuongThanCong.com https fb.com 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. CuuDuongThanCong.com https fb.com tailieudientucntt 2 19 Tìm luồng cực đại và lát cắt cực tiểu CuuDuongThanCong.com https fb.com tailieudientucntt 3 19 Tìm luồng cực đại và lát cắt cực tiểu 2 CuuDuongThanCong.com https fb.com tailieudientucntt 4 19 Tìm luồng cực đại và lát cắt cực tiểu 3 CuuDuongThanCong.com https fb.com 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. CuuDuongThanCong.com https fb.com tailieudientucntt 6 19 Tìm ghép cặp cực đại trên đồ thị hai phần CuuDuongThanCong.com https fb.com 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. CuuDuongThanCong.com https fb.com 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ờ. CuuDuongThanCong.com https fb.com 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. CuuDuongThanCong.com https fb.com 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. CuuDuongThanCong.com https fb.com 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