Giáo Trình Lý Thuyết Đồ Thị

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.