LÝ THUYẾT ĐỒ THỊ
Giảng viên: PGS.TS. Hoàng Chí Thành
Trường Đại học Khoa học Tự nhiên, ĐHQG HN
2/63
MỞ ĐẦU
- Lý thuyết Đồ thị là một trong những ngành khoa
học ra đời khá sớm.
- Lý thuyết Đồ thị giúp mô tả hình học và giải quyết
nhiều bài toán thực tế phức tạp liên quan đến các khái
niệm như: đường đi, chu trình, tập ổn định, chu số,
sắc số, duyệt đồ thị, đường đi ngắn nhất, tâm đồ thị,
luồng vận tải, đồ thị phẳng, cây bao trùm, cây biểu
thức, cây mã tối ưu …bằng các thuật toán ngắn gọn
và lý thú.
- Lý thuyết Đồ thị đã gắn kết nhiều ngành khoa học
với nhau.
3/63
MỞ ĐẦU (tiếp)
Bài giảng điện tử “Lý thuyết Đồ thị” này bao gồm:
- 11 chương
- phân thành 20 bài học
trình bày những vấn đề cốt lõi nhất của lý thuyết đồ
thị cùng các thuật toán tiêu biểu; giúp người học có
thể cài đặt trên máy tính và ứng dụng trong thực tế.
4/63
CHƯƠNG 1
ĐẠI CƯƠNG VỀ ĐỒ THỊ
5/63
NỘI DUNG
Các khái niệm về đồ thị
Biểu diễn đồ thị trong máy tính
Một số tính chất về đường đi trên đồ thị
Bậc của đỉnh và tính liên thông