Đồ án cơ sở Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã có từ lâu đờivà có nhiều ứng dụng hiện tư tưởng cơ bản của lý thuyết đồ thị đươc đề xuất từ những năm đầu của thế kỷ 18 bởi nhà toán học lỗi lạc người Thụy Sĩ Leonhard ông là người đã sử dụng đồ thị để giải bài toán nổi tiếng về các cái cầu ở thàng phố Konigsberg. Đồ thị được sử dụng để giải quyết các bài toán trong nhiều lĩnh vực khác nhau .Chẳng hạn , đồ thị có. | rx Ầ r . Đô án cơ sở Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã có từ lâu đờivà có nhiều ứng dụng hiện tư tưởng cơ bản của lý thuyết đồ thị đươc đề xuất từ những năm đầu của thế kỷ 18 bởi nhà toán học lỗi lạc người Thụy Sĩ Leonhard ông là người đã sử dụng đồ thị để giải bài toán nổi tiếng về các cái cầu ở thàng phố Konigsberg. Đồ thị được sử dụng để giải quyết 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 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ờ đồ ta có thể xác định xem 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 cùng một 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 và phân bố tần số cho các trạm phát thanh và truyền hình. Mục đích ta tìm hiểu là nhằm giới thiệu các khái niệm cơ bản các bài toán ứng dụng quan trọng của lý thuyết đồ thị như bài toán cây khung nhỏ nhất bài toán tìm đường đi ngắn nhất. và những thuật toán để giải quyết chúng đã được trình bày chi tiết cùng với việc phân tích và hướng dẫn cài đặt chương trình trên máy tính. SVTH Nguyễn Công Hiếu_SBD 0041 - Trang 1 - Củng cố và rèn luyện kỹ năng lập trình nhớ lại các thuật toán mà đặc biệt là thuật toán Dijkstra. Chương 1 Lý thuyết về thuật toán tìm đường đi ngắn nhất. Chương 2 Xây dựng thuật toán. Chương 3 Cài đặt thuật toán. SVTH Nguyễn Công Hiếu_SBD 0041 - Trang 2 - Chương I LÝ THUYẾT VỀ THUẬT TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT Các khái niệm cơ bản của lý thuyết đồ thị Định nghĩa đồ thị Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh ta phân biệt các loại đồ thị khác nhau bởi kiểu và số lượng cạnh nối hai đỉnh nào đó
