Lý thuyết đô thị - Bài toán 7 cái cầu ở TP Konigsberg

LÝ THUYẾT ĐỒ THỊGiới thiệu môn họcBài toán 7 cái cầu ở TP Konigsberg*Graph Theory*ABCDBài toán 7 cái cầu ở Tp. Konigsberg*Graph Theory*ABCDABDCMô hình thànhĐồ thị*Graph Theory*Bài toán người chào hàngTravelling Salesman ProblemBài toán tìm đường đi ngắn nhấtFinding Shortest Path*Graph Theory*www.diadiem.comBài toán giao việcGiả sử có 6 công việc cần làm: A, B, C, D, E, FCông việc A: Phải làm trước các công việc B, DCông việc B: Phải làm trước công việc DCông việc C: Phải làm sau công việc FCông việc D: Phải làm sau các công việc A, B, ECông việc E: Phải làm trước các công việc B, D, FHãy tìm một thứ tự thực hiện các công việc sao cho thỏa mãn các yêu cầu trên.*Graph Theory*Bài toán giao việc (tt)*Graph Theory*ABCDEFEFCABDLịch sử của lý thuyết đồ thịLý thuyết đồ thị được khởi xướng vào năm 1736 bởi Leonard Euler khi ông viết một bài báo về bài toán 7 cái cầu ở thành phố Konirgsberg.Một số nhà khoa học và các kết quả quan trọng:Hamilton: K/n đồ thị Hamilton và các bài toán liên quanDijsktra, Ployd, Ford, Bellman: các thuật toán tìm đường đi ngắn nhất.Prim, Kruscal: các thuật toán tìm cây khung nhỏ nhấtTham khảo thêm tại website: Theory*Những điều cần biết về môn họcHình thức thiThi trắc nghiệm và tự luận: 100 phút không sử dụng tài liệu*Graph Theory*Tài liệu tham khảoTóm tắt bài giảng + Slides: H. Rosen. Toán Rời Rạc ứng dụng trong tin học. NXB Khoa Học và Kỹ Thuật, 1998.Nguyễn Đức Nghĩa, Nguyễn Tô Thành. Toán Rời Rạc. NXB Giáo Dục, 1999*Graph Theory*