forever_yeunguoitrongimlang
New Member
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 2n2 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.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tả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 2n2 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.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links