tailieunhanh - Bài giảng Lý thuyết đồ thị: Bài toán ghép cặp
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,. . | Bài toán ghép cặp Graph Matching Graph Matching 1 Bài toán ghép cặp trên đồ thị Giả sử G V E là đổ thị vô hớng trong đó mỗi cạnh v w đợc gán với một số thực c v w gọi là trọng số của nó. Định nghĩa. Cặp ghép M trên đồ thị G là tạp các cạnh của đồ thị trong đó không có hai cạnh nào có đỉnh chung. Số cạnh trong M - kích thớc Tổng trọng số của các cạnh trong M - trọng lợng của cặp ghép. Cặp ghép với kích thớc lớn nhất đợc gọi là cặp ghép cực đại. Cặp ghép với trọng lợng lớn nhất đợc gọi là cặp ghép lớn nhất. Cặp ghép đợc gọi là đầy đủ hoàn hảo nếu mỗi đỉnh của đồ thị là đầu mút của ít nhất một cạnh trong cặp ghép. Graph Matching 2 Hai bài toán Bài toán cặp ghép cực đại Tìm cặp ghép với kích thớc lớn nhất trong đồ thị G. Oài toán cặp ghép lớn nhất Tìm cặp ghép với trọng lợng lớn nhất trong đồ thị G. Ta hạn chê xét các bài toán đặt ra trên đồ thị hai phía G Xu Y E . Graph Matching
đang nạp các trang xem trước