Lý thuyết đồ thị là một lĩnh vực đã có từ lâu và có nhiều ứng dụng hiện đại. Những tư tưởng cơ bản của lý thuyết đồ thị được đề xuất vào những năm đầu của thế kỷ 18 bởi nhà toán học lỗi lạc người Thuỵ Sĩ Leonhard Euler. Chính ông là người đã sử dụng đồ thị để giải bài toán nổi tiếng về các cây cầu ở thành phố Konigsberg.
Đồ thị được sử dụng để giải các bài toán trong nhiều lĩnh vực khác nhau. Chẳng hạn, đồ thị có thể sử dụng để xác định các mạch vòng trong vấn đề giải tích mạch điện. Chúng ta có thể phân biệt các hợp chất hoá học hữu cơ khác nhau với cùng công thức phân tử nhưng khác nhau về cấu trúc phân tử nhờ đồ thị. Chúng ta có thể xác định hai máy tính trong mạng có thể trao đổi thông tin được với nhau hay không nhờ mô hình đồ thị của mạng máy tính. Đồ thị có trọng số trên các cạnh có thể sử dụng để giải các bài toán như: Tìm đường đi ngắn nhất giữa hai thành phố trong mạng giao thông…Chúng ta còn sử dụng đồ thị để giải các bài toán về lập lịch, thời khoá biểu, phân bố tần số cho các trạm phát thanh và truyền hình…
Mục lục:
Lời nói đầu
Chương 1: Các khái niệm cơ bản của lý thuyết đồ thị
Định nghĩa đồ thị
Các thuật ngữ cơ bản
Đường đi. Chu trình. Đồ thị liên thông
Một số dạng đồ thị đặc biệt
Chương 2: Biểu diễn đồ thị trên máy tính
Ma trận kề. Ma trận trọng số
Danh sách cạnh
Danh sách kề
Chương 3: Các thuật toán tìm kiếm trên đồ thị và ứng dụng
Tìm kiếm theo chiều sâu trên đồ thị
Tìm kiếm theo chiều rộng trên đồ thị
Tìm đường đi và kiểm tra tính liên thông
Bài tập chương 3
Chương 4: Đồ thị Euler và đồ thị Hamilton
Đồ thị Euler
Đồ thị Hamilton
Bài tập chương 4
Chương 5: Cây và khung của đồ thị
Cây và các tính chất cơ bản của cây
Cây khung của đồ thị
Xây dựng tập các chu trình cơ bản của đồ thị
Bài toán cây khung nhỏ nhất
Bài tập chương 5
Chương 6: Bài toán đường đi ngắn nhất
Các khái niệm mở đầu
Đường đi ngắn nhất xuất phát từ một đỉnh
Trường hợp ma trận trong số không âm – Thuật toán Dijkstra
Đường đi trong đồ thị không có chu trình
Đường đi ngắn nhất giữa tất cả các cặp đỉnh
Bài tập chương 6
Chương 7: Bài toán luồng cực đại trong mạng
Mạng. Luồng trong mạng. Bài toán luồng cực đại
Lát cắt. Đường tăng luồng. Định lý Ford-Fulkerson
Thuật toán tìm luồng cực đại
Một số thuật toán luồng tổng quát
Một số ứng dụng trong tổ hợp
Bài tập chương 7
Phụ lục – một số bài tập khác
Mời bạn đón đọc.