›
›

Bài giảng Toán rời rạc - Phần 2 - Chương 1: Các khái niệm cơ bản - Nguyễn Đức Nghĩa

pptx 275 trang haiha333 08/01/2022 4520
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Phần 2 - Chương 1: Các khái niệm cơ bản - Nguyễn Đức Nghĩa", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptxbai_giang_toan_roi_rac_phan_2_chuong_1_cac_khai_niem_co_ban.pptx

Nội dung text: Bài giảng Toán rời rạc - Phần 2 - Chương 1: Các khái niệm cơ bản - Nguyễn Đức Nghĩa

  1. Phần 2 LÝ THUYẾT ĐỒ THỊ Graph Theory 1 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  2. Nội dung Chương 1. Các khái niệm cơ bản – Đồ thị vô hướng và có hướng – Các thuật ngữ cơ bản – Một số dạng đồ thị vô hướng đặc biệt Chương 2. Biểu diễn đồ thị – Ma trận kề, ma trận trọng số, Ma trận liên thuộc đỉnh cạnh – Danh sách cạnh, Danh sách kề Chương 3. Duyệt đồ thị – Tìm kiếm theo chiều sâu; Tìm kiếm theo chiều rộng – Tìm đường đi và kiểm tra tính liên thông 2 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  3. Nội dung Chương 4. Cây và cây khung của đồ thị – Cây và các tính chất của cây – Cây khung của đồ thị – Bài toán cây khung nhỏ nhất Chương 5. Bài toán đường đi ngắn nhất – Phát biểu bài toán – Đường đi ngắn nhất xuất phát từ một đỉnh (Thuật toán Dijkstra, Ford-Bellman) – Đường đi ngắn nhất trên đồ thị không có chu trình – Đường đi ngắn nhất giữa mọi cặp đỉnh (Thuật toán Floyd) Chương 6. Bài toán luồng cực đại trong mạng – Mạng, luồng và bài toán luồng cực đại – Định lý Ford-Fulkerson – Thuật toán Ford-Fulkerson – Một số ứng dụng 3 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  4. Chương 1 CÁC KHÁI NIỆM CƠ BẢN 4 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  5. Chương 1 CÁC KHÁI NIỆM CƠ BẢN 1.1. Đồ thị trong thực tế 1.2. Các loại đồ thị 1.3. Bậc của đỉnh 1.4. Đồ thị con 1.5. Đồ thị đẳng cấu 1.6. Đường đi và chu trình 1.7. Tính liên thông 1.8. Một số loại đồ thị đặc biệt 1.9. Tô màu đồ thị 5 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  6. Không phải Đồ thị là gì? cái này • Trong toán học đời thường hiểu là: Bản vẽ hay Sơ đồ biểu diễn dữ liệu nhờ sử dụng hệ thống toạ độ. • Trong toán rời rạc: Đây là cấu trúc rời rạc có tính trực quan cao, rất tiện ích để biểu diễn các quan hệ. 6 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  7. Các ứng dụng thực tế của đồ thị • Có tiềm năng ứng dụng trong nhiều lĩnh vực (Đồ thị có thể dùng để biểu diễn các quan hệ. Nghiên cứu quan hệ giữa các đối tượng là mục tiêu của nhiều lĩnh vực khác nhau). • Ứng dụng trong mạng máy tính, mạng giao thông, mạng cung cấp nước, mạng điện, ) lập lịch, tối ưu hoá luồng, thiết kế mạch, quy hoạch phát triển • Các ứng dụng khác: Phân tích gen, trò chơi máy tính, chương trình dịch, thiết kế hướng đối tượng, 7 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  8. Mối liên hệ giữa các môn học 461 322 143 373 321 142 326 410 415 370 341 413 417 378 Đỉnh = môn học 421 Cạnh có hướng = đk tiên quyết 401 8 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  9. Biểu diễn mê cung S S B E E Đỉnh = phòng Cạnh = cửa thông phòng hoặc hành lang 9 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  10. Biểu diễn mạch điện (Electrical Circuits) Nguồn Công tắc Đỉnh = nguồn, công tắc, điện trở, Điện trở Cạnh = đoạn dây nối 10 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  11. Các câu lệnh của chương trình Program statements x1 x2 x1=q+y*z + - x2=y*z-q Thoạt nghĩ: q * * q y*z tính hai lần y z x1 x2 Loại Biểu thức con + - chung: q * q Đỉnh = ký hiệu/phép toán y z Cạnh = mối quan hệ 11 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  12. Yêu cầu trình tự (Precedence) S a=0; 1 6 S2 b=1; S c=a+1 3 5 S4 d=b+a; S5 e=d+1; S6 e=c+d; 4 Các câu lệnh nào phải thực hiện trước S6? 3 S1, S2, S3, S4 Đỉnh = câu lệnh Cạnh = yêu cầu trình tự 1 2 12 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  13. Truyền thông trong mạng máy tính (Information Transmission in a Computer Network) 56 Tokyo Hà nội Seoul 128 16 181 New York 30 140 Bắc kinh Sydney Đỉnh = máy tính Cạnh = tốc độ truyền thông 13 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  14. Luồng giao thông trên xa lộ (Traffic Flow on Highways) UW Đỉnh = thành phố Cạnh = lượng xe cộ trên tuyến đường cao tốc kết nối giữa các thành phố 14 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  15. Mạng xe buýt 15 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  16. Mạng tàu điện ngầm 16 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  17. Sơ đồ đường phố 17 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  18. 18 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  19. 19 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  20. 20 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  21. Chương 1 CÁC KHÁI NIỆM CƠ BẢN 1.1. Đồ thị trong thực tế 1.2. Các loại đồ thị 1.3. Bậc của đỉnh 1.4. Đồ thị con 1.5. Đồ thị đẳng cấu 1.6. Đường đi và chu trình 1.7. Tính liên thông 1.8. Một số loại đồ thị đặc biệt 1.9. Tô màu đồ thị 21 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  22. Đồ thị vô hướng (Undirected Graphs) Định nghĩa. Đơn (đa) đồ thị vô hướng G = (V,E) là cặp gồm: • Tập đỉnh V là tập hữu hạn phần tử, các phần tử gọi là các đỉnh • Tập cạnh E là tập (họ) các bộ không có thứ tự dạng (u, v), u, v V, u≠v 22 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  23. Đơn đồ thị vô hướng (Simple Graph) • Ví dụ: Đơn đồ thị G1 = (V1, E1), trong đó V1={a, b, c, d, e, f, g, h}, E1={(a,b), (b,c), (c,d), (a,d), (d,e), (a,e), (d,b), (f,g)}. a f b h e c g d Đồ thị G1 23 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  24. Đa đồ thị vô hướng (Multi Graphs) • Ví dụ: Đa đồ thị G2 = (V2, E2), trong đó V2={a, b, c, d, e, f, g, h}, E2={(a,b), (b,c), (b,c), (c,d), (a,d), (d,e), (a,e), (a,e), (a, e), (d,b), (f,g)}. a b f e h Cạnh lặp c g d Đồ thị G2 24 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  25. Đồ thị có hướng (Directed Graph) Định nghĩa. Đơn (đa) đồ thị có hướng G = (V,E) là cặp gồm: • Tập đỉnh V là tập hữu hạn phần tử, các phần tử gọi là các đỉnh • Tập cung E là tập (họ) các bộ có thứ tự dạng (u, v), u, v V, u≠v 25 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  26. Đơn đồ thị có hướng (Simple digraph) • Ví dụ: Đơn đồ thị có hướng G3= (V3, E3), trong đó V3={a, b, c, d, e, f, g, h}, E3={(a,b), (b,c), (c,b), (d,c), (a,d), (b, d), (a,e), (d,e), (e,a), (f,g), (g,f)} a f b h e c g d Đồ thị G3 26 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  27. Đa đồ thị có hướng (Multi Graphs) • Ví dụ: Đa đồ thị có hướng G4= (V4, E4), trong đó V4={a, b, c, d, e, f, g, h}, E4={(a,b), (b,c), (c,b), (d,c), (a,d), (b, d), (a,e), (a,e), (d,e), (e,a), (f,g), (g,f)} a b f e h c g d Đồ thị G4 27 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  28. Các loại đồ thị: Tóm tắt Loại Kiểu cạnh Có cạnh lặp? Đơn đồ thị vô hướng Vô hướng Không Đa đồ thị vô hướng Vô hướng Có Đơn đồ thị có hướng Có hướng Không Đa đồ thị có hướng Có hướng Có • Chú ý: Khuyên (loop) – Một dạng đồ thị ít sử dụng hơn, đó là giả đồ thị. Giả đồ thị là đa đồ thị mà trong đó có các khuyên (cạnh nối 1 đỉnh với chính nó). – Cách phân loại đồ thị dùng ở đây chưa chắc đã được chấp nhận trong các tài liệu khác 28 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  29. Các thuật ngữ Graph Terminology Chúng ta cần các thuật ngữ liên quan đến mối quan hệ giữa các đỉnh và các cạnh của đồ thị sau: • Kề nhau, nối, đầu mút, bậc, bắt đầu, kết thúc, bán bậc vào, bán bậc ra, u u e e v v Cạnh vô hướng e=(u,v) Cạnh có hướng (cung) e=(u,v) 29 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  30. Kề (Adjacency) u e v Cho G là đồ thị vô hướng với tập cạnh E. Giả sử e E là cặp (u,v). Khi đó ta nói: • u, v là kề nhau/lân cận/nối với nhau (adjacent / neighbors / connected). • Cạnh e là liên thuộc với hai đỉnh u và v. • Cạnh e nối (connect) u và v. • Các đỉnh u và v là các đầu mút (endpoints) của cạnh e. 30 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  31. Tính kề trong đồ thị có hướng u e v • Cho G là đồ thị có hướng (có thể là đơn hoặc đa) và giả sử e = (u,v) là cạnh của G. Ta nói: – u và v là kề nhau, u là kề tới v, v là kề từ u – e đi ra khỏi u, e đi vào v. – e nối u với v, e đi từ u tới v – Đỉnh đầu (initial vertex) của e là u – Đỉnh cuối (terminal vertex) của e là v 31 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  32. Chương 1 CÁC KHÁI NIỆM CƠ BẢN 1.1. Đồ thị trong thực tế 1.2. Các loại đồ thị 1.3. Bậc của đỉnh 1.4. Đồ thị con 1.5. Đồ thị đẳng cấu 1.6. Đường đi và chu trình 1.7. Tính liên thông 1.8. Một số loại đồ thị đặc biệt 32 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  33. Bậc của đỉnh (Degree of a Vertex) • Giả sử G là đồ thị vô hướng, v V là một đỉnh nào đó. • Bậc của đỉnh v, deg(v), là số cạnh kề với nó. • Đỉnh bậc 0 được gọi là đỉnh cô lập (isolated). • Đỉnh bậc 1 được gọi là đỉnh treo (pendant). • Các ký hiệu thường dùng: (G) = min {deg(v): v V}, (G) = max {deg(v): v V}. 33 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  34. Ví dụ Cạnh (a,b) là liên thuộc b là kề với c và c là kề với b với hai đỉnh a và b b c a f d e deg(f) = 0 deg(d) = 3 f là đỉnh cô lập (G) = min {deg(v): v V} = 0, g deg(g) = 1 (G) = max {deg(v): v V}= 3. g là đỉnh treo 34 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  35. Định lý về các cái bắt tay (Handshaking Theorem) • Định lý. Giả sử G là đồ thị vô hướng (đơn hoặc đa) với tập đỉnh V và tập cạnh E. Khi đó deg(v) = 2 E v V CM: Trong tổng ở vế trái mỗi cạnh e=(u,v) E được tính hai lần: trong deg(u) và deg(v). • Hệ quả: Trong một đồ thị vô hướng bất kỳ, số lượng đỉnh bậc lẻ (đỉnh có bậc là số lẻ) bao giờ cũng là số chẵn. 35 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  36. Ví dụ. Biết rằng mỗi đỉnh của đồ thị vô hướng G=(V,E) với 14 đỉnh và 25 cạnh đều có bậc là 3 hoặc 5. Hỏi G có bao nhiêu đỉnh bậc 3? Giải. Giả sử G có x đỉnh bậc 3. Khi đó có 14-x đỉnh bậc 5. Do | E | = 25, nên tổng tất cả các bậc là 50. Từ đó, 3x + 5(14-x) = 50 Suy ra x = 10. 32
  37. Bậc của đỉnh của đồ thị có hướng • Cho G là đồ thị có hướng, v là đỉnh của G. – Bán bậc vào (in-degree) của v, deg-(v), là số cạnh đi vào v. – Bán bậc ra (out-degree) của v, deg+(v), là số cạnh đi ra khỏi v. – Bậc của v, deg(v):deg-(v)+deg+(v), là tổng của bán bậc vào và bán bậc ra của v. 37 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  38. Ví dụ b kề tới c và c kề từ b b c a f deg-(a) = 0 d deg+(a)= 2 e deg-(f) = 0 a- đỉnh nguồn deg+(f)= 0 deg-(d) = 2 deg-(e) = 2 deg+(d)= 1 deg+(e)= 0 e – đỉnh đích (target) 38 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  39. Định lý về các cái bắt tay có hướng Directed Handshaking Theorem • Định lý. Giả sử G là đồ thị có hướng (có thể là đơn hoặc đa) với tập đỉnh V và tập cạnh E. Khi đó: 1 deg- (v) = deg+ (v) = deg(v) = E v V v V 2 v V • Chú ý là khái niệm bậc của đỉnh là không thay đổi cho dù ta xét đồ thị vô hướng hay có hướng. 39 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  40. Chương 1 CÁC KHÁI NIỆM CƠ BẢN 1.1. Đồ thị trong thực tế 1.2. Các loại đồ thị 1.3. Bậc của đỉnh 1.4. Đồ thị con 1.5. Đồ thị đẳng cấu 1.6. Đường đi và chu trình 1.7. Tính liên thông 1.8. Một số loại đồ thị đặc biệt 1.9. Tô màu đồ thị 40 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  41. Đồ thị con (Subgraphs) • Định nghĩa. Đồ thị H=(W,F) được gọi là đồ thị con của đồ thị G=(V,E) nếu WV và FE. • Ký hiệu: HG. G H 41 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  42. Ví dụ Definition. A graph H is a subgraph of a graph G if V(H)  V(G) and E(H)  E(G) (denote H  G). Ví dụ v w v w v w u x y x y x y G H  G F  G
  43. Đồ thị con cảm sinh Induced Subgraph Định nghĩa. Cho G = (V, E) là đồ thị vô hướng. Giả sử S  V, S . Đồ thị con cảm sinh bởi S là đồ thị con cực đại của G với tập đỉnh là S. (thường ký hiệu là ) Đồ thị con H của đồ thị G được gọi là đồ thị con cảm sinh đỉnh (vertex-induced subgraph) của G nếu tìm được S  V sao cho H= . Ví dụ: G v w H v w H không là đồ thị con cảm sinh của G. u H ∪{(x,w)} đúng x y x y
  44. Loại bỏ đỉnh The deletion of vertices Định nghĩa. Cho G = (V, E) là đồ thị vô hướng. Giả sử S  V. Ta gọi việc loại bỏ tập đỉnh S khỏi đồ thị là việc loại bỏ tất cả các đỉnh trong S cùng các cạnh kề với chúng. • Như vậy nếu ký hiệu đồ thị thu được là G-S, ta có G-S = . Nếu S={v}, thì để đơn giản ta viết G-v. G v w G-S v w Giả sử S={x,u} u u x y x y
  45. Đồ thị con cảm sinh cạnh Edge Induced Subgraph Định nghĩa. Cho G = (V, E) là đồ thị vô hướng. Giả sử X  E, X . Đồ thị con cảm sinh bởi X là đồ thị con nhỏ nhất của G với tập cạnh là X. (ký hiệu bởi ) Đồ thị con H của G được gọi là đồ thị con cảm sinh cạnh (edge- induced subgraph) nếu H= đối với một tập con nào đó X  E. Ví dụ: G v w v w Cho X={(u,v),(v,w)} u u x y
  46. Đồ thị con cảm sinh cạnh và cảm sinh đỉnh Ví dụ. Cho G=(V,E) là đồ thị vô hướng. Nếu H= , thì có thể suy ra H= được không? No G u H v w v w Dễ thấy, G = . Ví dụ trên cho thấy không nhất thiết trùng với G
  47. Đồ thị con bao trùm Spanning Subgraph Định nghĩa. Đồ thị con H  G được gọi là đồ thị con bao trùm của G nếu tập đỉnh của H là tập đỉnh của G: V(H) = V(G). Định nghĩa. Ta viết H = G + {(u,v), (u,w)} hiểu là E(H) = E(G) ∪ {(u,v), (u,w)}, trong đó (u,v), (u,w) E(G).
  48. Hợp của hai đồ thị • Hợp G1G2 của hai đơn đồ thị G1=(V1, E1) và G2=(V2,E2) là đơn đồ thị (V1V2, E1E2). a b c  a b c d e d f 48 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  49. Hợp của các đồ thị Nếu S1, S2, S3, S4, S5, S6 là các hình vuông, khi đó Q3 là hợp của các diện của nó: Q3 = S1S2S3S4S5S6 49
  50. Chương 1 CÁC KHÁI NIỆM CƠ BẢN 1.1. Đồ thị trong thực tế 1.2. Các loại đồ thị 1.3. Bậc của đỉnh 1.4. Đồ thị con 1.5. Đồ thị đẳng cấu 1.6. Đường đi và chu trình 1.7. Tính liên thông 1.8. Một số loại đồ thị đặc biệt 1.9. Tô màu đồ thị 50 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  51. Đồ thị đẳng cấu Graph Isomorphism • Định nghĩa: Hai đơn đồ thị vô hướng G1=(V1, E1) và G2=(V2, E2) là đẳng cấu (isomorphic) iff  song ánh f : V1→V2 sao cho  a, b V1, a và b là kề nhau trên G1 iff f(a) và f(b) là kề nhau trên G2. • f là hàm đặt tên lại các đỉnh để cho hai đồ thị là đồng nhất. • Có thể tổng quát định nghĩa này cho các loại đồ thị còn lại. 51 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  52. Bất biến đối với đẳng cấu Điều kiện cần nhưng không phải là đủ để G1=(V1, E1) là đẳng cấu với G2=(V2, E2): – Ta phải có |V1|=|V2|, và |E1|=|E2|. – Số lượng đỉnh bậc k ở hai đồ thị là như nhau. 52 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  53. Ví dụ đẳng cấu • Nếu là đẳng cấu thì hãy gán tên cho đồ thị thứ hai để thấy rõ sự đẳng cấu, trái lại hãy nêu rõ sự khác biệt. b d a b a d c e e c f f 53 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  54. Có đẳng cấu không? • Nếu là đẳng cấu thì hãy gán tên cho đồ thị thứ hai để thấy rõ sự đẳng cấu, trái lại hãy nêu rõ sự khác biệt. • Cùng số a lượng đỉnh b • Cùng số lượng cạnh d • Khác số lượng c e đỉnh bậc 2 (1 3) 54 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  55. Chương 1 CÁC KHÁI NIỆM CƠ BẢN 1.1. Đồ thị trong thực tế 1.2. Các loại đồ thị 1.3. Bậc của đỉnh 1.4. Đồ thị con 1.5. Đồ thị đẳng cấu 1.6. Đường đi và chu trình 1.7. Tính liên thông 1.8. Một số loại đồ thị đặc biệt 1.9. Tô màu đồ thị 55 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  56. Đường đi, Chu trình • §Þnh nghÜa. §êng ®i P ®é dµi n tõ ®Ønh u ®Õn ®Ønh v, trong ®ã n lµ sè nguyªn d¬ng, trªn ®å thÞ G=(V,E) lµ d·y P: x0, x1, . . . , xn-1, xn trong ®ã u = x0, v = xn, (xi, xi+1) E, i = 0, 1, 2, , n-1. §êng ®i nãi trªn cßn cã thÓ biÓu diÔn díi d¹ng d·y c¸c c¹nh: (x0, x1), (x1, x2), . . . , (xn-1, xn). §Ønh u gäi lµ ®Ønh ®Çu, cßn ®Ønh v gäi lµ ®Ønh cuèi cña ®êng ®i. 56 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  57. Đường đi, Chu trình • Đường đi gọi là đường đi đơn nếu không có đỉnh nào bị lặp lại trên nó. • Đường đi gọi là đường đi cơ bản nếu không có cạnh nào bị lặp lại trên nó. • Nếu có đường đi từ u đến v thì ta nói đỉnh v đạt đến được từ đỉnh u. Ta quan niệm rằng một đỉnh v luôn đạt đến được từ chính nó. 57 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  58. Đường đi (Path) 5 c d a b 1 2 3 e 4 Ví dụ: 5, 2, 3, 4 hoặc 5, c, 2, b, 3, e, 4. Không có đỉnh lặp nên là đường đi đơn 5 c d a b 1 2 3 e 4 Ví dụ: 1, 2, 5, 3, 4 hoặc 1, a, 2, c, 5, d, 3, e, 4 • Là đường đi đơn 58 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  59. Ví dụ (cont.) • P1=(1,b,2,h,3) là đường 1 đi đơn a b P1 d • P =(4,c,5,e,2,g,6,f,5,d,1) 4 2 3 2 P2 h là đường đi nhưng c e không là đường đi đơn 5 g f 6 59 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  60. Ví dụ (cont.) • P1=(1, b, 2, h, 3) là 1 đường đi đơn a b P1 d • P =(4,c,5,e,2,g,6,f,5,d,1) 4 2 3 2 P2 h là đường đi nhưng c e không là đường đi đơn 5 g f 6 60 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  61. Chu trình • Đường đi cơ bản có đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi là chu trì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. 61 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  62. Chu trình (Cycle) 2 a b e Chu trình 1 3 1, 2, 3, 1. (hay 1, a, 2, b, 3, e) d c • Chu trình đơn 4 2 a b Chu trình: (1, 2, 3, 4, 1) hay e 1 3 1, a, 2, b, 3, c, 4, d, 1 d c • Chu trình đơn 4 62 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  63. Ví dụ: Chu trình trên đồ thị vô hướng • C1=(V,b,X,g,Y,f,W,c,U,a,V) là chu trình đơn • C2=(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 đơn V a b d U C2 X Z h e c C1 W g f Y 63 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  64. Ví dụ: Chu trình trên đồ thị có hướng • C1=(V,b,X,g,Y,f,W,c,U,a,V) là chu trình đơn • C2=(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 đơn V a b U d X Z C2 h e c C1 W g f Y 64 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  65. Chương 1 CÁC KHÁI NIỆM CƠ BẢN 1.1. Đồ thị trong thực tế 1.2. Các loại đồ thị 1.3. Bậc của đỉnh 1.4. Đồ thị con 1.5. Đồ thị đẳng cấu 1.6. Đường đi và chu trình 1.7. Tính liên thông 1.8. Một số loại đồ thị đặc biệt 1.9. Tô màu đồ thị 65 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  66. Tí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ụ i f j k G2 G1 • 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ông 66 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  67. Tí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. 67 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  68. Tí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, G3 i b c f a j k G 2 d e G3 g G1 68 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  69. Thành phần liên thông i b c V(a)={a,b,c,d,e,g}; f a j k G ≡G(f) 2 d e G3 ≡G(i) G ≡G(a) 1 g Gỉ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). 69 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  70. Ví dụ Ví dụ: Cho G là đồ thị vô hướng n 2 đỉnh. Biết rằng (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 (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?!
  71. Đỉ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ụ: b c a e là đỉnh rẽ nhánh d e Cạnh (e,g) là cầu g G 71 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  72. Ví dụ Mệ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)
  73. Chứng minh mệnh đề (cont) 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 C Vậy G-e là liên thông. P u1 u v v1
  74. Chứ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 ?!
  75. k-liên thông (k-Connectivity) 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) G1 2) G2 3) G3 4) G4 75
  76. k-Connectivity A: 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ểm yếu— “cut vertex” 2) 3rd best. Thông suốt nhưng mỗi máy đều là điểm “yếu” 3) Tồi nhất! Không thông suốt 4) Tốt nhất! Mạng chỉ không thông suốt nếu hỏng 2 máy 76
  77. k-Connectivity Mạ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. 77
  78. k-liên thông Tổ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ông • Q4 là ?-liên thông Q3 Q4 78 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  79. Tí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. 79 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  80. Ví dụ b c b c a f a f d e d e • Đồ thị liên thông mạnh Đồ thị liên thông yếu b c a f d e 80 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  81. Chương 1 CÁC KHÁI NIỆM CƠ BẢN 1.1. Đồ thị trong thực tế 1.2. Các loại đồ thị 1.3. Bậc của đỉnh 1.4. Đồ thị con 1.5. Đồ thị đẳng cấu 1.6. Đường đi và chu trình 1.7. Tính liên thông 1.8. Một số loại đồ thị đặc biệt 1.9. Tô màu đồ thị 81 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  82. Một số dạng đơn đồ thị vô hướng đặc biệt • Đồ thị đầy đủ (Complete graphs) Kn • Chu trình (Cycles) Cn • Bánh xe (Wheels) Wn • n-Cubes Qn • Đồ thị hai phía (Bipartite graphs) • Đồ thị hai phía đầy đủ (Complete bipartite graphs) Km,n • Đồ thị chính qui • Cây và rừng • Đồ thị phẳng 82 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  83. Đồ thị đầy đủ Complete Graphs • Vớ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. K 1 K K3 K4 2 K K5 6 n-1 n(n -1) i = Để ý là Kn có i = 1 2 cạnh. 83 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  84. Đồ thị đầy đủ Complete Graphs K25 84
  85. Đồ thị đầy đủ Complete Graphs 85 K42
  86. Chu 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)}. C3 C4 C 5 C6 C C7 8 Có bao nhiêu cạnh trong Cn? 86 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  87. Bá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)}. W3 W4 W 5 W6 W W7 8 Có bao nhiêu cạnh trong Wn? 87 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  88. Siê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. Q0 Q1 Q2 Q4 Q3 Số đỉnh: 2n. Số cạnh: ? 88 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  89. Siê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. Q0 Q1 Q2 Q3 Q4 Số đỉnh: 2n. Số cạnh: ? 89 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  90. Siêu cúp Q4 90 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  91. Siê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. 91 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  92. Đồ thị hai phía (Bipartite Graphs) • Đị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. V1 V2 Định nghĩa này là chung cho cả đơn lẫn đa đồ thị vô hướng, có hướng. 92 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  93. Đồ 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. Km,n có ___ đỉnh và ___ cạnh. K4,3 93 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  94. Đồ thị chính qui r-regular graph • Đị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 qui Đồ thị chính qui Đồ thị chính qui Đồ thị chính qui bậc 0 bậc 1 bậc 2 bậc 3 94 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  95. Đồ thị Platonic • Xét các khối đa diện Platonic trong không gian 3-chiều Tetrahedron Hexahedron (cube) Octahedron Tứ diện Lục diện Bát diện Dodecahedron Icosahedron Thập nhị diện Thập bát diện 95 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  96. Đồ 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ẳng Tetrahedron Hexahedron (cube) Octahedron Dodecahedron Icosahedron 96 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  97. Câ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. T 1 T2 T3 Rừng F gồm 3 cây T1, T2,, T3 97 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  98. VÍ DỤ G1, G2 là cây G3, G4 không là cây 98 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  99. Cá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. 99 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  100. Đồ 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! 100 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  101. Các đồ thị Platonic đều phẳng • Tất cả 5 đồ thị Platonic đều là đồ thị phẳng 101 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  102. 3-Cube là đồ thị phẳng 102 L25
  103. 4-Cube có là đồ thị phẳng không? Có vẻ phẳng, nhưng chứng minh bằng cách nào? 103
  104. K3,3 và K5 không là đồ thị phẳng • Đồ thị K3,3 và K5 không là đồ thị phẳng • Mọ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). 104 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  105. Khả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. 105 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  106. Khảo sát đồ thị phẳng • Ví dụ: Xét đồ thị phẳng • Loại bỏ khuyên và cạnh lặp: • Vẽ đơn đồ thị thu được: • Bổ sung khuyên và cạnh lặp: 106
  107. Công thức Euler Euler's Formula • Nế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. 107 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  108. Công thức Euler Euler's Formula • Ví 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). 108
  109. Công thức Euler • Cô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. 109 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  110. Chứng minh công thức Euler • Chứ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ạp n – (m – 1) + (f – 1) = 2 từ đó suy ra n – 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. 110
  111. Hệ 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 = 2 ta thu được m – n + 2 ≤ 2/3 m. Từ đó suy ra m ≤ 3n – 6. 111 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  112. K5 không là đồ thị phẳng • Hệ 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. 112 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  113. Hệ quả 3 • Hệ 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. 113 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  114. K3,3 không là đồ thị phẳng • Hệ 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ượng 114 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  115. Bài toán xây dựng hệ thống cung cấp năng lượng • Tì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: 115 TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  116. Chứng minh Q4 không phẳng Ta 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. 116
  117. Nhận biết đồ thị phẳng • Cá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ét • Nhậ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ủ định – Nhận xét 2a: Nếu G chứa đồ thị không phẳng như đồ thị con thì G không là đồ thị phẳng 117 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  118. • Ví 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 G2 118 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  119. Nhậ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ẳng • Ví 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 119 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  120. Nhậ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ụ: • đồng phôi với đồng phôi với 120 TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  121. Đị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ị K5 K. Kuratowski Đồ thị Petersen K 1896-1980 5 Poland 121 TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  122. Đồ thị Euler • Định nghĩa • Nhận biết đồ thị Euler 122 TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  123. Đồ thị Euler • Chu 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. 123
  124. Ví dụ a b a b f c d e c d e Đồ thị nửa Euler Đồ thị Euler a, c, d, b, e, d, a, b a, c, d, e, b, d, f, b, a 124 TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  125. Bài toán về 7 cái cầu ở Königsberg • Hiện nay là Kaliningrad (thuộc Nga) • Sông Pregel A B D C Leonhard Euler 1707-1783 125
  126. Bài toán về 7 cái cầu ở Königsberg • Tồ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? A A D D B B C C Đa đồ thị vô Sơ đồ 7 cái cầu hướng tương ứng 126
  127. Đị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. 127
  128. Ví dụ Đỉnh bậc lẻ Đỉnh bậc lẻ a b a b f c d e c d e Đồ thị nửa Euler Đồ thị Euler 128 TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  129. Vẽ một nét Hì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)? 129
  130. Vẽ một nét Trong ngôn ngữ đồ thị: Đồ thị nào trong hai đồ thị sau đây có đường đi Euler? 130
  131. Vẽ một nét – Đường đi Euler Trả lời: Ngôi nhà vẽ được bởi một nét, còn ôtô thì không thể. 1 2 3 start finish 4 6 5 131
  132. Đồ thị Hamilton • Định nghĩa • Nhận biết đồ thị Hamilton 132 TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  133. Đồ 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 Hamilton 133
  134. Trò chơi vòng quanh thế giới (Round-the-World Puzzle) • Bạn có thể chỉ ra cách đi qua tất cả các đỉnh Sir William của dodecahedron (thập nhị diện) mỗi đỉnh Rowan Hamilton 1805-1865 đúng một lần?` Dodecahedron puzzle Đồ thị Hộp trò chơi tương ứng 134
  135. Ví dụ • Đồ thị Hamilton 135 TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  136. Ví dụ Ví 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: x x’ x x’ y y’ y y’ 3 - cube (n -1)-cube (n -1)-cube
  137. Đồ thị Hamilton • Đồ thị có hai đỉnh bậc 1 không là đồ thị Hamilton • Dễ thấy đồ thị trên là đồ thị nửa Hamilton 137 TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  138. Tutte Graph 1. Đồ thị Tutte là 3-liên thông và chính qui bậc 3. 2. Đồ thị Tutte không là đồ thị Hamilton.
  139. Đồ thị không là nửa Hamilton • Các đỉnh bậc 1 phải là đỉnh bắt đầu hoặc kết thúc của đường đi Hamilton. Đồ thị có ba đỉnh bậc 1 không là nửa Hamilton 139 TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  140. Đồ 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. 140 TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  141. Đị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. 141
  142. Paul Adrien Maurice Dirac Oystein Ore 1902 - 1984 1899 - 1968 (USA) (Norway) 142 TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  143. 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. 143
  144. Chương 1 CÁC KHÁI NIỆM CƠ BẢN 1.1. Đồ thị trong thực tế 1.2. Các loại đồ thị 1.3. Bậc của đỉnh 1.4. Đồ thị con 1.5. Đồ thị đẳng cấu 1.6. Đường đi và chu trình 1.7. Tính liên thông 1.8. Một số loại đồ thị đặc biệt 1.9. Tô màu đồ thị 144 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  145. Tô màu đồ thị Graph Coloring • Tô màu đỉnh (Vertex Coloring) • Tô màu cạnh (Edge Coloring) 145 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  146. Tô màu đồ thị - Graph Coloring Xét bản đồ 146
  147. Tô màu bản đồ - Map Coloring Ta 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: 147
  148. Map Coloring Bổ sung thêm 1 màu nữa. Thử tô các nước bởi 2 màu. 148
  149. Map 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. 149
  150. Map 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. 150
  151. Map 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. 151
  152. Map Coloring Hai nước bị tô bởi cùng màu. Không phân biệt được danh giới. 152
  153. Map Coloring Vậy thì thêm 1 màu nữa: 153
  154. Map Coloring Vẫn không đủ. Cần ít ra là 4 màu bởi vì chính nước này. 154
  155. Map Coloring Với 4 màu, có thể tô được. 155
  156. 4-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.) 156
  157. Từ 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ị: 157
  158. Từ tô màu bản đồ đến tô màu đồ thị Mỗi vùng đặt tương ứng với một đỉnh: 158
  159. Từ tô màu bản đồ đến tô màu đồ thị Hai vùng có chung biên giới có cạnh nối: 159
  160. Từ 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ó. 160
  161. Từ 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: 161
  162. Từ 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: 162
  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ư sau – Tậ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. 163
  164. Từ tô màu bản đồ đến tô màu đồ thị Như vậy đồ thị đối ngẫu là: 164
  165. Từ 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. 165
  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). 166
  167. Từ 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: 167
  168. Từ 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: 168
  169. Từ 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: 169
  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. 170
  171. Thuật toán tham lam • Khở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ó. 3 2 1 1 4 2 5 2 3 2 3 3 4 5 1 6 4 4 6 1 • Chú ý: 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ị.
  172. Cậ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 minh • Trong 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).
  173. Tô màu đồ thị và Lập lịch Ví 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, 4156 • Giả 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-3137 1007-3157, 3137-3157 1007-3203 1007-3261, 3137-3261, 3203-3261 1007-4115, 3137-4115, 3203-4115, 3261-4115 1007-4118, 3137-4118 1007-4156, 3137-4156, 3157-4156 Hỏ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) 173
  174. Tô 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): 3203 3261 3137 4115 1007 4118 3157 4156 174
  175. Tô màu đồ thị và Lập lịch • Trướ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) 3203 3261 3137 4115 1007 4118 3157 4156 175
  176. Tô màu đồ thị và Lập lịch và sau đó xây dựng đồ thị bù (complementary graph): 3203 3261 3137 4115 1007 4118 3157 4156 176
  177. Tô màu đồ thị và Lập lịch và 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): 3203 3261 3137 4115 1007 4118 3157 4156 177
  178. Tô màu đồ thị và Lập lịch Vẽ lại: 3137 3203 3261 4115 1007 3157 4118 4156 178
  179. Tô màu đồ thị và Lập lịch Không thể tô bởi 1 màu vì cạnh này 3137 3203 3261 4115 1007 3157 4118 4156 179
  180. Tô màu đồ thị và Lập lịch 2 màu không đủ tô vì có tam giác này 3137 3203 3261 4115 1007 3157 4118 4156 180
  181. Tô 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. 3137 3203 3261 4115 1007 3157 4118 4156 181
  182. Tô màu đồ thị và Lập lịch 3203-Red, 3157-Blue, 4118-Green: 3137 3203 3261 4115 1007 3157 4118 4156 182
  183. Tô màu đồ thị và Lập lịch do đó 4156 phải tô bởi Blue: 3137 3203 3261 4115 1007 3157 4118 4156 183
  184. Tô màu đồ thị và Lập lịch vì thế 3261 và 4115 phải là Red. 3137 3203 3261 4115 1007 3157 4118 4156 184
  185. Tô màu đồ thị và Lập lịch 3137 và 1007 dễ dàng tô. 3137 3203 3261 4115 1007 3157 4118 4156 185
  186. Tô màu đồ thị và Lập lịch Vậy cần 3 ngày: Ngày 2 3137 3203 3261 Ngày 1 4115 1007 3157 4118 4156 Ngày 3 186
  187. Tô 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) 187 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  188. Tô 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ên – Vế 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 / 188 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  189. Thuậ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)| < (G) và |M(v)| < (G). Có hai tình huống: • 1) Nếu tìm được màu c C \ (M(u)  M(v)) thì có thể dùng màu c để tô màu cạnh e. 189 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  190. Thuật toán tô màu / 2) Không tìm được màu c C \ (M(u)  M(v)). Do |M(u)| < (G) và |M(v)| < (G) suy ra phải tìm được α là màu chưa được dùng để tô bất cứ cạnh nào kề với u nhưng đã được dùng để tô cạnh kề với v, và β là màu chưa được dùng để tô bất cứ cạnh nào kề với v nhưng đã được dùng để tô cạnh kề với u. Khi đó xuất phát từ u ta đi theo cạnh màu β ta đến đỉnh v1, nếu trong số các cạnh kề v1 đã có cạnh được tô màu α thi đi theo cạnh này ta đến đỉnh v2, Gọi đường đi tìm được là P. Lật ngược màu α/ β của các cạnh trên đường đi này, khi đó cách tô màu cạnh vẫn hợp lệ, đồng thời màu β có thể được dùng 190 đểPhần tô2. LÝ cạnhTHUYẾT ĐỒe. THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  191. Chương 2 BIỂU DIỄN ĐỒ THỊ Representations of Graphs 191 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  192. Biểu diễn đồ thị • Có nhiều cách biểu diễn. Việc lựa chọn cách biểu diễn phụ thuộc vào từng bài toán cụ thể cần xét, thuật toán cụ thể cần cài đặt. • Có hai vấn đề chính cần quan tâm khi lựa chọn cách biểu diễn: – Bộ nhớ mà cách biểu diễn đó đòi hỏi – Thời gian cần thiết để trả lời các truy vấn thường xuyên đối với đồ thị trong quá trình xử lý đồ thị: • Chẳng hạn: – Có cạnh nối hai đỉnh u, v ? – Liệt kê các đỉnh kề của đỉnh v ? 192 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  193. Ma trận kề (Adjacency Matrix) • |V| |V| ma trận A. • Các đỉnh được đánh số từ 1 đến |V| theo 1 thứ tự nào đó. • A xác định bởi: 1 nÕu (i , j ) E A[,] i j== aij 0 nÕu tr¸i l¹i • n = |V|; m = |E| 193 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  194. Ma trận kề của đồ thị vô hướng 1 2 3 4 5 6 2 3 1 0 1 0 1 0 0 1 2 1 0 1 0 0 0 6 3 0 1 0 1 1 0 4 5 4 1 0 1 0 1 0 5 0 0 1 1 0 0 1 nếu (u,v) E A[u,v] = 0 nếu trái lại 6 0 0 0 0 0 0 194 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  195. Ma trận kề của đồ thị có hướng 1 2 3 4 5 6 2 3 1 0 1 0 1 0 0 1 2 0 0 1 0 0 0 6 3 0 0 0 1 1 0 4 5 4 0 0 0 0 1 0 5 0 0 0 0 0 0 1 nếu (u,v) E A[u,v] = 0 nếu trái lại 6 0 0 0 0 0 0 195 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  196. Tính chất của ma trận kề –Gọi A là ma trận kề của đồ thị vô hướng: T • A là ma trận đối xứng: A = A (aij = aji) • deg(v) = Tổng các phần tử trên dòng v của A • Nếu ký hiệu Ak = (a(k)[u,v]) thì a(k)[u,v] là số lượng đường đi từ u đến v đi qua không quá k-1 đỉnh trung gian. – Khái niệm ma trận kề có thể mở rộng để biểu diễn đa đồ thị vô hướng: auv – số lượng cạnh nối hai đỉnh u và v. 196 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  197. Phân tích chi phí • Bộ nhớ (Space) – |V|2 bits – (|V|2 + |V|)/2 (nếu là đồ thị vô hướng, nhưng khó cài đặt). – Các thông tin bổ sung, chẳng hạn chi phí trên cạnh, cần được cất giữ dưới dạng ma trận. Một cách làm khác là cất giữ con trỏ đến các thông tin này. • Thời gian trả lời các truy vấn – Hai đỉnh i và j có kề nhau? O(1) – Bổ sung hoặc loại bỏ cạnh O(1) – Bổ sung đỉnh: tăng kích thước ma trận – Liệt kê các đỉnh kề của v O(|V|) (ngay cả khi v là đỉnh cô lập). 197 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  198. Ma trận liên thuộc đỉnh cạnh • XÐt G = (V, E), (V = {1, 2, , n}, E = {e1, e2, , em}), lµ ®¬n ®å thÞ cã híng. • Ma trËn liªn thuéc ®Ønh c¹nh A = (aij: i = 1, 2, , n; j = 1, 2, , m), víi • Ma trËn liªn thuéc ®Ønh-c¹nh lµ mét trong nh÷ng c¸ch biÓu diÔn rÊt hay ®îc sö dông trong c¸c bµi to¸n liªn quan ®Õn ®å thÞ cã híng mµ trong ®ã ph¶i xö lý c¸c cung cña ®å thÞ. 198 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  199. Ma trận liên thuộc đỉnh cạnh 199 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  200. Ma trận trọng số • Trong trêng hîp ®å thÞ cã träng sè trªn c¹nh, thay v× ma trËn kÒ, ®Ó biÓu diÔn ®å thÞ ta sö dông ma trËn träng sè C = c[i, j], i, j = 1, 2, , n, víi c( i , j ), nÕu ( i, j ) E c[,] i j = , nÕu (i, j ) E , trong ®ã  lµ gi¸ trÞ ®Æc biÖt ®Ó chØ ra mét cÆp (i,j) kh«ng lµ c¹nh, tuú tõng trêng hîp cô thÓ, cã thÓ ®îc ®Æt b»ng mét trong c¸c gi¸ trÞ sau: 0, + , - . 200 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  201. Danh sách kề • Danh sách kề (Adjacency Lists): Với mỗi đỉnh v cất giữ danh sách các đỉnh kề của nó. – Là mảng Ke gồm |V| danh sách. – Mỗi đỉnh có một danh sách. – Với mỗi u V, Ke[u] bao gồm tất cả các đỉnh kề của u. • Ví dụ: Đồ thị vô hướng Đồ thị có hướng u v w a b c v u w y b e w u v c b x z d y v e b z x f f t 201 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  202. Danh sách kề của đồ thị vô hướng Với mỗi v V, Ke(v) = danh sách các đỉnh u: (v, u) E a b A B Danh sách B D đỉnh kề C A B A C F C B D E D E D A C E E C D F Bộ nhớ = a |V| + 2 b |E| 202 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  203. Danh sách kề của đồ thị có hướng Với mỗi v V, Ke(v) = { u: (v, u) E } a b B A B D C A B C F C D E D E D E E F Bộ nhớ = a |V| + b |E| 203 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  204. Yêu cầu bộ nhớ • Tổng cộng bộ nhớ: (|V|+|E|) • Thường là nhỏ hơn nhiều so với |V|2, nhất là đối với đồ thị thưa (sparse graph). • Đồ thị thưa là đồ thị mà |E| = k |V| với k < 10. • Chú ý: – Phần lớn các đồ thị trong thực tế ứng dụng là đồ thị thưa! – Cách biểu diễn này được sử dụng nhiều nhất trong ứng dụng 204 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  205. Biểu diễn đồ thị • Thời gian trả lời các truy vấn: – Thêm cạnh O(1) – Xoá cạnh Duyệt qua danh sách kề của mỗi đầu mút. – Thêm đỉnh Phụ thuộc vào cài đặt. – Liệt kê các đỉnh kề của v: O( ) (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ề) 205 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  206. Chương 3 C¸c thuËt to¸n duyÖt ®å thÞ (Graph Searching, Graph Traversal) 206 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  207. Các thuật toán duyệt đồ thị • Duyệt đồ thị: Graph Searching hoặc Graph Traversal – Duyệ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) 207 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  208. Ý 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 đen • Trạ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). 208 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  209. Tìm kiếm theo chiều rộng Breadth-first Search (BFS) 209 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  210. Tìm kiếm theo chiều rộng Breadth-first Search • Input: Đồ 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. 210 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  211. Procedure BFS(s); (* Tìm kiếm theo chiều rộng bắt đầu từ đỉnh s *) begin color[s]  gray; d[s]  0; [s]  nil; Q  ; enqueue(Q,s); (* Nạp s vào Q *) Trắng: chưa thăm while Q  do xám: đã thăm begin đen: đã duyệt xong u  dequeue(Q); (* Lấy u từ Q *) for v Adj[u] do if color[v] = white then Q: hàng đợi các đỉnh được begin color[v]  gray; thăm d[v]  d[u] + 1; [v]  u; color[v]: màu của đỉnh v enqueue(Q,v) (* Nạp v vào Q *) d[v]: khoảng cách từ s đến v end; [u]: đỉnh đi trước v color[u]  black end; end; BEGIN (* Main Program*) Ví dụ: xem minh hoạ 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. 211 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  212. Ví dụ (BFS) r s t u 0 v w x y Q: s 0 212 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  213. Ví dụ (BFS) r s t u 1 0 1 v w x y Q: w r 1 1 213 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  214. Ví dụ (BFS) r s t u 1 0 2 1 2 v w x y Q: r t x 1 2 2 214 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  215. Ví dụ (BFS) r s t u 1 0 2 2 1 2 v w x y Q: t x v 2 2 2 215 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  216. Ví dụ (BFS) r s t u 1 0 2 3 2 1 2 v w x y Q: x v u 2 2 3 216 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  217. Ví dụ (BFS) r s t u 1 0 2 3 2 1 2 3 v w x y Q: v u y 2 3 3 217 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  218. Ví dụ (BFS) r s t u 1 0 2 3 2 1 2 3 v w x y Q: u y 3 3 218 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  219. Ví dụ (BFS) r s t u 1 0 2 3 2 1 2 3 v w x y Q: y 3 219 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  220. Ví dụ (BFS) r s t u 1 0 2 3 2 1 2 3 v w x y Q:  220 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  221. Ví dụ (BFS) r s t u 1 0 2 3 2 1 2 3 v w x y Cây BFS(s) 221 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  222. Phân tích BFS • Việc khởi tạo đòi hỏi O(|V|). • Vòng lặp duyệt – Mỗ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ị. 222 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  223. Câ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. 223 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  224. BFS – Loang trên đồ thị • Thứ tự thăm đỉnh nhờ thực hiện BFS(A) A L0 A B C D L1 B C D E F L2 E F 224 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  225. Ứng dụng trực tiếp cuả BFS • Sử 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ông • Xé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]] . . . s • Chú ý: BFS tìm được đường đi ngắn nhất theo số cạnh. 225 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  226. Tìm kiếm theo chiều sâu Depth-first Search (DFS) 226 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  227. Ý tưởng của tìm kiếm theo chiều sâu • Ta 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µ cha ®î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µ cha 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 cha thăm kÒ víi s. 227 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  228. Mô tả DFS • Input: Đồ 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ả. 228 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  229. Depth-First Search: Code DFS(G) procedure DFS(u); BEGIN begin color[u] = GRAY; for v V do time = time+1; begin d[u] = time; color[v] = WHITE; for v Ke(u)do [v] = NIL if (color[v]= WHITE)then end; begin time = 0; [v] = u; DFS(v); for u V do end; begin color[u] = BLACK; if (color[u]= WHITE) then time = time+1; DFS(u); f[u] = time; end; end; END. 229 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  230. Phân tích thuật toán DFS • Mỗ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ướng – Như 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ính 230 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  231. Ví dụ: DFS Đỉnh xuất phát tìm kiếm (Source vertex) a e g b f c d h Để 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ển 231 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  232. Ví dụ: DFS source vertex d[v] f[v] e g a 1 | | | b f | | | | | c d h 232 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  233. Ví dụ: DFS source vertex a e g 1 | | | b f 2 | | | | | c d h 233 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  234. Ví dụ: DFS source vertex a e g 1 | | | b f 2 | | 3 | | | c d h 234 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  235. Ví dụ: DFS source vertex a e g 1 | | | b f 2 | | 3 | 4 | | c d h 235 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  236. Ví dụ: DFS source vertex a e g 1 | | | b f 2 | | 3 | 4 5 | | c d h 236 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  237. Ví dụ: DFS source vertex a e g 1 | | | b f 2 | | 3 | 4 5 | 6 | c d h 237 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  238. Ví dụ: DFS source vertex a e g 1 | 8 | | b f 2 | 7 | 3 | 4 5 | 6 | c d h 238 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  239. Ví dụ: DFS source vertex a e g 1 | 8 | | b f 2 | 7 | 3 | 4 5 | 6 | c d h 239 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  240. Ví dụ: DFS source vertex a e g 1 | 8 | | b f 2 | 7 9 | 3 | 4 5 | 6 | c d h 240 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  241. Ví dụ: DFS source vertex a e g 1 | 8 | | b f 2 | 7 9 |10 3 | 4 5 | 6 | c d h 241 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  242. Ví dụ: DFS source vertex a e g 1 | 8 |11 | b f 2 | 7 9 |10 3 | 4 5 | 6 | d h 242 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  243. Ví dụ: DFS source vertex a e g 1 |12 8 |11 | b f 2 | 7 9 |10 3 | 4 5 | 6 | c d h 243 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  244. Ví dụ: DFS source vertex a e g 1 |12 8 |11 13| b f 2 | 7 9 |10 3 | 4 5 | 6 | c d h 244 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  245. Ví dụ: DFS source vertex a e g 1 |12 8 |11 13| b f 2 | 7 9 |10 3 | 4 5 | 6 14| c d h 245 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  246. Ví dụ: DFS source vertex a e g 1 |12 8 |11 13| b f 2 | 7 9 |10 3 | 4 5 | 6 14|15 c d h 246 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  247. Ví dụ: DFS source vertex a e g 1 |12 8 |11 13|16 b f 2 | 7 9 |10 3 | 4 5 | 6 14|15 c d h 247 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  248. DFS: Các loại cạnh • DFS(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) 248 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  249. Ví dụ: Rừng DFS source Cây DFS(g) vertex a a Cây DFS(a) e g 1 |12 8 |11 13|16 b f source 2 | 7 9 |10 vertex g 3 | 4 5 | 6 14|15 c d h Tree edges 249 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  250. DFS: Cạnh ngược • DFS 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) 250 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  251. Ví dụ: DFS Cạnh ngược source vertex a e g 1 |12 8 |11 13|16 b f 2 | 7 9 |10 3 | 4 5 | 6 14|15 c d h Tree edges Back edges 251 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  252. DFS: Cạnh tới • DFS 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áu • Không là cạnh của cây • Đi từ đỉnh xám đến đỉnh đen 252 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  253. Ví dụ: DFS Cạnh tới source vertex a e g 1 |12 8 |11 13|16 b f 2 | 7 9 |10 3 | 4 5 | 6 14|15 c d h Tree edges Back edges Forward edges 253 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  254. DFS: Cạnh vòng • DFS 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áu – Cạnh vòng (Cross edge): cạnh nối hai đỉnh không có quan hệ họ hàng • Khô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 đen 254 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  255. Ví dụ: DFS Cạnh vòng source vertex a e g 1 |12 8 |11 13|16 b f 2 | 7 9 |10 3 | 4 5 | 6 14|15 c d h Tree edges Back edges Forward edges Cross edges 255 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  256. DFS: Các loại cạnh • DFS 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ên – Forward edge: đi từ tổ tiên đến con cháu – Cross edge: giữa hai đỉnh không có họ hàng • Chú ý: 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òng 256 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  257. DFS: 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. source • Chứng minh bằng phản chứng: F? – Giả sử có cạnh tới (forward edge) – Nhưng khi đó F phải là cạnh ngược (back edge)?! 257 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  258. DFS: Các loại cạnh • Giả 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 source đỉnh kia được khảo sát – Do đó bức tranh bên là không đúng cả hai cạnh bên không thể là cạnh của cây C? 258 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  259. DFS: Phân biệt các loại cạnh • Dễ 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ây 2. GRAY cho biết e là cạnh ngược 3. BLACK cho biết e là cạnh tới hoặc vòng 259 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  260. Phân tích DFS (* Main Program*) DFS-Visit(u) 1. for u V do 1. color[u]  GRAY (* Thăm đỉnh u *) 2. color[u]  white 2. time  time + 1 3. [u]  NIL 3. d[u]  time 4. time  0 4. for each v Adj[u] do 5. for u V do 6. if color[u] = white 5. if color[v] = WHITE 7. then DFS-Visit(u) 6. then [v]  u 7. DFS-Visit(v) 8. color[u]  BLACK (* Đỉnh u đã Các biến time, color, là toàn cục . duyệt xong *) 9. f[u]  time  time + 1 260 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  261. Phân tích DFS • Vò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ính 261 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  262. CÁC ỨNG DỤNG CỦA DFS •Tí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ị 262 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  263. Bài toán về tính liên thông • Bà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ông 263 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  264. DFS giải bài toán liên thông (* Main Program*) DFS-Visit(u) 1. for u V do 1. id[u]  cnt 2. id[u]  0 2. for each v Adj[u] do 3. cnt  0 (* cnt – số lượng tplt *) 3. if id[v] = 0 4. for u V do 4. then DFS-Visit(v) 5. if id[u] = 0 6. then cnt  cnt +1 7. DFS-Visit(u) 264 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  265. Tìm đường đi • Bài toán tìm đường đi – Input: Đồ 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]] . . . s 265 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  266. DFS giải bài toán đường đi (* Main Program*) DFS-Visit(u) 1. for u V do 1. color[u]  GRAY (* Thăm đỉnh u *) 2. color[u]  white 2. for each v Adj[u] do 3. [u]  NIL 3. if color[v] = WHITE 4. DFS-Visit(s) 4. then [v]  u 5. DFS-Visit(v) 266 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  267. DFS và Chu trình • Bà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ậy • Không có cạnh ngược tức là chỉ có cạnh của cây • Nếu chỉ có cạnh của cây thì G chỉ là cây hoặc rừng • Vậy G không chứa chu trinh • Như vậy DFS có thể áp dụng để giải bài toán đặt ra. 267 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  268. DFS và chu trình • Cần phải điều chỉnh như thế nào để phát hiện chu trình? (* Main Program*) DFS(u) 1. for u V do 1. color[u]  GRAY (* Thăm đỉnh u *) 2. color[u]  white 2. time  time + 1 3. [u]  NIL 3. d[u]  time 4. time  0 5. for u V do 4. for each v Adj[u] do 6. if color[u] = white 5. if color[v] = WHITE 7. then DFS-Visit(u) 6. then [v]  u 7. DFS-Visit(v) 8. color[u]  BLACK (* Đỉnh u đã duyệt xong *) 9. f[u]  time  time + 1 268 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  269. DFS và chu trình • Câ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. 269 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  270. Kiểm tra tính liên thông mạnh • Bà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ên 270 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  271. Thuật toán kiểm tra tính liên thông mạnh • Thuậ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Õp –Thù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|) 271 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  272. Thuật toán kiểm tra tính liên thông mạnh a d a d f c f c b e b e Đồ thị G Đồ thị GT 272 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  273. Đị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. 273 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  274. Ví dụ: Định hướng đồ thị a d a d f c f c b e b e Đồ thị G Đồ thị G() 274 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội
  275. Questions? 275 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội