TAILIEUCHUNG - 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

• Cơ sở dữ liệu
• thuật toán tìm kiếm
• các chuyên đề thuật toán
• lập trình pascal
• lập trình các giải thuật
• Các thuật toán tìm kiếm
• Tìm kiếm trên đồ thị
• Bài toán tìm kiếm trên đồ thị
• Thuật toán tìm kiếm theo chiều rộng
• Thuật toán tìm kiếm theo chiều sâu
• Tìm kiếm tuần tự
• Tìm kiếm nhị phân
• Tìm kiếm dựa trên quy hoạch động
• Tìm kiếm dựa trên đệ quy
• Tìm kiếm dựa trên phân vùng
• Khái niệm tìm kiếm
• Bài toán tìm kiếm
• Tìm kiếm trên dãy chưa sắp
• Cấu trúc dữ liệu
• Kỹ thuật tìm kiếm
• Tìm kiếm trên mảng
• Giải thuật tìm kiếm
• Tìm kiếm trên tập tin
• Tìm kiến tuyến tính
• Thuật toán tìm kiếm tối ưu
• Tìm kiếm cứu nạn
• Thuật toán vi khuẩn
• Tính toán phương án tìm kiếm tối ưu
• Tàu tìm kiếm cứu nạn
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Thuật toán tìm kiếm trên đồ thị
• Ứng dụng thuật toán tìm kiếm đồ thị
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu và giải thuật
• Khái niệm về tìm kiếm
• Phương pháp tìm kiếm tuần tự
• Phương pháp tìm kiếm nhị phân
• Thuật toán tìm kiếm nhị phân
• Thuật toán tìm kiếm nhị phân cơ bản
• Thuật toán Quicksort
• Cách tìm kiếm nhị phân
• chiến lược tìm kiếm mù
• Tìm kiếm beam
• Tìm kiếm leo đồi
• tìm kiếm tối ưu
• Tìm kiếm có đối thủ
• Tìm kiếm mô phỏng sự tiến hóa
• Thuật toán di truyền
• Bài toán giải thuật
• Chiến lược tìm kiếm
• Tìm kiếm trình tự
• Lập trình C
• Bài giảng Lập trình căn bản
• Bài toán sắp xếp
• Thuật toán tìm kiếm tuần tự
• Thuật toán sắp xếp nổi bọt
• khoa học
• tự nhiên
• toán học
• Các thuật toán tìm kiếm trên đồ thị
• Các giải thuật tìm kiếm
• Giải thuật tìm kiếm tuyến tính
• Giải thuật Tìm kiếm nhị phân
• Các giải thuật sắp xếp
• Tóm tắt Luận án Thạc sĩ
• Hệ thống thông tin
• Tìm kiếm chuỗi DNA
• Tìm kiếm tương tự nhanh
• Bài giảng Toán rời rạc 2
• Toán rời rạc 2
• Toán rời rạc
• Ứng dụng của thuật toán tìm kiếm
• Bài giảng Tìm kiếm heuristic leo đồi
• Thuật giải di truyền
• Thuật giải leo đồi
• Các thuật toán tìm kiếm cục bộ
• Lựa chọn của thuật giải di truyền
• Nội dung về thuật giải leo đồi
• Bài giảng Cấu trúc dữ liệu
• Tìm kiếm trên danh sách
• Tìm kiếm trên văn bản
• Bài giảng Tìm kiếm
• Kỹ thuật lập trình
• Bài giảng Các hệ thống thông minh nhân tạo
• Hệ thống thông minh nhân tạo
• Bài toán tìm kiếm 1
• Cây tìm kiếm
• Thuật toán tìm kiếm mù
• Bài toán tìm đường đi
• Thuật giải HEURISTIC
• phương pháp tìm kiếm HEURISTIC
• thuật toán tìm kiếm leo đồi
• tìm kiếm ưu tiên tối ưu
• ứng dụng giải bài toán ta canh
• chiến lược tìm kiếm lai
• Bài giảng Thuật toán Ứng dụng
• Thuật toán Ứng dụng
• Cấu trúc dữ liệu trừu tượng
• Cài đặt tìm kiếm ở thư viện
• tài liệu học đại học
• bài giảng quy hoạch tuyến tính
• Khoa học máy tính
• tìm kiếm tuyến tính
• Tìm kiếm theo chiều sâu
• Tìm kiếm theo chiều rộng
• Ứng dụng các thuật toán
• Bài giảng Tìm kiếm đối kháng
• Tìm kiếm đối kháng
• Tìm kiếm đối kháng trò chơi
• Thuật toán MINIMAX
• Hàm lượng giá
• Tìm kiếm cắt nhánh