TAILIEUCHUNG - Bài giảng Toán rời rạc (Phần II: Lý thuyết đồ thị): Bài toán ghép cặp - Nguyễn Đức Nghĩa
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,. . | Bài toỏn ghộp cặp Graph Matching Graph Matching 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 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. Bà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 = (X Y, E). Graph Matching Vớ dụ Cặp ghộp cực đại Cặp ghộp khụng là cặp ghộp Cặp ghộp Cặp ghộp hoàn hảo Graph Matching Vớ dụ Cặp ghộp lớn nhất: M = {(x1, y1), (x2, y3), (x3, y2), (x4, y4)} Cú trọng lượng 29. y4 y3 y2 y1 x4 x3 x2 x1 12 3 4 8 3 2 4 6 Graph Matching Bài toán cặp ghép cực đại trên đồ thị hai phía Xét đồ thị hai phía G = (X Y, E). Cặp ghép là tập cạnh mà không có hai cạnh nào có chung đỉnh Bài toán: Tìm cặp ghép kích thước lớn nhất 1 2 3 4 5 6 7 8 9 10 Graph Matching Qui về Bài toán luồng cực đại 1 2 3 4 5 6 7 8 9 10 s t Mỗi cung (s, i) cú kntq 1. Mỗi cung (j, t) cú kntq 1. Mỗi cạnh được thay thế bởi cung cú kntq 1. Graph Matching Tỡm luồng cực đại Luồng cực đại từ s->t cú giỏ trị 4. Cặp ghộp cực đại cú kớch thước 4. 1 2 3 4 5 6 7 8 9 10 s t Graph Matching Bài toán cặp ghép cực đại trên đồ thị hai phía Giả sử M là một cặp ghép trên G. Nếu cạnh e = (x, y) M, ta nói e là cạnh của cặp ghép (hay cạnh đậm) và các đỉnh x, y là các đỉnh đậm (hay không tự do). Nếu cạnh e = (x, y) M, thì ta nói e là cạnh nhạt còn các đỉnh x, y là các đỉnh nhạt (hay tự .
đang nạp các trang xem trước
