Ghép cặp trên đồ thị hai phần

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 70 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 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 39 2   Download

Giả sử G là đồ thị hai phần có n đỉnh. Ký hiệu k là số phần tử của tập đỉnh tựa bé nhất. Khi đó thì: Định lý 5.2: 1. Số ổn định trong của đồ thị hai phần G là bằng n-k. 2. Số phần tử của cặp ghép lớn nhất của G là bằng k. Chứng minh: 1. Suy từ nhận xét trên: C là tập đỉnh tựa nhỏ nhất ⇔ V \ C là tập ổn định trong lớn nhất.

5p yeuthuong 01-12-2010 146 13   Download