Lý thuyết đồ thị là một ngành khoa học được phát triển từ lâu nhưng lại có nhiều ứng dụng hiện đại. Những ý tưởng cơ bản của nó được đưa ra từ thế kỷ 18 bởi nhà toán học Thụy Sĩ tên là Leonhard Euler. Ông đã dùng đồ thị để giải quyết bài toán 7 chiếc cầu Konigsberg nổi tiếng. Đồ thị được dùng để giải các bài toán trong nhiều lĩnh vực khác nhau như: xác định xem có thực hiện một mạch điện trên một bảng điện phẳng được không, phân biệt hai hợp chất hóa học có cùng công thức phân tử nhưng có cấu trúc khác nhau nhờ đồ thị, xác định xem hai máy tính có được nối với nhau bằng một đường truyền thông hay không thông qua mô hình đồ thị mạng máy tính, giải các bài toán như bài toán tìm đường đi ngắn nhất giữa hai thành phố trong một mạng giao thông (sau khi đã gán các trọng số cho các cạnh của nó). Để tìm hiểu rõ hơn nội dung tài liệu, mời các bạn cùng xem và tham khảo. | TRƯỜNG ĐẠI HỌC QUỐC TẾ HỒNG BÀNG KHOA CÔNG NGHỆ THÔNG TIN _oOo_ LÝ THUYẾT ĐỒ THỊ (Graph Theory) (TÀI LIỆU THAM KHẢO) LÊ VĂN HẠNH MỤC LỤC 1 ĐẠI CƯƠNG VỀ ĐỒ THỊ (GRAPH) . KHÁI NIỆM . Định nghĩa . Biểu diễn đồ thị . Đồ thị có hướng và đồ thị vô hướng . Đơn đồ thị (simple graph), đa đồ thị (Multigraph) . Một số dạng đơn đồ thị đặc biệt . Bậc của một đỉnh (degree) . MỘT SỐ ỨNG DỤNG CỦA CÁC ĐỒ THỊ ĐẶC BIỆT . Các mạng cục bộ (LAN) . Xử lý song song . ĐƯỜNG ĐI, CHU TRÌNH VÀ LIÊN THÔNG . Đường đi . Chu trình . Liên thông . ĐỒ THỊ CON VÀ ĐỒ THỊ RIÊNG . Định nghĩa đồ thị con . Định nghĩa đồ thị riêng . SỰ ĐẲNG HÌNH . BÀI TẬP . CÂU HỎI ÔN TẬP 1 1 1 2 2 2 2 5 6 6 6 8 8 8 8 9 9 10 10 11 14 2 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ 15 . 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 (cung) . Danh sách kề . TÌM KIẾM TRÊN ĐỒ THỊ . Tìm kiếm theo chiều sâu trên đồ thị (Depth First Search) . Tìm kiếm theo chiều rộng trên đồ thị (Breadth First Search) . Ứng dụng DFS/BFS trong kiểm tra tính liên thông và tìm đường đi . BÀI TẬP . CÂU HỎI ÔN TẬP 3 ĐỒ THỊ EULER ĐỒ THỊ HAMILTON . ĐƯỜNG ĐI EULER VÀ ĐỒ THỊ EULER . Giới thiệu . Định nghĩa . Ví dụ . Định lý Euler . Xác định chu trình Euler bằng thuật toán Flor . Thuật toán tìm chu trình Euler bằng cách sử dụng cấu trúc Stack . ĐƯỜNG ĐI HAMILTON VÀ ĐỒ THỊ HAMILTON . Giới thiệu . Đồ thị Hamilton . Xác định đường đi và đồ thị Hamilton . Một số ứng dụng của đồ thị Hamilton . BÀI TẬP 4 BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT 15 15 16 17 18 18 23 28 30 30 32 32 32 32 32 33 33 34 37 37 37 38 40 42 46 . CÁC KHÁI NIỆM . THUẬT TOÁN DIJKSTRA . Công dụng . Cách thực hiện . Ví dụ . THUẬT TOÁN FLOYD . Công dụng . Thuật toán Floyd . Ví dụ . BÀI TẬP 5 ĐỒ THỊ .
