Luận văn Thạc sĩ Toán học: Một số kết quả về hình lồi, đường kính và ứng dụng

Luận văn thạc sĩ tập trung vào các kết quả mới về hình lồi đường kính và ứng dụng thực tiễn. Khám phá lý thuyết và bài toán liên quan.

• Tác giả: Vũ Văn Ninh
• Người hướng dẫn: TS. Trần Xuân Quý
• Trường học: Trường Đại học Khoa học
• Chuyên ngành: Toán học
• Đề tài: Một số kết quả về hình lồi, đường kính của hình và vận dụng
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2017
• Địa điểm: Thái Nguyên

Tóm tắt

I. Tổng quan về hình lồi và đường kính trong toán học

Hình lồi là khái niệm cơ bản trong hình học phẳng và không gian. Một tập hợp được gọi là hình lồi nếu đoạn thẳng nối hai điểm bất kỳ trong tập hợp đó luôn nằm hoàn toàn trong tập hợp. Các hình tam giác, tứ giác đều, hình bình hành đều là những ví dụ điển hình về hình lồi. Đường kính của hình là khoảng cách lớn nhất giữa hai điểm thuộc hình đó. Trong luận văn Thạc sĩ Toán học của tác giả Vũ Văn Ninh, các vấn đề liên quan đến hình lồi và đường kính được nghiên cứu một cách hệ thống. Công trình này tập trung vào giao khác rỗng của các hình lồi, bài toán chia hình phẳng và hình cầu dựa trên đường kính. Các kết quả thu được không chỉ có giá trị lý thuyết mà còn mở ra nhiều hướng ứng dụng thực tiễn trong tối ưu tổ hợp và giải các bài toán thi học sinh giỏi quốc gia, quốc tế.

1.1. Khái niệm hình lồi và tính chất cơ bản

Hình lồi được định nghĩa qua tính chất: với mọi hai điểm trong tập hợp, đoạn thẳng nối chúng phải thuộc hoàn toàn tập hợp đó. Trong hình học phẳng, đa giác lồi là hình đa giác mà mọi cạnh đều hướng ra ngoài. Một tính chất quan trọng là giao của các hình lồi luôn là hình lồi. Bao lồi của một tập điểm hữu hạn là hình lồi nhỏ nhất chứa tất cả các điểm đó. Các tính chất này đóng vai trò nền tảng cho việc giải quyết nhiều bài toán hình học tổ hợp phức tạp trong toán học hiện đại.

1.2. Định nghĩa đường kính của hình

Đường kính của hình là đại lượng đo khoảng cách lớn nhất giữa hai điểm bất kỳ thuộc hình. Ký hiệu d là đường kính, đại lượng này thể hiện kích thước tối đa của hình theo bất kỳ phương nào. Đối với hình tròn, đường kính là khoảng cách giữa hai điểm đối diện qua tâm. Với đa giác lồi n cạnh, số đường kính không vượt quá n. Một kết quả quan trọng trong luận văn chỉ ra mối liên hệ giữa bán kính đường tròn ngoại tiếp và nội tiếp thông qua bất đẳng thức R ≥ r, trong đó đẳng thức xảy ra khi và chỉ khi hình là hình tròn.

II. Phân tích các bài toán về hình lồi và đường kính

Các bài toán về hình lồi và đường kính thuộc lĩnh vực toán học rời rạc và hình học tổ hợp. Luận văn Thạc sĩ phân tích nhiều dạng bài toán khác nhau. Bài toán thứ nhất liên quan đến giao khác rỗng của các hình lồi: xác định điều kiện để giao của nhiều hình lồi luôn khác rỗng. Bài toán thứ hai là chia hình phẳng thành số phần nhỏ nhất sao cho mỗi phần có đường kính nhỏ hơn đường kính hình ban đầu. Đặc biệt, bài toán chia hình cầu thành bốn phần có đường kính nhỏ hơn nhận được sự quan tâm lớn vì tính bất khả quy về số lượng phần tối thiểu. Các bài toán này đòi hỏi tư duy logic chặt chẽ, khả năng xây dựng chứng minh phản chứng và kỹ năng áp dụng định lý Helly một cách sáng tạo trong không gian Euclid.

2.1. Bài toán giao khác rỗng của các hình lồi

Bài toán giao khác rỗng là vấn đề trung tâm trong lý thuyết hình lồi. Định lý Helly phát biểu rằng trong ℝⁿ, nếu mỗi n+1 hình lồi trong một tập hợp hữu hạn có giao khác rỗng thì toàn bộ tập hợp có giao khác rỗng. Trong mặt phẳng, điều này có nghĩa nếu mỗi ba hình lồi có điểm chung thì tất cả hình lồi có điểm chung. Luận văn mở rộng kết quả này cho các trường hợp đặc biệt và xây dựng các ước lượng chặt hơn cho số lượng hình lồi tối thiểu cần xét. Các ứng dụng của định lý Helly xuất hiện trong lý thuyết tối ưu và khoa học máy tính.

2.2. Bài toán chia hình theo đường kính

