Luận văn Thạc sĩ Khoa học: Về lục giác lồi rỗng

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.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Khoa học: Về lục giác lồi rỗng ĐẠI HỌC QUỐC GIA HÀ NỘITRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------ NGUYỄN GIANG THÀNHVỀ 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- 2013Mục lụcMở đầu 31 TỔNG QUAN VỀ BÀI TOÁN ERDOS ¨ VỀ ĐA GIÁC LỒI RỖNG 5 1.1 Bài toán 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.1 Bài toán 1a . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.2 Bài toán 1b . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.3 Bài toán 1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.4 Bài toán 1.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.5 Bài toán 1.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2 Bài toán 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3 Bài toán 3 (Bài toán về tồn tại đa giác chứa k điểm trong ) . . . . . 19 1.4 Bài toán 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 CHỨNG MINH ĐÁNH GIÁ E(6) ≤ ES(9) VÀ HỆ QUẢ 23 2.1 Định lý E(6) ≤ ES(9) . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2 Lược đồ chứng minh . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2.1 Kí hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2.2 Các định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3 Các trường hợp đơn giản . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.4 Các trường hợp (3, ≥ 0) và (≥ 6, 3) . . . . . . . . . . . . . . . . . . . . 27 2.4.1 Các trường hợp (3, ≥ 0) và (8,3) . . . . . . . . . . . . . . . . . 27 2.4.2 Các trường hợp (6,3) và (7,3) . . . . . . . . . . . . . . . . . . 29 2.5 Các trường hợp (4, ≥ 0) và (≥ 7, 4) . . . . . . . . . . . . . . . . . . . . 34 2.5.1 Bước 1a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.5.2 Bước 1b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.5.3 Bước 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.5.4 Bước 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.5.5 Tổng kết . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.6 Các trường hợp (5, 0) và (≥ 7, 5, 0) . . . . . . . . . . . . . . . . . . . . 40 2.6.1 Các trường hợp (5, 0) và (8, 5, 0) . . . . . . . . . . . . . . . . . 40 2.6.2 Trường hợp (7, 5, 0) . . . . . . . . . . . . . . . . . . . . . . . . 40 2.7 Các trường hợp riêng . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.7.1 Trường hợp (5,1) . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.7.2 Trường hợp (6,1) . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.7.3 Các trường hợp (6,2) và (7,1) . . . . . . . . . . . . . . . . . . 43 2.8 Các trường hợp (5, ≥ 2) . . . . . . . . . . . . . . . . . . . . . . . . . . 43 1 2.8.1 Một quan sát cơ bản . . . . . . . . . . . . . . . . . . . . . . . 43 2.8.2 Các trường hợp (5, ≥ 2) . . . . . . . . . . . . . . . . . . . . . . 462.9 Các trường hợp (6, ≥ 4) . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.9.1 TW X ∩ TXY 6= ∅ . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.9.2 TW X ∩ TXY = ∅ . . . . . . . . . . . . . . . . . . . . . . . . . . 512.10 Các trường hợp (≥ 7, ≥ 5, ≥ 1) . . . . . . . . . . . . . . . . . . . . . . 52 2.10.1 Quy tắc 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.10.2 Quy tắc 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.10.3 Ứng dụng của Quy tắc 1 và 2 . . . . . . . . . . . . . . . . . . 54 2.10.4 Quy tắc 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.10.5 Ứng dụng các Quy tắc 1-3 . . . . . . . . . . . . . . . . . . . 58 2.10.6 Trường hợp (1, 1, 1, 1, 1, 1, 1) . . . . . . . . . . . . . . . . . . 59 2.10.7 Trường hợp (1, 1, 1, 1, 1, 1, 1, 0) . . . . . . . . . . . . . . . . . 59 2.10.8 Trường hợp (1, 1, 1, 1, 1, 1, 1, 1) . . . . . . . . . . . . . . . . . . 61Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 2Mở đầu Năm 1935, Erdo˝s và Szekeres đã đưa ra giả thuyết sau đây (giả thuyết Erdo˝s-Szekeres): ...