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

Bài giảng Lý thuyết đồ thị: Chương 0 do Nguyễn Trần Phi Phượng biên soạn nêu lên bài toán 7 cái cầu ở TP Königsberg; lịch sử của lý thuyết đồ thị; ứng dụng của đồ thị. Mời các bạn tham khảo bài giảng để bổ sung thêm kiến thức về lĩnh vực này.
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết đồ thị: Chương 0 - Nguyễn Trần Phi Phượng LÝ THUYẾT ĐỒ THỊ GV: Nguyễn Trần Phi Phượng Bài toán 7 cái cầu ở TP Königsberg A B D C 18/02/2011 Lý thuyết đồ thị 2 Bài toá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 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 toá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 toá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: http://en.wikipedia.org/wiki/Graph_theory 18/02/2011 Lý thuyết đồ thị 4 Ứng dụng của đồ thị Đồ thị được sử dụng để giải các bài toá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 toán lập lịch, thời khóa biểu,… 18/02/2011 Lý thuyết đồ thị 5 Tài liệu tham khảo 1. Keneth – HH Rosen, Toá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, Toá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