Chia sẻ đồ án, luận văn ngành Khoa học Tự nhiên miễn phí
Nội quy chuyên mục: - Hiện nay có khá nhiều trang chia sẻ Tài liệu nhưng mất phí, đó là lý do ket-noi mở ra chuyên mục Tài liệu miễn phí.

- Ai có tài liệu gì hay, hãy đăng lên đây để chia sẻ với mọi người nhé! Bạn chia sẻ hôm nay, ngày mai mọi người sẽ chia sẻ với bạn!
Cách chia sẻ, Upload tài liệu trên ket-noi

- Những bạn nào tích cực chia sẻ tài liệu, sẽ được ưu tiên cung cấp tài liệu khi có yêu cầu.
Nhận download tài liệu miễn phí
By forever_yeunguoitrongimlang
#973260 Link tải luận văn miễn phí cho ae Kết nối
Lời nói đầu 2
Chương 1 Kiến thức chuẩn bị 4
Chương 2 Định lí Ramsey 7
§1 Định lí Ramsey trong lí thuyết đồ thị 7
§2 Định lí Ramsey trong tập hợp hữu hạn 15
Chương 3 Ứng dụng của định lí Ramsey 15
§1 Định lí Schur 25
§2 Định lí Erdös–Szekeres 32
§3 Ứng dụng trong giải toán phổ thông 39
Kết luận 51
Tài liệu tham khảo 52
LỜI NÓI ĐẦU
Năm 1928, nhà toán học người Anh Frank Plumpton Ramsey đã công bố kết quả
chứng minh của ông trên tạp chí “On a Proplem of Formal logic” trong đó ông đã
chứng minh định lí”Giả sử họ  r S được phân hoạch thành hai họ các tập
hợp Avà B , p và q là hai số nguyên sao cho r  p, q  s . Khi ấy tồn tại số nguyên
nhỏ nhất R p, q, r chỉ phụ thuộc vào các số p, q, r mà không phụ thuộc vào tập
S , sao cho nếu s  R p, q, r thì tồn tại một tập P gồm p phần tử của S , mà tất
cả các tập con r phần tử của P đều thuộc A, hay tồn tại một tập Q gồm q phần
tử của S , mà tất cả các tập con r phần tử của Q đều thuộc B ”. Định lí trên sau
này được gọi là Định lý Ramsey. Định lí trên đã mở ra một cách tiếp cận mới về
các bài toán tổ hợp nay được gọi là lý thuyết Ramsey.
Trong luận văn này tui sẽ giới thiệu một số kết quả quan trọng trong lý thuyết
Ramsey và một số ứng dụng của lí thuyết này.
Năm 1916 Issai Schur đã chứng minh rằng “Cho r là số tự nhiên, r 1. Khi đó tồn
tại một số tự nhiên S(r) sao cho N  S(r) , tập số {1,2,…,N} được tô bởi r màu
luôn tồn tại ba số x,y,z có cùng màu sao cho x  y  z ”. Kết quả cơ bản này đã
được tổng quát hóa bởi Richard Rado vào năm 1933.
Định lý Van der Waerden đã được chứng minh vào năm 1927, một năm sớm hơn
so với chứng minh của Ramsey. Van der Waerden đã chứng minh rằng “Cho k,r
là số tự nhiên k,r 1. Khi đó tồn tại một số tự nhiên W(k,r) sao cho
N  W(k,r), tập số {1,2,…, W(k,r)} được tô bởi r màu luôn tồn tại k số được
tô cùng màu lập thành một cấp số cộng”.
Năm 1935, Paul Erdös và György Szekeresđã phát biểu giả thuyết (Erdös–
Szekeres, 1935) “ Với mỗi số tự nhiên n  3, mọi tập có tối thiểu N n  2n2 1
điểm trên mặt phẳng ở vị trí tổng quát, đều chứa n điểm là đỉnh của một đa giác
lồi n cạnh.”
Các kết quả trên có thể được chứng minh độc lập với định lý Ramsey, tuy nhiên
sau khi Ramsey công bố kết quả chứng minh của mình thì các bài toán trên đã
được chứng minh lại theo cách ngắn gọn hơn nhờ áp dụng định lý Ramsey.
Luận văn được chia làm ba chương
Chương I Kiến thức chuẩn bị
Chương II Định lý Ramsey
Chương III Ứng dụng của định lý Ramsey.
Luận văn được hoàn thành dưới sự hướng dẫn tận tình của PGS.TS. Tạ Duy
Phượng, Viện Toán học – Viện Khoa học và Công nghệ Việt Nam. Em xin bày tỏ
lòng biết ơn sâu sắc nhất đối với Thầy.
tui xin được Thank khoa Toán, khoa Sau Đại học trường Đại học Khoa học Tự
nhiên, Đại học Quốc gia Hà Nội đã quan tâm giúp đỡ, tạo điều kiện thuận lợi cho
tui thực hiện kế hoạch học tập.
CHƯƠNG 1 KIẾN THỨC CHUẨN BỊ
§1.1 Một số khái niệm cơ bản của lí thuyết đồ thị
Định nghĩa 1.1.1Đồ thị được hiểu là một bộ hai tập hợp hữu hạn : tập hợp đỉnh và
tập hợp cạnh nối các đỉnh này với nhau.
Định nghĩa 1.1.2Mộtđồ thị n đỉnh được gọi là đồ thị đầy đủ nếu hai đỉnh bất kì của
nó có đúng một cạnh nối.
Một đồ thị đầy đủ n đỉnh kí hiệu là Kn .
Định nghĩa 1.1.3 Một đồ thị gọi được là đồ thị đều bậc t nếu mỗi đỉnh của đồ thị G
có bậc là t.
Định nghĩa 1.1.4 Một đồ thị n đỉnh gọi là đồ thị hai màu nếu các cạnh của nó
được tô bởi hai màu xanh hay đỏ.
Định nghĩa 1.1.5 Một đồ thị n đỉnh gọi là đồ thị r màu nếu các cạnh của nó được
tô bởi một trong r màu k1,k2,...,kr .
§1.2 Nguyên lí Dirichlet
Định lí Ramsey là một cách mở rộng của Nguyên lí chuồng chim bồ câu (Nguyên lí
Dirichlet): Một tập gồm s phần tử được chia thành n các tập con phân biệt. Nếu
s  n thì tồn tại ít nhất một tập con chứa nhiều hơn một phần tử.
Nguyên lí Dirichlet được dùng để giải bài toán sau.
Bài toán 1.2.1
Sáu điểm được nối với nhau bởi các đoạn thẳng tô màu đỏ hay xanh. Chứng minh
rằng tìm được một tam giác đơn sắc, nghĩa là tam giác có ba cạnh cùng có màu đỏ
hay màu xanh.
Link Download bản DOC
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link tải, không dùng IDM để tải:

Bấm vào đây để đăng nhập và xem link!
Hình đại diện của thành viên
By nguyenvannay14125
Kết nối đề xuất:
Learn Synonym
Advertisement