Chương 1 Một số kiến thức chuẩn bị 1. Khái niệm về hình lồi [3] Khi học hình học phẳng chúng ta đã làm quen với các hình lồi, chẳng hạn các hình tam giác, các hình bình hành, các hình thang và các đa giác đều là các hình lồi. Hình 1 Trong sách giáo khoa các đa giác lồi được đề cập tới và được định nghĩa như sau: một đa giác là đa giác lồi khi nó nằm về một phía của đường thẳng đi qua một cạnh bất kì. Nhưng định nghĩa này rất hạn chế không thể áp dụng cho hình có ít nhất một cạnh không phải là đoạn thẳng (chẳng hạn hình tròn, các hình e-lip), hoặc là hình không có giới hạn trong mặt phẳng (một góc chẳng hạn).
Để mở rộng khái niệm hình lồi người ta đưa ra định nghĩa sau đây mở rộng cho các hình không phải là các đa giác. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 3 Định nghĩa 1.1 Một hình F được gọi là lồi khi và chỉ khi mọi điểm A, B thuộc F thì đoạn AB thuộc F. Hình 2 Dễ thấy rằng các đa giác lồi cũng lồi theo khái niệm này. Và ngoài các đa giác lồi thì các hình tròn, hình elip, hình viên phân hình không có giới hạn trong mặt phẳng cũng là hình lồi.
Hình 3 Trong hình trên ta có thể tìm thấy các ví dụ về hình không phải là hình lồi. Các hình lồi đóng (hiểu theo nghĩa giải tích là nó chứa tất cả các điểm giới hạn của nó) và bị chặn (có thể phủ nó bằng một hình tròn đủ lớn) được gọi là các oval. Ngoài ra còn có các hình lồi không bị chặn: nửa mặt phẳng, một góc nhỏ hơn 180 độ, một dải, phần mặt phẳng giới hạn bởi một đường thẳng parabol. Các điểm của một hình lồi được chia thành hai loại điểm trong và điểm biên.2 Một điểm gọi là điểm trong của hình lồi F nếu tồn tại một hình tròn nhận nó làm tâm và nằm hoàn toàn trong F.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 4 Hình 4 Định nghĩa 1.3 Một điểm gọi là điểm biên của hình lồi F nếu mỗi hình tròn nhận nó làm tâm chứa ít nhất một điểm không thuộc hình lồi F. Hình 5 Định nghĩa 1.4 Nếu F hình lồi đóng thì tập hợp các điểm biên là những đường liên tục được gọi là biên của F. Các oval có biên là một đường khép kín. Các hình trong luận văn này đều được hiểu là các hình đóng có tính cả biên, trừ trường hợp ngoại lệ mà ta nói rõ.1 Một đường thẳng qua điểm trong hình lồi F cắt biên tại đúng 2 điểm.
Khi đó đoạn nối hai điểm này nằm trong F. Bây giờ xét B là một điểm biên tùy ý của một hình lồi F. Từ B ta kẻ những nửa đường thẳng xuất phát từ B và chạy qua ít nhất một điểm bên trong của F. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 5 Hình 6 Các tia này sẽ tạo nên một nửa mặt phẳng hoặc là tạo nên một góc lồi.5 Đường thẳng d đi qua ít nhất một điểm biên và không đi qua điểm trong nào của hình lồi F gọi là đường thẳng tựa của F.
Trong trường hợp thứ nhất đường thẳng tạo nên nửa mặt phẳng là đường thẳng tựa duy nhất của F. Hình 7 Còn trong trường hợp thứ hai, hình F nằm trong miền trong của góc ABC [ nhỏ hơn 180 độ và qua B sẽ có vô hạn đường thẳng tựa của hình lồi F: bất kỳ đường thẳng nào không đi qua điểm trong của góc ABC [ đều sẽ là đường thẳng tựa của F. Các tia tạo nên bởi BA+ và BC + được gọi là nửa tiếp tuyến của F tại B. Tóm lại là đi qua một điểm biên tùy ý của F có ít nhất một đường thẳng tựa.2 Qua một điểm biên B của hình lồi F có ít nhất một đường thẳng tựa.
Trong trường hợp có duy nhất một đường thẳng tựa thì B gọi là điểm chính quy của F. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 6 Định nghĩa 1.6 Nếu qua điểm biên B của hình F có vô hạn đường thẳng tựa thì điểm B gọi là không chính quy hoặc là đỉnh của F. Giao của các hình lồi [7] Trong phần này chúng ta làm quen với một định lý rất quan trọng của hình học tổ hợp. Nếu cho trước một họ các hình lồi, chúng ta quan tâm đến câu hỏi khi nào họ hình lồi này có giao khác rỗng.
Những câu hỏi đó được đặt ra khi xem xét một hệ điểm có thể phủ được bởi một hình tròn có bán kính cho trước hay không (ta có thể thấy ngay điều đó tương đương với câu hỏi: liệu họ các hình tròn có tâm tại các điểm đã cho và bán kính cho trước có giao với nhau khác rỗng hay không?). Những câu hỏi tương tự như vậy có thể đặt ra mặc dù có thể khó nhận biết hơn. Chẳng hạn ta có thể hỏi khi nào trong đa giác cho trước tồn tại một điểm, có thể từ đó quan sát được hết tất cả các cạnh của đa giác. Nhưng hình lồi trong không gian một chiều (đường thẳng) có thể nhận biết và chia lớp khá đơn giản.
Chúng chỉ có thể là một đoạn, một khoảng, một tia hoặc là cả đường thẳng mà thôi. Trong không gian 2- chiều, tức là trên mặt phẳng thì hình lồi đa dạng hơn và đặc biệt khó là vấn đề nhận biết khi nào giao của chúng khác rỗng. Chẳng hạn nếu cho trước một hình (hoặc hệ một điểm) thì rất khó trả lời khi nào có thể phủ nó bằng một hình tròn bán kính R. Ta có thể dễ dàng nhận thấy rằng câu hỏi đó tương đương với câu hỏi liệu hệ các hình tròn bán kính R có tâm tại các điểm thuộc hình (hoặc hệ điểm cho trước) có giao khác rỗng hay không? Trước hết ta có thể dễ dàng chứng minh mệnh đề sau cho không gian một chiều: Định lý 1.3 Một họ I các đoạn thẳng [ai , bi ] trên đường thẳng cho trước có giao khác rỗng khi và chỉ khi giao của hai đoạn bất kì trong chúng khác rỗng.
Chứng minh: LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 7 Điều kiện cần: Nếu giao các đoạn của họ I khác rỗng ⇒ ∃c ∈ ∩I ⇒ c ∈ [ai , bi ] ∩ [aj , bj ] , ∀i, j. Điều kiện đủ: Nếu giao của hai đoạn thẳng bất kì trong một họ các đoạn thẳng khác rỗng thì giao của họ các đoạn thẳng này sẽ khác rỗng. Lưu ý rằng [ai , bi ] ∩ [aj , bj ] tương đương với điều kiện min{bi , bj } ≥ max{ai , aj }. Thậy vậy, nếu: [ai , bi ] ∩ [aj , bj ] 6= thì tồn tại: c ∈ [ai , bi ] ∩ [aj , bj ].
Khi đó ta có bi , bj ≥ c và c 6= ai , aj. Do đó ta có: min{bi , bj } ≥ c ≥ max{ai , aj } Ngược lại, nếu min{bi , bj } ≥max{ai , aj }, thì chọn c thỏa mãn: min{bi , bj } ≥ c ≥ max{ai , aj } Khi đó c ∈ [ai , bi ] và c ∈ [aj , bj ] cho nên: c ∈ [ai , bi ] ∩ [aj , bj ]. Vậy ta có điều kiện: [ai , bi ] ∩ [aj , bj ] 6= tương đương với điều kiện min{bi , bj } ≥ max{ai , aj }. Với lưu ý trên, nếu có một họ I các đoạn thẳng [ai , bi ] sao cho giao của hai đoạn thẳng trong chúng khác rỗng thì ta có: inf{bi : i ∈ I } ≥ sup{ai : i ∈ I } Khi đó điểm c thỏa mãn: inf{bi : i ∈ I } ≥ c ≥ sup{ai : i ∈ I } sẽ thuộc giao chung của tất cả các đoạn thẳng thuộc họ I.
♦ Chú ý: Ta phải dùng inf và sup vì nếu I là họ vô hạn các đoạn thì min{bi , bj }; max{ai , aj } có thể không tồn tại. Ví dụ 1 1 I= 1 − ;1 + , n ∈ N∗ n n 1 1 I= ;1 + , n ∈ N∗ n n LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 8 1 1 I= 1 − ;2 − , n ∈ N∗ n n Trên mặt phẳng, mệnh đề tương tự cũng đúng. Tuy nhiên chứng minh cho trường hợp họ vô hạn các hình lồi sẽ khó hơn rất nhiều. Ở đây ta chứng minh mệnh đề tương tự cho hữu hạn các hình lồi.4 Giao của một họ hữu hạn các hình lồi trên mặt phẳng khác rỗng nếu giao của ba hình bất kì trong chúng khác rỗng.
Chứng minh: Định lý hiển nhiên đúng cho 3 hình. Ta chứng minh quy nạp theo số n các hình lồi (n ≥ 4). ∗ Ta chứng minh cho n = 4. Gọi F1 , F2 , F3 , F4 là 4 hình lồi sao cho 3 hình bất kỳ trong chúng có giao khác rỗng.
A1 ∈ F2 ∩ F3 ∩ F4 A2 ∈ F1 ∩ F3 ∩ F4 A3 ∈ F1 ∩ F2 ∩ F4 A4 ∈ F1 ∩ F2 ∩ F3 Trường hợp 1. Nếu 2 điểm trong số 4 điểm A1 , A2 , A3 , A4 trùng nhau. Vậy ta chỉ xét 4 điểm A1 , A2 , A3 , A4 phân biệt. Trường hợp 2.
Trường hợp 3. Bao lồi của A1 , A2 , A3 , A4 là tứ giác A1 A2 A3 A4. Xét O là giao điểm của 2 đường chéo A1 A3 và A2 A4. Trường hợp 4.
Bao lồi của A1 A2 A3 A4 là tam giác. Giả sử A4 nằm trong hoặc trên 4A1 A2 A3 mà A1 , A2 , A4 ∈ F4. LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Vậy định lý đúng cho trường hợp n = 4.
Giả sử định lý đúng cho trường hợp n ≥ 4. Ta chứng minh nó đúng với n + 1. Thật vậy, xét n + 1 hình lồi F1 , F2 , ., Fn , Fn+1 thỏa mãn giao của 3 hình bất kỳ khác rỗng. Xét n hình lồi sau: F1 , F2 , ., Fn−1 , Fn ∩ Fn+1 , n hình này thỏa mãn điều kiện của định lý vì nếu 3 hình bất kỳ trong chúng không chứa Fn ∩ Fn+1 có giao khác rỗng.
Nếu có một trong ba hình là Fn ∩ Fn+1 thì ta quy về bốn hình Fn , Fn−1 và 2 hình kia, nên có giao khác rỗng. Vậy n hình trên thỏa mãn điều kiện của định lý. Theo giả thiết quy nạp F1 ∩ F2 ∩. ∩ Fn−1 ∩ Fn ∩ Fn+1 6= ∅.
Tức là n + 1 hình lồi đã cho có giao khác rỗng.