Lý thuyết đồ thị là một trong những môn học căn bản và quan trọng trong lĩnh vực ứng dụng toán trong tin học. Trong một vài trường hợp Lý thuyết đồ thị còn được coi như là một thành phần của Toán rời rạc. Kiến thức về Lý thuyết đồ thị có ứng dụng đa dạng trong cuộc sống. Nó cung cấp các công cụ, phương pháp, thuật toán và hỗ trợ chúng ta xây dựng các mô hình nhằm giải quyết nhiều bài toán thực tiễn. Lý thuyết đồ thị hiện là môn học bắt buộc trong chương trình đào tạo các ngành Công nghệ thông tin, Toán tin, Khoa học máy tính, …

Sau khi học xong môn Lý thuyết đồ thị, sinh viên sẽ có kiến thức để hiểu và vận dụng được những qui trình, giải thuật trên đồ thị, có kỹ năng trong việc lập trình để giải quyết các bài toán trên đồ thị. Một năng lực quan trọng khác là sinh viên sẽ biết sử dụng đồ thị như một công cụ mô hình hóa trong việc mô phỏng các vấn đề thực tế để chuyển thành các bài toán có thể giải được trên đồ thị.

Nội dung giáo trình gồm có 8 chương, bao quát hầu hết các vấn đề cốt lõi của môn học. Giáo trình không đi sâu vào các vấn đề lý thuyết mà tập trung vào các giải thuật cũng như tính ứng dụng của môn học. Cuối mỗi chương đều có phần bài tập để sinh viên có thể tự kiểm tra kiến thức của mình. Các thuật toán trong giáo trình hầu hết được trình bày dưới dạng mã giả. Phần phụ lục có mã nguồn của một số thuật toán.

Với kinh nghiệm nhiều năm giảng dạy môn Lý thuyết đồ thị tại trường đại học, chúng tôi đã cố gắng đem những kiến thức và kinh nghiệm của mình để trình bày các vấn đề nêu trong giáo trình một cách rõ ràng và đơn giản nhất. Tuy nhiên, cũng không tránh khỏi những thiếu sót. Trong quá trình biên soạn giáo trình này chúng tôi đã nhận được nhiều lời động viên và góp ý của các đồng nghiệp. Chúng tôi xin chân thành cám ơn và mong muốn tiếp tục nhận được ý kiến đóng góp của các giảng viên và các bạn sinh viên để giáo trình ngày càng hoàn thiện hơn.

Mọi ý kiến đóng góp xin vui lòng gửi theo địa chỉ email:

sondt@fit.hcmute.edu.vn

Đặng Trường Sơn – Lê Văn Vinh