[FONT=Times New Roman]

Mục lục

Lời mở đầu 3

Chương 1 Kiến thức chuẩn bị về đồ thị 5

1.1 Các Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Các Đường, Vòng và Cây . . . . . . . . . . . . . . . . . . . 12

1.3 Các Vòng Hamilton và Chu trình Euler . . . . . . . . . . . . 18

Chương 2 Phương pháp Cơ bản 22

2.1 Phương pháp xác suất . . . . . . . . . . . . . . . . . . . . 22

2.2 Lý thuyết Đồ thị . . . . . . . . . . . . . . . . . . . . . . . 24

2.3 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.4 Lý thuyết Số Tổ hợp . . . . . . . . . . . . . . . . . . . . . 30

2.5 Các cặp rời nhau . . . . . . . . . . . . . . . . . . . . . . . 30

Chương 3 Sự tuyến tính của kỳ vọng 32

3.1 Cơ sở . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.2 Các đồ thị tách . . . . . . . . . . . . . . . . . . . . . . . . 33

3.3 Hai kết quả nhanh . . . . . . . . . . . . . . . . . . . . . . 35

3.4 Vectơ cân bằng . . . . . . . . . . . . . . . . . . . . . . . . 36

3.5 Đèn nhấp nháy . . . . . . . . . . . . . . . . . . . . . . . . 38

Chương 4 Bổ đề Địa phương 40

4.1 Bổ đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

4.2 Tính chất B và các tập đa sắc của các số thực . . . . . . . . . 43

4.3 Cận dưới cho các số Ramsey . . . . . . . . . . . . . . . . . 44

4.4 Một kết quả hình học . . . . . . . . . . . . . . . . . . . . . 46

4.5 Số arboricity tuyến tính của đồ thị . . . . . . . . . . . . . . 47

4.6 Bước chuyển Latin . . . . . . . . . . . . . . . . . . . . . . 52

4.7 Khía cạnh giải thuật . . . . . . . . . . . . . . . . . . . . . 54

Chương 5 Chứng minh Định lý Weierstrass theo Phương pháp xác suất 58

5.1 Một số kiến thức xác suất cơ sở chuẩn bị . . . . . . . . . . . 58

5.2 Định lý xấp xỉ Weierstrass . . . . . . . . . . . . . . . . . . 61

5.3 Một đánh giá về tốc độ hội tụ của đa thức Bernstein . . . . . . 64

Kết luận 68

Tài liệu tham khảo 69