Bài giảng Phương pháp tối ưu trong kinh tế: Chương 3 - Nguyễn Phương

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

Thêm vào BST

Báo xấu

6
lượt xem 1
download

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

Bài giảng "Phương pháp tối ưu trong kinh tế - Chương 3: Các bài toán dòng trên mạng" cung cấp cho người đọc các nội dung: Giới thiệu, các khái niệm cơ bản, bài toán đường đi ngắn nhất, bài toán dòng cực đại, hướng dẫn sử dụng Excel để giải. Mời các bạn cùng tham khảo nội dung chi tiết.

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 Phương pháp tối ưu trong kinh tế: Chương 3 - Nguyễn Phương

Chương 3 CÁC BÀI TOÁN DÒNG TRÊN MẠNG NGUYỄN PHƯƠNG Khoa Khoa Học Dữ Liệu trong Kinh Doanh Trường Đại Học Ngân Hàng TPHCM Blog: https://nguyenphuongblog.wordpress.com Email: nguyenphuong0122@gmail.com 1
NỘI DUNG 1. Giới thiệu 2. Các khái niệm cơ bản 3. Bài toán đường đi ngắn nhất 4. Bài toán dòng cực đại 5. Hướng dẫn sử dụng Excel để giải 2
Bài toán tìm đường đi ngắn nhất Finding Shortest Path www.diadiem.com 3
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. 4
Bài toán giao việc (tt) A B C E D F 5
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: 6 http://en.wikipedia.org/wiki/Graph_theory
Các khái niệm cơ bản Định nghĩa : Đồ thị là một cặp G = (V, E), trong đó: b c - V là tập hợp các đỉnh. - E V V là tập hợp các cạnh. a d e Ví dụ: Đồ thị G cho như hình vẽ. - Tập đỉnh V = {a, b , c, d, e}, - Tập các cạnh E = {(a, b), (a, d), (b, c), (b, d ), (b, e), (c, d), (c, e), (d, e)}.
ĐỒ THỊ VÔ HƯỚNG VÀ CÓ HƯỚNG • Định nghĩa : - Đồ thị chỉ chứa các cạnh vô hướng được gọi là đồ thị vô hướng - Đồ thị chỉ chứa các cạnh có hướng được gọi là đồ thị có hướng. Mỗi đồ thị vô hướng có thể biểu diễn bằng một đồ thị có hướng bằng cách thay mỗi cạnh vô hướng bằng hai cạnh có hướng tương ứng.
Vd: đồ thị có hướng. (không có trọng số) b c a e d
Vd: đồ thị có hướng có trọng số b 1 3 c 2 a 6 5 3 2 e d
Vd: đồ thị vô hướng (không có trọng số) b c a e d
Vd: đồ thị vô hướng có trọng số b 5 1 c 3 3 a 2 6 4 e 5 d
ĐỒ THỊ ĐỐI XỨNG • Định nghĩa 1.4 Đồ thị G = (V, E) được gọi là đối xứng nếu: x, y V : (x, y) E (y, x) E. - Các đồ thị vô hướng là đối xứng.
Đồ Thị Đối Xứng Có Hướng b c a d e Đồ Thị Đối Xứng Vô Hướng b c a d e
ĐƠN VÀ ĐA ĐỒ THỊ • Định nghĩa 1.5 - Đồ thị G = (V, E) mà mỗi cặp đỉnh được nối với nhau không quá một cạnh được gọi là đơn đồ thị (gọi tắtlà đồ thị). - Đồ thị có những cặp đỉnh được nối với nhau nhiều hơn một cạnh thì được gọi là đa đồ thị.
Đơn Đồ Thị Vô Hướng a a a a a Đa Đồ Thị Vô Hướng a a a a a
Đơn Đồ Thị Có Hướng b c a d e Đa Đồ Thị Có Hướng b c a d e
TÍNH KỀ TRONG ĐỒ THỊ Đỉnh kề: Nếu (a,b) là một cạnh của đồ thị G thì: - Đỉnh b kề với đỉnh a - Hai đỉnh a và b cùng kề với cạnh (a,b). Hai cạnh kề nhau: là hai cạnh có ít nhất một đỉnh chung.
• Định nghĩa: Đồ thị là một cặp G = (V, F), trong đó: - V là tập hợp các đỉnh, -F:V 2V , được gọi là ánh xạ kề. • Sự tương đương của hai định nghĩa: x, y V : (x, y) E y F(x).
Đường Đi • Độ dài của đường đi: là số cạnh của đường đi đó. • Đường đi đơn: Các đỉnh trên nó khác nhau từng đôi một.