Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Đồ thị
Nội dung xem thử
Mô tả chi tiết
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
---------------
Nguyễn Thị Kim Ngân
ĐỒ THỊ
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên, năm 2015
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
---------------
Nguyễn Thị Kim Ngân
ĐỒ THỊ
Chuyên ngành: Phương pháp toán sơ cấp
Mã số: 60.46.01.13
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS.TS. ĐÀM VĂN NHỈ
Thái Nguyên, năm 2015
i
Mục lục
Mở đầu 1
1 Một số khái niệm cơ bản 3
1.1 Tập hợp và quan hệ . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Tập hợp và phép toán . . . . . . . . . . . . . . . . 3
1.1.2 Quan hệ tương đương . . . . . . . . . . . . . . . . 4
1.2 Đồ thị và đường đi . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Khái niệm đồ thị . . . . . . . . . . . . . . . . . . 5
1.2.2 Đường đi và chu trình . . . . . . . . . . . . . . . 6
1.2.3 Bậc của đỉnh và tính liên thông của đồ thị . . . . . 7
1.3 Đồ thị con và sự đẳng hình . . . . . . . . . . . . . . . . . 12
1.3.1 Đồ thị con và đồ thị riêng . . . . . . . . . . . . . 12
1.3.2 Sự đẳng hình của các đồ thị . . . . . . . . . . . . 12
1.4 Một vài mô hình đồ thị . . . . . . . . . . . . . . . . . . . 13
1.4.1 Lấn tổ trong sinh học . . . . . . . . . . . . . . . . 13
1.4.2 Thi đấu vòng tròn . . . . . . . . . . . . . . . . . . 14
1.4.3 Bài toán đường đi . . . . . . . . . . . . . . . . . . 14
1.5 Chu trình Euler và chu trình Hamilton . . . . . . . . . . . 15
1.5.1 Chu trình Euler . . . . . . . . . . . . . . . . . . . 15
1.5.2 Chu trình Hamilton . . . . . . . . . . . . . . . . . 17
1.6 Tập ổn định . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.6.1 Tập ổn định trong, tập ổn định ngoài . . . . . . . . 18
1.6.2 Tập nhân của đồ thị . . . . . . . . . . . . . . . . . 19
1.7 Chu số và Sắc số . . . . . . . . . . . . . . . . . . . . . . 20
1.7.1 Chu số của đồ thị . . . . . . . . . . . . . . . . . . 20
1.7.2 Sắc số của đồ thị . . . . . . . . . . . . . . . . . . 23
ii
2 Ứng dụng của lý thuyết đồ thị 25
2.1 Phương pháp đồ thị . . . . . . . . . . . . . . . . . . . . . 25
2.2 Ví dụ vận dụng . . . . . . . . . . . . . . . . . . . . . . . 26
Kết luận 38
Tài liệu tham khảo 39