Bài giảng Lý thuyết đồ thị - Chương mở đầu - Nguyễn Trần Phi Phượng

Nội dung text: Bài giảng Lý thuyết đồ thị - Chương mở đầu - Nguyễn Trần Phi Phượng

1. LÝ THUYẾT ĐỒ THỊ GV: Nguyễn Trần Phi Phượng
2. Bài tốn 7 cái cầu ở TP Kưnigsberg A B D C 18/02/2011 Lý thuyết đồ thị 2
3. Bài tốn 7 cái cầu ở TP Kưnigsberg A A Mơ hình thành Đồ thị B B D D C C 18/02/2011 Lý thuyết đồ thị 3
4. Lịch sử của lý thuyết đồ thị Một trong những kết quả đầu tiên trong lý thuyết đồ thị xuất hiện trong bài báo của Leonhard Euler về Bảy cây cầu ở Kưnigsberg, xuất bản năm 1736. Năm 1852, Francis Guthrie đưa ra bài tốn bốn màu: chỉ với bốn màu cĩ thể tơ màu một bản đồ bất kỳ sao cho khơng cĩ hai nước nào cùng biên giới được tơ cùng màu. Bài tốn này được xem như đã khai sinh ra lý thuyết đồ thị, và chỉ được giải sau một thế kỷ vào năm 1976 bởi Kenneth Appel và Wolfgang Haken. Tham khảo thêm tại website: 18/02/2011 Lý thuyết đồ thị 4
5. Ứng dụng của đồ thị Đồ thị được sử dụng để giải các bài tốn trong nhiều lĩnh vực khác nhau: - Xác định các mạch vịng trong vấn đề giải tích mạch điện. - Phân biệt các hợp chất hĩa học hữu cơ khác nhau với cùng cơng thức phân tử nhưng khác nhau về cấu trúc phân tử. - Xác định xem hai máy tính trong mạng cĩ thể trao đổi thơng tin được với nhau hay khơng nhờ mơ hình đồ thị của mạng máy tính. - Tìm đường đi ngắn nhất giữa hai thành phố nhờ đồ thị cĩ trọng số. - Giải các bài tốn lập lịch, thời khĩa biểu, 18/02/2011 Lý thuyết đồ thị 5
6. Tài liệu tham khảo 1. Keneth – HH Rosen, Tốn học rời rạc và ứng dụng trong tin học, NXB Khoa học và kỹ thuật, 1997. 2. Nguyễn Đức Nghĩa – Nguyễn Tơ Thành, Tốn rời rạc, NXB Đại học Quốc gia Hà nội, 2003. 3. Nguyễn Cam – Chu Đức Khánh, Lý thuyết đồ thị, NXB Trẻ, 1998. 18/02/2011 Lý thuyết đồ thị 6