Month: November 2007

Convex set


Trong bài này, \mathbb{R}^1, \mathbb{R}^2 và \mathbb{R}^3 lần lượt là tập các điểm thuộc đường thẳng, mặt phẳng và không gian.

Cho số nguyên dương d\leq 3. Một tập hợp C\subset \mathbb{R}^d được gọi là tập hợp lồi nếu với mỗi hai điểm A và B thuộc C, cả đoạn thẳng AB cũng nằm trong C.

Dễ thấy giao của một họ bất kỳ các tập hợp lồi là một tập hợp lồi. Vì thế ta có thể định nghĩa bao lồi của một tập hợp X\subset \mathbb{R}^d là giao của tất cả các tập hợp lồi trong \mathbb{R}^d chứa X. Như vậy bao lồi của một tập hợp là tập hợp lồi nhỏ nhất chứa nó.

Nếu A và B là hai điểm khác nhau thì bao lồi của tập hợp \{A,B\} là đoạn thẳng AB. Nếu A,B và C là ba điểm không thẳng hàng thì bao lồi của tập \{A,B,C\} là tam giác ABC (phần trong và biên).

Dùng tổ hợp lồi ta có một mô tả khác của bao lồi.

Định lí 1. Cho X là một tập hợp con khác rỗng của \mathbb{R}^2. Khi đó điểm x thuộc bao lồi của X khi và chỉ khi tồn tại các điểm x_1,x_2,\ldots,x_n\in X và các số thực không âm t_1,t_2,\ldots,t_n thỏa mãn \sum t_i=1 và x=\sum t_ix_i.

Biểu diễn \sum t_ix_i như trong định lí trên được gọi là tổ hợp lồi của các điểm x_1,x_2,\ldots,x_n.

Với tập hợp hữu hạn trong mặt phẳng ta có kết quả sau, kết quả này được dùng nhiều trong các bài toán thi chọn học sinh giỏi.

Định lí 2. Cho số nguyên n>2 và n điểm A_1,A_2,\ldots,A_n trong \mathbb{R}^2. Khi đó bao lồi của tập \{A_i\} là đa giác lồi có tập đỉnh là tập con của tập \{A_i\}.

Trong định lí trên một đoạn thẳng được xem là một đa giác lồi với hai đỉnh là các đầu mút.

Định lí Helly là một kết quả cơ bản trong hình học tổ hợp về giao của các tập hợp lồi. Nó được Eduard Helly phát hiện vào năm 1913, nhưng mãi đến năm 1923 ông mới công bố, lúc đó các chứng minh của Radon (1921) và Konig (1922) đã xuất hiện.

Định lí 3 (Helly). Cho số nguyên n>3 và n tập hợp lồi X_1,X_2,\ldots,X_n trong \mathbb{R}^2. Khi đó nếu mỗi ba tập trong chúng có giao khác rỗng thì cả n tập có giao khác rỗng.

Chứng minh. Ta chứng minh bằng quy nạp theo n. Đầu tiên ta xét n=4. Giả sử bốn tập hợp lồi X_1,X_2,X_3 và X_4 trong \mathbb{R}^2 có tính chất: mỗi ba tập trong chúng có giao khác rỗng. Lấy bốn điểm A_1,A_2,A_3 và A_4 sao cho A_i thuộc \displaystyle \bigcap_{j\not=i}A_j với mỗi i.

Nếu bốn điểm A_1, A_2, A_3 và A_4 thẳng hàng theo thứ tự đó thì A_2 thuộc cả bốn tập lồi. Nếu bao lồi của \{A_i\} là một tam giác thì điểm còn lại không phải là đỉnh của bao lồi sẽ thuộc cả bốn tập lồi. Nếu bao lồi của \{A_i\} là một tứ giác thì giao điểm của hai đường chéo tứ giác sẽ thuộc cả bốn tập lồi.

Vậy khẳng định đúng với n=4. Bây giờ ta giả sử khẳng định đúng với n\, (n\geq 4), và đi chứng minh nó đúng với n+1. Xét n+1 tập hợp lồi X_1,X_2,\ldots,X_{n+1} trong \mathbb{R}^2 có tính chất: mỗi ba tập trong chúng có giao khác rỗng. Dùng giả thiết quy nạp cho n tập hợp lồi X_1\cap X_{n+1},X_2\cap X_{n+1},\ldots,X_n\cap X_{n+1} ta có điều cần chứng minh.  \Box

Một cách tổng quát ta có kết quả sau, chứng minh được thực hiện tương tự như trên.

Cho số nguyên n>d+1 và n tập hợp lồi X_1,X_2,\ldots,X_n trong \mathbb{R}^d. Khi đó nếu mỗi d+1 tập trong chúng có giao khác rỗng thì cả n tập có giao khác rỗng.