Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã có từ lâu đời 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 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 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ái cầu ở thành phố Konigsberg. Từ đó lý thuyết đồ thị ngày càng khẳng định được vị trí quan trọng trong việc áp dụng để giải quyết các bài toán thực tế nhờ vào việc tìm ra ngày càng nhiều các định lý, công thức và thuật toán. Lý thuyết đồ thị không những có nhiều ứng dụng trong thực tế mà còn là công cụ đắc lực cho ngành công nghệ thông tin. Nó giúp cho chúng ta mô tả một cách dễ dàng các bài toán phức tạp cụ thể, để từ đó ta có thể mã hoá các bài toán đó vào máy tính. Ngoài r a lý thuyết đồ 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. Hiện nay có rất nhiều tài liệu, sách, giáo trình đã viết về lý thuyết đồ thị với những nội dung, đầy đủ giúp cho những người muốn nghiên cứu về lý thuyết đồ thị tham khảo. Tuy nhiên hầu hết các tài liệu đều chỉ nghiên cứu về lý thuyết và xây dựng các thuật toán chung cho các bài toán mà chưa có nhiều tài liệu viết về các ứng dụng các thuật toán để giải các bài toán ứng dụng cụ thể.