Bài giảng Lý thuyết đồ thị - Giới thiệu môn học - Nguyễn Trần Phi Phượng

LÝ THUYẾT ĐỒ THỊ
GV: Nguyễn Trần Phi Phượng
218/02/2011
Bài toán 7 cái cầu ở TP Königsberg
Lý thuyết đồ thị
A
B
C
D
318/02/2011 Lý thuyết đồ thị
A
B
C
D
Bài toán 7 cái cầu ở TP Königsberg
A
B
C
D
Mô hình thành
Đồ thị
418/02/2011
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:
Lý thuyết đồ thị
518/02/2011
Ứ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,
Lý thuyết đồ thị
618/02/2011
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.
Lý thuyết đồ thị