Bài giảng Lý thuyết đồ thị - Chương 1: Các khái niệm cơ bản

rỡnh. Chu trỡnh được gọi là đơn nếu như ngoại trừ đỉnh đầu trựng với đỉnh cuối, khụng cú đỉnh nào bị lặp lại. Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội62Chu trỡnh  1, 2, 3, 1. (hay 1, a, 2, b, 3, e) Chu trỡnh đơnChu trỡnh: (1, 2, 3, 4, 1) hay  1, a, 2, b, 3, c, 4, d, 1 Chu trỡnh đơn234 a bc d1e234 a bc d1eChu trỡnh (Cycle)Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội63Vớ dụ: Chu trỡnh trờn đồ thị vụ hướngC1=(V,b,X,g,Y,f,W,c,U,a,V) là chu trỡnh đơnC2=(U,c,W,e,X,g,Y,f,W,d,V,a,U) là chu trỡnh nhưng khụng là chu trỡnh đơnC1XUVWZYacbedfghC2Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội64Vớ dụ: Chu trỡnh trờn đồ thị cú hướngC1=(V,b,X,g,Y,f,W,c,U,a,V) là chu trỡnh đơnC2=(U,c,W,e,X,g,Y,f,W,d,V,a,U) là chu trỡnh nhưng khụng là chu trỡnh đơnC1XUVWZYacbedfghC2Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội65Chương 1 CÁC KHÁI NIỆM CƠ BẢN1.1. Đồ thị trong thực tế1.2. Cỏc loại đồ thị1.3. Bậc của đỉnh1.4. Đồ thị con1.5. Đồ thị đẳng cấu1.6. Đường đi và chu trỡnh1.7. Tớnh liờn thụng1.8. Một số loại đồ thị đặc biệt1.9. Tụ màu đồ thịPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội66Tớnh liờn thụng (Connectedness)Đồ thị vụ hướng được gọi là liờn thụng nếu luụn tỡm được đường đi nối hai đỉnh bất kỳ của nú.Vớ dụG1 và G2 là cỏc đồ thị liờn thụngĐồ thị G bao gồm G1 và G2 khụng là đồ thị liờn thụngfijkG1G2Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội67Tớnh liờn thụng (Connectedness)Mệnh đề: Luụn tỡm được đường đi đơn nối hai đỉnh bất kỳ của đồ thị vụ hướng liờn thụng.Chứng minh. Theo định nghĩa, luụn tỡm được đường đi nối hai đỉnh bất kỳ của đồ thị liờn thụng. Gọi P là đường đi ngắn nhất nối hai đỉnh u và v. Rừ ràng P phải là đường đi đơn.Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội68Tớnh liờn thụng (Connectedness)Thành phần liờn thụng (Connected component): Đồ thị con liờn thụng cực đại của đồ thị vụ hướng G được gọi là thành phần liờn thụng của nú.Vớ dụ: Đồ thị G cú 3 thành phần liờn thụng G1, G2, G3G1abcedgfijkG3G2Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội69Thành phần liờn thụngGỉa sử vV. Gọi V(v) – tập cỏc đỉnh của đồ thị đạt đến được từ v, E(v) – tập cỏc cạnh cú ớt nhất một đầu mỳt trong V(v).Khi đú G(v) = (V(v), E(v)) là đồ thị liờn thụng và được gọi là thành phần liờn thụng sinh bởi đỉnh v. Dễ thấy G(v) là thành phần liờn thụng sinh bởi mọi đỉnh uV(v).V(a)={a,b,c,d,e,g};G1≡G(a)abcedgfijkG3 ≡G(i)G2 ≡G(f)Vớ dụ: Cho G là đồ thị vụ hướng n  2 đỉnh. Biết rằng d(G) = min{deg(v): v V}  (n-1)/2. Chứng minh rằng G liờn thụng.Chứng minh. Phản chứng. Giả sử G khụng liờn thụng, khi đú do d(G)  (n-1)/2, nờn mỗi thành phần liờn thụng phải chứa ớt ra (n-1)/2+1 = (n+1)/2 đỉnh. Suy ra đồ thị cú ớt ra (n+1) đỉnh?!Vớ dụ Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội71Đỉnh rẽ nhỏnh và cầu (Connectedness)Đỉnh rẽ nhỏnh (cut vertex): là đỉnh mà việc loại bỏ nú làm tăng số thành phần liờn thụng của đồ thị Cầu (bridge): Cạnh mà việc loại bỏ nú làm tăng số thành phần liờn thụng của đồ thị .Vớ dụ:Cạnh (e,g) là cầuGabcedge là đỉnh rẽ nhỏnhMệnh đề. Cạnh e của đồ thị liờn thụng G là cầu iff e khụng thuộc bất cứ chu trỡnh nào trờn G.Chứng minh () Cho e là cầu của G. Giả sử e = (u,v), và giả sử ngược lại là e nằm trờn chu trỡnh C：u, v, w, , x, u.　Khi đú C - e：v, w, , x, u là đường đi từ u đến v trờn đồ thị G - e. Ta sẽ chứng minh: G - e là là liờn thụng. (Điều đú sẽ mõu thuẫn với giả thiết e là cầu)Vớ dụ Thực vậy, giả sử u1, v1  V(G-e)=V(G) Do G là liờn thụng, nờn  đường đi P: u1v1 trờn G. Nếu e  P, thỡ P cũng là đường đi trờn G-e   đường đi u1v1 trờn G-e Nếu e  P, thỡ (PC)-e là đường đi u1v1 trờn G-e (xem hỡnh) Vậy luụn tỡm được đường đi u1v1 trờn G-e Vậy G-e là liờn thụng.v1uu1vCPChứng minh mệnh đề (cont) () Giả sử e=(u,v) là cạnh khụng nằm trờn bất cứ chu trỡnh nào của G. Khi đú G-e khụng chứa đường đi uv. Trỏi lại, nếu P là đường đi uv trờn G-e, thỡ P{(u,v)} là chu trỡnh trờn G chứa e ?!Chứng minh mệnh đề (cont) Khụng phải tất cả cỏc đồ thị liờn thụng là đồng giỏ trị! Q: Hóy đỏnh giỏ xem đồ thị nào dưới đõy là sơ đồ nối mạng mỏy tớnh cú giỏ trị hơn:1) G12) G23) G34) G475k-liờn thụng (k-Connectivity)76k-ConnectivityA: Ta muốn mạng mỏy tớnh vẫn là thụng suốt ngay cả khi cú một mỏy bị hỏng:1) 2nd best. Vẫn cú một điểmyếu— “cut vertex”2) 3rd best. Thụng suốtnhưng mỗi mỏy đều là điểm “yếu” 3) Tồi nhất! Khụng thụng suốt4) Tốt nhất! Mạng chỉ khụng thụng suốt nếu hỏng 2 mỏy77k-ConnectivityMạng là tốt nhất bởi vỡ nú mất tớnh liờn thụng chỉ khi cú 2 đỉnh bị loại bỏ. Núi cỏch khỏc mạng là 2-liờn thụng (song liờn thụng).Định nghĩa. Đơn đồ thị vụ hướng liờn thụng với n3 đỉnh được gọi là song liờn thụng nếu nú vẫn là liờn thụng sau khi loại bỏ một đỉnh bất kỳ.Q: Tại sao lại cú điều kiện với số đỉnh?A: Trỏnh trường hợp đồ thị chỉ cú 1 cạnh.k-liờn thụngTổng quỏt:Định nghĩa. Đơn đồ thị vụ hướng được gọi là k-liờn thụng nếu như muốn phỏ vỡ tớnh liờn thụng của nú ta phải loại bỏ ớt nhất k đỉnh.Vớ dụ: Q3 là 3-liờn thụngQ4 là ?-liờn thụngPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội78Q3Q4Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội79Tớnh liờn thụng của Đồ thị cú hướngĐồ thị cú hướng được gọi là liờn thụng mạnh (strongly connected) nếu như luụn tỡm được đường đi nối hai đỉnh bất kỳ của nú.Đồ thị cú hướng được gọi là liờn thụng yếu (weakly connected ) nếu như đồ thị vụ hướng thu được từ nú bởi việc bỏ qua hướng của tất cả cỏc cạnh của nú là đồ thị vụ hướng liờn thụng.Dễ thấy là nếu G là liờn thụng mạnh thỡ nú cũng là liờn thụng yếu, nhưng điều ngược lại khụng luụn đỳng.Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội80Vớ dụĐồ thị liờn thụng mạnh Đồ thị liờn thụng yếuabcedfabcedfabcedfPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội81Chương 1 CÁC KHÁI NIỆM CƠ BẢN1.1. Đồ thị trong thực tế1.2. Cỏc loại đồ thị1.3. Bậc của đỉnh1.4. Đồ thị con1.5. Đồ thị đẳng cấu1.6. Đường đi và chu trỡnh1.7. Tớnh liờn thụng1.8. Một số loại đồ thị đặc biệt1.9. Tụ màu đồ thịPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội82Một số dạng đơn đồ thị vụ hướng đặc biệtĐồ thị đầy đủ (Complete graphs) KnChu trỡnh (Cycles) CnBỏnh xe (Wheels) Wnn-Cubes QnĐồ thị hai phớa (Bipartite graphs)Đồ thị hai phớa đầy đủ (Complete bipartite graphs) Km,nĐồ thị chớnh quiCõy và rừngĐồ thị phẳngPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội83Đồ thị đầy đủComplete GraphsVới nN, đồ thị đầy đủ n đỉnh, Kn, là đơn đồ thị vụ hướng với n đỉnh trong đú giữa hai đỉnh bất kỳ luụn cú cạnh nối: u,vV: uv  (u,v)E.Để ý là Kn cú cạnh.K5K6K1K2K3K4Đồ thị đầy đủComplete GraphsK2584Đồ thị đầy đủComplete GraphsK4285Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội86Chu trỡnh (Cycles)Giả sử n3. Chu trỡnh n đỉnh, Cn, là đơn đồ thị vụ hướng với V={v1,v2, ,vn} và E={(v1,v2),(v2,v3),,(vn1,vn),(vn,v1)}.C3C4C5C6C7C8Cú bao nhiờu cạnh trong Cn? Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội87Bỏnh xe (Wheels)Với n3, bỏnh xe Wn, là đơn đồ thị vụ hướng thu được bằng cỏch bổ sung vào chu trỡnh Cn một đỉnh vhub và n cạnh nối {(vhub,v1), (vhub,v2),,(vhub,vn)}.W3W4W5W6W7W8Cú bao nhiờu cạnh trong Wn? Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội88Siờu cỳp (n-cubes /hypercubes)Với nN, siờu cỳp Qn là đơn đồ thị vụ hướng gồm hai bản sao của Qn-1 trong đú cỏc đỉnh tương ứng được nối với nhau. Q0 gồm duy nhất 1 đỉnh.Q0Q1Q2Q3Q4Số đỉnh: 2n. Số cạnh: ? Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội89Siờu cỳp (n-cubes /hypercubes)Với nN, siờu cỳp Qn là đơn đồ thị vụ hướng gồm hai bản sao của Qn-1 trong đú cỏc đỉnh tương ứng được nối với nhau. Q0 gồm duy nhất 1 đỉnh.Q0Số đỉnh: 2n. Số cạnh: ? Q1Q2Q3Q4Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội90Siờu cỳp Q4Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội91Siờu cỳp(n-cubes /hypercubes)Với nN, siờu cỳp Qn cú thể định nghĩa đệ qui như sau: Q0={{v0},} (một đỉnh và khụng cú cạnh)Với mọi nN, nếu Qn=(V,E), trong đú V={v1,,va} và E={e1,,eb}, thỡ Qn+1=(V{v1´,,va´}, E{e1´,,eb´}{(v1,v1´),(v2,v2´),,(va,va´)})Nghĩa là siờu cỳp Qn+1 thu được từ hai siờu cỳp Qn và Q’n bằng việc nối cỏc cặp đỉnh tương ứng.Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội92Định nghĩa. Đồ thị G=(V,E) là hai phớa nếu và chỉ nếu V = V1 V2 với V1∩V2= và eE: v1V1, v2V2: e=(v1,v2).Bằng lời: Cú thể phõn hoạch tập đỉnh thành hai tập sao cho mỗi cạnh nối hai đỉnh thuộc hai tập khỏc nhau.Đồ thị hai phớa (Bipartite Graphs)V1V2Định nghĩa này là chung cho cả đơn lẫn đa đồ thị vụ hướng, cú hướng.Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội93Đồ thị hai phớa đầy đủ(Complete Bipartite Graphs)Với m, nN, đồ thị hai phớa đầy đủ Km,n là đồ thị hai phớa trong đú |V1| = m, |V2| = n, và E = {(v1,v2)|v1V1 và v2V2}.Km,n cú m đỉnh ở tập bờn trỏi, n đỉnh ở tập bờn phải, và mỗi đỉnh ở phần bờn trỏi được nối với mỗi đỉnh ở phần bờn phải.K4,3Km,n cú _____ đỉnhvà _____ cạnh.Định nghĩa. Đồ thị G được gọi là đồ thị chớnh qui bậc r nếu tất cả cỏc đỉnh của nú cú bậc bằng r. Vớ dụ:Đồ thị chớnh quir-regular graph Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội94Đồ thị chớnh qui bậc 0Đồ thị chớnh qui bậc 1Đồ thị chớnh qui bậc 2Đồ thị chớnh qui bậc 3Đồ thị PlatonicXột cỏc khối đa diện Platonic trong khụng gian 3-chiềuPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội95TetrahedronTứ diệnHexahedron (cube)Lục diệnOctahedronBỏt diệnDodecahedronThập nhị diệnIcosahedronThập bỏt diệnĐồ thị PlatonicĐồ thị platonic thu được bằng việc chiếu cỏc khối đa diện tương ứng xuống mặt phẳngPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội96TetrahedronHexahedron (cube)OctahedronDodecahedronIcosahedronPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội97Cõy và rừng (Tree and Forest)Định nghĩa. Ta gọi cõy là đồ thị vụ hướng liờn thụng khụng cú chu trỡnh. Đồ thị khụng cú chu trỡnh được gọi là rừng.Như vậy, rừng là đồ thị mà mỗi thành phần liờn thụng của nú là một cõy. T1T3Rừng F gồm 3 cõy T1, T2,, T3T2Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội98VÍ DỤG1, G2 là cõyG3, G4 khụng là cõyPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội99Cỏc tớnh chất cơ bản của cõyĐịnh lý. Giả sử T=(V,E) là đồ thị vụ hướng n đỉnh. Khi đú cỏc mệnh đề sau đõy là tương đương: (1) T là cõy; (2) T khụng chứa chu trỡnh và cú n-1 cạnh; (3) T liờn thụng và cú n-1 cạnh; (4) T liờn thụng và mỗi cạnh của nú đều là cầu; (5) Hai đỉnh bất kỳ của T được nối với nhau bởi đỳng một đường đi đơn; (6) T khụng chứa chu trỡnh nhưng hễ cứ thờm vào nú một cạnh ta thu được đỳng một chu trỡnh.Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội100Đồ thị phẳng(Planar Graphs)Định nghĩa. Đồ thị vụ hướng G được gọi là đồ thị phẳng nếu như cú thể vẽ nú trờn mặt phẳng sao cho khụng cú hai cạnh nào cắt nhau ngoài ở đỉnh.Vớ dụ: K4 là đồ thị phẳng?K4 là đồ thị phẳng!Cỏc đồ thị Platonic đều phẳngTất cả 5 đồ thị Platonic đều là đồ thị phẳngPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội101L251023-Cube là đồ thị phẳng1034-Cube cú là đồ thị phẳng khụng?Cú vẻ phẳng, nhưng chứng minh bằng cỏch nào?K3,3 và K5 khụng là đồ thị phẳngĐồ thị K3,3 và K5 khụng là đồ thị phẳngMọi cỏch vẽ K3,3 đều phải cú ớt nhất một giao điểm ngoài đỉnh (gọi là vết cắt).Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội104Khảo sỏt đồ thị phẳngĐể khảo sỏt đồ thị phẳng ta cú thể chỉ hạn chế ở đơn đồ thị. Bởi vỡ:Nếu đồ thị phẳng cú cạnh lặp hay là khuyờn (loop)Chập cỏc cạnh lặp lại thành một cạnh đơn. Loại bỏ tất cả cỏc khuyờn. Vẽ đơn đồ thị thu được sao cho khụng cú vết cắt. Sau đú chốn vào cỏc khuyờn và cạnh lặp. Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội105Khảo sỏt đồ thị phẳngVớ dụ: Xột đồ thị phẳng106Loại bỏ khuyờn và cạnh lặp:Vẽ đơn đồ thị thu được:Bổ sung khuyờn và cạnh lặp:Cụng thức EulerEuler's FormulaNếu G là đồ thị phẳng, thỡ mọi cỏch vẽ phẳng G đều chia mặt phẳng ra thành cỏc vựng mà ta sẽ gọi là cỏc diện (faces). Một trong cỏc diện này là khụng bị chặn và nú được gọi là diện vụ hạn. Giả sử f là một diện nào đú, ta gọi bậc của f , ký hiệu bởi deg(f ), là số cạnh trờn đường đi vũng quanh biờn của diện f. Nếu tất cả cỏc diện đều cú cựng bậc (chẳng hạn, g), thỡ G được gọi là diện chớnh quy bậc g.Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội107Cụng thức EulerEuler's FormulaVớ dụ: Đồ thị G sau đõy cú 4 diện, trong đú f4 là diện vụ hạn.Dễ thấy là trong đồ thị trờn: deg(f1)=3, deg(f2)=4, deg(f3)=9, deg(f4)=8. Nhận thấy là tổng bậc của cỏc diện là bằng 2 lần số cạnh của đồ thị, bởi vỡ mỗi cạnh là biờn chung của hai diện (vớ dụ, bg, cd, và cf) hoặc xuất hiện hai lần khi đi vũng quanh một diện (vớ dụ, cỏc cạnh ab và gh). 108Cụng thức EulerCụng thức Euler cho biết mối liờn hệ giữa số đỉnh, số cạnh và số diện của đồ thị phẳng. Nếu n, m, và f theo thứ tự là số đỉnh, cạnh và diện của đồ thị phẳng liờn thụng thỡ ta cú n – m+f = 2. Cụng thức Euler khẳng định rằng mọi cỏch vẽ phẳng của đồ thị phẳng liờn thụng đều cho cựng một số diện như nhau là 2 – n + m.Theorem (Euler's Formula)    Let G be a connected planar graph, and let n, m and f  denote, respectively, the numbers of vertices, edges, and faces in a plane drawing of G. Then n – m + f = 2.Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội109Chứng minh cụng thức EulerChứng minh.  Qui nạp theo số cạnh m. Cơ sở qui nạp: Khi m=0, ta cú n=1 và f=1. Do đú n–m+f = 2.Bước qui nạp: Giả sử khẳng định đỳng cho mọi đồ thị phẳng liờn thụng cú ớt hơn m cạnh, trong đú m  1, và giả sử rằng G cú m cạnh. Nếu G là cõy, thỡ n=m+1 và f=1 và do đú cụng thức là đỳng. Mặt khỏc, nếu G khụng là cõy thỡ gọi e là một cạnh trờn chu trỡnh của G và xột G\e. Đồ thị phẳng liờn thụng G\e cú n đỉnh, m-1 cạnh, và f – 1 diện, do đú theo giả thiết qui nạpn – (m – 1) + (f – 1) = 2 từ đú suy ran – m + f = 2.Ta sẽ phỏt biểu một loạt hệ quả thỳ vị suy ra từ cụng thức Euler.110Hệ quảHệ quả 1.  Giả sử G là đơn đồ thị phẳng liờn thụng với n đỉnh, trong đú n ≥ 3 và m cạnh. Khi đú m ≤ 3n – 6.Chứng minh.  Đối với đồ thị G cú f diện, từ bổ đề về cỏc cỏi bắt tay, suy ra 2m = (tổng bậc của cỏc diện) ≥ 3f  (bởi vỡ bậc của mỗi diện của đơn đồ thị ớt nhất là 3), do đú f ≤ 2/3 m.Kết hợp với cụng thức Euler n – m + f  = 2ta thu được        m – n + 2 ≤ 2/3 m.Từ đú suy ra       m ≤ 3n – 6.Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội111K5 khụng là đồ thị phẳngHệ quả 2. K5 khụng là đồ thị phẳng.Chứng minh. Giả sử K5 là đồ thị phẳng. Do K5  cú 5 đỉnh và 10 cạnh, nờn từ bổ đề 1 suy ra 10 (3 ì 5) – 6 = 9. Điều phi lý này đó chứng minh K5 khụng là đồ thị phẳng.Chỳ ý: K3,3  cú 6 đỉnh và 9 cạnh, và bất đẳng thức 9 ≤ (3 ì 6) – 6 = 12 là đỳng. Sự kiện này cho thấy là ta khụng thể sử dụng hệ quả 1 để chỉ ra K3,3  khụng là phẳng.Ta sẽ phải sử dụng hệ quả khỏc.Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội112Hệ quả 3Hệ quả 3. Giả sử G là đơn đồ thị phẳng liờn thụng với n đỉnh và m cạnh và khụng chứa tam giỏc. Khi đú m ≤ 2n – 4.Chứng minh. Giả sử G cú f diện, khi đú từ bổ đề về cỏc cỏi bắt tay đối với đồ thị phẳng ta cú 2m ≥ 4 f (bởi vỡ bậc của diện của đơn đồ thị khụng chứa tam giỏc ớt nhất là 4), vỡ thế f ≤ 1/2 m. Theo cụng thức Euler ta cú n – m + f = 2 hay   m – n + 2 = f.Từ đú ta thu được       m – n + 2 ≤ m/2.Từ đú suy ra m ≤ 2n – 4.Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội113K3,3 khụng là đồ thị phẳngHệ quả 4. K3,3 khụng là đồ thị phẳng.Chứng minh. Giả sử K3,3 là phẳng. Do K3,3 cú 6 đỉnh, 9 cạnh và khụng chứa tam giỏc, nờn từ hệ quả 3 suy ra 9 ≤ (2ì6) – 4 = 8. Điều phi lý này đó chứng tỏ K3,3 khụng là đồ thị phẳng.Kết quả trờn đó giải quyết bài toỏn đố húc bỳa về: ba căn nhà và 3 nguồn cung cấp năng lượngPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội114Bài toỏn xõy dựng hệ thống cung cấp năng lượngTỡm cỏch xõy dựng hệ thống đường ống nối 3 nguồn cung cấp khớ ga, nước và điện cho 3 ngụi nhà sao cho chỳng khụng cắt nhau:TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội115116Chứng minh Q4 khụng phẳngTa chứng minh Q4 khụng là đồ thị phẳng.Trước hết ta tớnh số đỉnh và cạnh: |V | = 16 (gấp đụi số đỉnh của 3-cube) |E | = 32 (hai lần số cạnh của 3-cube cộng với số đỉnh của 3-cube)Bõy giờ, giả sử 4-cube là đồ thị phẳng, khi đú theo hệ quả 3 ta phải cú:32 = m  2n – 4 = 2*16 – 4 = 28 ?!Tổng quỏt: Qn khụng là đồ thị phẳng khi n  4.Nhận biết đồ thị phẳngCỏc hệ quả 1 và 3 là cỏc điều kiện cần để đồ thị là phẳng và vỡ thế chỉ cú thể sử dụng để chỉ ra một đồ thị khụng phải là phẳng. Cú nhiều đồ thị thoả món cỏc hệ quả này nhưng khụng phải là phẳng. Vỡ thế ta cần đưa ra tiờu chuẩn nhận biết đồ thị phẳng. Ta bắt đầu bằng một số nhận xộtNhận xột 1 Khụng phải mọi đồ thị là phẳng. Vớ dụ, ta đó chứng minh K5 và K3,3 khụng phẳng. Nhận xột 2 Nếu G là đồ thị phẳng thỡ mọi đồ thị con của nú cũng là phẳng; Ta thường sử dụng dạng phủ địnhNhận xột 2a: Nếu G chứa đồ thị khụng phẳng như đồ thị con thỡ G khụng là đồ thị phẳngPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội117Vớ dụ: Đồ thị G1 chứa K5 như là đồ thị con, cũn đồ thị G2 chứa K3,3 như là đồ thị con, nờn G1 và G2 khụng là đồ thị phẳng: G1 G2Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội118Nhận xột Nhận xột 3.Nếu G là phẳng thỡ mọi cỏch chia cạnh của G đều là đồ thị phẳng. Nhận xột 3a: Nếu G thu được bằng cỏch chia cạnh của một đồ thị khụng phẳng thỡ nú khụng là đồ thị phẳngVớ dụ: Đồ thị G3 thu được từ K5 cũn G4 thu được từ K3,3 G3 : G4: Từ nhận xột (2a) và (3a) ta suy ra nếu đồ thị G chứa đồ thị con thu được bằng phộp chia cạnh của K5 hoặc K3,3 thỡ G khụng phẳng..Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội119Nhận biết đồ thị phẳngĐịnh nghĩa. Ta gọi phộp chia cạnh (u,v) của đồ thị G là việc thờm vào G một đỉnh w, loại bỏ cạnh (u,v) và thờm vào hai cạnh (u,w) và (w,v).Định nghĩa. Hai đồ thị G và H được gọi là đồng phụi (homeomorphic) nếu ta cú thể thu được chỳng từ đồ thị nào đú bởi cỏc phộp chia cạnh.Vớ dụ:TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội120đồng phụi vớiđồng phụi vớiĐịnh lý KuratowskiĐịnh lý Kuratowski (1930). Đồ thị G là đồ thị phẳng khi và chỉ khi nú khụng chứa đồ thị con đồng phụi với K5 hoặc K3, 3.Vớ dụ: Đồ thị Petersen khụng là đồ thị phẳng bởi vỡ nú là đồng phụi với đồ thị K5TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội121Đồ thị Petersen K5K. Kuratowski1896-1980PolandĐồ thị EulerĐịnh nghĩaNhận biết đồ thị EulerTOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội122Đồ thị EulerChu trỡnh Euler trong đồ thị G là chu trỡnh đi qua mỗi cạnh của G đỳng một lần. Đường đi Euler trong đồ thị G là đường đi qua mỗi cạnh của G đỳng một lần. Đồ thị cú chu trỡnh Euler được gọi là đồ thị Euler. Đồ thị cú đường đi Euler được gọi là đồ thị nửa Euler. Rừ ràng mọi đồ thị Euler đều là nửa Euler.123Vớ dụ Đồ thị nửa Euler Đồ thị Euler a, c, d, b, e, d, a, b a, c, d, e, b, d, f, b, a TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội124abcdeabcdefBài toỏn về 7 cỏi cầu ở Kửnigsberg125Hiện nay là Kaliningrad (thuộc Nga)Sụng PregelABCDLeonhard Euler 1707-1783Bài toỏn về 7 cỏi cầu ở Kửnigsberg126Tồn tại hay chăng cỏch đi qua tất cả 7 cỏi cầu mỗi cỏi đỳng một lần rồi lại quay về vị trớ xuất phỏt?ABCDSơ đồ 7 cỏi cầuĐa đồ thị vụ hướng tương ứngABDCĐịnh lý EulerĐịnh lý: Đa đồ thị vụ hướng liờn thụng cú chu trỡnh Euler khi và chỉ khi nú khụng cú đỉnh bậc lẻ. Proof: (→) Đi vũng quanh chu trỡnh Euler để tớnh bậc của cỏc đỉnh, mỗi lần đi qua một đỉnh bậc của nú tăng lờn 2.(←) Xem trong giỏo trỡnh.Định lý: Đa đồ thị vụ hướng liờn thụng cú đường đi Euler khi và chỉ khi nú cú khụng quỏ 2 đỉnh bậc lẻ. Một đỉnh sẽ là đỉnh xuất phỏt, cũn đỉnh kia sẽ là đỉnh kết thỳc của đường đi Euler.127Vớ dụ Đồ thị nửa Euler Đồ thị EulerTOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội128abcdeabcdefĐỉnh bậc lẻĐỉnh bậc lẻ129Vẽ một nộtHỡnh nào trong cỏc hỡnh sau đõy cú thể tụ bởi bỳt chỡ mà khụng được nhấc bỳt khỏi mặt giấy cũng như khụng được tụ lại bất cứ đoạn nào (vẽ bởi một nột)?130Vẽ một nộtTrong ngụn ngữ đồ thị: Đồ thị nào trong hai đồ thị sau đõy cú đường đi Euler?131Vẽ một nột – Đường đi EulerTrả lời: Ngụi nhà vẽ được bởi một nột, cũn ụtụ thỡ khụng thể.startfinish123456Đồ thị HamiltonĐịnh nghĩaNhận biết đồ thị HamiltonTOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội132Đồ thị Hamilton Chu trỡnh Hamilton trong đồ thị G là chu trỡnh đi qua mỗi đỉnh của G đỳng một lần. Đường đi Hamilton trong đồ thị G là đường đi qua mỗi đỉnh của G đỳng một lần. Đồ thị cú chu trỡnh Hamilton được gọi là đồ thị Hamilton. Đồ thị cú đường đi Hamilton được gọi là đồ thị nửa Hamilton. Rừ ràng mọi đồ thị Hamilton đều là nửa Hamilton133Trũ chơi vũng quanh thế giới(Round-the-World Puzzle)134Bạn cú thể chỉ ra cỏch đi qua tất cả cỏc đỉnh của dodecahedron (thập nhị diện) mỗi đỉnh đỳng một lần?`Dodecahedron puzzleĐồ thịtương ứngHộp trũ chơiSir William Rowan Hamilton 1805-1865Vớ dụĐồ thị HamiltonTOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội135Vớ dụ: CM Qn (n  3) là đồ thị Hamilton.Chứng minh. Qui nạp theo n. Cơ sở: n=3 đỳng Chuyển qui nạp: Giả sử Qn-1 là hamilton. Xột Qn:(n -1)-cube(n -1)-cubexyy’ x’Vớ dụ3 - cubexyx’y’Đồ thị HamiltonĐồ thị cú hai đỉnh bậc 1 khụng là đồ thị HamiltonTOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội137Dễ thấy đồ thị trờn là đồ thị nửa HamiltonTutte GraphĐồ thị Tutte là 3-liờn thụng và chớnh qui bậc 3.Đồ thị Tutte khụng là đồ thị Hamilton.Đồ thị khụng là nửa HamiltonCỏc đỉnh bậc 1 phải là đỉnh bắt đầu hoặc kết thỳc của đường đi Hamilton. TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội139Đồ thị cú ba đỉnh bậc 1 khụng là nửa HamiltonĐồ thị khụng là nửa Hamilton Đồ thị sau đõy khụng là nửa Hamilton.Chỳ ý: Phần khú nhất trong chứng minh đồ thị Tutte khụng là Hamilton dựa vào kết quả này.TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội140Định lý về sự tồn tại đường đi HamiltonĐịnh lý Dirac: Nếu G là đơn đồ thị vụ hướng liờn thụng với n3 đỉnh, và v deg(v)  n/2, thỡ G cú chu trỡnh Hamilton.Định lý Ore: Nếu G đơn đồ thị vụ hướng liờn thụng với n3 đỉnh, và deg(u) + deg(v)  n với mọi cặp đỉnh khụng kề nhau u, v, thỡ G cú chu trỡnh Hamilton.141TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội142Paul Adrien Maurice Dirac1902 - 1984 (USA)Oystein Ore1899 - 1968 (Norway)HAM-CIRCUIT là NP-đầy đủGọi HAM-CIRCUIT là bài toỏn:Cho đơn đồ thị vụ hướng G, hỏi G cú chứa chu trỡnh Hamilton hay khụng?Bài toỏn này được chứng minh là thuộc lớp bài toỏn NP-đầy đủ!Cú nghĩa là, nếu như tỡm được thuật toỏn để giải nú trong thời gian đa thức, thỡ thuật toỏn này cú thể sử dụng để giải mọi bài toỏn thuộc lớp NP trong thời gian đa thức.143Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội144Chương 1 CÁC KHÁI NIỆM CƠ BẢN1.1. Đồ thị trong thực tế1.2. Cỏc loại đồ thị1.3. Bậc của đỉnh1.4. Đồ thị con1.5. Đồ thị đẳng cấu1.6. Đường đi và chu trỡnh1.7. Tớnh liờn thụng1.8. Một số loại đồ thị đặc biệt1.9. Tụ màu đồ thịTụ màu đồ thịGraph Coloring Tụ màu đỉnh (Vertex Coloring) Tụ màu cạnh (Edge Coloring)Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội145146Tụ màu đồ thị - Graph ColoringXột bản đồ147Tụ màu bản đồ - Map ColoringTa muốn nhận biết cỏc nước bằng cỏch tụ màu. Rừ ràng: Tụ bởi 1 màu là khụng thể phõn biệt được:148Map ColoringBổ sung thờm 1 màu nữa. Thử tụ cỏc nước bởi 2 màu. 149Map Coloring Cho phộp sử dụng hai màu, ta thử tụ mỗi nước bởi một trong hai màu.150Map Coloring Cho phộp sử dụng hai màu, ta thử tụ mỗi nước bởi một trong hai màu.151Map Coloring Cho phộp sử dụng hai màu, ta thử tụ mỗi nước bởi một trong hai màu.152Map Coloring Hai nước bị tụ bởi cựng màu. Khụng phõn biệt được danh giới. 153Map ColoringVậy thỡ thờm 1 màu nữa:154Map ColoringVẫn khụng đủ. Cần ớt ra là 4 màu bởi vỡ chớnh nước này.155Map ColoringVới 4 màu, cú thể tụ được.1564-Color Theorem Định lý 4 màu: Mọi bản đồ hành chớnh đều cú thể tụ bởi bốn màu sao cho khụng cú 2 đơn vị hành chớnh cú chung biờn giới nào bị tụ bởi cựng màu. Proof. Năm 1976, Haken và Appel chứng minh được định lý 4 màu “bằng mỏy tớnh”. (Thực hiện kiểm tra tụ bởi 4 màu gần 2000 bản đồ đặc biệt bằng mỏy tớnh.)157Từ tụ màu bản đồ đến tụ màu đồ thị Bài toỏn tụ màu bản đồ cú thể dẫn về bài toỏn tụ màu đồ thị:158Từ tụ màu bản đồ đến tụ màu đồ thịMỗi vựng đặt tương ứng với một đỉnh:159Từ tụ màu bản đồ đến tụ màu đồ thịHai vựng cú chung biờn giới cú cạnh nối: 160Từ tụ màu bản đồ đến tụ màu đồ thị Thực ra, ta cũng cú thể xem bản đồ là đồ thị và khi đú sẽ xột đồ thị đối ngẫu của nú. 161Từ tụ màu bản đồ đến tụ màu đồ thịĐồ thị đối ngẫu (Dual Graphs) :1) Đặt mỗi miền ứng với 1 đỉnh: 162Từ tụ màu bản đồ đến tụ màu đồ thịĐồ thị đối ngẫu (Dual Graphs) :2) Nối cỏc đỉnh bởi cỏc cạnh:163Định nghĩa đồ thị đối ngẫuĐịnh nghĩa: Đồ thị đối ngẫu G* của đồ thị phẳng G = (V, E) với tập cỏc miền R là đồ thị với tập đỉnh và cạnh được xõy dựng như sauTập đỉnh của G*: V (G*) = R Tập cạnh của G*: E (G*) = tập cỏc cạnh dạng (F1,F2) trong đú 2 miền F1 và F2 cú cạnh chung.164Từ tụ màu bản đồ đến tụ màu đồ thịNhư vậy đồ thị đối ngẫu là:165Từ tụ màu bản đồ đến tụ màu đồ thị Tụ màu miền tương đương với tụ màu đỉnh của đồ thị đối ngẫu.166Định nghĩa sắc sốĐịnh nghĩa: Giả sử c là số nguyờn dương. Đơn đồ thị vụ hướng được gọi là tụ được bởi c màu nếu cú thể tụ cỏc đỉnh của nú bởi c màu sao cho khụng cú hai đỉnh kề nhau nào bị tụ bởi cựng một màu. Sắc số (chromatic number) của đồ thị G, ký hiệu bởi (G), là số c nhỏ nhất sao cho cú thể tụ được G bởi c màu.Vớ dụ: Ta cú (G) = 2, nếu G là đồ thị hai phớa. Dễ thấy điều ngược lại cũng đỳng.Rừ ràng (G)  (G).167Từ tụ màu bản đồ đến tụ màu đồ thị Bản đồ khụng tụ được bởi 2 màu, vỡ thế đồ thị đối ngẫu khụng tụ được bởi 2 màu:168Từ tụ màu bản đồ đến tụ màu đồ thị Bản đồ khụng tụ được bởi 3 màu, vỡ thế đồ thị đối ngẫu khụng tụ được bởi 3 màu:169Từ tụ màu bản đồ đến tụ màu đồ thị Đồ thị tụ được bởi 4 màu vỡ thế bản đồ cũng tụ được bởi 4 màu:170Định lý 4 màu trong ngụn ngữ đồ thịĐịnh lý. Mọi đồ thị phẳng đều tụ được bởi 4 màu.Thuật toỏn tham lamKhởi tạo. Sắp xếp cỏc đỉnh của đồ thị theo thứ tự v1, v2, , vn Bước i (i=1, 2,..., n): Tụ đỉnh vi bởi màu cú chỉ số nhỏ nhất trong số cỏc màu chưa được sử dụng để tụ cỏc đỉnh kề của nú.1234561234561243Chỳ ý: Kết quả thực hiện thuật toỏn là phụ thuộc vào trỡnh tự sắp xếp cỏc đỉnh của đồ thị.1342Cận trờn cho sắc số Định lý. Đối với đơn đồ thị vụ hướng bất kỳ G ta cú (G)  (G)+1.Chứng minhTrong dóy đỉnh, mỗi đỉnh cú nhiều nhất (G) đỉnh kề. Do đú, thuật toỏn tham lam khụng thể sử dụng nhiều hơn (G)+1 màu.Một cận trờn tốt hơn được cho trong định lý sau đõy Định lý Brook (1941). Giả sử G là đơn đồ thị vụ hướng liờn thụng khỏc với đồ thị đầy đủ và chu trỡnh độ dài lẻ. Khi đú (G)  (G).173Tụ màu đồ thị và Lập lịchVớ dụ: Ta cần lập lịch thi kết thỳc mụn học cho cỏc chuyờn đề cú mó số: 1007, 3137, 3157, 3203, 3261, 4115, 4118, 4156Giả sử cỏc mụn học sau khụng cú sinh viờn nào đồng thời cựng thi (do điều kiện tiờn quyết) :1007-31371007-3157, 3137-31571007-32031007-3261, 3137-3261, 3203-32611007-4115, 3137-4115, 3203-4115, 3261-41151007-4118, 3137-41181007-4156, 3137-4156, 3157-4156Hỏi lịch thi gồm ớt nhất bao nhiờu ngày? (Lịch thi phải đảm bảo mỗi sinh viờn trong một ngày phải thi khụng quỏ 1 mụn)174Tụ màu đồ thị và Lập lịchĐưa bài toỏn về bài toỏn tụ màu đồ thị: Cỏc đỉnh tương ứng với cỏc mụn học, cạnh nối cú giữa hai đỉnh nếu hai mụn tương ứng cú thể cú chung sinh viờn dự thi (vỡ thế khụng được tổ chức đồng thời):10073137315732034115326141564118175Tụ màu đồ thị và Lập lịchTrước hết ta đưa vào cạnh nối giữa cỏc mụn chắc chắc khụng cú chung sinh viờn (từ điều kiện tiờn quyết)10073137315732034115326141564118176Tụ màu đồ thị và Lập lịchvà sau đú xõy dựng đồ thị bự (complementary graph):10073137315732034115326141564118177Tụ màu đồ thị và Lập lịchvà sau đú làm việc với đồ thị bự (chỉ cỏc mụn học cú cạnh nối mới cú thể cú chung sinh viờn):10073137315732034115326141564118178Tụ màu đồ thị và Lập lịchVẽ lại:10073137315732034115326141564118179Tụ màu đồ thị và Lập lịchKhụng thể tụ bởi 1 màu vỡ cạnh này10073137315732034115326141564118180Tụ màu đồ thị và Lập lịch100731373157320341153261415641182 màu khụng đủ tụ vỡ cú tam giỏc này181Tụ màu đồ thị và Lập lịch 3 màu là đủ tụ tam giỏc này. Ta tụ bởi ba màu Red, Green, Blue.10073137315732034115326141564118182Tụ màu đồ thị và Lập lịch 3203-Red, 3157-Blue, 4118-Green:10073137315732034115326141564118183Tụ màu đồ thị và Lập lịchdo đú 4156 phải tụ bởi Blue:10073137315732034115326141564118184Tụ màu đồ thị và Lập lịchvỡ thế 3261 và 4115 phải là Red.10073137315732034115326141564118185Tụ màu đồ thị và Lập lịch3137 và 1007 dễ dàng tụ.10073137315732034115326141564118186Tụ màu đồ thị và Lập lịchVậy cần 3 ngày:Ngày 1Ngày 2Ngày 310073137315732034115326141564118Tụ màu cạnhỞ phần trờn ta xột tụ màu đỉnh của đồ thị. Một cỏch hoàn toàn tương tự, ta cú thể phỏt biểu bài toỏn tụ màu cạnh của đồ thị.Định nghĩa. Ta gọi một phộp tụ màu cạnh của đơn đồ thị vụ hướng G=(V,E) là phộp gỏn cho mỗi cạnh của đồ thị một màu sao cho khụng cú hai cạnh cú chung đỉnh nào bị tụ bởi một màu. Số màu ớt nhất cần sử dụng để tụ màu cỏc cạnh của đồ thị G được gọi là sắc số cạnh và ký hiệu là ’(G)Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội187Tụ màu cạnhĐịnh lý Vizing. Đối với đơn đồ thị vụ hướng G ta cú (G)  ’(G)  (G)+1.Chứng minh.Vế trỏi của bất đẳng thức là hiển nhiờnVế phải cú thể chứng minh bằng qui nạpĐịnh lý. Đối với đơn đồ thị hai phớa G ta cú ’(G) = (G).Chứng minh. Thuật toỏn tụ màu /Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội188Thuật toỏn tụ màu /Ký hiệu C = {1, 2, , (G)} là tập màu được sử dụng. Lần lượt tụ màu cỏc cạnh của đồ thị theo qui tắc sau:Giả sử ta đang xột việc tụ màu cạnh e=(u,v). Ký hiệu M(z) là tập màu đó dựng để tụ cỏc cạnh kề của đỉnh z. Rừ ràng |M(u)| ) (tốt hơn ma trận kề)Hai đỉnh i, j cú kề nhau? Tỡm kiếm trờn danh sỏch: (degree(i)). Đỏnh giỏ trong tỡnh huống tồi nhất là O(|V|) => khụng hiệu quả (tồi hơn ma trận kề)Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội206Chương 3Các thuật toán duyệt đồ thị (Graph Searching, Graph Traversal)Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội207Cỏc thuật toỏn duyệt đồ thịDuyệt đồ thị: Graph Searching hoặc Graph TraversalDuyệt qua mỗi đỉnh và mỗi cạnh của đồ thịỨng dụng:Cần để khảo sỏt cỏc tớnh chất của đồ thịLà thành phần cơ bản của nhiều thuật toỏn trờn đồ thịHai thuật toỏn duyệt cơ bản: Tỡm kiếm theo chiều rộng (Breadth First Search – BFS) Tỡm kiếm theo chiều sõu (Depth First Search – DFS)Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội208í tưởng chung của cỏc thuật toỏn duyệtí tưởng chung: Trong quỏ trỡnh thực hiện thuật toỏn, mỗi đỉnh ở một trong ba trạng thỏi: Chưa thăm, thể hiện bởi màu trắngĐó thăm (nhưng chưa duyệt xong), thể hiện bởi màu xỏmĐó duyệt xong, thể hiện bởi màu đenTrạng thỏi của đỉnh sẽ biến đổi theo qui tắc sau:Thoạt đầu mỗi đỉnh đều cú màu trắng (chưa thăm - not visited).Đỉnh đó được thăm sẽ chuyển thành màu xỏm (trở thành đó thăm nhưng chưa duyệt xong - visited).Khi tất cả cỏc đỉnh kề của một đỉnh v là đó được thăm, đỉnh v sẽ cú màu đen (đó duyệt xong – discovered).Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội209Tỡm kiếm theo chiều rộngBreadth-first Search (BFS)Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội210Tỡm kiếm theo chiều rộngBreadth-first SearchInput: Đồ thị G = (V, E), vụ hướng hoặc cú hướng.Output: d[v] = khoảng cỏch (độ dài của đường đi ngắn nhất) từ s (là đỉnh xuất phỏt tỡm kiếm) đến v, với mọi v  V. d[v] =  nếu v khụng đạt tới được từ s.[v] = u đỉnh đi trước v trong đường đi từ s (là đỉnh xuất phỏt tỡm kiếm) đến v cú độ dài d[v].Xõy dựng cõy BFS với gốc tại s chứa tất cả cỏc đỉnh đạt tới được từ s.Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội211Procedure BFS(s); (* Tỡm kiếm theo chiều rộng bắt đầu từ đỉnh s *)begincolor[s]  gray;d[s]  0; [s]  nil;Q  ; enqueue(Q,s); (* Nạp s vào Q *)while Q   do begin u  dequeue(Q); (* Lấy u từ Q *) for v Adj[u] do if color[v] = white then begin color[v]  gray; d[v]  d[u] + 1; [v]  u; enqueue(Q,v) (* Nạp v vào Q *) end; color[u]  blackend;end;BEGIN (* Main Program*)for v  V do (* Khởi tạo *)begin color[v]  white; d[v]  ; [v]  nil;end;for v  V do if color[v]=white then BFS(v);END.Trắng: chưa thămxỏm: đó thămđen: đó duyệt xongQ: hàng đợi cỏc đỉnh được thămcolor[v]: màu của đỉnh vd[v]: khoảng cỏch từ s đến v[u]: đỉnh đi trước vVớ dụ: xem minh hoạPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội212Vớ dụ (BFS)0rstuvwxyQ: s 0Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội213Vớ dụ (BFS) 101rstuvwxyQ: w r 1 1Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội214Vớ dụ (BFS)10122rstuvwxyQ: r t x 1 2 2Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội215Vớ dụ (BFS)101222rstuvwxyQ: t x v 2 2 2Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội216Vớ dụ (BFS)1012232rstuvwxyQ: x v u 2 2 3Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội217Vớ dụ (BFS)10123232rstuvwxyQ: v u y 2 3 3Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội218Vớ dụ (BFS)10123232rstuvwxyQ: u y 3 3Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội219Vớ dụ (BFS)10123232rstuvwxyQ: y 3Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội220Vớ dụ (BFS)10123232rstuvwxyQ: Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội221Vớ dụ (BFS)10123232rstuvwxyCõy BFS(s)Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội222Phõn tớch BFSViệc khởi tạo đũi hỏi O(|V|).Vũng lặp duyệtMỗi đỉnh được nạp vào và loại ra khỏi hàng đợi một lần, mỗi thao tỏc đũi hỏi thời gian O(1). Như vậy tổng thời gian làm việc với hàng đợi là O(V).Danh sỏch kề của mỗi đỉnh được duyệt qua đỳng một lần. Tổng độ dài của tất cả cỏc danh sỏch kề là (|E|).Tổng cộng ta cú thời gian tớnh của BFS(s) là O(|V|+|E|),là tuyến tớnh theo kớch thước của danh sỏch kề biểu diễn đồ thị. Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội223Cõy BFS(s)Đối với đồ thị G = (V, E) và đỉnh s. Thực hiện BFS(s), xột đồ thị con G = (V , E) trong đú V ={vV : [v]  NIL}{s} E ={([v],v) E : v  V \ {s}} G = (V , E) là cõy và được gọi là cõy BFS(s)Cỏc cạnh trong E được gọi là cạnh của cõy. |E | = |V | - 1.BFS(s) cho phộp đến thăm tất cả cỏc đỉnh đạt tới được từ s.Trỡnh tự thăm cỏc đỉnh khi thực hiện BFS(s): Đầu tiờn đến thăm cỏc đỉnh đạt được từ s bởi đường đi qua 1 cạnh, sau đú là thăm cỏc đỉnh đạt được từ s bởi đường đi qua 2 cạnh, Do đú nếu đỉnh t được thăm trong BFS(s) thỡ nú sẽ được thăm theo đường đi ngắn nhất theo số cạnh.Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội224BFS – Loang trờn đồ thịThứ tự thăm đỉnh nhờ thực hiện BFS(A)CBAEDFCBAEDL0L1FL2Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội225Ứng dụng trực tiếp cuả BFSSử dụng BFS để kiểm tra tớnh liờn thụng của đồ thị vụ hướng:Mỗi lần gọi đến BFS ở trong chương trỡnh chớnh sẽ sinh ra một thành phần liờn thụngXột sự tồn tại đường đi từ đỉnh s đến đỉnh t:Thực hiện BFS(s).Nếu [t] = NIL thỡ khụng cú đường đi, trỏi lại ta cú đường đi t  [t]  [[ t]]  . . .  sChỳ ý: BFS tỡm được đường đi ngắn nhất theo số cạnh.Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội226Tỡm kiếm theo chiều sõuDepth-first Search (DFS)Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội227í tưởng của tỡm kiếm theo chiều sõuTa sẽ bắt đầu tìm kiếm từ một đỉnh s nào đó của đồ thị. Sau đó chọn u là một đỉnh tuỳ ý kề với s và lặp lại quá trình đối với u. ở bước tổng quát, giả sử ta đang xét đỉnh v: Nếu như trong số các đỉnh kề với v tìm được đỉnh w là chưa được thăm thì ta sẽ thăm đỉnh này (nó sẽ trở thành đã thăm nhưng chưa duyệt xong) và bắt đầu từ nó ta sẽ tiếp tục quá trình tìm kiếm. Nếu như không còn đỉnh nào kề với v là chưa thăm thì ta sẽ nói rằng đỉnh này là đã duyệt xong và quay trở lại tiếp tục tìm kiếm từ đỉnh mà trước đó ta đến được đỉnh v (nếu v = s, thì kết thúc tìm kiếm). Có thể nói nôm na là tìm kiếm theo chiều sâu bắt đầu từ đỉnh s được thực hiện trên cơ sở tìm kiếm theo chiều sâu từ tất cả các đỉnh chưa thăm kề với s. Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội228Mụ tả DFSInput: Đồ thị G = (V, E) cho bởi danh sỏch kềOutput:2 mốc thời gian cho mỗi đỉnh (là cỏc số nguyờn trong khoảng 1 và 2|V|).d[v] = thời điểm bắt đầu thăm (v chuyển từ trắng sang xỏm)f [v] = thời điểm kết thỳc thăm (v chuyển từ xỏm sang đen)[v] : đỉnh đi trước v – tức là đỉnh mà từ đú ta đến thăm v.Sử dụng biến color để ghi nhận trạng thỏi của cỏc đỉnh như đó mụ tả.Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội229Depth-First Search: CodeDFS(G)BEGIN for vV do begin color[v] = WHITE; [v] = NIL end; time = 0; for uV do begin if (color[u]= WHITE) then DFS(u); end;END.procedure DFS(u);begin color[u] = GRAY; time = time+1; d[u] = time; for v  Ke(u)do if (color[v]= WHITE)then begin [v] = u; DFS(v); end; color[u] = BLACK; time = time+1; f[u] = time;end;Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội230Phõn tớch thuật toỏn DFSMỗi đỉnh được thăm đỳng 1 lần, việc thăm mỗi đỉnh đũi hỏi chi phớ thời gian O(1), suy ra thao tỏc thăm đỉnh đũi hỏi thời gian O(|V|). Vũng lặp trong DFS(u) thực hiện việc duyệt cạnh của đồ thịMỗi cạnh được duyệt qua đỳng một lần nếu đồ thị là cú hướng và 2 lần nếu đồ thị là vụ hướngNhư vậy tổng số lần lặp là O(|E|). Vậy, thuật toỏn cú thời gian O(|V|+|E|)Đối với đồ thị, thuật toỏn cú đỏnh giỏ như vậy gọi là thuật toỏn thời gian tuyến tớnhPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội231Vớ dụ: DFS Đỉnh xuất phỏt tỡm kiếm (Source vertex)adehgfcbĐể hoạt động của thuật toỏn là xỏc định, giả thiết rằng ta duyệt cỏc đỉnh trong danh sỏch kề của một đỉnh theo thứ tự từ điểnPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội232Vớ dụ: DFS 1 | | | | | | | | sourcevertexd[v] f[v]abfehgdcPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội233Vớ dụ: DFS 1 | | | | | | 2 | | sourcevertexagfehdcbPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội234Vớ dụ: DFS 1 | | | | | 3 | 2 | | sourcevertexaghfdecbPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội235Vớ dụ: DFS 1 | | | | | 3 | 42 | | sourcevertexahgfedcbPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội236Vớ dụ: DFS 1 | | | | 5 | 3 | 42 | | sourcevertexahgfedcbPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội237Vớ dụ: DFS 1 | | | | 5 | 63 | 42 | | sourcevertexagfehdcbPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội238Vớ dụ: DFS 1 | 8 | | | 5 | 63 | 42 | 7 | sourcevertexahfgedbcPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội239Vớ dụ: DFS 1 | 8 | | | 5 | 63 | 42 | 7 | sourcevertexagfehdcbPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội240Vớ dụ: DFS 1 | 8 | | | 5 | 63 | 42 | 79 | sourcevertexcabghfdePhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội241Vớ dụ: DFS 1 | 8 | | | 5 | 63 | 42 | 79 |10sourcevertexafbcdeghPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội242Vớ dụ: DFS 1 | 8 |11 | | 5 | 63 | 42 | 79 |10sourcevertexabecfdhgPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội243Vớ dụ: DFS1 |128 |11 | | 5 | 63 | 42 | 79 |10sourcevertexacbdegfhPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội244Vớ dụ: DFS 1 |128 |1113| | 5 | 63 | 42 | 79 |10sourcevertexaebcgdhfPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội245Vớ dụ: DFS 1 |128 |1113| 14| 5 | 63 | 42 | 79 |10sourcevertexaebgdchfPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội246Vớ dụ: DFS1 |128 |1113| 14|155 | 63 | 42 | 79 |10sourcevertexaebdcgfhPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội247Vớ dụ: DFS 1 |128 |1113|1614|155 | 63 | 42 | 79 |10sourcevertexaebdcgfhPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội248DFS: Cỏc loại cạnhDFS(G) sinh ra một cỏch phõn loại cỏc cạnh của đồ thị đó cho:Cạnh của cõy (Tree edge): là cạnh mà theo đú từ một đỉnh ta đến thăm một đỉnh mới (cạnh đi vào đỉnh trắng) Cỏc cạnh này tạo thành một rừng gọi là rừng tỡm kiếm DFS. Cỏc đỉnh được thăm khi thực hiện DFS(v) và cỏc cạnh của cõy tạo thành cõy được gọi là cõy DFS(v)Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội249Vớ dụ: Rừng DFS 1 |128 |1113|1614|155 | 63 | 42 | 79 |10sourcevertex aTree edgesCõy DFS(a)sourcevertex gCõy DFS(g)aedcgfhbPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội250DFS: Cạnh ngượcDFS tạo ra một cỏch phõn loại cỏc cạnh của đồ thị đó cho:Cạnh của cõy (Tree edge): là cạnh mà theo đú từ một đỉnh ta đến thăm một đỉnh mới (cạnh đi vào đỉnh trắng) Cạnh ngược (Back edge): đi từ con chỏu (descendent) đến tổ tiờn (ancestor)Đi vào đỉnh xỏm (đi từ đỉnh xỏm đến đỉnh xỏm)Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội251Vớ dụ: DFS Cạnh ngược1 |128 |1113|1614|155 | 63 | 42 | 79 |10sourcevertexTree edgesBack edgesadecgfhbPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội252DFS: Cạnh tớiDFS tạo ra một cỏch phõn loại cỏc cạnh của đồ thị đó cho:Cạnh của cõy (Tree edge): là cạnh mà theo đú từ một đỉnh ta đến thăm một đỉnh mới (cạnh đi vào đỉnh trắng) Cạnh ngược (Back edge): đi từ con chỏu (descendent) đến tổ tiờn (ancestor)Cạnh tới (Forward edge): đi từ tổ tiờn đến con chỏuKhụng là cạnh của cõyĐi từ đỉnh xỏm đến đỉnh đenPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội253Vớ dụ: DFS Cạnh tới1 |128 |1113|1614|155 | 63 | 42 | 79 |10sourcevertexTree edgesBack edgesForward edgesadcgfhebPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội254DFS: Cạnh vũngDFS tạo ra một cỏch phõn loại cỏc cạnh của đồ thị đó cho:Cạnh của cõy (Tree edge): là cạnh mà theo đú từ một đỉnh ta đến thăm một đỉnh mới (cạnh đi vào đỉnh trắng) Cạnh ngược (Back edge): đi từ con chỏu (descendent) đến tổ tiờn (ancestor)Cạnh tới (Forward edge): đi từ tổ tiờn đến con chỏuCạnh vũng (Cross edge): cạnh nối hai đỉnh khụng cú quan hệ họ hàngKhụng là cạnh của cõy, và giống như cạnh vũng cũngĐi từ đỉnh xỏm đến đỉnh đenPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội255Vớ dụ: DFS Cạnh vũng1 |128 |1113|1614|155 | 63 | 42 | 79 |10sourcevertexTree edgesBack edgesForward edgesCross edgesafdhgcebPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội256DFS: Cỏc loại cạnhDFS tạo ra một cỏch phõn loại cỏc cạnh của đồ thị đó cho:Tree edge: cạnh theo đú từ một đỉnh đến thăm đỉnh mới (trắng) Back edge: đi từ con chỏu đến tổ tiờnForward edge: đi từ tổ tiờn đến con chỏuCross edge: giữa hai đỉnh khụng cú họ hàngChỳ ý: Cạnh của cõy & cạnh ngược là quan trọng; nhiều thuật toỏn khụng đũi hỏi phõn biệt cạnh tới và cạnh vũngPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội257DFS: Cỏc loại cạnhĐịnh lý: Nếu G là đồ thị vụ hướng, thỡ DFS chỉ sản sinh ra cạnh của cõy và cạnh ngược.Chứng minh bằng phản chứng:Giả sử cú cạnh tới (forward edge)Nhưng khi đú F phải là cạnh ngược (back edge)?!sourceF?Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội258DFS: Cỏc loại cạnhGiả sử cú cạnh vũng (cross edge)Khi đú C khụng thể là cạnh vũng bởi vỡ:Nú phải được khảo sỏt từ một trong hai đỉnh đầu mỳt và trở thành cạnh của cõy trước khi đỉnh kia được khảo sỏtDo đú bức tranh bờn là khụng đỳngcả hai cạnh bờn khụng thể là cạnh của cõysourceC?Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội259DFS: Phõn biệt cỏc loại cạnhDễ dàng phõn biệt cỏc loại cạnh nhờ phân tích màu của các đỉnh và/hoặc xét các giá trị của các mốc thời gian d và f. Khi ta duyệt cạnh e=(u, v) từ đỉnh u, căn cứ vào màu của v ta cú thể biết cạnh này thuộc loại cạnh nào:1. WHITE cho biết e là cạnh của cõy2. GRAY cho biết e là cạnh ngượcBLACK cho biết e là cạnh tới hoặc vũngPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội260Phõn tớch DFS(* Main Program*)1. for u  V do2. color[u]  white3. [u]  NIL4. time  05. for u  V do6. if color[u] = white7. then DFS-Visit(u)Cỏc biến time, color,  là toàn cục .DFS-Visit(u)color[u]  GRAY (* Thăm đỉnh u *)time  time + 1 d[u]  time for each v  Adj[u] do if color[v] = WHITE then [v]  u DFS-Visit(v) color[u]  BLACK (* Đỉnh u đó duyệt xong *) f[u]  time  time + 1Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội261Phõn tớch DFSVũng lặp trờn cỏc dũng 1-2 và 5-7 đũi hỏi thời gian (|V|), chưa tớnh thời gian thực hiện lệnh DFS(v).DFS(v) thực hiện đối với mỗi đỉnh trắng vV và ngay sau khi được thăm nú được tụ màu xỏm. Cỏc dũng 3-6 của DFS(v) sẽ thực hiện |Adj[v]| lần. Vậy thời gian tổng cộng của DFS(v) là vV|Adj[v]| = (|E|) Do đú thời gian của DFS là (|V|+|E|).Thuật toỏn trờn đồ thị cú đỏnh giỏ thời gian như trờn gọi là thuật toỏn thời gian tuyến tớnhPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội262CÁC ỨNG DỤNG CỦA DFSTớnh liờn thụng của đồ thịTỡm đường đi từ s đến t Phỏt hiện chu trỡnh Kiểm tra tớnh liờn thụng mạnh Định hướng đồ thịPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội263Bài toỏn về tớnh liờn thụngBài toỏn: Cho đồ thị vụ hướng G = (V,E). Hỏi đồ thị gồm bao nhiờu thành phần liờn thụng, và từng thành phần liờn thụng gồm cỏc đỉnh nào?Giải: Sử dụng DFS (BFS) :Mỗi lần gọi đến DFS (BFS) ở trong chương trỡnh chớnh sẽ sinh ra một thành phần liờn thụngPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội264DFS giải bài toỏn liờn thụng(* Main Program*)1. for u  V do2. id[u]  03. cnt  0 (* cnt – số lượng tplt *)4. for u  V do5. if id[u] = 0 then cnt  cnt +1 DFS-Visit(u) DFS-Visit(u)id[u]  cnt for each v  Adj[u] do if id[v] = 0 then DFS-Visit(v)Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội265Tỡm đường điBài toỏn tỡm đường điInput: Đồ thị G = (V,E) xỏc định bởi danh sỏch kề và hai đỉnh s, t.Đầu ra: Đường đi từ đỉnh s đến đỉnh t, hoặc khẳng định khụng tồn tại đường đi từ s đến t.Thuật toỏn: Thực hiện DFS(s) (hoặc BFS(s)).Nếu [t] = NIL thỡ khụng cú đường đi, trỏi lại ta cú đường đi t  [t]  [[ t]]  . . .  sPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội266DFS giải bài toỏn đường đi(* Main Program*)1. for u  V do2. color[u]  white3. [u]  NIL4. DFS-Visit(s)DFS-Visit(u)color[u]  GRAY (* Thăm đỉnh u *)for each v  Adj[u] do if color[v] = WHITE then [v]  u DFS-Visit(v)Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội267DFS và Chu trỡnhBài toỏn: Cho đồ thị G=(V,E). Hỏi G cú chứa chu trỡnh hay khụng?Định lý: Đồ thị G là khụng chứa chu trỡnh khi và chỉ khi trong quỏ trỡnh thực hiện DFS ta khụng phỏt hiện ra cạnh ngược.Chứng minh:Nếu G khụng chứa chu trỡnh thỡ rừ ràng khụng cú cạnh ngược (bởi vỡ sự tồn tại cạnh ngược dẫn đến phỏt hiện chu trỡnh) Nếu khụng cú cạnh ngược thỡ G là khụng chứa chu trỡnh (acyclic). Thực vậyKhụng cú cạnh ngược tức là chỉ cú cạnh của cõyNếu chỉ cú cạnh của cõy thỡ G chỉ là cõy hoặc rừngVậy G khụng chứa chu trinhNhư vậy DFS cú thể ỏp dụng để giải bài toỏn đặt ra.Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội268DFS và chu trỡnh (* Main Program*)1. for u  V do2. color[u]  white3. [u]  NIL4. time  05. for u  V do6. if color[u] = white7. then DFS-Visit(u)DFS(u)color[u]  GRAY (* Thăm đỉnh u *)time  time + 1 d[u]  time for each v  Adj[u] do if color[v] = WHITE then [v]  u DFS-Visit(v) color[u]  BLACK (* Đỉnh u đó duyệt xong *) f[u]  time  time + 1Cần phải điều chỉnh như thế nào để phỏt hiện chu trỡnh?Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội269DFS và chu trỡnhCõu hỏi: Thời gian tớnh là bao nhiờu?Trả lời: Chớnh là thời gian thực hiện DFS: O(|V|+|E|).Cõu hỏi: Nếu G là đồ thị vụ hướng thỡ cú thể đỏnh giỏ thời gian tớnh sỏt hơn nữa được khụng?Trả lời: Thuật toỏn cú thời gian tớnh O(|V|), bởi vỡ:Trong một rừng (đồ thị khụng chứa chu trỡnh) |E|  |V| - 1 Vỡ vậy nếu đồ thị cú |V| cạnh thỡ chắc chắn nú chứa chu trỡnh, và thuật toỏn kết thỳc.Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội270Kiểm tra tớnh liờn thụng mạnhBài toỏn: Hỏi đồ thị cú hướng G cú là liờn thụng mạnh?Mệnh đề: Đồ thị cú hướng G=(V,E) là liờn thụng mạnh khi và chỉ khi luụn tỡm được đường đi từ một đỉnh v đến tất cả cỏc đỉnh cũn lại và luụn tỡm được đường đi từ tất cả cỏc đỉnh thuộc V \ {v} đến v.Chứng minh: Hiển nhiờnPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội271Thuật toỏn kiểm tra tớnh liờn thụng mạnhThuật toỏn.Chọn v  V là một đỉnh tuỳ ýThực hiện DFS(v) trên G. Nếu tồn tại đỉnh u không được thăm thì G không liên thông mạnh và thuật toán kết thúc. Trái lại thực hiện tiếpThực hiện DFS(v) trên GT = (V, ET), với ET thu được từ E bởi việc đảo ngược hướng các cung. Nếu tồn tại đỉnh u không được thăm thì G không liên thông mạnh, nếu trái lại G là liên thông mạnh.Thời gian tớnh: O(|V|+|E|)cadebfPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội272Thuật toỏn kiểm tra tớnh liờn thụng mạnh Đồ thị G Đồ thị GTcadebfcadebfPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội273Định hướng đồ thịBài toán: Cho đồ thị vô hướng liên thông G= (V, E). Hãy tìm cách định hướng các cạnh của nó để thu được đồ thị có hướng liên thông mạnh hoặc trả lời G là không định hướng được.Thuật toán định hướng : Trong quá trình thực hiện DFS(G) định hướng các cạnh của cây DFS theo chiều từ tổ tiên đến con cháu, các cạnh ngược theo hướng từ con cháu đến tổ tiên. Ký hiệu đồ thị thu được là G()Bổ đề. G là định hướng được khi và chỉ khi G() là liên thông mạnh.Phần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội274Vớ dụ: Định hướng đồ thị Đồ thị G Đồ thị G()cadebfcadebfaPhần 2. Lí THUYẾT ĐỒ THỊNguyễn Đức Nghĩa- Bộ mụn KHMT, ĐHBK Hà nội275Questions?