ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
---------------------------

NGUYỄN THỊ HÂN

VỀ ĐỊNH LÝ HELLY
VÀ MỘT SỐ ỨNG DỤNG

LUẬN VĂN THẠC SĨ TOÁN HỌC

THÁI NGUYÊN - 2017


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
---------------------------

NGUYỄN THỊ HÂN

VỀ ĐỊNH LÝ HELLY
VÀ MỘT SỐ ỨNG DỤNG
LUẬN VĂN THẠC SĨ TOÁN HỌC

Chuyên ngành: Phương pháp Toán sơ cấp
Mã số: 60 46 01 13

NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS.TS. Nguyễn Thị Thu Thủy

THÁI NGUYÊN - 2017

1.2.2

Khái niệm và ví dụ . . . . . . . . . . . . . . . . . . . 13
Tính chất của tập lồi . . . . . . . . . . . . . . . . . . 14

Chương 2. Về định lý Helly và một số ứng dụng
20
2.1 Định lý Helly . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.1.1
2.1.2
2.2

Một số ứng dụng của Định lý Helly . . . . . . . . . . . . . . 28
2.2.1
2.2.2

2.3

Tính chất giao hữu hạn . . . . . . . . . . . . . . . . 20
Định lý Helly . . . . . . . . . . . . . . . . . . . . . . 23
Định lý Thư viện Nghệ thuật . . . . . . . . . . . . . 28
Bài toán của Vincensini . . . . . . . . . . . . . . . . 36

Một số bài toán áp dụng . . . . . . . . . . . . . . . . . . . . 44

Kết luận

48

Tài liệu tham khảo

và F.A. Vanlentine, V.L. Klee, C. Carathéodery . . . Đặc biệt là nhà toán
học E. Helly.
Định lý Helly là một kết quả cơ bản trong hình học rời rạc về giao của
các tập hợp lồi. Định lý cho ta một điều kiện đủ để nhận biết khi nào một
họ các hình lồi sẽ có giao khác rỗng. Nó được phát hiện bởi E. Helly năm
1913, nhưng chỉ được xuất bản vào năm 1923, khi các chứng minh khác
của Radon (1921) và K¨onig (1922) đã được đăng.
Định lý Helly được phát biểu như sau: Giả sử F := {F1 , F2 , . . . , Fk } là
họ gồm k tập hợp lồi F1 , F2 , . . . , Fk trong Rn , trong đó k > n. Nếu giao
của mọi bộ n+1 tập của họ F là khác rỗng, thì giao của tất cả các tập hợp
trong họ F là khác rỗng, nghĩa là kj=1 Fj = ∅. Để áp dụng cho một số vô
hạn các tập hợp ta cần có thêm tính chất compact: Nếu F := {Fα , α ∈ I}
là một họ các tập hợp lồi compact trong Rn và giao của mọi bộ không quá
n + 1 tập của họ F là khác rỗng thì giao của tất cả các tập hợp trong họ
đó là khác rỗng.
Mục đích của đề tài luận văn là tìm hiểu và trình bày các chứng minh
của định lý Helly, trình bày một số ứng dụng của định lý Helly như định
lý Thư Viện Nghệ Thuật, bài toán của Vincensini, đồng thời tìm hiểu một
số đề thi học sinh giỏi toán quốc gia và quốc tế áp dụng định lý Helly để
giải.
Nội dung của đề tài luận văn được trình bày trong hai chương. Chương
1 giới thiệu một số khái niệm và tính chất của tập compact, tập hợp lồi


3

trong không gian Rn . Chương 2 trình bày chứng minh định lý Helly, một
số ứng dụng của định lý Helly và một số bài toán áp dụng định lý Helly
để giải.


5

Định lý 1.1.4 (xem [6]) Tập tập hợp con K compact của Rn là tập đóng
và bị chặn.
Cho
I = {(x1 , x2 , . . . , xn )} ∈ Rn ;

