BỘ GIÁO DỤC
VÀ ĐÀO TẠO
VIỆN HÀN LÂM KHOA HỌC
VÀ CÔNG NGHỆ VIỆT NAM
HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ
Trần Mỹ Đức
BAO CỦA ĐỒ THỊ NGẪU NHIÊN
LUẬN VĂN THẠC SĨ TOÁN HỌC
Hà Nội - 2023
Mục lục
Lời cam đoan i
Lời cảm ơn ii
Mục lục iv
Danh mục các kí hiệu v
Giới thiệu 1
1 Kiến thức chuẩn bị 3
1.1 Một số kiến thức cơ sở trong Lý thuyết đồ thị . . . . . . 3
1.2 Một số bất đẳng thức xác suất . . . . . . . . . . . . . . . 5
1.2.1 Bất đẳng thức Markov . . . . . . . . . . . . . . . 5
1.2.2 Bất đẳng thức Chebyshev . . . . . . . . . . . . . 5
1.2.3 Bất đẳng thức Chernoff cho phân phối nhị thức . 6
1.3 Một số khái niệm và kết quả được sử dụng . . . . . . . . 6
1.3.1 Khái niệm với xác suất cao . . . . . . . . . . . . . 6
1.3.2 Thuật toán Dijkstra tìm đường đi ngắn nhất . . . 6
1.3.3 Một kết quả của phân phối đều . . . . . . . . . . 11
1.3.4 So sánh giữa phân phối mũ và phân phối đều . . 11
1.3.5 Xấp xỉ Stirling . . . . . . . . . . . . . . . . . . . 11
2 Bao của đồ thị có trọng ngẫu nhiên 12
iii