›
›

Bài giảng Toán rời rạc - Phần 2: Lý thuyết đồ thị - Một số bài toán luồng tổng quát - Nguyễn Đức Nghĩa

Download
Toán rời rạc – Fall 2005  
NGUYỄN ĐỨC NGHĨA  
Bộ môn KHMT  
Toán rời rạc – Fall 2005  
NGUYỄN ĐỨC NGHĨA  
Bộ môn KHMT  
NỘI DUNG  
Một số bài toán luồng tổng quát  
–Bài toán với nhiều điểm phát và điểm thu  
–Bài toán với hạn chế thông qua ở nút  
Một số ứng dụng trong tổ hợp  
–Bài toán cặp ghép cực đại trong đồ thị hai phía  
–Độ tin cậy của mạng  
Toán rời rạc – Fall 2005  
NGUYỄN ĐỨC NGHĨA  
Bộ môn KHMT  
3
Một số bài toán luồng tổng quát  
Toán rời rạc – Fall 2005  
NGUYỄN ĐỨC NGHĨA  
Bộ môn KHMT  
4
Toán rời rạc – Fall 2005  
NGUYỄN ĐỨC NGHĨA  
Bộ môn KHMT  
M¹ng víi nhiÒu ®iÓm ph¸t vµ ®iÓm thu  
Đa vµo mét ®iÓm ph¸t gi¶ s vµ mét ®iÓm thu gi¶ t vµ c¸c c¹nh nèi s víi tÊt c¶ c¸c  
®iÓm ph¸t vµ c¸c c¹nh nèi c¸c ®iÓm thu víi t.  
Kntq cña cung (s,si) sÏ b»ng ai là lîng ph¸t cña si.  
Kntq cña (ti, t) sÏ bằng bi là lîng thu cña ®iÓm thu ti.  
Bài to¸n dẫn về bài to¸n với 1 điểm ph¸t và một điểm thu.  
s1  
s2  
t1  
t2  
b1  
a1  
t
b2  
a2  
ap  
s
bq  
sp  
tq  
Toán rời rạc – Fall 2005  
NGUYỄN ĐỨC NGHĨA  
Bộ môn KHMT  
6
Toán rời rạc – Fall 2005  
NGUYỄN ĐỨC NGHĨA  
Bộ môn KHMT  
Toán rời rạc – Fall 2005  
NGUYỄN ĐỨC NGHĨA  
Bộ môn KHMT  
Các ứng dụng của bài toán luồng cực đại  
ỨNG DỤNG TRONG TỔ HỢP  
Toán rời rạc – Fall 2005  
NGUYỄN ĐỨC NGHĨA  
Bộ môn KHMT  
9
Bài toán ghép cặp  
(Matching Problems)  
Toán rời rạc – Fall 2005  
NGUYỄN ĐỨC NGHĨA  
Bộ môn KHMT  
10  
Toán rời rạc – Fall 2005  
NGUYỄN ĐỨC NGHĨA  
Bộ môn KHMT  
Toán rời rạc – Fall 2005  
NGUYỄN ĐỨC NGHĨA  
Bộ môn KHMT  
Toán rời rạc – Fall 2005  
NGUYỄN ĐỨC NGHĨA  
Bộ môn KHMT  
Tìm luồng cực đại  
1
2
6
7
s
3
4
5
8
9
t
10  
Giá trị luồng cực đại từ s đến t là 4.  
Cặp ghép cực đại có lực lượng là 4.  
Toán rời rạc – Fall 2005  
NGUYỄN ĐỨC NGHĨA  
Bộ môn KHMT  
14  
Toán rời rạc – Fall 2005  
NGUYỄN ĐỨC NGHĨA  
Bộ môn KHMT  
Toán rời rạc – Fall 2005  
NGUYỄN ĐỨC NGHĨA  
Bộ môn KHMT  
Cặp ghép hoàn hảo (Perfect Matching)  
ĐN. Cặp ghép M E được gọi là hoàn hảo (perfect) nếu mỗi  
đỉnh của đồ thị là đầu mút của đúng 1 cạnh trong M.  
Câu hỏi. Khi nào đồ thị hai phía có cặp ghép hoàn hảo?  
Cấu trúc của đồ thị hai phía có cặp ghép hoàn hảo.  
Rõ ràng ta phải có |X| = |Y|.  
Điều kiện nào là cần nữa?  
Các điều kiện đủ là gì?  
Toán rời rạc – Fall 2005  
NGUYỄN ĐỨC NGHĨA  
Bộ môn KHMT  
17  
Toán rời rạc – Fall 2005  
NGUYỄN ĐỨC NGHĨA  
Bộ môn KHMT  
Toán rời rạc – Fall 2005  
NGUYỄN ĐỨC NGHĨA  
Bộ môn KHMT  
Chứng minh định lý về các đám cưới  
CM. ) Giả sử G khô ng có cặp ghép hoàn hảo.  
Xét bài toán luồng cực đại tương ứng và (A, B) là lát cắt nhỏ nhất trong G'.  
Theo định lý luồng cực đại và lát cắt nhỏ nhất, cap(A, B) < | X |.  
Gọi XA = X A, XB = X B , YA = Y A.  
cap(A, B) = | XB | + | YA |.  
Do lát cắt nhỏ nhất không sử dụng cạnh : (XA) YA. Suy ra:  
|(XA )| | YA | = (| XB | + | YA |) - | XB | = cap(A, B) - | XB | < | X | - | XB | = | XA |.  
Chọn S = XA ta có |(S)| < |S| ?! ■  
1
1
G'  
1'  
A
2'  
XA = {2, 4, 5}  
XB = {1, 3}  
2
1
s
YA = {2', 5'}  
3'  
4'  
1
3
4
(XA) = {2', 5'}  
t
5
1
5'  
Toán rời rạc – Fall 2005  
NGUYỄN ĐỨC NGHĨA  
Bộ môn KHMT  
20  
Tải về để xem bản đầy đủ
ppt 53 trang Thùy Anh 16300 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Phần 2: Lý thuyết đồ thị - Một số bài toán luồng tổng quát - Nguyễn Đức Nghĩa", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pptbai_giang_toan_roi_rac_phan_2_ly_thuyet_do_thi_mot_so_bai_to.ppt