tailieunhanh - bài giảng các chuyên đề phần 10

Lát cắt hẹp nhất: Cho một đồ thị liên thông gồm n đỉnh và m cạnh, hãy tìm cách bỏ đi một số ít nhất các cạnh để làm cho đồ thị mất đi tính liên thông 4. Tập đại diện: Một lớp học có n bạn nam, n bạn nữ. Cho m món quà lưu niệm, (n ≤ m). Mỗi bạn có sở thích về một số món quà nào đó. Hãy tìm cách phân cho mỗi bạn nam tặng một món quà cho một bạn nữ thoả mãn: • Mỗi bạn nam chỉ tặng. | Lý thuyết đồ thị 88 3. Lát cắt hẹp nhất Cho một đồ thị liên thông gồm n đỉnh và m cạnh hãy tìm cách bỏ đi một số ít nhất các cạnh để làm cho đồ thị mất đi tính liên thông 4. Tập đại diện Một lớp học có n bạn nam n bạn nữ. Cho m món quà lưu niệm n m . Mỗi bạn có sở thích về một số món quà nào đó. Hãy tìm cách phân cho mỗi bạn nam tặng một món quà cho một bạn nữ thoả mãn Mỗi bạn nam chỉ tặng quà cho đúng một bạn nữ Mỗi bạn nữ chỉ nhận quà của đúng một bạn nam Bạn nam nào cũng đi tặng quà và bạn nữ nào cũng được nhận quà món quà đó phải hợp sở thích của cả hai người. Món quà nào đã được một bạn nam chọn thì bạn nam khác không được chọn nữa. Lê Minh Hoàng Lý thuyết đồ thị 89 11. BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI TRÊN ĐỒ THỊ HAI PHÍA I. ĐỒ THỊ HAI PHÍA BIPARTITE GRAPH Các tên gọi đồ thị hai phía đồ thị lưỡng phân đồ thị phân đôi đồ thị đối sánh hai phần . là để chỉ chung một dạng đơn đồ thị vô Sy hướng G V E mà tập đỉnh của nó có thể chia làm hai tập con X Y rời nhau sao cho bất kỳ cạnh nào của đồ thị cũng nối một đỉnh của Y X với một đỉnh thuộc Y. Khi đó người ta còn ký hiệu G là XuY E X và gọi một tập chẳng hạn tập X là tập các đỉnh trái và tập còn lại I ------r là tập các đỉnh phải của đồ thị hai phía G. Các đỉnh thuộc X còn gọi là các X_đỉnh các đỉnh thuộc Y gọi là các Y_đỉnh. Để kiểm tra một đồ thị liên thông có phải là đồ thị hai phía hay không ta có thể áp dụng thuật toán sau Với một đỉnh v bất kỳ X v Y 0 repeat Y Y u Kề X X X u Kề Y until X ìY 0 or X và Y là tối đại - không bổ sung được nữa if XnY 0 then Không phải đồ thị hai phía else Đây là đồ thị hai phía X là tập các đỉnh trái các đỉnh đến được từ v qua một số chẵn cạnh Y là tập các đỉnh phải các đỉnh đến được từ v qua một số lẻ cạnh Đồ thị hai phía gặp rất nhiều mô hình trong thực tế. Chẳng hạn quan hệ hôn nhân giữa tập những người đàn ông và tập những người đàn bà việc sinh viên chọn trường thầy giáo chọn tiết dạy trong thời khoá biểu . II. BÀI TOÁN GHÉP ĐÔI KHÔNG TRỌNG VÀ CÁC KHÁI NIỆM Cho một đồ thị hai