Bài giảng Lý thuyết đồ thị

hông cần quan tâm đến cạnh song song và vòng. Bài toán tô màu là bài toán phân hoạch. Tô màu cạnh là tô hai cạnh kề không cùng màu.sTÔ MÀU Định lý : Mọi đồ thị phẳng là 5-màu. sTÔ MÀU Sắc độ cạnh của một đồ thị là số màu nhỏ nhất dùng để tô màu cạnh.sTÔ MÀU Định lý : 1. Kn có sắc độ cạnh là n1 nếu n chẵn, là n nếu n lẻ. 2. Đồ thị lưỡng phân có sắc độ cạnh bằng với bậc lớn nhất.sBài toán tô màu bản đồCho một bản đồ, tô màu cho mỗi nước trên bản đồ sao cho hai nước láng giềng (có chung đường biên giới) có hai màu khác nhau. Vấn đề: số màu cần dùng tối đa là bao nhiêu? 1976 người ta đã dùng máy tính để chứng minh được là chỉ cần dùng tối đa là 4 màu. Chuyển bài toán về dạng đồ thị, mỗi đỉnh là một nước. Hai nước có chung đường biên giới thì hai đỉnh tương ứng sẽ có cung nối với nhau. 413567Bài toán tô màu bản đồCách giải : thuật toán tối ưu dựa trên nguyên lý thứ tự. Bậc của một đỉnh : là tổng số cung nối đến đỉnh đó.234567Bậc (2) = 2Bậc (3) = 4Bậc (4) = 2Bậc (5) = 2Bậc (6) = 3Bậc (7) = 3Bài toán tô màu bản đồi := 1;WHILE DOWHILE DO Chọn đỉnh Pm có bậc cao nhất ( có thể tô màu Ci ) Tô màu Ci cho đỉnh Pm Đặt bậc của đỉnh Pm = 0  Với mỗi đỉnh Lk có cung nối với đỉnh Pm  Bậc(Lk) = Bậc(Lk) – 1 Cấm tô màu Ci cho đỉnh Lki = i + 1; { Chọn màu tô kế tiếp } Thuật toán Bài toán tô màu bản đồ123456[4][2][3][3][2][2]Bài toán tô màu bản đồ123456[4]  [0][2]  [1][3]  [2][3]  [2][2][2]  [1]Bài toán tô màu bản đồ123456[0] [1] [2] [2]  [1][2]  [0][1]  [0]Bài toán tô màu bản đồ123456[0] [1]  [0][2]  [0] [1]  [0] [0] [0] Bài toán tô màu bản đồ123456[0] [0][0][0][0] [0] Bài toán tô màu bản đồ123456[0] [0][0][0][0] [0] Bài toán tô màu bản đồĐỉnhLisbonLMadridMParisPBerneBeRomeRVieneVBerlinBerLuxemburgLxBrusenBruHagueHBậc1264336342Thuật toán tô màu tối ưu trên đồ thịThuật toán tô màu tối ưu trên đồ thịMàu tô lần 7(Các nước có bậc là 0 mà chưa tô màu)2141Màu tô lần 63-3Màu tô lần 51-1Màu tô lần 4-33-3Màu tô lần 3-22-2Màu tô lần 2-2-22-2-2-2Màu tô lần 1-11-1-1-1-1-1ĐỉnhLMPBeRVBerLxBruHBậc126*4336342Hạ bậc lần 11103235*232Hạ bậc lần 211022*20121Hạ bậc lần 3110101012*1Hạ bậc lần 41*101010000Hạ bậc lần 50001*010000Hạ bậc lần 60000000000Bài tậpVí dụ 2: Phân công, lịch công tác, lịch thi đấuCó một cuộc hội thảo khoa học với 9 chủ đề khác nhau, mỗi chủ đề diễn ra trong một buổi.Các chủ đề sau không được đồng thời: AE, BC, CD, ED, ABD, AHI, BHI, DFI, DHI, FGH.Xây dựng lịch sao cho số buổi diễn ra là ít nhất.Gợi ý: số màu = số buổi.-1-1-11-1-1-1-1ĐỉnhABCDEFGHIBậc552724265441013254AE, BC, CD, ED, ABD, AHI, BHI, DFI, DHI, FGH.LÝ THUYẾT ĐỒ THỊsMẠNG CƠ BẢN Mạng cơ bản là đồ thị đơn giản có hướng có : Hai nguồn (nguồn vào S và nguồn raT). Mỗi cạnh có một tải.SBCDEF235143AT221114sABDÒNG Dòng của cạnh là lượng nước chảy qua cạnh. Dòng của mạng là tổng dòng của các cạnh xuất phát từ S. Dòng của mạng được gọi đơn giản là dòng Tải của mỗi cạnh là dòng tối đa chảy qua cạnh.dòdòngtảisDÒNGDòng của mạng cũng là tổng dòng của các cạnh đến T.Vì dòng của các cạnh xuất phát từ S đều được bảo tồn tại các đỉnh, nên dòng của tất cả các cạnh đến T phải bằng tồng dòng của các cạnh xuất phát từ S.sDÒNG Dòng của cạnh là một giá trị không âm thỏa 2 điều kiện : Dòng của cạnh  Tải của cạnh. Tại mỗi đỉnh : [tổng dòng cạnh vào] = [tổng dòng cạnh ra].SBCDEF0,22,32,50,10,42,3AT2,22,20,10,10,12,4sCẠNH BẢO HÒA Cạnh bảo hòa là cạnh có dòng = tải. eg : Cạnh SB, ET. Dòng của mạng là dòng của các cạnh từ đỉnh S. eg : SA + SB + SC = 2+2+0 = 4 Dòng cực đại là dòng của mạng có giá trị lớn nhất có thể.SBCDEF0,22,32,50,10,42,3AT2,22,20,10,10,12,4sĐƯỜNG TĂNG DÒNGĐường tăng dòng là đường từ S đến T không chứa cạnh bảo hòa.Đường SADT là đường tăng dòng.Đường SBFT không là đường tăng dòng vì có cạnh SB bảo hòa.SBCDEF0,22,32,50,10,42,3AT2,22,20,10,10,12,4sĐƯỜNG TĂNG DÒNG Tăng dòng cho mỗi cạnh của SADT lên 1. Dòng tăng từ 4 lên 5 (3+2+0). Mạng bây giờ không có đường nào là đường tăng dòng. Nhưng 5 chưa phải là dòng cực đại.2,32,52,43,33,53,4SBCEF0,20,10,42,3T2,22,20,10,10,1ADsĐƯỜNG TĂNG DÒNGTăng dòng SC lên 1. dòng CE cũng phải tăng 1.Tại E bị lệch (3 đến và 2 ra) . giảm dòng BE đi 1.Tại B lại bị lệch. tăng dòng BF (hay BD) lên 1Tại F (hay D) lại bị lệch. tăng dòng FT (hay DT) lên 1.Dòng của mạng bây giờ là 6.1,21,11,41,31,1SBCDEF3,33,5AT2,22,20,10,13,40,20,10,42,30,1sĐƯỜNG TĂNG DÒNG Định nghĩa lại khái niệm đường tăng dòng. Đường tăng dòng là đường từ S đến T chứa : các cạnh cùng hướng không bảo hòa, các cạnh nghịch hướng có dòng  0.1,21,11,41,31,10,20,10,42,30,11,21,11,11,31,40,20,10,12,30,4SBCEFTSBCEFTsTHÍ DỤ Tìm đường tăng dòng cực đại. SA có thể tăng tối đa là 3 BC là 3 CD là 7 AB có thể giảm tối đa là 3 DE là 2 ET là 5 Do đó dòng có thể tăng tối đa 2 (= min {3, 2}).SCABETD4,73,42,92,55,60,76,71,40,94,53,62,7 min là 2s min là 3TÌM DÒNG CỰC ĐẠI Để tìm dòng cực đại thì tìm những đường tăng dòng và giatăng cực đại, việc này được thực hiện cho đến khi không còn đườngtăng dòng. Tuy nhiên khi đồ thị có số cạnh khá lớn thì việc tìm tất cảđường tăng dòng không còn dễ dàng. Cần nghiên cứu thuật toán dòng cực đại.sTẬP CẮT Tập cắt của mạng là tập hợp các cạnh sao cho lấy đi thì mạng bị rời rạc thành 2 thành phần (phần X chứa nguồn vào S, phần Y chứa nguồn ra T). Yù niệm tập cắt bắt nguồn từ khái niệm bottle-neck.SBCTAEDkhông là tập cắtlà tập cắtsTẬP CẮTDòng của mạng = Tổng dòng của các cạnh của tập cắt hướng từ S đến T  Tổng dòng của các cạnh của tập cắt hướng từ T đến S.sTẬP CẮT Tải của tập cắt là tổng tải của các cạnh trong tập cắt có hướng từ phần chứa S vào phần chứa T.AB2SC4TD633104522Tải của tập cắt = 7 Tải của tập cắt = 11 sTẬP CẮT Tập cắt cực tiểu là tập cắt có tải nhỏ nhất.Tải của tập cắt C1 = {SA, AB, BD, BE, CE} = SA+BD+BE+CE = 25.Tải của tập cắt C2 = {SA, AB, BD, ET} = SA + BD + ET = 12.Mọi tập cắt khác đều có tải lớn hơn 12  C2 là tập cắt cực tiểu.AB3SC10TD668114592E4sTẬP CẮT Tất cả các tập cắt của đồ thị : Tập cắt cực tiểu là {BC, BT, CD}.Taäp caétÑænh trong XÑænh trong YTaûi taäp caét {SA, SD} S A, B, C, D, T 5 + 4 = 9 {SD, AD, AB} S, A B, C, D, T 4 + 4 = 8 {SA, DA, DC} S, D A, B, C, T 5 + 3 + 3 = 11 {AB, CD} S, A, D B, C, T 4 + 3 = 7 {SD, AD, BC, BT} S, A, B C, D, T 4 + 1 + 2 = 7 {BC, BT, CD} S, A, B, D C, T 3 + 1 + 2 = 6 {SA, AD, BC, BT} S, C, D A, B, T 5 + 3 + 8 = 16 {AB, BC, BT} S, A, C, D B, T 4 + 8 = 12 {BT, CT} S, A, B, C, D T 2 + 8 = 10AB4SD5TC243813sMAX-FLOW MIN-CUT Một dòng bất kỳ  Tải của mọi tập cắt.  Dòng cực đại  Tải của mọi tập cắt.  Dòng cực đại  Tải của tập cắt cực tiểu.Tập cắtDòngsSXTYMAX-FLOW MIN-CUT Tải của tập cắt   Dòng cạnh từ X vào Y Dòng = ( Dòng cạnh từ XY)  ( Dòng cạnh từ YX)Dòng từ Y vào XTập cắtDòng từ X vào YTải của tập cắtsTẬP CẮT Tập cắt  = {AD, BT, BD, CD}, X = {S, A, B, C}, Y = {D, T}. Tải của tập cắt = AD + BT + CD = 2 + 6 + 3 = 11. Dòng từ X vào Y = AD + BT + CD = 2 + 4 + 2 = 8. Dòng từ Y vào X = BD = 2. Dòng của mạng = (Dòng từ X vào Y)  (Dòng từ Y vào X) = 6.AB1,2SC4,4TD4,62,32,32,101,42,51,22,2sMAX-FLOW MIN-CUT Định lý : (max-flow min-cut theorem) Dòng cực đại = Tải của tập cắt cực tiểu. Chứng minh : Ta có dòng cực đại  tải của tập cắt cực tiểu. Để chứng minh đẳng thức chỉ cần tìm tập cắt có tải bằng với dòng cực đại. Gọi  là dòng cực đại. X = {W  có một đường tăng dòng đi từ S đến đỉnh W} Y = (Tập đỉnh của đồ thị)  (X  {S}).  T  Y, nếu T  X thì có đường tăng dòng từ S đến T và  không là dòng cực đại.sMAX-FLOW MIN-CUTChứng minh : (tiếp theo)  = {cạnh nối X và Y} là tập cắt.Mọi cạnh MN   từ X hướng vào Y phải bảo hòa, (1) từ Y hướng vào X có dòng bằng 0, (2)nếu không thì có đường tăng dòng từ S vào N và N  X.(1)  Tải của  = Tổng dòng các cạnh của  nối X vào Y.(2)  Dòng của mạng = Tổng dòng các cạnh của  nối X vào Y.Dòng của mạng = Tải của tập cắt .(dòng nào đó  dòng cựcđại  tải của tập cắt cựctiểu  tải của 1 tập cắt)Vậy Dòng cực đại  = Tải của tập cắt cực tiểu.sMAX-FLOW MIN-CUT Chứng minh trên cho một thuật toán tìm dòng cực đại. 1. Tìm tập X = {W  có đường tăng dòng từ S đến W}. 2. Tìm tập Y = V  (X  {S}). 3. Tìm  = {cạnh nối X và Y}. 4. Tải của  = Tổng dòng các cạnh của  nối X vào Y. 5. Dòng cực đại  = Tải của .sMAX-FLOW MIN-CUTX = {A, B, C, D, E}.Đỉnh A (SB, BA), B (SB), C (SB, BE, EC), D (SB, BA, AD), E (SB, BE).Y = {F, T}. Tập cắt  = {CF, EF, DT, ET, FE}. Tải của tập cắt = 40+12+36+48 = 136.  Dòng cực đại là 136.AD38,50SCB40,40ETF36,3630,3040,4052,6048,4866,7013,1515,1510,2420,2022,2220,200,1812,1228,30sTHUẬT TOÁN MAX-FLOW Tìm dòng cực đại của mạng : Cho mỗi cạnh một dòng bằng 0. Bắt đầu từ S chọn cạnh không bảo hòa SA. SA có tải 3, cho đỉnh A nhãn (S,3).235142321114SBCDEFAT0,20,30,50,10,40,20,30,20,10,10,10,4(S,3)sTHUẬT TOÁN MAX-FLOW Chọn AD, AD có tải 5 nhưng SA có tải 3 nên cho D nhãn (A,3). Tương tự, T có nhãn (D,3). Tìm được đường tăng dòng SADT.0,20,30,50,10,40,20,30,20,10,10,10,4SBCDEFAT(S,3)(A,3)(D,3)0,23,33,50,10,40,20,30,20,10,10,13,4sTHUẬT TOÁN MAX-FLOW Tương tự, tìm đường tăng dòng thứ 2 SBDT. Đỉnh B có nhãn (S,3), D nhãn (B,1), T nhãn (D,1). Dòng tăng được 1. Vẫn còn cạnh không bảo hòa đến B.SBCDEFAT0,23,33,50,10,40,20,30,20,10,10,13,40,23,33,50,10,40,21,30,20,10,11,14,4sTHUẬT TOÁN MAX-FLOW Tìm được đường tăng dòng thứ 3 SBET. Đỉnh B có nhãn (S,2), E nhãn (B,2), T nhãn (E,2). Dòng tăng được 2. Tiếp tục với đỉnh C.SBCDEFAT0,23,33,50,10,40,21,30,20,10,11,14,40,23,33,50,10,42,23,32,20,10,11,14,4sTHUẬT TOÁN MAX-FLOW Tìm được đường tăng dòng SCEBFT. C có nhãn (S,2), E có nhãn (C,1). Từ ET đã bảo hòa nên E lui về B, B có nhãn (E,1), F nhãn (B,1), T nhãn (F,1). Dòng tăng được 1.SBCDEFAT1,23,33,51,11,41,23,32,21,10,11,14,40,23,33,50,10,42,23,32,20,10,11,14,4sTHUẬT TOÁN MAX-FLOW SC không bảo hòa cho đỉnh C nhãn (S,1), nhưng không thể tiếp tục. Thuật toán dừng với dòng cực đại 7.SBCDEFAT1,23,33,51,11,41,23,32,21,10,11,14,4sTHUẬT TOÁN MAX-FLOWTìm dòng cực đại của mạng. Dùng phương pháp bảng. Điền vào bảng tải của các cạnh với dòng 0.0,40,20,40,10,10,20,10,10,50,20,30,3TFEDCBASTFEDCBAS235142321114SBCDEFATsTHUẬT TOÁN MAX-FLOW Đỉnh S, SA có thể có dòng 3, gán A nhãn (S,3). Đỉnh A, AD có thể có dòng 5, gán D nhãn (A,3). Đỉnh D, DT có thể có dòng 4, gán T nhãn (D,3).  Đường tăng dòng SADT tăng 3.0,40,20,40,10,10,20,10,10,50,20,30,3TFEDCBASTFEDCBAS0,40,23,40,10,10,20,10,13,50,20,33,3sTHUẬT TOÁN MAX-FLOW Chọn SB, gán B nhãn (S,3). Chọn BD, gán D nhãn (B,1). Chọn DT, đỉnh T có nhãn (D,1).  Đường tăng dòng SBDT tăng 1.0,40,23,40,10,10,20,10,13,50,20,33,3TFEDCBASTFEDCBAS0,40,24,40,10,10,21,10,13,50,21,33,3sTHUẬT TOÁN MAX-FLOW Chọn SB (chưa bảo hòa), gán B nhãn (S,2). Chọn BE, gán E nhãn (B,2). Chọn ET, đỉnh T có nhãn (E,2).  Đường tăng dòng SBET tăng 2.0,40,24,40,10,10,21,10,13,50,21,33,3TFEDCBASTFEDCBAS0,42,24,40,10,12,21,10,13,50,23,33,3sTHUẬT TOÁN MAX-FLOW SC, gán C nhãn (S,2). CE, gán E nhãn (C,1). E bị đứng nên lui lại B. BE, gán B nhãn (E,1). BF, F gán nhãn (B,1). FT, T gán nhãn (F, 1).  Đường tăng dòng SCEBFT tăng 1.0,42,24,40,10,12,21,10,13,50,23,33,3TFEDCBASTFEDCBAS1,42,24,41,11,11,21,10,13,51,23,33,3sTHUẬT TOÁN MAX-FLOW Đỉnh C có nhãn (S,1), nhưng không còn cạnh không bảo hòa và nghịch hướng từ C. Do đó thuật toán dừng. Dòng cực đại là 4+2+1 = 7 (hay 3+3+1).1,42,24,41,11,12,21,10,13,51,23,33,3TFEDCBASTFEDCBASsLÝ THUYẾT ĐỒ THỊsFLOW NETWORKSNhà máy LAMILK sản xuất sữa hộp tại Long An có kho hàng tại Cần Thơ. Mỗi ngày phải mang sản phẩm về chứa tại kho Cần Thơ. Từ LA đến CT có nhiều con đường đi qua một số địa phương như hình vẽ sau :Trên các đoạn đường này có giới hạn về trọng tải của xe, trên mỗi tuyến đường xe chỉ đủ thời gian chạy qua một lần trong ngày. Hỏi rằng LAMILK phải sản xuất bao nhiêu tấn mỗi ngày để chở hết đến kho.sCFLong AnBDE2t3t5t4t3tACần Thơ2t2t3t2t4t4tFLOW NETWORKSMạng là đồ thị = đơn giản có hướng liên thông có : 1. đỉnh S gọi là nguồn vào và đỉnh T gọi là nguồn ra, 2. c : V  V  R+ là ánh xạ thỏa : c(X, Y) = 0 nếu (X, Y)  E, 3. f : V  V  R (số thực) là ánh xạ thỏa : f(X, Y)  c(X, Y), X, Y  V f(X, Y) =  f(Y, X), X, Y  V YV f(X, Y) = 0, X  V  {S, T} 4. dòng f được ký hiệu là |f| = YV f(S, Y) sFLOW NETWORKSThí dụ : Đồ thị này là flow networks Đồ thị này cũng là flow networkssCSBDE42,574,53,5AT7,105,94,62,26FLOWBổ đề :Cho mạng = và f là một dòng.Ký hiệu : f(H, K) = XH YK f(X, Y), H, K  V.Ta có : 1. f(H, H) = 0, H  V. 1. f(H, K) =  f(K, H), H, K  V. 1. f(HL, K) = f(H, K) + f(L, K), H, K, L  V và HL=. 1. f(H, KL) = f(H, K) + f(H, L), H, K, L  V và KL=.sRESIDUAL NETWORKSCho mạng = và f là một dòng.Tải thặng dư (residual capacity) của một cạnh XY là : cf(X, Y) = c(X, Y)  f(X, Y), X, Y  V.Mạng thặng dư của tương ứng với dòng f là mạng = với Ef được định nghĩa như sau : Ef = {(X, Y) | cf(X, Y) > 0, X, Y  V}sRESIDUAL NETWORKSThí dụ : = và f như sau : = sCFSBDE42,574,53,5AT8,105,94,62,21,41,42S815437423T244213231RESIDUAL NETWORKSBổ đề :Mạng = và mạng thặng dư ø = tương ứng với dòng f.Lấy f’ là một dòng của mạng thặng dư ø, khi đó : |f + f’| = |f| + |f’| với phép tính + của dòng được định nghĩa như sau : (f + f’)(X, Y) = f(X, Y) + f’(X, Y), X, Y  V.sAUGMENTING PATHMạng = và mạng thặng dư ø tương ứng với dòng f.Đường tăng dòng của f là một đường từ S vào T trong mạng . cf(p) = min {cf(XY) | XY }sCFSBDE42,574,53,5AT8,105,94,62,21,41,42S815437423T244213231cf(p) = min {2, 3, 3} = 2cf(p) = min {2, 2, 4} = 2cf(p) = min {2, 2, 1} = 1cf(p) = min {4, 7, 4} = 4AUGMENTING PATHBổ đề :Mạng = với dòng f và là một đường tăng dòng trong mạng .Hàm fp : V  V  R được định nghĩa như sau : fp(X, Y) = cf(), Nếu XY  fp(X, Y) =  cf(), Nếu YX  fp(X, Y) = 0, trường hợp khác.Khi đó fp là một dòng trong và |fp| = cf() > 0.sAUGMENTING PATHBổ đề :Mạng = với dòng f và là một đường tăng dòng trong mạng .Hàm f’ : V  V  R được định nghĩa : f’ = f + fp.Khi đó f’ là một dòng trong và |f’| = |f| + |fp| > |f|.sCUTS OF FLOW NETWORKSTập cắt (Mạng = với dòng f và là một đường tăng dòng trong mạng .Hàm f’ : V  V  R được định nghĩa : f’ = f + fp.Khi đó f’ là một dòng trong và |f’| = |f| + |fp| > |f|.sMAX-FLOW MIN-CUT Định lý : (max-flow min-cut theorem) Dòng cực đại = Tải của tập cắt cực tiểu. sLÝ THUYẾT ĐỒ THỊsCHUYỂN VỀ MẠNG CƠ BẢNMạng mixed là mạnh cơ bản nhưng có một số cạnh có 2 chiều.Trường hợp này thì thêm cạnh song song cho các cạnh 2 chiều.sCHUYỂN VỀ MẠNG CƠ BẢNMạng mixed là mạnh cơ bản nhưng có một số cạnh có 2 chiều.Trường hợp này thì thêm cạnh song song cho các cạnh 2 chiều.sLÝ THUYẾT ĐỒ THỊHẾTs