Thạc Sĩ Số Ramsey

Mục lục
1 Lý thyết đồ thị 6
1.1 Các khái niệm cơ bản . 6
1.1.1 Đồ thị có hướng-Đồ thị vô hướng . 7
1.1.2 Hành trình, đường, chu trình, vết và mạch 10
1.1.3 Tính liên thông 14
1.1.4 Cây . 15
1.2 Một vài đồ thị đặc biệt 17
1.2.1 Đồ Thị Euler 17
1.2.2 Đồ thị Hamilton 20
1.2.3 Đồ thị phẳng 22
1.3 Bài toán tô màu 25
1.3.1 Định lý bốn màu . 28
1.3.2 Tô màu đỉnh 29
1.3.3 Tô màu cạnh 30
1.3.4 Một vài bài toán vận dụng 30
2 Lý thuyết số Ramsey 33
2.1 Nguyên lý Dirichlet 33
2.1.1 Nguyên lý lồng-chim 33
12
2.1.2 Một vài ví dụ ứng dụng 34
2.2 Khái niệm số Ramsey . 43
2.2.1 Bậc của đỉnh đồ thị 43
2.2.2 Số Ramsey và số chặn . 44
2.3 Một vài vận dụng . 52
2.3.1 Lý thuyết Ramsey trong Hình học 52
2.3.2 Tồn tại tam giác cùng màu 55Lời nói đầu
Bài toán sử dụng k màu để tô dãy số nguyên dương từ 1 đến n với n
đủ lớn đạt được dãy số cùng màu u 1 , u 2 , . , u r thỏa mãn u r =
rư1
P
i=1
u i đã
được I. Schur chứng minh vào năm 1916. Kết quả ấy được coi như viên
gạch đầu tiên để dẫn đến định lý tổng quát được Frank Ramsey (1902-
1930) chứng minh vào năm 1928. Kết quả của F. Ramsey với nhiều dạng
mở rộng đã được ứng dụng không chỉ trong tổ hợp, đồ thị mà còn trong
nhiều lĩnh vực khác chẳng hạn như Đại số, Hình học, Lý thuyết tập
hợp,v.v . Vậy, bài toán đặt ra bởi F. Ramsey là gì?
Ramsey xét bài toán chia tập hợp các cạnh của một đồ thị đầy đủ vào
hai ngăn kéo bằng cách tô màu tất cả các cạnh đồ thị bởi hai màu đen
và trắng. Ông khẳng định rằng, với mỗi cặp số nguyên dương p và q
luôn tồn tại một số nguyên dương n sao cho với mọi cách tô các cạnh
của đồ thị đầy đủ K n bởi hai màu nói trên hoặc ta sẽ được một đồ thị
đầy đủ K p màu đen hoặc một đồ thị K q màu trắng. Số nguyên nhỏ nhất
n ở đây thường được ký hiệu bởi R(p, q) hoặc N(p, q). Chỉ trong những
trường hợp đặc biệt hoặc giá trị nhỏ của số p, q ta có thể xác định chính
xác giá trị N(p, q). Trong phần lớn các trường hợp khác ta chỉ có thể
đưa ra cận trên hoặc cận dưới của N(p, q) mà thôi.
Vấn đề tìm hiểu số Ramsey và vận dụng chúng trong công việc giảng
34
dạy, dạy học sinh chuyên toán và tự đào tạo là cần thiết. Do vậy, chúng
tôi đã tập trung nghiên cứu lý thuyết đồ thị, nguyên lý Dirichlet và lý
thuyết Ramsey trong luận văn của mình.
Luận văn được chia ra làm 2 chương.
Chương 1 tập trung trình bày về lý thuyết đồ thị gồm 3 mục. Mục
1.1 tập trung trình bày những khái niệm cơ bản của lý thuyết đồ thị.
Mục 1.2 được dành để trình bày về những đồ thị hay tính chất đặc biệt
như Đồ thị Euler, Đồ thị Hamilton. Mục 1.3 được dành để giới thiệu bài
toán tô màu như: tô màu đỉnh, tô màu cạnh, tô màu đồ thị phẳng.
Chương 2 tập trung trình bày về nguyên lý Dirichlet và lý thuyết
Ramsey gồm 3 mục. Mục 2.1 tập trung trình bày nguyên lý Dirichlet
và một vài ví dụ áp dụng. Đây là kỹ thuật để chứng minh một vài kết
quả trong lý thuyết Ramsey. Mục 2.2 được dành để trình bày lý thuyết
Ramsey. Chúng tôi cũng đã chứng minh một vài số chặn trên hoặc chặn
dưới của số N(p, q). Mục 2.3 được dành để giới thiệu một vài mở rộng
và xét bài toán Ramsey trong hình học.
Tác giả xin bày tỏ lòng kính trọng và biết ơn chân thành đến người
thầy, người hướng dẫn khoa học PGS. TS. Đàm Văn Nhỉ về sự giúp đỡ
chu đáo, chỉ bảo tận tâm của thầy trong suốt quá trình hoàn thành luận
văn.
Trong quá trình học tập, nghiên cứu và hoàn thành bản luận văn,
tác giả đã nhận được sự quan tâm giúp đỡ của các thầy, cô giáo, cán
bộ nhân viên của Phòng đào tạo sau đại học và quan hệ quốc tế trường
Đại học khoa học - Đại học Thái Nguyên.5
Tác giả xin chân thành cảm ơn tác giả Kỷ yếu hội thảo khoa học
các chuyên đề toán học bồi dưỡng học sinh giỏi khu vực duyên hải Nam
Trung bộ và Tây nguyên và Bồi dưỡng học sinh giỏi Toán tổ hợp - rời
rạc nhà xuất bản Đại học quốc gia Hà Nội.
Thái Nguyên ngày 15 tháng 04 năm 2015
Lưu Ngọc Hoàn