Chưa có bài trả lời

[LNH]

Định lí Hall và ứng dụng

Trước hết, ta nhắc lại định nghĩa của đơn đồ thị, đồ thị 2 phe (lưỡng phân), ghép cặp và một số tính chất liên quan

Định nghĩa 1: Một đơn đồ thị G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một tập E mà các phần tử của nó gọi là các cạnh, đó là các cặp không có thứ tự của các đỉnh phân biệt.

Định nghĩa 2: Đơn đồ thị G=(V,E) sao cho V=V₁ÈV₂, V₁ÇV₂=Æ, V₁¹Æ, V₂¹Æ và mỗi cạnh của G được nối một đỉnh trong V₁ và một đỉnh trong V₂ được gọi là đồ thị 2 phe.

Cho đồ thị 2 phe G=(A,B,E). Một ghép cặp là một tập hợp các cạnh sao cho không có cạnh nào có chung 1 đầu mút. Một ghép cặp từ A đến B được gọi là hoàn hảo khi nó có thể nối tất cả các đỉnh của A đến B

Bây giờ, ta sẽ đề cập định lí Hall (còn được gọi là định lí đám cưới)

Định lí Hall:

Cho đồ thị hai phe X, Y. Với mỗi tập con A thuộc X, gọi G(A) là tập các đỉnh thuộc Y kề với một đỉnh nào đó thuộc A. Khi đó điều kiện cần và đủ để tồn tại một đơn ánh f: X à Y sao cho x kề f(x) là |G(A)| ≥ |A| với mọi A khác rỗng thuộc X.

Chứng minh.

Điều kiện cần là hiển nhiên: Nếu tồn tại đơn ánh f thì với mỗi thuộc X, ta có  chứa các phần tử phân biệt , do đó .

Ta chứng minh điều kiện đủ bằng quy nạp theo |X|. Khi , khẳng định là hiển nhiên. Giả sử định lý đã đúng với các tập X với . Giả sử bây giờ . Ta xét hai trường hợp:

1) Giả sử với mọi , ta có . Chọn một phần tử bất kỳ thuộc X, theo điều kiện , do đó tồn tại  thuộc Y kề với X. Ta đặt . Bây giờ xét  và , và G’(A) là tập các đỉnh thuộc Y’ kề với A. Khi đó . Vì  nên theo giả thiết quy nạp, tồn tại đơn ánh sao cho  kề x với mọi x thuộc x’. Bổ sung thêm ta được đơn ánh  thỏa mãn yêu cầu định lý.

2) Trong trường hợp ngược lại, tồn tại  sao cho . Khi đó, do  nên tồn tại đơn ánh . Xét , . Xét B thuộc X’ và  là tập các đỉnh thuộc Y’ kề với B. Nếu  thì ta có

           

mâu thuẫn với điều kiện định lý. Như vậy ta có  với mọi B thuộc X’. Theo giả thiết quy nạp, tồn tại đơn ánh  sao cho g(x) kề với x. Như vậy, ta có thể xây dựng được đơn ánh  sao cho h(x) kề với x: cụ thể h(x) = f(x) nếu x thuộc A và h(x) = g(x) nếu x thuộc .

Chúng ta hãy cùng khám phá những ứng dụng của định lí Hall nào

Bài toán 1 : (Canada 2006) Trong một bảng ô vuông mxn chứa các số không âm, mỗi hàng (hoặc cột) chứa ít nhất 1 số dương. Ngoài ra, nếu 1 hàng giao một cột 1 ô chứa một số dương, khi đó tổng của hàng và cột bằng nhau. Chứng minh rằng :

Ý tưởng :

Một cách tự nhiên, ta nghĩ đến việc chứng minh  và  bằng cách xây dựng đồ thị lưỡng phân với tập hợp các hàng và các cột rồi áp dụng định lí Hall.

Giải :

Ta sẽ xây dựng một đồ thị lưỡng phân là , với A là tập hợp các hàng, B là tập hợp các cột. Nếu cột và hàng giao nhau tại 1 ô chung chứa số dương thì nối chúng bởi một cạnh.

Không mất tính tổng quát, giả sử

Gọi S là tập con của A sao cho  với T là tập hợp các đỉnh của B kề với ít nhất một đỉnh của S.

Giả sử tổng các số trên các hàng thuộc S là s₁,…,s_k . Mỗi cột thuộc T sẽ có tổng là một s_i nào đó. Vì vậy, nếu nhìn theo góc độ ở cột thì tổng các hàng thuộc S chỉ bằng tổng của một tập con các hàng nào đó thuộc S. Mà mọi s_i >0, vô lí

Suy ra , với mọi S là tập con của A

Theo định lí Hall thì tồn tại một ghép cặp hoàn hảo từ A đến B

Điều này có nghĩa là

Suy ra  (đpcm)

