Bài giảng Toán rời rạc: Ghép cặp trên đồ thị hai phần cung cấp cho người học những nội dung kiến thức như: Ghép cặp Nam & Nữ, định lý Hall, làm thế nào để tìm ghép cặp cực đại? Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết. | Ghép cặp trên đồ thị hai phần Trần Vĩnh Đức HUST Ngày 24 tháng 7 năm 2018 https tailieudientucntt 1 39 Ghép cặp trên đồ thị hai phần Eric Lehman F Thomson Leighton amp Albert R Meyer Mathematics for Computer Science 2013 Miễn phí Albert R Meyer s slides https tailieudientucntt 2 39 Tìm bạn nhảy Tối thứ bảy hội sinh viên tổ chức tiệc. Có 300 sinh viên tham gia. Họ không quen hết nhau Trong 6 người luôn có ba người đôi một quen nhau hoặc ba người đôi một lạ nhau https tailieudientucntt 3 39 Tìm bạn nhảy Tối thứ bảy hội sinh viên tổ chức tiệc. Có 300 sinh viên tham gia. Họ không quen hết nhau Nhưng mỗi cô gái quen đúng 50 chàng trai và mỗi chàng trai quen đúng 50 cô gái Liệu mọi sinh viên có thể nhảy đồng thời sao cho hai người nhảy cùng nhau phải biết nhau https tailieudientucntt 4 39 Nội dung Ghép cặp Nam amp Nữ Định lý Hall Làm thế nào để tìm ghép cặp cực đại https tailieudientucntt Đồ thị Nam amp Nữ Nam amp Nữ hợp nhau G B Hợp nhau Albert R Meyer. April 3 2013 https tailieudientucntt 6 39 Đồ thị Nam amp Nữ Compatible Boys amp Girls G B Albert R Meyer. April 3 2013 Hãy tìm cách ghép cặp mỗi cô gái với chỉ một chàng trai phù hợp. https tailieudientucntt 7 39 Đồ thị Nam amp Nữ Compatible Boys amp Girls G B Albert R Meyer. April 3 2013 Hình Một ghép cặp https tailieudientucntt 8 39 Đồ thị Nam amp Nữ Compatible Boys amp Girls G B suppose this edge was missing Albert R Meyer. April 3 2013 Giả sử không có cạnh này. https tailieudientucntt 9 39 Đồ thị Nam amp Nữ Compatible Boys amp Girls G B suppose this edge was missing Albert R Meyer. April 3 2013 Giả sử không có cạnh này. https tailieudientucntt 10 39 Đồ thị Nam amp Nữ Compatible Boys
