Bài toán cặp ghép cực đại

Bài giảng "Toán rời rạc: Bài toán ghép cặp" giới thiệu tới người học một số bài toán ghép cặp như: Bài toán ghép cặp trên đồ thị, bài toán cặp ghép cực đại trên đồ thị hai phía, đường tăng cặp ghép, điều chỉnh nhãn, tìm đỉnh tự do, sơ đồ thuật toán. Đây là một tài liệu hữu ích dành cho các bạn sinh viên các ngành Khoa học tự nhiên dùng làm tài liệu học tập và nghiên cứu.

43p nhasinhaoanh_08 13-10-2015 272 20   Download

Bài giảng "Toán rời rạc: Các ứng dụng của bài toán luồng cực đại" trình bày một số bài toán luồng tổng quát luồng cực đại (bài toán với nhiều điểm phát và điểm thu, bài toán với hạn chế thông qua ở nút), ứng dụng trong tổ hợp (bài toán cặp ghép cực đại trong đồ thị hai phía, độ tin cậy của mạng). Mời các bạn cùng tham khảo.

53p nhasinhaoanh_08 13-10-2015 158 15   Download

Bài giảng Lý thuyết đồ thị này giới thiệu về bài toán ghép cặp với các nội dung như: Bài toán ghép cặp trên đồ thị, qui về bài toán luồng cực đại, bài toán cặp ghép cực đại trên đồ thị hai phía, đường tăng cặp ghép, định lý Berge, tìm đường tăng,... Mời các bạn cùng tham khảo.

43p kiepnaybinhyen_01 01-12-2015 174 6   Download

Bài giảng Lý thuyết đồ thị (Graph Theory) trình bày những nội dung chính sau: Các khái niệm cơ bản, biểu diễn đồ thị, các thuật toán duyệt đồ thị, đồ thị Euler và đồ thị Haminton, bài toán cây khung nhỏ nhất, bài toán đường đi ngắn nhất, bài toán luồng cực đại, bài toán ghép cặp,... Mời các bạn tham khảo.

132p nomoney3 10-02-2017 136 8   Download

Chương này trình bày một số ứng dụng của bài toán luồng cực đại như: Bài toán với nhiều điểm phát và điểm thu, bài toán với hạn chế thông qua ở nút, bài toán cặp ghép cực đại trong đồ thị hai phía, độ tin cậy của mạng. Mời các bạn cùng tham khảo.

53p dien_vi01 04-10-2018 72 4   Download

Chương này trình bày về Bài toán ghép cặp (Graph Matching) với những nội dung chính sau: Bài toán ghép cặp trên đồ thị, bài toán cặp ghép cực đại trên đồ thị hai phía, qui về bài toán luồng cực đại, đường tăng cặp ghép, thuật toán tìm cặp ghép cực đại,... Mời các bạn cùng tham khảo.

43p dien_vi01 04-10-2018 68 4   Download

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.

39p lovebychance07 12-07-2021 18 3   Download

Bài giảng Lý thuyết đồ thị: Chương 6 Một số ứng dụng, cung cấp cho người đọc những kiến thức như: Bài toán luồng cực đại (Max-flow problem); Bài toán ghép cặp (Matching problem);... Mời các bạn cùng tham khảo!

44p chankora08 04-07-2023 17 2   Download

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.

19p lovebychance07 12-07-2021 36 2   Download

Thuật toán ghép cặp của Edmonds (còn gọi là thuật toán bông hoa) là một thuật toán trong lý thuyết đồ thị để tìm cặp ghép cực đại trong đồ thị. Thuật toán được tìm ra bởi Jack Edmonds năm 1961,[1] và xuất bản năm 1965.[2] Cho trước một đồ thị vô hướng G = (V, E), thuật toán tìm ra cặp ghép M sao cho mỗi đỉnh trong V kề với tối đa một cạnh trong M và |M| là lớn nhất có thể. Cặp ghép được xây dựng bằng cách khởi đầu từ cặp ghép rỗng và tăng...

26p esc_12 03-08-2013 133 21   Download

Tóm tắt luận văn thạc sĩ khoa học: Bài toán ghép cặp và ứng dụng nhằm trình bày về những kiến thức cơ bản về lý thuyết đồ thị, giới thiệu bài toán cặp, bài toán luồng cực đại và các định lý, thuật toán liên quan đến những bài toán này, ứng dụng của bài toán cặp.

24p ctrl_12 08-07-2013 598 33   Download