Theo Wikipedia
Trong toán học và tin học, lý thuyết đồ thị (tiếng Anh: graph theory) nghiên cứu các tính chất của đồ thị. Một cách không chính thức, đồ thị là một tập các đối tượng được gọi là các đỉnh (hoặc nút) nối với nhau bởi các cạnh (hoặc cung). Cạnh có thể có hướng hoặc vô hướng. Đồ thị thường được vẽ dưới dạng một tập các điểm (các đỉnh nối với nhau bằng các đoạn thẳng (các cạnh).
Đồ thị biểu diễn được rất nhiều cấu trúc, nhiều bài toán thực tế có thể được biểu diễn bằng đồ thị. Ví dụ, cấu trúc liên kết của một website có thể được biểu diễn bằng một đồ thị có hướng như sau: các đỉnh là các trang web hiện có tại website, tồn tại một cạnh có hướng nối từ trang A tới trang B khi và chỉ khi A có chứa 1 liên kết tới B. Do vậy, sự phát triển của các thuật toán xử lý đồ thị là một trong các mối quan tâm chính của khoa học máy tính.
Cấu trúc đồ thị có thể được mở rộng bằng cách gán trọng số cho mỗi cạnh. Có thể sử dụng đồ thị có trọng số để biểu diễn nhiều khái niệm khác nhau. Ví dụ, nếu đồ thị biểu diễn một mạng đường giao thông, các trọng số có thể là độ dài của mỗi con đường. Một cách khác để mở rộng đồ thị cơ bản là quy định hướng cho các cạnh của đồ thị (như đối với các trang web, A liên kết tới B, nhưng B không nhất thiết cũng liên kết tới A). Loại đồ thị này được gọi là đồ thị có hướng. Một đồ thị có hướng với các cạnh có trọng số được gọi là một lưới.
Các lưới có nhiều ứng dụng trong khía cạnh thực tiễn của lý thuyết đồ thị, chẳng hạn, phân tích lưới có thể dùng để mô hình hoá và phân tích mạng lưới giao thông hoặc nhằm "phát hiện" hình dáng của Internet - (Xem thêm các ứng dụng đưới đây. Mặc dù vậy, cũng nên lưu ý rằng trong phân tích lưới, thì định nghĩa của khái niệm "lưới" có thể khác nhau và thường được chỉ ra bằng một đồ thị đơn giản.)
Lý thuyết đồ thị nói riêng, toán rời rạc nói chung là nội dung không thể thiếu trong chương trình đào tạo của kỹ sư ngành CNTT. Học phần này sẽ giúp sinh viên hình thành được kỹ năng giải quyết bài toán một cách tối ưu thông qua các thuật toán kinh điển trong toán học, đặc biệt là các thuật toán tìm đường đi ngắn nhất.
Đã có rất nhiều ứng dụng của lý thuyết này trong các lĩnh vực khác nhau như: bài toán vấn tải, bài toán người du lịch, bài toán tìm đường của gói tin trên Internet, bài toán tối ưu, các bài toán sinh học, di truyền, ...
Cách tốt nhất để làm chủ các thuật toán về đồ thị là cài đặt và chạy thử nó trên một bài tóan cụ thể nào đó. Trong bài viết này, tôi sẽ mang đến cho bạn một số ví dụ cài đặt thuật toán quan trọng trong lý thuyết đồ thị.
Ví dụ cài đặt thuật toán đồ thị:
1. [THUẬT TOÁN ĐỒ THỊ / CODE C++] TÌM SỐ THÀNH PHẦN LIÊN THÔNG CỦA ĐỒ THỊ G
2. [THUẬT TOÁN ĐỒ THỊ / CODE C++] THUẬT TOÁN KRUSKAL TÌM CÂY KHUNG NHỎ NHẤT CỦA ĐỒ THỊ G
3. [THUẬT TOÁN ĐỒ THỊ / CODE C++] THUẬT TOÁN PRIM TÌM CÂY KHUNG NHỎ NHẤT CỦA ĐỒ THỊ G
4. [THUẬT TOÁN ĐỒ THỊ / CODE C++] THUẬT TOÁN DIJKSTRA TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ G
5. [THUẬT TOÁN ĐỒ THỊ / CODE C++] THUẬT TOÁN ELUER - TÌM CHU TRÌNH ELUER TRÊN ĐỒ THỊ G
6. [THUẬT TOÁN ĐỒ THỊ / CODE C++] THUẬT TOÁN HAMILTON - TÌM CHU TRÌNH HAMILTON TRÊN ĐỒ THỊ G
7. [THUẬT TOÁN ĐỒ THỊ / CODE C++] THUẬT TOÁN EULER - TÌM ĐƯỜNG ĐI EULER TRÊN ĐỒ THỊ G (VỚI ĐỒ THỊ NỬA EULER)
8. [THUẬT TOÁN ĐỒ THỊ / CODE C++] THUẬT TOÁN DIJKSTRA - TÌM ĐƯỜNG ĐI NGẮN NHẤT TỪ ĐỈNH D ĐẾN ĐỈNH C TRÊN ĐỒ THỊ G.
9. [C\C++] CÀI ĐẶT THUẬT TOÁN DUYỆT ĐỒ THỊ (DFS, BFS) [LÝ THUYẾT ĐỒ THỊ]
10. [THUẬT TOÁN ĐỒ THỊ / CODE C++] KIỂM TRA TÍNH LIÊN THÔNG CỦA ĐỒ THỊ G
Tài liệu tham khảo:
1. Bài giảng: Toán rời rạc - PTIT [Download]
2. Tài liệu: Giải thuật đồ thị - ĐHQG [Download]
3. Giáo trình: Toán rời rạc [Download]