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ế

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ĩLeonhardEuler. Ô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ìmra 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 giaothông , và phổ biến nhất hiện nay là mạng internet đã làm nảy sinh ranhu 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 độantoàn , bài toánluồ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Ế”