Định lýĐã chứng minh

Định lý đám cưới Hall

Phát biểu

Cho $G=(X \cup Y, E)$ là một đồ thị hai phía hữu hạn. Tồn tại một cặp ghép phủ hết mọi đỉnh của $X$ khi và chỉ khi với mọi tập con $W \subseteq X$ , tập đỉnh kề $N(W) \subseteq Y$ thỏa mãn $|N(W)| \ge |W|$ .

Vì sao đúng?

Nếu có một nhóm ứng viên $W$ nào đó mà tính gộp lại chỉ đủ điều kiện cho ít hơn $|W|$ công việc, thì hiển nhiên không thể tuyển tất cả họ vào các công việc phân biệt. Định lý Hall nói rằng điều kiện cần hiển nhiên này — kiểm tra trên mọi tập con $W$ — thực ra là rào cản duy nhất: nếu không có nhóm con nào bị nghẽn cổ chai, thì một cặp ghép đầy đủ luôn tồn tại.

Phác thảo chứng minh

Điều kiện cần là hiển nhiên vì một cặp ghép phủ $X$ ánh xạ đơn ánh mỗi $W \subseteq X$ vào $N(W)$ . Với điều kiện đủ, quy nạp theo $|X|$ : nếu $|N(W)| \ge |W|+1$ với mọi tập con thực sự khác rỗng $W \subset X$ , ghép một $x \in X$ bất kỳ với một $y \in N(\{x\})$ bất kỳ rồi áp dụng quy nạp cho $G - \{x,y\}$ , nơi điều kiện Hall vẫn thỏa; ngược lại có một tập con thực sự khác rỗng $W$ đạt dấu bằng ( $|N(W)| = |W|$ ), khi đó ghép $W$ với $N(W)$ theo quy nạp và kiểm tra rằng $X \setminus W$ thỏa điều kiện Hall trong $G - (W \cup N(W))$ , nhờ đó các đỉnh còn lại cũng ghép được theo quy nạp.

Chủ đề chứa định lý này

Đồ thị, bậc, đường đi

Định lý liên quan

Bổ đề bắt tay

Chứng minh từng bước

Chưa có chứng minh từng bước cho định lý này.

Tài liệu tham khảo

Philip Hall (1935). On Representatives of Subsets