Đề tài “Mô phỏng phương pháp giải một số bài toán về lý thuyết đồ thị trên máy tính” là đề tài nghiên cứu thuộc lĩnh vực đổi mới phương pháp giảng dạy, có phạm vi nghiên cứu rộng và được thực hiện một cách có hệ thống trên cơ sở trải nghiệm nhiều năm, phân tích làm rõ các đặc điểm, đặc thù của các học phần Toán rời rạc thuộc bộ môn KHTN nhằm mục tiêu nâng cao hiệu quả và ý nghĩa của việc dạy và học.

Trong đó, lý thuyết về đồ thị và thuật toán trên đồ thị là một lĩnh vực rộng và phức tạp. Việc hiểu và cài đặt các thuật toán đó đòi hỏi nhiều công sức. Hiện nay, việc truyền đạt kiến thức các thuật toán trên đồ thị cho sinh viên chuyên ngành Công nghệ thông tin gặp nhiều khó khăn. Có rất nhiều lý do: Các thuật toán khó hình dung, việc tổ chức dữ liệu cho nó cũng phức tạp, thời gian giảng dạy trên lớp có hạn, tài liệu tự học còn hạn chế.

Trong đề tài này, chúng tôi xây dựng một phần mềm nhằm mô phỏng hoạt động của các thuật toán trên đồ thị gồm:

- Tìm chu trình Euler

- Tìm đường đi ngắn nhất bằng thuật toán Dijkstra cho đồ thị vô hướng

- Tìm đường đi ngắn nhất bằng thuật toán Floyd cho đồ thị có hướng

- Tìm đường đi ngắn nhất bằng thuật toán Bellman – Ford cho đồ thị có hướng, trọng số có thể âm.

- Tìm cây phủ nhỏ nhất bằng thuật toán Prim

- Tìm cây phủ nhỏ nhất bằng thuật toán Kruskal

- Bài toán luồng cực đại
Các nội dung trên theo phân phối chương trình trong học phần Toán rời rạc đang giảng dạy tại trường với mục đích: Sinh viên có thể nắm bắt cách thức hoạt động của thuật toán, giúp giảng viên giảng dạy về các thuật toán trở nên dễ hiểu, trực quan và dễ dàng truyền đạt đến sinh viên hơn.