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