Đề tài Nghiên cứu một số vấn đề của lý thuyết đồ thị ứng dụng trong giải quyết một số bài toán thực tế

Tiêu đề: NGHIÊN CỨU MỘT SỐ VẤN ĐỀ CỦA LÝ THUYẾT ĐỒ THỊ ỨNG DỤNG TRONG GIẢI QUYẾT MỘT SỐ BÀI TOÁN THỰC TẾ Các tác giả: GVHD : T.S DƯƠNG ANH ĐỨC SVTH : TẠ TRƯỜNG ĐỨC ANH - NGUYỄN NHẬT QUỲNH Tóm tắc: Lý thuyết đồ thị là ngành khoa học xuất hiệ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ĩ Leonhard Euler. Ông đã dùng đồ thị để giải quyết bài toán cây cầu Konigsberg nổi tiếng. Từ đó lý thuyết đồ thị ngày càng khẳng định được vị trí quan trọng của mình trong việc áp dụng để giải các bài toán thực tế nhờ vào việc tìm ra ngày càng nhiều của các định lý, công thức và thuật toán. Một bộ phận quan trọng của lý thuyết đồ thị là dạng bài toán luồng trên mạng, xuất hiện từ những nghiên cứu của Gustav Kirchhoff, và được những nhà nghiên cứu tiên phong như Lester Ford và Ray Fulkerson Phát triển thành một lĩnh vực khoa học độc lập. Bài toán này có nhiều biến thể như: bài toán luồng có chi phí cực tiểu, bài toán đường đi ngắn nhất, bài toán luồng cực đại, bài toán vận chuyển, bài toán luồng tổng quát, bài toán luồng nhiều mặt hàng Với sự xuất hiện ngày càng nhiều của các hệ thống mạng như: hệ thống mạng điện, mạng sản xuất và phân phối hàng hóa, mạng giao thông , và phổ biến nhất hiện nay là mạng internet đã làm nảy sinh ra nhu cầu vận chuyển các chất liệu trên các mạng này sao cho đạt hiệu quả cao nhất; chất liệu ở đây có thể là dòng điện, dữ liệu, hàng hóa ; hiệu quả ở đây có thể xét theo tiêu chuẩn về thời gian, độ dài quãng đường, chi phí tiền bạc, mức độ an toàn , bài toán luồng trên mạng ngày càng khẳng định được tính quan trọng của nó trong các ngành khoa học hiện đại. Sự Phát triển mạnh mẽ của ngành Công nghệ thông tin cùng với khả năng tính toán rất nhanh của máy tính đã giúp việc giải quyết các bài toán luồng trên mạng hiệu quả hơn và đem lại nhiều ứng dụng thực tiễn hơn. Với sự hướng dẫn của Tiến sĩ Dương Anh Đức, chúng em đã tập trung thực hiện đề tài “NGHIÊN CỨU MỘT SỐ VẤN ĐỀ CỦA LÝ THUYẾT ĐỒ THỊ ỨNG DỤNG TRONG VIỆC GIẢI QUYẾT BÀI TOÁN THỰC TẾ” nhằm tìm hiểu, thử nghiệm và ứng dụng các thuật toán của bài toán luồng trên mạng, nhất là bài toán luồng có chi phí cực tiểu, dạng tổng quát nhất của bài toán luồng trên mạng, trong đó bao gồm việc Xây dựng ứng dụng Distribution phục vụ cho việc lập kế hoạch giao hàng của nhà phân phối đến các đại lý với chi phí tối thiểu. Luận văn dài 132 trang, chia làm 3 chưỡng