Bài toán chia hình yêu cầu phân hoạch một hình thành các phần con sao cho đường kính mỗi phần nhỏ hơn đường kính hình gốc. Đối với hình phẳng, kết quả nổi tiếng cho thấy bất kỳ hình nào cũng có thể chia thành ba phần có đường kính nhỏ hơn. Với hình cầu, bài toán trở nên phức tạp hơn: hình cầu có thể chia thành bốn phần có đường kính nhỏ hơn nhưng không thể chia thành ít hơn bốn phần. Chứng minh tính tối thiểu này sử dụng kỹ thuật tô pô và lý thuyết điểm cố định. Kết quả có ý nghĩa quan trọng trong giải tích hàm và hình học metric.

III. Phương pháp giải quyết và kỹ thuật chứng minh hình lồi

Luận văn áp dụng nhiều phương pháp chứng minh sáng tạo để giải quyết các bài toán về hình lồi và đường kính. Phương pháp quy nạp được sử dụng phổ biến khi chứng minh tính chất của đa giác lồi n cạnh. Kỹ thuật phản chứng đóng vai trò quan trọng trong việc chứng minh các bất đẳng thức liên quan đến đường kính. Cụ thể, khi chứng minh R ≥ r, giả sử tồn tại cặp điểm P, Q sao cho R(P) < r(Q), dẫn đến mâu thuẫn vì đường tròn tâm P bán kính R(P) phủ hình F nhưng lại không phủ được đường tròn tâm Q bán kính r(Q). Phương pháp hình học giải tích kết hợp lý thuyết tập hợp lồi cho phép chuyển đổi bài toán hình học thành bài toán tối ưu. Các kỹ thuật xây dựng ví dụ đối chứng giúp xác định tính tối ưu của các kết quả thu được.

3.1. Kỹ thuật quy nạp và phản chứng

Quy nạp toán học là công cụ mạnh mẽ trong chứng minh tính chất hình lồi. Với đa giác n cạnh, giả sử tính chất đúng cho n-1 cạnh rồi suy ra cho n cạnh bằng cách loại bỏ một đỉnh phù hợp. Kỹ thuật phản chứng đặc biệt hiệu quả khi chứng minh đường kính: giả sử điều kiện đường kính bị vi phạm, từ đó xây dựng mâu thuẫn hình học. Ví dụ, khi chứng minh số đường kính của n-giác không vượt quá n, giả sử có đỉnh với nhiều hơn hai đường kính, kỹ thuật cung tròn giúp chỉ ra mâu thuẫn về vị trí tương đối của các đỉnh trong đa giác lồi.

3.2. Ứng dụng định lý Helly và bao lồi

Định lý Helly là công cụ then chốt trong nghiên cứu giao của các hình lồi. Định lý phát biểu rằng với tập hợp hữu hạn các hình lồi trong ℝ², nếu mỗi ba hình có giao khác rỗng thì toàn bộ tập hợp có giao khác rỗng. Bao lồi của tập điểm là hình lồi nhỏ nhất chứa tất cả các điểm, có thể xây dựng bằng thuật toán Graham scan hoặc Jarvis march. Kết hợp định lý Helly với tính chất bao lồi, luận văn giải quyết các bài toán về điểm chung của các hình và xác định điều kiện để tập điểm thỏa mãn tính chất hình lồi. Phương pháp này cũng áp dụng thành công trong lý thuyết tối ưu tổ hợp.

IV. Kết luận và ứng dụng của hình lồi đường kính toán học

Luận văn Thạc sĩ của Vũ Văn Ninh đã tổng hợp và phát triển nhiều kết quả có giá trị về hình lồi và đường kính. Về mặt lý thuyết, công trình làm rõ điều kiện giao khác rỗng của hình lồi, chứng minh tính tối ưu trong bài toán chia hình phẳng và hình cầu. Kết quả về số đường kính của n-giác lồi không vượt quá n được chứng minh chặt chẽ bằng quy nạp. Về ứng dụng, các kết quả này phục vụ giải bài toán thi học sinh giỏi quốc gia và quốc tế, hỗ trợ giảng dạy hình học tổ hợp trong chương trình phổ thông. Hướng nghiên cứu mở rộng bao gồm tổng quát hóa cho không gian nhiều chiều, áp dụng trong lý thuyết tập hợp mờ và tối ưu lồi trong khoa học dữ liệu. Các phương pháp chứng minh trong luận văn cũng là tài liệu tham khảo quý giá cho nghiên cứu sinh và giảng viên toán học.

4.1. Ứng dụng trong thi học sinh giỏi toán

4.2. Hướng phát triển và mở rộng nghiên cứu

Trích đoạn nội dung tài liệu

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.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. 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. 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 [ nhỏ hơn 180 độ và qua B sẽ có vô hạn đường thẳng tựa của hình ABC [ 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.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: 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 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 ∈ F 2 ∩ F 3 ∩ F 4 A2 ∈ F 1 ∩ F 3 ∩ F 4 A3 ∈ F 1 ∩ F 2 ∩ F 4 A4 ∈ F 1 ∩ F 2 ∩ F 3 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 △A1 A2 A3 mà A1 , A2 , A4 ∈ F4.

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.5 Cho ba hình bình hành F1 , F2 , F3 , các cạnh của chúng song song với hai đường thẳng cố định. Khi đó, nếu mọi cặp hai hình trong chúng có điểm chung, thì cả ba hình bình hành cũng có điểm chung.