Chủ đề này có 4 trả lời

[lovePearl_maytrang]

Định lý Konig: Cho G là đơn đồ thị lưỡng phân, vô hướng. Tập đỉnh là V, tập cạnh là E.Ta gọi một tập con của V là tập phủ cạnh nếu bất kì cạnh nào của G đều có một trong hai đầu mút nằm trong tập con này. Gọi số phần tử nhỏ nhất của các tập con như thế là
Ta cũng gọi một tập con của E là tập cạnh độc lập nếu các cạnh nằm trong đó đôi một không có đỉnh chung. Gọi (G) là số phần tử lớn nhất của các tập như thế.
CMR (G) =
Bài toán: Trong một buổi dạ hội có 42 người tham dự.Biết rằng trong 31 người bất kì có ít nhất một đôi nam nữ quen nhau. CMR ta có thể chọn ra 12 đôi nam nữ quen nhau từ 42 người đó.

DDTH

[lehoan]

Nếu G là đồ thị lưỡng phân thì có thể Lehoan đã có lời giải (dựa theo cách giải của bài tóan 42 người)
Còn G là đồ thị bất kì thì LPm có thể post lời giải được không

[lovePearl_maytrang]

Liên quan đến vấn đề này còn có định lý kết hôn Hall và định lý kết hôn Konig, tất cả đều được xét với đơn đồ thị lưỡng phân
Thông thường các bài toán về cặp ghép chỉ được xét với đồ thị lưỡng phân, tuy nhiên cũng có những ngoại lệ, chẳng hạn định lý sau:
Cho G là đơn đồ thị vô hướng với tập đỉnh V tập cạnh E
Khi đó trong G tồn tại cặp ghép khi và chỉ khi card(X) lớn hơn hoặc bằng số thành phần liên thông lẻ đỉnh của đồ thị G-X, với mọi tập X là con của V.

[lehoan]

Định lí Hall là gì vậy LPm ???

[lovePearl_maytrang]

Cho đơn đồ thị lưỡng phân có hướng từ tập hợp X vào tập hợp Y
Tồn tại một bộ ghép đầy đủ từ tập hợp X vào tập hợp Y A là tập con của X thì card(A) card( (A)), trong đó (A) là tập các đỉnh của Y là đỉnh cuối của một cung xuất phát từ một đỉnh của A.
Bộ ghép đầy đủ:nôm na là giống như đơn ánh vậy đó.