Bài giảng Lý thuyết đồ thị: Chương 0 - Giới thiệu môn học

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PPT | Số trang:12

Thêm vào BST

Báo xấu

106
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Lý thuyết đồ thị: Chương 0 - Giới thiệu môn học sau đây được biên soạn nhằm giúp cho các bạn nắm bắt được những thông tin tổng quan về môn học như hình thức thi, tài liệu tham khảo,... Mời các bạn tham khảo bài giảng để hiểu rõ hơn về môn học này.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Lý thuyết đồ thị: Chương 0 - Giới thiệu môn học

LÝ THUYẾT ĐỒ THỊ
Giới thiệu môn học
Bài toán 7 cái cầu ở TP Konigsberg A B D Graph Theory C 11/26/15 3
Bài toán 7 cái cầu ở Tp. Konigsberg A A Mô hình thành B Đồ thị B D D C C Graph Theory 11/26/15 4
Bài toán người chào hàng Travelling Salesman Problem Graph Theory 11/26/15 5
Bài toán tìm đường đi ngắn nhất Finding Shortest Path www.diadiem.com Graph Theory 11/26/15 6
Bài toán giao việc  Giả sử có 6 công việc cần làm: A, B, C, D, E, F  Công việc A: Phải làm trước các công việc B, D  Công việc B: Phải làm trước công việc D  Công việc C: Phải làm sau công việc F  Công việc D: Phải làm sau các công việc A, B, E  Công việc E: Phải làm trước các công việc B, D, F  Hã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 11/26/15 7
Bài toán giao việc (tt) A B C E D F E F C A B D Graph Theory 11/26/15 8
Lị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 quan  Dijsktra, 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ất …  Tham khảo thêm tại website: http://en.wikipedia.org/wiki/Graph_theory Graph Theory 11/26/15 9
Những điều cần biết về môn học
Hình thức thi  Thi trắc nghiệm và tự luận: 100 phút không sử dụng tài liệu Graph Theory 11/26/15 11
Tài liệu tham khảo 1. Tóm tắt bài giảng + Slides: http://fit.hcmup.edu.vn/~hoangth/lythuyetdothi.rar 1. Kenneth H. Rosen. Toán Rời Rạc ứng dụng trong tin học. NXB Khoa Học và Kỹ Thuật, 1998. 2. Nguyễn Đức Nghĩa, Nguyễn Tô Thành. Toán Rời Rạc. NXB Giáo Dục, 1999 Graph Theory 11/26/15 12