Bài giảng Lý thuyết đồ thị - Nguyễn Văn Lễ

Nội dung text: Bài giảng Lý thuyết đồ thị - Nguyễn Văn Lễ

1. GIỚI THIỆU MƠN HỌC Tên mơn học: Lý thuyết đờ thị  Sớ tiết: 30 LT  Hình thức đánh giá: -Thi giữa kỳ: 20% -Bài tập lớn: 30% -Thi cuới kỳ: 50% Giáo viên: Nguyễn Văn Lễ 1
2. Nợi dung CHƯƠNG 1: CÁC KHÁI NIỆM CƠ BẢN CHƯƠNG 2: BIỂU DIỄN ĐỜ THỊ TRÊN MÁY TÍNH CHƯƠNG 3: CÁC THUẬT TOÁN DUYỆT ĐỜ THỊ CHƯƠNG 4: ĐỜ THỊ EULER VÀ ĐỜ THỊ HAMILTON CHƯƠNG 5: CÂY CHƯƠNG 6: BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT 2
3. CHUƠNG 1: CÁC KHÁI NIỆM CƠ BẢN Định nghĩạ đờ thị: • Mợt đờ thị ký hiệu là G=(V,E), trong đó V: tập đỉnh E={(u,v) | u,v V}: tập cạnh n=|V| gọi là cấp của đờ thị • Đờ thị vơ hướng: Là đờ thị gờm các cạnh vơ hướng (khơng thứ tự): (u,v) E; (v,u) E 2 3 V={1,2,3,4} E={(1,2), (1,3), (2,3), (3,4)} 1 4 3
4. Định nghĩa đờ thị • Đờ thị có hướng: là đờ thị gờm các cạnh có thứ tự được gọi là cung. 2 3 V={1,2,3,4} E={(1,2),(2,3),(3,1),(5,3)} 4 1 5 • Đơn đờ thị: Mỡi cặp đỉnh chỉ có duy nhất mợt cạnh (cung) 2 3 2 3 1 4 5 1 4 5 4
5. Định nghĩa đờ thị • Đa đờ thị: mỡi cặp đỉnh có thể có mợt hay nhiều cạnh (cung) 2 3 2 3 1 4 5 1 4 5 • Đờ thị có trọng sớ: trên mỡi cạnh (cung) được gắn mợt giá trị gọi là trọng sớ -2 2 2 3 2 3 5 3 1 2 1 1 3 1 4 3 5 1 4 5 5
6. Mợt sớ khái niệm Mợt sớ khái niệm: • Khuyên: cạnh (cung) gọi là khuyên nếu đỉnh đầu trùng với đỉnh cuới. 1 • Cạnh (cung) lặp: là hai cạnh (cung) cùng tương ứng với mợt cặp đỉnh. 1 2 1 2 • Đỉnh kề: nếu (u,v) là cạnh (cung) của đờ thị thì v gọi là kề của u. Trong đờ thị vơ hướng nếu v kề u thì u cũng kề v. 6
7. Mợt sớ khái niệm • Cạnh liên thuộc: cạnh e=(u,v) gọi là cạnh liên thuợc với hai đỉnh u, v. • Bậc của đỉnh: sớ cạnh liên thuợc với v gọi là bậc của đỉnh v, kí hiệu là d(v). Bậc của đỉnh có khuyên được cợng thêm 2 cho mỡi khuyên. 2 3 d(1)=1 d(2)=3 d(3)=2 1 4 5 d(4)=3 d(5)=3 7
8. Mợt sớ khái niệm • Đỉnh cơ lập, đỉnh treo: Đỉnh bậc 0 gọi là đỉnh cơ lập, đỉnh bậc 1 gọi là đỉnh treo. 2 3 Đỉnh cơ lập: 4 Đỉnh treo: 5 1 4 5 • Cung vào, ra: cung e=(u,v) gọi là cung ra khỏi u và là cung vào v. 1 2 Cung (1,2) là cung ra của 1 và là cung vào của 2 8
9. Mợt sớ khái niệm • Bán bậc của đỉnh: – Sớ cung vào của đỉnh v gọi là bán bậc vào của v, kí hiệu d–(v) – Sớ cung ra của đỉnh v gọi là bán bậc ra của v, kí hiệu d+(v) d–(1)=1; d+(1)=0 2 3 d–(2)=2; d+(2)=3 d–(3)=2; d+(3)=1 1 4 5 d–(4)=1; d+(4)=3 d–(5)=1; d+(5)=0 9
10. Mợt sớ khái niệm Định lý: Trong đờ thị vơ hướng: Tổng bậc các đỉnh =2 lần sớ cạnh. Chứng minh: Gọi m là sớ cạnh, thì cần chứng minh d(v) = 2m v V Mỡi cạnh e=(u,v) được tính mợt lần trong d(u) và mợt lần trong d(v) trong tổng bậc của các đỉnh, mỡi cạnh được tính hai lần tổng bậc bằng 2m. 2 3 Sớ cạnh: 5 Tổng bậc các đỉnh: 10 1 4 5 10
11. Mợt sớ khái niệm Hệ quả: Trong đờ thị vơ hướng thì: Sớ đỉnh bậc lẻ là mợt sớ chẵn Chứng minh: Gọi O là tập các đỉnh có bậc là sớ lẻ, và U là tập các đỉnh có bậc là sớ chẵn. Ta có: d(v) = d(v) + d(v) =2m v V v O v U Do v U, deg(v) chẵn nên d(v) chẵn d(v) chẵn v U v O Do v O,deg(v) lẻ mà tổng d(v) chẵn, nên tổng này phải gờm mợt sớ chẵn các sớ hạng v O sớ đỉnh có bậc lẻ là mợt sớ chẵn (đpcm). 11
12. Mợt sớ khái niệm Định lý 2: Trong đờ thị có hướng: Tổng bán bậc ra = tổng bán bậc vào = sớ cung Chứng minh: Gọi m là sớ cung thì cần cm: d − (v) = d + (v) = m v V v V Hiển nhiên vì mỡi cung (u,v) ra ở đỉnh u và vào ở đỉnh v nên được tính mợt lần trong bậc ra của u và mợt lần trong bậc vào của v nên suy ra đpcm. 12
13. Mợt sớ khái niệm Đường đi, chu trình, liên thơng: • Đường đi: Đường đi có đợ dài n từ đỉnh v0 đến đỉnh vn là dãy v0, v1, ,vn-1, vn ; với (vi,vi+1) E, i=0, ,n-1. Đường đi có thể biểu diễn bằng mợt dãy n cạnh (cung): (v0,v1), (v1,v2), , (vn-1, vn). Đỉnh v0 gọi là đỉnh đầu, đỉnh vn gọi là đỉnh cuới của đường đi. Dãy các đỉnh sau là đường đi: 2 3 1,3,4,5,3,2 5,3,4,1,2 1 4 5 2,3,1,4,5,3 13
14. Mợt sớ khái niệm • Chu trình: là đường đi có đỉnh đầu trùng với đỉnh cuới. Đường đi (hay chu trình) gọi là đơn nếu khơng có cạnh (cung) bị lặp lại; gọi là sơ cấp nếu khơng có đỉnh nào bị lặp lại 2 3 Dãy các đỉnh trên đờ thị vơ hướng sau đây là các chu trình: 1,2,3,5,4,3,1 (chu trình đơn) 1 4 5 2,3,4,1,2 (chu trình sơ cấp) 1,3,4,1,3,2,1 (khơng đơn) 2 3 Dãy các đỉnh trên đờ thị có hướng sau đây là các chu trình: 1,2,4,3,2,4,1 (khơng đơn) 1 4 5 1,2,4,3,5,4,1 (chu trình đơn) 14
15. Mợt sớ khái niệm • Đới chu trình: Cho G=(V,E) và AV, đới chu trình xác định bởi A được định nghĩa là: w(A)={e E | e có mợt đỉnh ở trong A} • Đới chu trình sơ cấp: Cho G liên thơng đới chu trình w=w(A) được gọi là sơ cấp (hay tập cắt) nếu: ➢ G – w khơng liên thơng và ➢  w’ w thì G - w’ liên thơng 2 3 1 e2 e6 A={2,7} thì w(A)={e1,e2, e4, e5, e6} khơng sơ cấp e3 e7 e11 e1 e 5 e9 A={1,7} thì w(A)={e2, e3, e4} sơ cấp A={3,5,6}, w(A)=? 7 e4 6 e8 5 e10 4 A={2,5}, w(A)=? 15
16. Mợt sớ khái niệm • Đờ thị liên thơng: Mợt đờ thị được gọi là liên thơng nếu hai đỉnh bất kỳ luơn có đường đi. 2 3 2 1 1 4 5 1 3 2 3 Liên thơng Liên thơng 2 3 4 5 2 Liên thơng 1 4 5 1 3 Khơng liên thơng Khơng liên thơng 16
17. Mợt sớ khái niệm • Đờ thị liên thơng mạnh: là đờ thị có hướng liên thơng • Đờ thị liên thơng yếu: là đờ thị có hướng khơng liên thơng, nhưng đờ thị vơ hướng tương ứng liên thơng • Đờ thị vơ hướng liên thơng gọi là định hướng được: nếu có thể định hướng các cạnh để thu được đờ thị có hướng liên thơng. 2 2 Vơ hướng liên thơng định hướng được 1 3 1 3 Liên thơng mạnh 2 2 Vơ hướng liên thơng khơng định hướng 1 3 1 3 được Liên thơng yếu 17
18. Mợt sớ khái niệm • Đỉnh rẽ nhánh: Đỉnh v gọi là đỉnh rẽ nhánh nếu việc loại bỏ v cùng với các cạnh liên thuợc với nó làm tăng sớ thành phần liên thơng. • Cạnh cầu: Cạnh e gọi là cầu nếu việc loại bỏ e làm tăng sớ thành phần liên thơng. 2 3 Đỉnh 3,4 gọi là đỉnh rẽ nhánh Cạnh (3,4), (3,5) gọi là cạnh cầu 1 4 5 18
19. Mợt sớ đờ thị đặc biệt • Đờ thị đủ cấp n: Là đơn đờ thị vơ hướng có n đỉnh, ký hiệu bởi Kn, mà giữa hai đỉnh bất kỳ của nó luơn có cạnh nới. Kn có sớ cạnh là: n(n-1)/2 K3 K4 K4 K5 • Đờ thị vịng: Đờ thị vịng Cn,n≥3 gờm n đỉnh v1,v2, ,vn và các cạnh (v1,v2), (v2,v3) . . . (vn-1,vn), (vn,v1). C 19 C3 4 C5 C6
20. Mợt sớ đờ thị đặc biệt • Đờ thị bánh xe: Đờ thị bánh xe Wn thu được từ đờ thị vịng Cn bằng cách bổ sung vào mợt đỉnh mới nới với tất cả các đỉnh của Cn W W3 4 W5 W6 • Đờ thị lập phương: Đờ thị lập phương Qn là đờ thị với các đỉnh biểu diễn 2n xâu nhị phân đợ dài n. 110 111 10 11 100 101 0 1 010 011 00 01 000 001 Q1 20 Q2 Q3
21. Mợt sớ đờ thị đặc biệt • Đờ thị lưỡng phân(hai phía): Đơn đờ thị G=(V,E) được gọi là lưỡng phân(hai phía) nếu như tập đỉnh V của nó có thể phân hoạch thành hai tập X và Y sao cho mỡi cạnh của đờ thị chỉ nới mợt đỉnh trong X với mợt đỉnh trong Y. Ký hiệu G=(XY, E) 4 2 3 1 3 2 1 4 2 3 5 3 2 6 1 4 1 4 6 5 21
22. Mợt sớ đờ thị đặc biệt • Đờ thị lưỡng phân đủ: Đờ thị lưỡng phân G=(X,Y, E) với |X|= m, |Y| = n được gọi là đờ thị lưỡng phân đủ, ký hiệu là Km,n nếu mỡi đỉnh trong tập X được nới với tất cả các đỉnh trong tập Y. K2,2 K2,3 K4,3 Định lý: G là đờ thị lưỡng phân nếu G khơng có chu trình đợ dài lẻ 22
23. Mợt sớ đờ thị đặc biệt • Đờ thị con: Cho hai đờ thị G=(V,E) và G’(V’, E’). G’ là đờ thị con của G nếu V’ V và E’ E. Nếu V’=V thì G’ gọi là đờ thị bợ phận hay đờ thị khung của G. 2 3 2 3 2 3 1 4 5 1 4 1 4 5 Đờ thị bợ phận G Đờ thị con của G của G 23
24. Mợt sớ đờ thị đặc biệt • Đờ thị bù: Cho Kn=(V,E) và G=(V,E1) là đờ thị khung của Kn.G =(V,E2) gọi là đờ thị bù của G nếu E2=E-E1 G • Đờ thị đẳng cấu: Hai đờ thị đơn vơ hướng G1=(V1,E1) và G2(V2,E2) được gọi là đẳng cấu nếu có mợt song ánh f: V1→V2 sao cho với (u,v) E1 (f(u),f(v)) E2 B 1 2 3 Song ánh f: f(A)=5; f(B)=4; f(C)=3; A C D E 4 5 f(D)=2; f(E)=1 24 G1 G2
25. Mợt sớ đờ thị đặc biệt Các cặp đờ thị sau có đẳng cấu khơng?. Nếu có thì hãy xây dựng mợt song ánh f? 1 A D 6 B E C F 4 5 2 3 G1 G2 Đờ thị Petersen Đờ thị Herschel 25
26. Mợt sớ đờ thị đặc biệt • Đờ thị đờng cấu: Phép chia cạnh (u,v) của đờ thị là việc loại bỏ cạnh này khỏi đờ thị và thêm vào đờ thị mợt đỉnh mới w cùng với hai cạnh (u,w), (w, u) . Hai đờ thị G=(V,E) và H=(W,F) được gọi là đờng cấu nếu chúng có thể thu được từ cùng mợt đờ thị nào đó nhờ phép chia cạnh. 26
27. Mợt sớ đờ thị đặc biệt • Đờ thị phẳng: Bài toán 3 căn hợ: Cần xây dựng mợt hệ thớng cung cấp điện, hơi đớt và nước cho ba căn hợ sao cho mỗi căn hợ đều được nới với các nguồn cung cấp trên và đường dẫn của chúng khơng cắt nhau điện ? Hơi đớt ? nước ? Để giải quyết bài toán trên, ta sẽ sử dụng khái niệm đờ thị phẳng. 27
28. Mợt sớ đờ thị đặc biệt Định nghĩa: Đờ thị được gọi là đờ thị phẳng nếu ta có thể vẽ nó trên mặt phẳng sao cho các cạnh của nó khơng cắt nhau ngoài ở đỉnh. Cách vẽ như vậy sẽ được gọi là biểu diễn phẳng của đờ thị. K 4 K4 Định lý Kuratowski: (dùng kiểm tra mợt đờ thị có là phẳng hay khơng) Đờ thị G là phẳng G khơng chứa đờ thị con đờng cấu với K3,3 hoặc K5 28
29. Mợt sớ đờ thị đặc biệt K3,3 K5 29
30. Mợt sớ đờ thị đặc biệt Định lý: (Cơng thức Euler) G là đờ thị phẳng liên thơng, G có n đỉnh, m cạnh, r là sớ miền của mặt phẳng bị chia bởi biểu diễn phẳng của G. Ta có: r = m - n + 2 Sớ đỉnh: 7 r2 r4 r5 r1 Sớ cạnh: 10 r3 Sớ miền: 10 – 7 + 2 = 5 30
31. Sắc sớ của đờ thị 31
32. Sắc sớ của đờ thị 32
33. Sắc sớ của đờ thị Định nghĩa: Tơ màu mợt đờ thị vơ hướng là mợt sự gán màu cho các đỉnh sao cho hai đỉnh kề nhau phải khác màu nhau. Sớ màu (sắc sớ) của mợt đờ thị là sớ màu tới thiểu cần thiết để tơ màu đờ thị này. Thuật tốn tơ màu Welch-Powell B1: Sắp xếp danh sách các đỉnh theo thứ tự bậc giảm dần B2: Chọn đỉnh v chưa tơ trên danh sách theo thứ tự từ trái sang phải, chọn mợt màu để tơ đỉnh v và các đỉnh khơng kề với v B3: Lặp lại B2 đến khi tất cả các đỉnh đều được tơ. 33
34. Sắc sớ của đờ thị 3 2 5 Đỉnh 4 3 5 6 1 2 Bậc 3 3 2 2 2 2 Màu 1 2 2 1 2 1 1 4 6 1 2 3 Đỉnh 1 5 2 6 3 4 Bậc 4 4 3 3 2 2 5 4 Màu 1 2 2 3 3 1 6 2 1 6 3 6 10 5 7 8 2 1 4 10 7 5 9 9 8 3 4 11 34
35. CHƯƠNG 2: BIỂU DIỄN ĐỜ THỊ • Ma trận kề: Cho G=(V,E), V={1,2,3, ,n}, ma trận kề A=(Ai,j) của G là ma trận vuơng cấp n xác định bởi: Ai,j=sớ cạnh (cung) từ i đến j 1 2 3 4 5 2 3 1 0 1 1 2 0 2 1 0 1 0 0 Ai,j= 3 1 1 0 1 1 4 2 0 1 0 1 1 4 5 5 0 0 1 1 1 1 2 3 4 5 2 3 1 0 1 1 0 0 2 0 0 1 0 0 5 Ai,j= 3 0 0 0 1 0 1 4 4 1 0 0 0 1 5 0 1 1 0 0 35
36. Ma trận trọng sớ • Ma trận trọng sớ: Cho G=(V,E) là mợt đờ thị có trọng sớ, nghĩa là mỡi cạnh (i,j) E đều có mợt giá trị c(i,j) gọi là trọng sớ của cạnh. trọng sớ cạnh|cung (i,j) nếu (i,j) E Ma trận trọng sớ Ai,j =  nếu (i,j) E Trong đó là mợt trong các giá trị: 0, , + , - -2 1 2 3 4 5 2 3 1 0 2 4 3 2 7 2 2 0 -2 1 2 2 1 3 -2 0 3 7 1 5 4 4 1 3 0 4 4 5 2 7 0 36
37. Ma trận liên kết • Ma trận liên kết (ma trận liên thuộc đỉnh-cạnh): Cho G=(V,E) với V={1,2,3, ,n}; E=(e1, e2, , em). Ma trận liên kết của G là ma trận A=(Ai,j) có n dịng, m cợt được định nghĩa như sau: 1 nếu đỉnh i kề với cạnh e Nếu G vơ hướng thì A = j i,j 0 nếu ngược lại 1 nếu ej rời khỏi đỉnh i Nếu G vơ hướng thì Ai,j= -1 nếu ej đi đến đỉnh i 0 nếu ej khơng kề với đỉnh i 37
38. Ma trận liên kết b a b c d e f g 2 3 1 1 0 0 0 1 0 0 f a g 2 1 1 1 1 0 0 0 c d 3 0 1 0 0 0 1 1 1 5 4 0 0 0 1 1 1 0 e 4 5 0 0 1 0 0 0 1 b 2 3 a b c d e f g 1 1 0 0 0 1 0 0 f a g c 2 -1 -1 1 1 0 0 0 d 3 0 1 0 0 0 -1 -1 1 5 4 0 0 0 -1 -1 1 0 e 4 5 0 0 -1 0 0 0 1 38
39. Danh sách cạnh (cung) • Danh sách cạnh(cung): Trong trường hợp sớ cạnh ít hơn nhiều so với sớ cạnh thì người ta thường dùng danh sách cạnh(cung) để lưu trữ đờ thị. Mỡi cạnh được biểu diễn bởi đỉnh đầu và đỉnh cuới. Đầu Cuới 2 3 1 2 1 4 2 3 1 5 2 4 2 5 4 3 4 3 5 39
40. Danh sách kề • Danh sách kề: Danh sách kề là danh sách lưu các đỉnh kề của mợt đỉnh nào đó. Nếu đờ thị có n đỉnh thì sẽ lưu trữ với n danh sách kề 2 3 DS 1 2 4 nil DS 2 3 4 5 nil DS 3  1 5 DS 4 3 nil 4 DS 5 3 nil 40
41. Nhận xét Lưu trữ Ưu điểm Khuyết điểm -Truy xuất - Luơn sử dụng 2n đơn vị bợ nhớ Ma trận kề nhanh các đỉnh cho dù sớ cạnh rất ít kề - Tiết kiệm bợ Ma trận liên kết nhớ đới với đờ - Tìm đỉnh kề khó khăn thị có ít cạnh -Thực hiện nhiều phép so sánh khi -Tiết kiệm bợ tìm đỉnh kề Danh sách cạnh nhớ đới với đờ thị có ít cạnh -Trong trường hợp đờ thị có trọng sớ phải thêm đơn vị bợ nhớ - Phân nhóm -Thực hiện thao tác chậm do phải đỉnh kề rõ ràng truy xuất tuần tự Danh sách kề thành các danh -Tìm mợt đỉnh là kề của những đỉnh sách nào phải duyệt hết các danh sách 41
42. Biểu diễn đờ thị trên máy tính • Viết chương trình đọc mợt đờ thị vào máy tính bằng: – Ma trận kề – Ma trận liên kết 2 5 – Danh sách cạnh – Danh sách kề 1 3 4 6 • Viết chương trình chuyển đổi qua lại giữa các hình thức lưu trữ trên • Viết chương trình tìm các đỉnh có đỉnh kề là k với k nhập vào từ bàn phím và đờ thị được lưu trữ bằng danh sách kề 42
43. CHUƠNG 3: CÁC THUẬT TOÁN DUYỆT VÀ TÌM KIẾM TRÊN ĐỜ THỊ 1) Tìm theo chiều sâu(Depth First Search - DFS) 2) Tìm theo chiều rợng(Breadth First Search - BFS) 43
44. Thuật toán DFS Ý tưởng: • Từ đỉnh v1 nào đó chưa thăm, thăm v1 rời tìm đỉnh v2 (chưa thăm) kề với v1, thăm v2 • Nếu tại mợt đỉnh vi nào đó khơng cịn đỉnh kề chưa thăm thì quay trở lại tìm đỉnh kề chưa thăm khác của vi-1 và thăm đỉnh này. • Thuật toán lặp lại việc thăm cho đến khi tất cả các đỉnh đều được thăm. 3 Nếu bắt đầu từ đỉnh 1 thì thứ tự duyệt 2 có thể là: 1, 3, 2, 5, 4 1 5 4 44
45. Thuật toán DFS Thuật tốn: void DFS1(v)//duyệt mợt thành phần liên thơng chứa v { Tham_Dinh(v); tham[v]=1; //ghi nhận là đã thăm v để về sau khơng thăm nữa. For (u Ke(v)) // xét tất cả các đỉnh u kề với v If (!tham[u]) DFS1(u); //neu u chua thăm, thăm u } void DFS() //duyệt tất cả các thành phần liên thơng { for (v V) tham[v]=0; //ban đầu tất cả các đỉnh đều chưa thăm. for (v V) //xét tất cả các dinh if (!tham[v]) DFS1(v); // neu đỉnh v chua tham thi tham v } 45
46. Thuật toán BFS Ý tưởng: • Từ đỉnh v nào đó chưa thăm, cất v vào hàng đợi. • Lấy từ hàng đợi mợt đỉnh v, thăm v, rời cất các đỉnhu chưa thăm kề với v vào hàng đợi • Lặp lại cho tới khi hàng đợi rỡng. 3 1 2 3 4 5 2 1 3 4 4 2 5 1 5 2 5 4 5 Thứ tự duyệt theo BFS là: 1, 3, 4, 2, 5 46
47. Thuật toán BFS Thuật tốn: void BFS1(v) //duyệt mợt thành phần liên thơng { queue=; //khoi tạo hàng đợi rỗng push(queue,v); //cất v vào hàng đợi tham[v]=1; //ghi nhận là đã thăm v để về sau khơng thăm nữa. while (queue <>) // trong khi hàng đợi cịn khác rỗng { v=pop(queue); //lay mot dinh v từ hàng đợi for (u Ke(v)) // xét các đỉnh u kề với v if(!tham[u]) //nếu u chưa thăm { push(queue,u); //cất u vào hàng đợi tham[u]=1; //ghi nhan u tham roi } } } 47
48. Thuật toán BFS void BFS() //duyệt tất cả các thành phần liên thơng { for (v V) tham[v]=0; //ban đầu tất cả các đỉnh đều chưa thăm. for (v V) //xét tất cả các dinh if (!tham[v]) BFS1(v); // neu đỉnh v chua tham thi tham v } Dùng thuật toán DFS và BFS duyệt đờ thị sau: 3 2 7 5 8 1 4 6 12 9 13 10 11 48
49. Tìm sớ thành phần liên thơng Hãy cho biết đờ thị có bao nhiêu thành phần liên thơng và mỡi thành phần liên thơng gờm những đỉnh nào? Ý tưởng: Do sớ thành phần liên thơng bằng sớ lần DFS() gọi DFS1() hoặc BFS() gọi BFS1(), nên ta dùng biến stplt để đếm sớ thành phần liên thơng, mỡi lần DFS() gọi DFS1() hoặc BFS() gọi BFS1() ta tăng biến stplt lên 1. Khi thăm v thay vì gán thăm[v] = true (=1) ta gán thăm[v] = stplt (sớ hiệu thành phần liên thơng chứa v). 49
50. Tìm sớ thành phần liên thơng Thuật tốn: void DFS1(v) //duyệt mợt thành phần liên thơng { Tham_Dinh(v); tham[v]=stplt; //ghi nhận là đã thăm v để về sau khơng thăm nữa. For (u Ke(v)) // xét tất cả các đỉnh u kề với v If(!tham[u]) DFS1(u); //neu u chua thăm, thăm u } void DFS() //duyệt tất cả các thành phần liên thơng { for (v V) tham[v]=0; //ban đầu tất cả các đỉnh đều chưa thăm. stplt=0; for (v V) //xét tất cả các dinh if (!tham[v]) { stplt++; DFS1(v); // neu đỉnh v chua tham thi tham v } } 50
51. Tìm sớ thành phần liên thơng void BFS1(v) //duyệt mợt thành phần liên thơng { queue=; //khoi tạo hàng đợi rỡng push(queue,v); //cất v vào hàng đợi tham[v]=stplt; //ghi nhận là đã thăm v để về sau khơng thăm nữa. while (queue) // trong khi hàng đợi cịn khác rỡng { v=pop(queue); //lay v từ hàng đợi Tham_Dinh(v); for (u Ke(v)) // xét các đỉnh u kề với v if (!tham[u]) //nếu u chưa thăm { push(queue,u); //cất u vào hàng đợi tham[u]=stplt; //ghi nhan u tham roi } } } 51
52. Bài tập • Viết chương trình duyệt đờ thị với thuật toán DFS dùng cấu trúc stack • Viết chương trình duyệt đờ thị bằng thuật toán DFS và BFS với đờ thi được lưu trữ bằng danh sách kề. 52
53. CHUƠNG 4: ĐỜ THỊ EULER VÀ ĐỜ THỊ HAMILTON Leonhard Euler (15/04/1707 -18/09/1783) Người Thuỵ Sĩ, là nhà toán học, vật lý học William Rowan Hamilton (04/08/1805 – 02/09/1865), người Ireland, là mợt nhà toán học, vật lý và thiên văn học 53
54. Đờ thị Euler Bài tốn bảy cây cầu: Có thểb ắt đầu từ mợt điểm và đi qua mỡi cây cầu đúng mợt lần rời quay lại điểm xuất phát hay khơng ? Bản đồ Kưnigsberg thời Euler, mơ tả vị trí thực của bay cây cầu và sơng Pregel. Năm 1736 Leonhard Euler đã chứng minh rằng điều đó là khơng thể được. 54
55. Đờ thị Euler • Đường đi Euler: Đường đi qua tất cả các cạnh của đờ thị, mỡi cạnh đúng mợt lần gọi là đường đi Euler. • Chu trình Euler: Chu trình đi qua tất cả các cạnh của đờ thị, mỡi cạnh đúng mợt lần gọi là chu trình Euler. • Đờ thị Euler, nửa Euler: Đờ thị có chu trình Euler gọi là đờ thị Euler, đờ thị có đường đi Euler gọi là đờ thị nửa Euler. G2 G3 G1 55
56. Đờ thị Euler Định lý Euler a/ G là đờ thị vơ hướng liên thơng. G là đờ thị Euler mọi đỉnh của G đều có bậc chẵn. b/ G là đờ thị có hướng liên thơng. G là đờ thị Euler bậc vào và bậc ra của mỡi đỉnh là bằng nhau Định lý nửa Euler Cho đờ thị vơ hướng liên thơng G. G là nửa Euler  G có khơng quá 2 đỉnh bậc lẻ (có0 đỉnh bậc lẻ hoặc có 2 đỉnh bậc lẻ). 56
57. Đờ thị Euler Thuật tốn tìm chu trình Euler void Euler() { stack= ; CE= ; // CE là tập chứa các đỉnh của chu trình Euler Chọn mợt đỉnh x bất kỳ, cất x vào //xstack gọi là đỉnh xuất phát. While (stack ) { x = phần tử ở đỉnh stack ; if (x cịn đỉnh kề) { chọn y kề x, cất y vào stack; loại bỏ cạnh (x,y) } else //x khong con dinh ke { lấy x ra khỏi stack ; cất x vào tập CE } } } xuất tập CE; 57 }
58. Đờ thị Euler 7 7 1 2 6 3 4 5 3 5 5 5 2 1 4 4 4 4 4 7 7 7 3 3 3 3 3 3 3 3 3 6 6 6 6 6 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 CE = {1, 3, 5, 4, 3, 2, 7, 6, 2, 1} Chu trình Euler:1->3->5->4->3->2->7->6->2->1 58
59. Đờ thị Hamilton • Đường đi Hamilton: Là đường đi qua tất cả các đỉnh của đờ thị, mỡi đỉnh đúng mợt lần gọi là đường đi Hamilton. • Chu trình Hamilton: Là chu trình qua tất cả các đỉnh của đờ thị, mỡi đỉnh đúng mợt lần gọi là chu trình Hamilton. G G G2 3 1 59
60. Đờ thị Hamilton Định lý Dirak: a/ G là đơn đờ thị vơ hướng có n đỉnh (n>2).  đỉnh u, deg(u) n/2 G là đờ thị Hamilton b/ G là đơn đờ thị có hướng liên thơng với n đỉnh.  đỉnh u, deg+(u) ≥n/2, deg–(u) ≥ n/2, G là đờ thị Hamilton. 60
61. Đờ thị Hamilton Thuật tốn liệt kê các chu trình và đường đi Hamilton: void hamilton(i) //tìm đỉnh thứ i trên chu trình hamilton { for (j kề(i – 1)) { if (i=n+1) và (j=v0) { Xuất chu trình x[1], x[2], ,x[1] else if(! Tham[j]) { x[i]=j; //Chọn j làm đỉnh thứ i trong chu trình tham[j]=1; Timdinh(i+1); tham[j]=0; } } } 61
62. Đờ thị Hamilton void Hamilton() { for i=1 to n tham[i]=0; //gán tất cả các đỉnh là chưa thăm x[1]=v0; tham[v0]=1; timdinh(2); //gọi hàm tìm đỉnh thứ 2 } 62
63. Đờ thị Hamilton Cây đường đi và chu trình Hamilton 1 2 2 4 3 5 3 5 1 5 3 2 3 4 2 3 4 5 5 4 2 2 4 5 4 3 5 3 1 1 1 1 63
64. Bài tập • Viết chương trình kiểm tra đờ thị Euler, đờ thị Hamilton • Viết chương trình tìm chu trình Euler và đường đi Euler • Viết chương trình tìm chu trình Hamilton và đường đi hamilton 64
65. CHƯƠNG 5: CÂY Định nghĩa: • Cây là mợt đờ thị liên thơng khơng có chu trình • Rừng là mợt đờ thị có nhiều thành phần liên thơng, mỡi thành phần liên thơng là mợt cây. T1 T2 T3 Rừng gờm 3 cây T1, T2, T3 65
66. CHƯƠNG 5: CÂY Định lý: Cho T là một đờ thị có n 2 đỉnh. Những điều sau đây tương đương • T là cây • T khơng có chu trình và có n – 1 cạnh • T liên thơng và có n – 1 cạnh • T liên thơng và mỗi cạnh là mợt cầu Cây T có 9 đỉnh, 8 cạnh T 66
67. CHƯƠNG 5: CÂY Hệ luận: Nếu G là một rừng n đỉnh, p cây thì sớ cạnh của G là: m=n-p T1 T2 T3 Rừng có sớ đỉnh: 16 Sớ cây: 3 Sớ cạnh: 16-3=13 67
68. Cây khung của đờ thị Định nghĩa cây khung: Cho G=(V,E) là đờ thị vơ hướng liên thơng. Cây khung của G là cây T=(V,F) với FE 68
69. Thuật toán tìm cây khung Thuật tốn DFS: void DFS1(v) { tham[v]=1; //ghi nhận là đã thăm v để về sau khơng thăm nữa. For (u Ke(v)) // xét tất cả các đỉnh u kề với v if (!tham[u]) { //T la tap chua cac canh cua cay khung T=T(v,u); //them canh (v,u) vao tap T DFS1(u); //neu u chua thăm, thăm u } } void DFS() { for (v V) tham[v]=0; T=; // T là tập cạnh của cây khung, khởi trị ban đầu là rỡng DFS1(dxp); // dxp la mot dinh xuat phat nao do cua do thị xuất tập T; 69 }
70. Thuật toán tìm cây khung Thuật tốn BFS: void BFS1(v) { queue=; push(queue,v); tham[v]=1; while (queue ) { v=pop(queue); for (u Ke(v)) If (!tham[u]) { push(queue,u); tham[u]=1; T=T(v,u); //them canh (v,u) vao tap T } } } void BFS() { for (v V) tham[v]=0; T=; // T là tập cạnh của cây khung BFS1(dxp); //dxp la mot dinh xuât phát nào đó của đờ thị xuat tap T; 70 }
71. Cây khung ngắn nhất Bài tốn xây dựng hệ thớng đường sắt: Cần xây dựng mợt hệ thớng đường sắt nới n thành phớ sao cho giữa 2 thành phớ bất kỳ luơn có đường đi và tổng chi phí xây dựng là nhỏ nhất. B A C D E 71
72. Cây khung ngắn nhất Định nghĩa cây khung ngắn nhất: Cho mợt đờ thị vơ hướng G, trên mỡi cạnh của G đuợc gán mợt trọng sớ c(i,j). Cây khung T của G được gọi là cây khung ngắn nhất nếu tổng trọng sớ các cạnh của T là nhỏ nhất 3 2 3 2 1 4 1 1 1 5 5 1 1 6 2 2 3 3 4 5 4 72
73. Thuật toán tìm cây khung ngắn nhất Thuật tốn Kruskal: Ý tưởng: Bước 1: Sắp các cạnh theo thứ tự khơng giảm của trọng sớ, T= Bước 2: Lần lượt duyệt trong danh sách cạnh đã sắp xếp theo thứ tự trọng sớ từ nhỏ đến lớn, chọn cạnh bổ sung vào tập T với điều kiện việc bổ sung này khơng tạo thành chu trình. Bước 3: Tiếp tục thực hiện bước 2 cho đến khi T có n-1 cạnh thì dừng. 73
74. Thuật toán Kruskal Sắp các cạnh theo thứ tự khơng giảm của trọng sớ 4 2 1 4 Cạnh (1,3) (1,5) (3,5) (4,5) (1,2) (2,5) (3,4) 1 5 Trọng sớ 1 1 2 3 4 4 5 1 2 T= 3 3 4 5 Bổ sung vào T cạnh (1,3) Bổ sung vào T cạnh (4,5) 1 1 1 5 1 1 3 3 3 4 Bổ sung vào T cạnh (1,5) Bổ sung vào T cạnh (1,2) 2 1 4 1 1 5 1 1 5 1 3 3 3 74 4
75. Thuật toán Kruskal void Kruskal() { T= ; while ((|T| < n-1) && (E ≠ )) //T chưa đủ -n 1 cạnh và cịn cạnh để chọn { Chọn e là cạnh có đợ dài nhỏ nhất trong E; E = E\{e}; //loại e khỏi tập cạnh if (T  {e} khơng chứa chu trình) T= T  {e} ; //thêm e vào T } if (|T| < n-1) đờ thị khơng liên thơng; else Xuất cây T } 75
76. Thuật toán Prim Ý tưởng: Bước 1: Gọi T là tập chứa các cạnh của cây khung; T=. S là tập chứa các đỉnh của cây khung; S={x} (với x là đỉnh bắt kỳ thuợc đờ thị) Bước 2: Tìm cạnh (x,y) w(s) sao cho cạnh này có trọng sớ bé nhất trong w(s). T=T(x,y); S=S{y} Bước 3: Lặp bước 2 đến khi T có n-1 cạnh thì dừng. 76
77. Thuật toán Prim T=, S={1}, S={1,3,5}, w(s)={(1,2), (1,3), (1,5)} w(s)={(1,2), (2,5), (3,4), (4,5)} 4 2 chọn (1,3) chọn (4,5) 1 4 T=T(1,3)={(1,3)} T=T(4,5)={(1,3), (1,5), (4,5)} 1 5 1 1 1 2 1 5 3 1 3 1 4 5 3 3 3 4 S={1,3} S={1,3,5,4}, w(s)={(1,2), (1,5), (3,4),(3,5)} w(s)={(1,2), (2,5)} chọn (1,5) chọn (1,2) T=T(1,5)={(1,3), (1,5)} T=T(1,2)={(1,3), (1,5), (4,5),(1,2)} 1 4 2 1 1 5 1 1 5 1 3 77 3 4 3
78. Thuật toán Prim void Prim() { //bước khởi tạo chon s la mot dinh nao do cua do thi; VH={s} ; T=  ; d[s]=0; near[s]=s; for (v V \VH) { d[v]=c[v,s]; near[v]=s; } // buoc lap stop=false; while (! stop) { Tim u V \VH thoa man:d[u] =min{d[v]: v V \VH } ; VH= VH { u} ; T = T  { (u, near[u])} ; 78
79. Thuật toán Prim if (| VH| ==n) { H=( VH,T) la cay khung nho nhat cua do thi; stop:=true; } else for (v V\ VH) if (d[v]>c[v,u]) //neu v gan dinh u moi ket nap vao cay khung { d[v]=c[v,u]; //cap nhat lai nhan near[v]=u; } } } 79
80. CHƯƠNG 6: ĐƯỜNG ĐI NGẮN NHẤT Một sớ khái niệm: Cho G=(V,E) là mợt đờ thị có hướng được biểu diễn bởi ma trận trọng sớ A • Trọng sớ của mợt cung (u,v) ký hiệu là a[u,v] là giá trị của ma trận trọng sớ tại dịng u cợt v. 1 2 3 4 5 -2 3 2 1 0 2 3 2 7 2 0 -2 1 2 1 3 0 3 7 1 5 4 4 0 4 4 5 2 0
81. Mợt sớ khái niệm: • Đường di ngắn nhất từ đỉnh s đến đỉnh v là đường đi có đợ dài nhỏ nhất từ s đến v, ký hiệu là d[s,v] hay d[v] (được hiểu ngầm từ s đến v) đỉnh 20 s 30 v xuất u phát d[u,v]=20 + 30 • Nếu G có chu trình đợ dài âm trên đường đi từ i đến j thì đường đi từ i đến j khơng tờn tại -5 20 30 i u j
82. Thuật toán Ford-Bellman Điều kiện: Đờ thị khơng có chu trình âm Thuật toán: Dữ liệu vào: Đờ thị có hướng G=(V,E) với n đỉnh, s là đỉnh xuất phát, a[u,v] là ma trận trọng sớ thực; Giả thiết: Đờ thị khơng có chu trình âm. Dữ liệu ra: d[v] là khoảng cách từ đỉnh s đến tất cả các đỉnh v cịn lại Trước[v] ghi nhận đỉnh đi trước v trong đường đi ngắn nhất từ s đến v.
83. Thuật toán Ford-Bellman void Ford_Bellman() { // Khởi tạo for (v V) { d[v]=a[s,v]; Truoc[v]=s; //s là đỉnh xuất phát } d[s]=0; for (k=1;k d[u] +a[u,v]) { d[v]=d[u]+a[u,v]; Truoc[v]=u; } }
84. Thuật toán Ford-Bellman Tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh khác: 3 2 2 4 1 2 1 1 2 -2 5 -4 3 7 4 3 1 3 5 2 5 6 2 1 1 2 5 5 1 2 5 3 2 5 1 -4 7 3 4 3 3 4 3 6 2 6 4
85. Thuật toán Dijkstra Điều kiện: Đờ thị khơng trọng sớ âm Thuật toán: Dữ liệu vào: Đờ thị có hướng G=(V,E) với n đỉnh, s là đỉnh xuất phát, a[u,v] >=0 Dữ liệu ra: Khoảng cách từ đỉnh s đến tất cả các đỉnh cịn lại d[v] Truoc[v], đỉnh đi trước v trong đường đi ngắn nhất từ s đến v
86. Thuật toán Dijkstra void Dijkstra() { for (v V) // Khởi tạo { d[v]=a[s,v]; Truoc[v]=s; } d[s]=0; T:=V\{s}; // T là tập các đỉnh có nhãn tạm thời while (T !=) { Tìm đỉnh u T thoả mãn d[u]=min {d[z]: z T} ; T=T\{u} ; // Cớ định nhãn của đỉnh u for (v T) if (d[v]>d[u]+a[u,v]) { d[v]=d[u]+a[u,v]; Truoc[v]=u; } } }
87. Thuật toán Dijkstra Tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh khác: 2 4 4 5 6 1 2 2 5 3 6 5 3 1 6 8 7 1 3 7 5 6 2 2 1 3 5 7 4 5 4 6 6 2 3 5 1 5 2 3 1 3 2 1 1 6 4 6 4 2 87
88. Thuật toán Floyd • Tìm đường đi giữa tất cả các cặp đỉnh • Có thể giải bài toán tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh của đờ thị bằng cách sử dụng n lần thuật toán mơ tả ở phần trước, trong đó ta sẽ chọn s lần lượt là các đỉnh của đờ thị. Khi đó ta thu được thuật toán với đợ phức tạp O(n4) (Ford_Bellman) hoặc O(n3) (Dijkstra) Ta có thuật toán Floyd tớt hơn với đợ phức tạp O(n3) Dữ liệu vào: Đờ thị cho bởi ma trận trọng sớ a[i,j], i, j=1, 2,. . ,n. Dữ liệu ra: Ma trận đường đi ngắn nhất giữa các cặp đỉnh: d[i,j] cho đợ dài đường đi ngắn nhất từ đỉnh i đến đỉnh j. Ma trận ghi nhận đường đi: q[i,j] ghi nhận đường đi ngắn nhất từ i đến j.
89. Thuật toán Floyd Ý tưởng: - Tìm đường đi giữa tất cả các cặp đỉnh của G - Sử dụng 2 ma trận Di,j (lưu trọng sớ)và Qi,j (lưu đường đi) - Bước khởi tạo (bước 1) tính: D1 = Di,j là ma trận trọng sớ của G Q1 = Qi,j = j nếu (i,j) E 0 nếu (i,j) E - Tại bước lặp thứ k ta tính Dk và Qk như sau: Dk(i,j) = Dk-1 (i,k) + Dk-1 (k,j) nếu Dk-1 (i,j) > Dk-1 (i,k) + Dk-1 (k,j) Dk-1 (i,j) nếu ngược lại Qk(i,j) = Qk-1 (i,k) nếu Dk-1 (i,j) > Dk-1 (i,k) + Dk-1 (k,j) Qk-1 (i,j) nếu ngược lại - Thuật toán dừng khi đã thực hiện n bước lặp 89
90. Thuật toán Floyd Xét bước lặp thứ k = 6 K=5 K=6 1 2 3 4 k 6 7 1 2 3 4 5 6 7 1 0 6 4 7 9 1 0 6 4 7 9 2 8 0 4 2 6 0 4 3 9 7 3 8 7 D5 = 4 2 9 D6 = 4 2 9 k 2 8 1 0 5 5 2 8 1 0 5 6 6 4 1 5 0 6 4 5 7 1 6 0 7 1 6 90
91. Thuật toán Floyd K=5 K=6 1 2 3 4 k 6 7 1 2 3 4 5 6 7 1 1 2 3 4 2 4 3 6 7 3 7 Q = Q5 = 4 6 4 k 5 6 6 7 7 91
92. Thuật toán Floyd void Floyd() { for i=1 to n for j=1 to n //Bước khởi tạo { d[i][j]=a[i][j]; if (d[i][j] = hay d[i][j] = 0) q[i][j]=0; else q[i][j]=j; } for k=2 to n // bước lặp for i=1 to n for j=1 to n if (d[i][j]>d[i][k]+d[k][j]) { d[i][j]=d[i][k]+d[k][j]; q[i][j]=q[i][k]; } }
93. Thuật toán Floyd Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh: 12 5 2 4 6 9 2 1 1 2 2 1 4 6 6 3 1 4 3 5 3 7 2 8 3 7 3 5 4 5 7