Lý Thuyết Đồ Thị

LÝ THUYẾT ĐỒ THỊ
Giảng viên: Nguyễn Ngọc Trung
Email: [email protected]
ĐT: 0918 88 75 94
Giới thiệu môn học
Giảng viên: Nguyen Ngoc Trung
[email protected]
Bài toán 7 cái cầu ở TP Konigsberg
3/5/2010
Graph Theory
3
A
B
C
D
Bài toán 7 cái cầu ở Tp. Konigsberg
3/5/2010
Graph Theory
4
A
B
D
C
Mô hình thành
Đồ thị
3/5/2010
Graph Theory
5
Bài toán người chào hàng
Travelling Salesman Problem
Bài toán tìm đường đi ngắn nhất
Finding Shortest Path
3/5/2010
Graph Theory
6
www.diadiem.com
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.

3/5/2010
Graph Theory
7
Bài toán giao việc (tt)
3/5/2010
Graph Theory
8
A
B
C
D
E
F
E
F
C
A
B
D
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
3/5/2010
Graph Theory
9
Những điều cần biết về môn học
Giảng viên: Nguyen Ngoc Trung
[email protected]
Hệ thống điểm
Đồ án môn học:
Làm theo nhóm: (4-6 SV/nhóm)
Hình thức: GV cho đề bài, SV làm ở nhà và nộp vào cuối môn học.
Thi cuối kỳ: 90 phút – không sử dụng tài liệu
Cộng điểm
3/5/2010
Graph Theory
11
Tài liệu tham khảo
Tóm tắt bài giảng + Slides:
http://fit.hcmup.edu.vn/~trungnn/lythuyetdothi/
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.
Nguyễn Đức Nghĩa, Nguyễn Tô Thành. Toán Rời Rạc. NXB Giáo Dục, 1999
3/5/2010
Graph Theory
12