ai ≤ xi ≤ bi ,

i = 1, n

với a = (a1 , a2 , . . . , an ) và b = (b1 , b2 , . . . , bn ) và ta đặt l (I) là cạnh lớn
nhất của I, nghĩa là
l (I) = sup {b1 − a1 , b2 − a2 , . . . , bn − an } .
Định lý 1.1.5 (Bolzano–Weierstrass) (xem [6]) Mọi tập con vô hạn bị
chặn của Rn đều có điểm tụ.
Chứng minh. Giả sử A là một tập hợp con vô hạn bị chặn của Rn và cho
I1 là một hình đóng chứa A. Chia I1 thành 2n hình đóng bằng cách cắt
ngang mỗi cạnh của nó. Vì I1 chứa vô số điểm của A, nên tồn tại ít nhất
một hình I2 trong số những hình được chia nhỏ sẽ chứa vô số điểm của A.
Tiếp theo ta lại chia hình I2 thành 2n hình đóng bằng cách cắt ngang
mỗi cạnh của nó, sao cho có ít nhất một hình đóng I3 , trong số những hình
được chia nhỏ, chứa vô số điểm của A.
Tiếp tục theo cách này, ta nhận được dãy {Ik }k≥1 các hình đóng lồng
nhau khác rỗng, mỗi một hình trong đó chứa vô hạn điểm của A.
Chú ý rằng cạnh dài nhất của hình thứ k thỏa mãn
0 < l (Ik ) =

l (I1 )
2k−1


Ki = ∅.

thì
i=1

Sau đây sự tương đương của định nghĩa tập compact trong Rn ở trên
với định nghĩa theo quan điểm của phủ các tập hợp mở.
Định lý 1.1.11 (xem [6]) Tập con K của không gian Rn là tập compact
khi và chỉ khi mọi phủ mở của K đều có phủ con hữu hạn.
Chứng minh. Từ những kết quả trên, ta chỉ cần chứng minh K đóng và
bị chặn (và do đó compact) nếu và chỉ nếu mỗi phủ mở của K đều có phủ
con hữu hạn.
Giả sử mỗi phủ mở của K đều có phủ con hữu hạn. Đặt U là họ các
hình cầu mở dạng B (k, 1) tâm k bán kính 1, trong đó k ∈ K. Hình cầu
B (k, 1) này là một phủ mở của tập compact K và do đó có phủ con hữu
hạn. Nếu {k1 , k2 , . . . , km } là tâm của các phủ con này, thì
m

K⊂

B (ki , 1)
i=1

và tập K bị chặn.
Bây giờ, giả sử mọi phủ mở của K đều có một một phủ con hữu hạn.
Gọi U = Rn \K là phần bù của K. Vì tập K bị chặn nên U = ∅. Ta sẽ


7


B (q, r)∩K ⊂ B (q, r)∩

m

B (pi , δ (pi )) =
i=1

B (q, r)∩B (pi , δ (pi )) = ∅.
i=1

Vì vậy B (p, r) ⊂ Rn \K và do đó Rn \K là tập mở nên K là tập đóng.
Ngược lại, giả sử tập K là tập đóng và bị chặn của Rn và
U = {Uα : α ∈ I}
là một họ các tập mở của Rn sao cho K ⊂ ∪ {Uα : α ∈ I}. Giả sử K không
chứa trong hợp của bất kỳ họ hữu hạn các tập mở của U.
Vì tập K là bị chặn nên có một số M > 0 sao cho K ⊆ I1 trong đó I1
là hình đóng trong Rn được cho bởi
I1 = {(x1 , x2 , . . . , xn ) ∈ Rn : |xk | ≤ M,

k = 1, . . . , n} .

Bằng cách cắt ngang mỗi cạnh của I1 , ta nhận được 2n khoảng đóng trong
I1 chứa các điểm của K nhưng không được chứa trong hợp của bất kỳ số


Luận văn đầy đủ ở file: Luận văn full