Về định lý Helly và một số ứng dụng

ĐẠ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

i

Mục lục

Lời cảm ơn ii

Mở đầu 2

Chương 1. Một số kiến thức chuẩn bị 4

1.1 Tập compact trong R

n

. . . . . . . . . . . . . . . . . . . . . 4

1.1.1 Tập compact . . . . . . . . . . . . . . . . . . . . . . 4

1.1.2 Dãy Cauchy . . . . . . . . . . . . . . . . . . . . . . . 11

1.2 Tập hợp lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.2.1 Khái niệm và ví dụ . . . . . . . . . . . . . . . . . . . 13

1.2.2 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 Tính chất giao hữu hạn . . . . . . . . . . . . . . . . 20

2.1.2 Định lý Helly . . . . . . . . . . . . . . . . . . . . . . 23

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

2.2.1 Định lý Thư viện Nghệ thuật . . . . . . . . . . . . . 28

2.2.2 Bài toán của Vincensini . . . . . . . . . . . . . . . . 36

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

Kết luận 48

Tài liệu tham khảo 49

ii

Lời cảm ơn

Với lòng biết ơn sâu sắc em xin chân thành gửi tới PGS.TS. Nguyễn Thị

Thu Thủy - người cô đã tận tâm, nhiệt tình chỉ bảo, động viên giúp đỡ

em trong suốt quá trình nghiên cứu và hoàn thành luận văn.

Em xin chân thành cảm ơn các thầy cô trong khoa Toán - Tin, Trường

Đại học Khoa học – Đại học Thái Nguyên, các giáo sư của Trường Đại

học Khoa học Tự nhiên – Đại học quốc gia Hà Nội; của Viện Toán học –

Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã tạo điều kiện thuận

lợi giúp đỡ em trong quá trình học tập và nghiên cứu tại trường Đại học

Khoa học.

Em xin chân thành cảm ơn các anh chị và bạn bè đồng nghiệp trong

lớp Cao học Toán K9B2 đã luôn giúp đỡ em trong suốt quá trình học tập

và nghiên cứu.

Thái Nguyên, tháng 10 năm 2017

Tác giả luận văn

Nguyễn Thị Hân

2

Mở đầu

Tập hợp lồi là một khái niệm xuất hiện từ lâu trong nhiều ngành của Toán

học, nó được nhiều nhà toán học quan tâm nghiên cứu như E. Buchman

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 R

n

, 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à Tk

j=1 Fj 6= ∅. Để á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 R

n 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