Bài giảng Lý thuyết đồ thị
Đặng Nguyễn Đức Tiến
HCMUS – 2009
Gi i thi uớ ệ
Lu ng trong m ngồ ạ
Bài toán lu ng c c đ iồ ự ạ
Thu t toán Ford Fulkersonậ
M t s ng d ng c a bài toán lu ng c c đ iộ ố ứ ụ ủ ồ ự ạ
HCMUS –
2009 Bài giảng Lý thuyết đồ thị – Đặng Nguyễn Đức Tiến2
Nguy n Đ c Nghĩa, Nguy n Tô Thành, ễ ứ ễ Toán r i ờ
r cạ, ltb. 1, nxb. Giáo d c, 1998, ch. 7, tr. 215 – 236. ụ
Đ Minh Hoàng, ỗBài gi ng Chuyên đ Gi i thu t ả ề ả ậ
& L p trìnhậ, ĐHSP Hà N i, 2004, ch. 10, tr. 257 – ộ
267.
D ng Anh Đ c, Tr n Đan Th , ươ ứ ầ ư Bài gi ng lý ả
thuy t đ thế ồ ị, 2002, ch. 5.
HCMUS –
2009 Bài giảng Lý thuyết đồ thị – Đặng Nguyễn Đức Tiến3
Lu ng c c đ i là m t trong nh ng bài toán t i u ồ ự ạ ộ ữ ố ư
trên đ th tìm đ c nh ng ng d ng r t r ng rãi ồ ị ượ ữ ứ ụ ấ ộ
trong c th c t cũng nh trong lý thuy t t h p. ả ự ế ư ế ổ ợ
Bài toán đ c đ xu t vào đ u nh ng năm 1950 và ượ ề ấ ầ ữ
g n li n v i tên tu i c a 2 nhà toán h c M : ắ ề ớ ổ ủ ọ ỹ Ford
(Lester Randolph Ford: 1927 - ) và Fulkerson
(Delbert Ray Fulkerson: 1924 - 1976).
HCMUS –
2009 Bài giảng Lý thuyết đồ thị – Đặng Nguyễn Đức Tiến4
M ng (network) ạlà m t đ th có h ng ộ ồ ị ướ G = (V, E)
trong đó:
Có duy nh t m t đ nh ấ ộ ỉ s không có cung đi vào, đ c g i là ượ ọ
đ nh phát (source)ỉ
Có duy nh t m t đ nh t không có cung đi ra, đ c g i là đ nh ấ ộ ỉ ượ ọ ỉ
thu (sink)
M i c nh ỗ ạ e = (u, v) ∈ E đ c gán m t s nguyên không âm ượ ộ ố
c(e) = c[u, v] và g i là ọkh năng thông quaả c a cung đó ủ
(capacity).
Ta quy c n u m ng không có cung (u, v) thì ta thêm ướ ế ạ
vào cung (u, v) v i kh năng thông qua c[u, v] b ng 0.ớ ả ằ
HCMUS –
2009 Bài giảng Lý thuyết đồ thị – Đặng Nguyễn Đức Tiến5