Năm 1935, Erdos và Szekeres đã đưa ra giả thuyết sau đây (giả thuyết Erdos-Szekeres): Mọi tập không ít hơn 2 n−2 + 1 điểm trên mặt phẳng ở vị trí tổng quát (không có ba điểm nào thẳng hàng) đều chứa n điểm là đỉnh của một đa giác lồi. Giả thuyết Erdos-Szekeres có ý nghĩa triết học sâu sắc: Từ một tập hợp hỗn độn, không có trật tự, đủ lớn (tập các điểm bất kì trên mặt phẳng), ta có thể tìm được một tập con có cấu trúc đẹp (đa giác lồi). Mời các bạn cùng tìm hiểu. | ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------ NGUYỄN GIANG THÀNH VỀ LỤC GIÁC LỒI RỖ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. TẠ DUY PHƯỢNG HÀ NỘI- 2013 Mục lục Mở đầu 3 1 TỔNG QUAN VỀ BÀI TOÁN ERDOS VỀ ĐA GIÁC LỒI RỖNG 5 Bài toán 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Bài toán 1a . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Bài toán 1b . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Bài toán 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Bài toán 3 Bài toán về tồn tại đa giác chứa k điểm trong . . . . . 19 Bài toán 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2 CHỨNG MINH ĐÁNH GIÁ E 6 ES 9 VÀ HỆ QUẢ 23 Định lý E 6 ES 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Lược đồ chứng minh . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Kí hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Các định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Các trường hợp đơn giản . . . . . . . . . . . . . . . . . . . . . . . . . 27 Các trường hợp 3 0 và 6 3 . . . . . . . . . . . . . . . . . . . . 27 Các trường hợp 3 0 và 8 3 . . . . . . . . . . . . . . . . . 27 Các trường hợp 6 3 và 7 3 . . . . . . . . . . . . . . . . . . 29 Các trường hợp 4 0 và 7 4 . . . . . . . . . . . . . . . . . . . . 34 Bước 1a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Bước 1b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Bước 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
