00 - Giới thiệu

Lý thuyết đồ thị là một nhánh lớn trong toán rời rạc. Khởi phát từ những ý tưởng ban đầu của nhà toán học người Thụy Sỹ Leohard Euler. Năm 1976, ông đã dùng một mô hình đồ thị để giải bài toán bảy cây cầu ở Kognigsberg. Bài toán này cũng với bài toán mã đi tuần (Knight Tour) được xem là những bài toán đầu tiền được giải bằng mô hình đồ thị. 

Sau những phát hiện đầu tiên này, người ta thấy rằng trong thực tế có rất nhiều bài toán tương tự. Đó chính là những bài toán gốm tập những đối tượng và các mối liên quan giữa chúng. Điều này đòi hỏi Toán học phải đặt ra một mô hình toán để biểu diễn chặt chẽ và tổng quát bằng ngôn ngữ ký hiệu --> Lý thuyết đồ thị ra đời.

Rất nhiều bài toán của Lý thuyết đồ thị đã trở nên nổi tiếng và thu hút được sự quan tâm lớn của cộng đồng nghiên cứu như bài toán bốn màu, bài toán đẳng cấu đồ thị, bài toán người đi du lịch, người đưa thư Trung Hoa, đường đi ngắn nhất, luồng cực đại trên mạng, ...

Trong phạm vi chuyên đề này, chúng ta sẽ cùng thảo luận qua các chủ đề chính:

1. Các khái niệm cơ bản về đồ thị

2. Các phương pháp biểu diễn đồ thị trong máy tính

3. Các thuật toán duyệt trên đồ thị

4. Tính liên thông của đồ thị

5. Ứng dụng của các thuật toán duyệt đồ thị

6. Đường đi ngắn nhất trên đồ thị

7. Cây khung nhỏ nhất

8. Đồ thị Euler và đồ thị Hamilton

9. Luồng cực đại và ứng dụng