Bài toán 2: (Vietnam TST 2010) Có n nước, mỗi nước có k đại diện (n>k>1). Người ta chia n.k người này thành n nhóm, mỗi nhóm có k người sao cho không có 2 người nào cùng nhóm đến từ một nước. Chứng minh rằng có thể chọn ra n người đến từ các nhóm khác nhau và đến từ các nước khác nhau.

Ý tưởng:

Yêu cầu của bài toán như một lời nhắc nhở không thể rõ hơn về việc sử dụng định lí Hall.

Giải:

Nhận xét: Với mọi h thuộc {1,2,…,n} thì tập hợp các đại biểu ở h nhóm bất kì đến từ ít nhất h nước

Nếu ta xây dựng một đồ thị lưỡng phân  với A là tập hợp các nhóm còn B là tập hợp các nước thì theo định lí Hall, tồn tại một ghép cặp hoàn hảo từ A đến B (đpcm)

Bài toán 3: Bảng  được gọi là bảng hoán vị nếu các số trên bảng là 0 và 1 sao cho trên mỗi hàng và mỗi cột có đúng một số 1. Cho G là 1 bảng  gồm các số nguyên không âm sao cho tổng các số trên mỗi hàng và trên mỗi cột bằng nhau. Chứng minh rằng G có thể viết dưới dạng tổng các bảng hoán vị.
Ý tưởng:

Ta có thể thấy được sự giống nhau giữa bảng hoán vị và bảng G, đó là: bảng hoán vị cũng có tổng ở các cột và các hàng bằng nhau và bằng 1. Nên từ đó, thay vì biểu diễn G thành tổng các bảng hoán vị, ta sẽ trừ đi 1 ở các ô được chọn tương ứng trong bảng G (các ô đó được chọn bởi định lí Hall).

Giải:
Ta sẽ chứng minh luôn tìm được n số nguyên dương nằm ở các hàng và cột khác nhau.
Xét đồ thị lưỡng phân . Trong đó U là các hàng và V là các cột. Một đỉnh trong U được bối với 1 đỉnh trng V khi và chỉ khi giao của hàng và cột này có là một số nguyên dương. Ta sẽ chứng minh k đỉnh trong U kề với ít nhất k đỉnh trong V. Giả sử như k đỉnh trong U chỉ kề với k-1 đỉnh trong V thì xét 1 bảng con ,  tổng các ô trong bảng bằng tổng các ô tính theo hàng và tổng các ô tính theo cột nên có (vô lí). Vậy k đỉnh trong U phải kề ít nhất k đỉnh trong V. Từ đây theo điều kiện Hall thì ta luôn chọn ra được n ô chứa n số nguyên dương và các ô này nằm ở các hàng và cột khác nhau. Giảm đi các ô đó 1 đơn vị thì tính chất của bảng vẫn không đổi nên tiếp tục áp dụng nhiều lần thì ta sẽ được 1 bảng toàn số 0 (đpcm).
Bài toán 4: Bảng  gồm các số thuộc  sao cho với mọi tập con gồm n ô, trong đó không có hai ô cùng hàng hoặc cùng cột, chứa ít nhất một số 1. Chứng minh rằng tồn tại i hàng và j cột với  , có giao chứa toàn 1.
Ý tưởng:

Bài toán này yêu cầu tìm l hàng và k cột, tức là yêu cầu chỉ ra l+k đỉnh kề nhau của đồ thị lưỡng phân thỏa đề, khác hẳn với bài toán trước nên sẽ gặp khó khăn. Nhưng thay vì đi chứng minh trực tiếp thì tại sao lại không chứng minh gián tiếp ? Nếu thay vì 2 đỉnh của đồ thị nối với nhau nếu hàng và cột giao nhau tại ô chứa số 1 thì ta cho chúng nối với nhau khi ô giao của chúng chứa  số 0 và ta sẽ đi chứng minh luôn chọn ra l cột chỉ kề được nhiều nhất l-1 hàng.
Lời giải:
Bỏ qua TH đơn giản toàn bộ các ô trong 1 cột chứa số 1.
Xét TH không  có cột nào chứa toàn số 1.
Ta sẽ chứng minh rằng, nếu có k cột chứa các số 1 trong bảng thì phải tồn tại l cột (1<l<k+1) mà mỗi cột trong l cột đó sẽ có đúng ô chứa số 0 và các ô tương ứng của mỗi cột phải nằm cùng 1 hàng.
(ví dụ với bảng 5x5 và i=3)
 

11111

11101

01010

10111

01010

Giả sử phản chứng có 1 cách đặt sao cho nó không thỏa nhận xét trên. Khi đó, ta luôn tìm được n ô không cùng hàng hoặc cột mà trong các ô đó không chưa số 1 nào (dễ thấy) từ đó tría với giải thiết của đề, vô lí.
Như vậy, theo nhận xét trên thì luôn chọn được l cột chỉ kề với nhiều nhất l-1 hàng nên theo điều kiện Hall thì không tồn tại ghép cặp từ tập hàng tới tập cột thỏa điều kiện ta cho ban đầu. Vậy nên luôn chọn ra từ các tập đỉnh đó l đỉnh thuộc tập cột và t đỉnh thuộc tập hàng sao cho  suy ra số hàng mà các ô giao của chúng với l cột kia chứa toàn số 1 là  hay (đpcm).

Bài toán 5: Cho đồ thị hai phe G, chứng minh rằng nếu các bậc của các đỉnh đều dương và bằng nhau thì tồn tại một ghép cặp hoàn hảo

Chứng minh: Đây là một bài toán dễ, xin nhường lại cho bạn đọc

Bài toán 6: Cho một bảng  với  sao cho trong mỗi ô vuông có một số từ 1 đến n. Biết rằng trong mỗi hàng và mỗi cột không có số nào trùng nhau. Chứng minh rằng ta có thể mở rộng bảng trên thành bảng  với một số từ 1 đến n trong mỗi ô, sao cho trong mỗi hàng và mỗi cột không có số nào trùng nhau

Ý tưởng:

Một ý tưởng tự nhiên khi gặp bài toán này là ta sẽ thêm tuần tự các số vào từng cột. Vì vậy, ta cần chứng minh có thể mở rộng bảng trên thành một bảng  thỏa mãn yêu cầu đề bài. Và việc xây dựng đồ thị lưỡng phân kết hợp với định lí Hall là một điều không thể thiếu để giải quyết bài toán này

Giải:

Ta sẽ chứng minh rằng ta có thể mở rộng bảng trên thành một bảng  thỏa mãn yêu cầu đề bài. Xét một đồ thị với  đỉnh trong đó có n đỉnh biểu diễn các hàng và n đỉnh biểu diễn các số từ 1 đến n. Nếu một số chưa xuất hiện ở một hàng thì ta đặt một cạnh nối hai đỉnh tương ứng. Để ý rằng bậc mỗi đỉnh biểu thị các hàng là . Tuy nhiên, mỗi số xuất hiện một lần trong mỗi cột, nên chúng ở trong k hàng khác nhau. Vì vậy, bậc các đỉnh biểu thị các số cũng là . Theo bài toán 5, tồn tại một ghép cặp hoàn hảo, đây cũng chính là đpcm.

Bài toán 7 (Russia MO 2006) : Có 100 người đến từ 25 quốc gia.Mỗi nước 4 người và họ ngồi trên một cái bàn tròn .CMR ta có thể chia họ thành 4 nhóm sao cho mỗi nhóm có 25 người của 25 quốc qia khác nhau và không có ai cùng nhóm ngồi cạnh nhau trên bàn tròn.

Giải:

Bổ đề: Cho 100 người đến từ 50 quốc gia, mỗi quốc gia có 2 người xếp thành một vòng tròn. CMR: có thể chia 100 người này thành 2 nhóm, mỗi nhóm có 50 người sao cho không có 2 người nào cùng một quốc gia và không có 3 người nào đứng kề nhau trên vòng tròn

Chứng minh:

Ta đáng số và chia những người này thành từng cặp theo chiều kim đồng hồ:

 

Ta xây dựng một đồ thị lưỡng phân với các đỉnh lần lượt là các cặp và 50 nước, nếu một người của nước nào đó được chọn từ một cặp nào đó thì ta nối 2 đỉnh tương ứng bằng một cạnh. Dễ thấy đồ thị trên thỏa mãn điều kiện Hall. Vậy ta chọn được 50 người từ 50 cặp đến từ các nước khác nhau. Những người còn lại sẽ thuộc nhóm thứ hai. Cách chia trên thỏa mãn yêu cầu của bổ đề, suy ra đpcm

Trở lại bài toán:

Trong mỗi bộ 4 người ở một quốc gia, ta chia làm 2 tỉnh, mỗi tỉnh có 2 người. Ta có tất cả 50 tỉnh. Theo bổ đề trên thì ta có thể chia 100 người này thành 2 nhóm, mỗi nhóm có 50 người sao cho không có 2 người nào cùng một tỉnh và không có 2 người nào đứng kề nhau trên vòng tròn.

Có thể thấy rằng trong 50 người của nhóm 1 sẽ có 25 cặp có cùng một quốc gia. Ta chia 50 người này thành 2 nhóm sao cho không có 2 người nào cùng một cặp ở chung một nhóm.

Làm tương tự với nhóm 2

Suy ra đpcm

File gửi kèm

•  Hall.pdf   546.21K   1877 Số lần tải

Bài viết đã được chỉnh sửa nội dung bởi LNH: 30-01-2014 - 20:47