Nội dung

Phần 2 LÝ THUYẾT ĐỒ THỊ Graph Theory Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 1 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 2 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 3 Chương 1 CÁC KHÁI NIỆM CƠ BẢN Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 4 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ị Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 5 Đồ thị là gì? Không phải 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ệ. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 6 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, … Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 7 Mối liên hệ giữa các môn học 461 373 413 321 142 415 410 322 143 370 326 341 417 378 Đỉnh = môn học Cạnh có hướng = đk tiên quyết Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 421 401 8 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 9 Biểu diễn mạch điện (Electrical Circuits) Nguồn Đỉnh = nguồn, công tắc, điện trở, … Cạnh = đoạn dây nối Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, Công tắc Điện trở 10 Các câu lệnh của chương trình Program statements x1=q+y*z x2=y*z-q Thoạt nghĩ: x1 x2 + * q y y*z tính hai lần Loại Biểu thức con chung: Đỉnh = ký hiệu/phép toán Cạnh = mối quan hệ Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, * z x1 x2 + - q * y q q z 11 Yêu cầu trình tự (Precedence) S1 S2 S3 S4 S5 S6 a=0; b=1; c=a+1 d=b+a; e=d+1; e=c+d; 6 5 Các câu lệnh nào phải thực hiện trước S6? 3 4 S1, S2, S3, S4 Đỉnh = câu lệnh Cạnh = yêu cầu trình tự Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 1 2 12 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 30 Sydney Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, New York 181 140 Bắc kinh Đỉnh = máy tính Cạnh = tốc độ truyền thông 13 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ố Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 14 Mạng xe buýt Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 15 Mạng tàu điện ngầm Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 16 Sơ đồ đường phố Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 17 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 18 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 19 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 20 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ị Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 21 Đồ 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 22 Đơ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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 23 Đ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 Cạnh lặp b f h e c g d Đồ thị G2 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 24 Đồ 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 25 Đơ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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 26 Đ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 h e c g d Đồ thị G4 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 27 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ú ý: – 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... Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, Khuyên (loop) 28 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 Cạnh vô hướng e=(u,v) Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, v Cạnh có hướng (cung) e=(u,v) 29 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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 30 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 31 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 32 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}. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 33 Ví dụ Cạnh (a,b) là liên thuộc với hai đỉnh a và b b là kề với c và c là kề với b b c a f d e deg(f) = 0 f là đỉnh cô lập deg(d) = 3 (G) = min {deg(v): v  V} = 0, (G) = max {deg(v): v  V}= 3. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, g deg(g) = 1 g là đỉnh treo 34 Đị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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 35 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 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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 37 Ví dụ b kề tới c và c kề từ b b c a deg-(a) = 0 deg+(a)= 2 a- đỉnh nguồn f d deg-(d) = 2 deg+(d)= 1 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, e deg-(e) = 2 deg+(e)= 0 e – đỉnh đích (target) deg-(f) = 0 deg+(f)= 0 38 Đị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  2 vV vV 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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 39 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ị Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 40 Đồ 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, H 41 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 y x G y x H G y x FG Đồ 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 w H v H không là đồ thị con cảm sinh của G. u x y x y H ∪{(x,w)} đúng 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 Giả sử S={x,u}  u x y v w x y u Đồ 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 (edgeinduced 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 Đồ 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 u G 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 Đồ 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). 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 d e Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, c  a d b c f 48 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 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ị Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 50 Đồ 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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 51 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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 52 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. d b a d e Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, b c f c a f e 53 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. • a b Cùng số lượng đỉnh • Cùng số lượng cạnh d c Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, e • Khác số lượng đỉnh bậc 2 (1 < >3) 54 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ị Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 55 Đườ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µ 56 Phần 2. LÝ THUYẾT ĐỒ THỊ ®Ønh cuèi cña ®­êng ®i. Nguyễn Đức Nghĩa- Bộ môn KHMT, Đườ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ó. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 57 Đường đi (Path) c 1 a 2 5 b d 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 c 1 Ví dụ: 1, 2, 5, 3, 4 • Là đường đi đơn Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, a 2 5 b d 3 e 4 hoặc 1, a, 2, c, 5, d, 3, e, 4 58 Ví dụ (cont.) • P1=(1,b,2,h,3) là đường đi đơn • P2=(4,c,5,e,2,g,6,f,5,d,1) là đường đi nhưng không là đường đi đơn Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, a 4 c 1 b d P2 P1 2 e 5 h 3 g f 6 59 Ví dụ (cont.) • P1=(1, b, 2, h, 3) là đường đi đơn • P2=(4,c,5,e,2,g,6,f,5,d,1) là đường đi nhưng không là đường đi đơn Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, a 4 c 1 b d P2 P1 2 e 5 h 3 g f 6 60 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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 61 Chu trình (Cycle) 2 a Chu trình 1, 2, 3, 1. (hay 1, a, 2, b, 3, e) e 1 d • Chu trình đơn Chu trình: (1, 2, 3, 4, 1) hay 1, a, 2, b, 3, c, 4, d, 1 • Chu trình đơn Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, b c 3 4 2 a e 1 d b c 3 4 62 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 a V b U d C2 c e W f Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, X g h C1 Z Y 63 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 a U c V b d C2 X e Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, C1 g W f h Z Y 64 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ị Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 65 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 66 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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 67 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 f j k G3 G2 b c d e a G1 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, g 68 Thành phần liên thông i f j k G2 ≡G(f) b c d e V(a)={a,b,c,d,e,g}; a G3 ≡G(i) G1≡G(a) 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). Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 69 Ví dụ Ví dụ: Cho G là đồ thị vô hướng n  2 đỉnh. Biết rằng d(G) = min{deg(v): v V}  (n-1)/2. Chứng minh rằng G liên thông. Chứng minh. Phản chứng. Giả sử G không liên thông, khi đó do d(G)  (n-1)/2, nên mỗi thành phần liên thông phải chứa ít ra (n-1)/2+1 = (n+1)/2 đỉnh. Suy ra đồ thị có ít ra (n+1) đỉnh?! Đỉ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 e là đỉnh rẽ nhánh a d e Cạnh (e,g) là cầu G Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, g 71 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) 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 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 ?! 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 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 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 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà Q4 78 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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 79 Ví dụ b c b f a d f a e d • Đồ thị liên thông mạnh b c f d Nguyễn Đức Nghĩa- Bộ môn KHMT, e Đồ thị liên thông yếu a Phần 2. LÝ THUYẾT ĐỒ THỊ c e 80 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ị Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 81 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 82 Đồ 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. K1 K3 K2 K4 K5 K6 n 1 n(n  1) Để ý là Kn có  i  2 cạnh. i 1 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 83 Đồ thị đầy đủ Complete Graphs K25 84 Đồ thị đầy đủ Complete Graphs K42 85 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 C5 C6 C7 C8 Có bao nhiêu cạnh trong Cn? Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 86 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 W5 W6 W7 W8 Có bao nhiêu cạnh trong Wn? Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 87 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: ? Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 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 Q3 Q4 Số đỉnh: 2n. Số cạnh: ? Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 89 Siêu cúp Q4 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 90 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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 91 Đồ 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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 92 Đồ 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 93 Đồ 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 bậc 0 Đồ thị chính qui bậc 1 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Đồ thị chính qui bậc 2 Đồ thị chính qui bậc 3 94 Đồ thị Platonic • Xét các khối đa diện Platonic trong không gian 3-chiều Tetrahedron Tứ diện Hexahedron (cube) Lục diện Dodecahedron Thập nhị diện Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Octahedron Bát diện Icosahedron Thập bát diện 95 Đồ 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 Dodecahedron Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, Hexahedron (cube) Icosahedron Octahedron 96 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. T1 T2 T3 Rừng F gồm 3 cây T1, T2,, T3 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 97 VÍ DỤ G1, G2 là cây G3, G4 không là cây Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 98 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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 99 Đồ 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! Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 100 Các đồ thị Platonic đều phẳng • Tất cả 5 đồ thị Platonic đều là đồ thị phẳng Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn 101 3-Cube là đồ thị phẳng 102 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 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). Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK 104 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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà 105 Khảo sát đồ thị phẳng • Ví dụ: Xét đồ thị phẳng • Vẽ đơn đồ thị thu được: • Loại bỏ khuyên và cạnh lặp: • Bổ sung khuyên và cạnh lặp: 106 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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà 107 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 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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà 109 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 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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà 111 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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà 112 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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà 113 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 114 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: TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà 115 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 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà nội 117 • 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK G2 118 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.. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà 119 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 TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà đồng phôi với 120 Đị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 Đồ thị Petersen TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà K5 K. Kuratowski 1896-1980 Poland 121 Đồ thị Euler • Định nghĩa • Nhận biết đồ thị Euler TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà 122 Đồ 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 Ví dụ a a b b f c d Đồ thị nửa Euler a, c, d, b, e, d, a, b TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà e c d e Đồ thị Euler a, c, d, e, b, d, f, b, a 124 Bài toán về 7 cái cầu ở Königsberg • Hiện nay là Kaliningrad (thuộc Nga) • Sông Pregel A D B C Leonhard Euler 1707-1783 125 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 C Sơ đồ 7 cái cầu B C Đa đồ thị vô hướng tương ứng 126 Đị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 Ví dụ Đỉnh bậc lẻ a Đỉnh bậc lẻ a b b f c d Đồ thị nửa Euler TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà e c d e Đồ thị Euler 128 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 Vẽ một nét Trong ngôn ngữ đồ thị: Đồ thị nào trong hai đồ thị sau đây có đường đi Euler? 130 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 4 finish 6 5 131 Đồ thị Hamilton • Định nghĩa • Nhận biết đồ thị Hamilton TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà 132 Đồ 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 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 của dodecahedron (thập nhị diện) mỗi đỉnh đúng một lần?` Dodecahedron puzzle Đồ thị tương ứng Sir William Rowan Hamilton 1805-1865 Hộp trò chơi 134 Ví dụ • Đồ thị Hamilton TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà 135 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 ’ y x y x’ y’ y ’ 3 - cube (n -1)-cube (n -1)-cube Đồ 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 TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà 137 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. Đồ 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 TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà 139 Đồ thị không là nửa Hamilton • Đồ thị sau đây không là nửa Hamilton. • Chú ý: Phần khó nhất trong chứng minh đồ thị Tutte không là Hamilton dựa vào kết quả này. TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà 140 Đị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 Paul Adrien Maurice Dirac 1902 - 1984 (USA) TOÁN RỜI RẠC - Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK Hà Oystein Ore 1899 - 1968 (Norway) 142 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 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ị Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 144 Tô màu đồ thị Graph Coloring • Tô màu đỉnh (Vertex Coloring) • Tô màu cạnh (Edge Coloring) Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK 145 Tô màu đồ thị - Graph Coloring Xét bản đồ 146 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 Map Coloring Bổ sung thêm 1 màu nữa. Thử tô các nước bởi 2 màu. 148 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 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 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 Map Coloring Hai nước bị tô bởi cùng màu. Không phân biệt được danh giới. 152 Map Coloring Vậy thì thêm 1 màu nữa: 153 Map Coloring Vẫn không đủ. Cần ít ra là 4 màu bởi vì chính nước này. 154 Map Coloring Với 4 màu, có thể tô được. 155 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 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 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 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 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 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 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 Đị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 Từ tô màu bản đồ đến tô màu đồ thị Như vậy đồ thị đối ngẫu là: 164 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 Đị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 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 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 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 Đị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 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 1 2 4 2 2 5 3 3 4 5 1 6 6 4 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ị. 1 2 3 4 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). 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 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 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 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 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 Tô màu đồ thị và Lập lịch Vẽ lại: 3137 1007 3203 3261 4115 3157 4156 4118 178 Tô màu đồ thị và Lập lịch Không thể tô bởi 1 màu vì cạnh này 3137 1007 3203 3261 4115 3157 4156 4118 179 Tô màu đồ thị và Lập lịch 2 màu không đủ tô vì có tam giác này 3137 1007 3203 3261 4115 3157 4156 4118 180 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 1007 3203 3261 4115 3157 4156 4118 181 Tô màu đồ thị và Lập lịch 3203-Red, 3157-Blue, 4118-Green: 3137 1007 3203 3261 4115 3157 4156 4118 182 Tô màu đồ thị và Lập lịch do đó 4156 phải tô bởi Blue: 3137 1007 3203 3261 4115 3157 4156 4118 183 Tô màu đồ thị và Lập lịch vì thế 3261 và 4115 phải là Red. 3137 1007 3203 3261 4115 3157 4156 4118 184 Tô màu đồ thị và Lập lịch 3137 và 1007 dễ dàng tô. 3137 1007 3203 3261 4115 3157 4156 4118 185 Tô màu đồ thị và Lập lịch Vậy cần 3 ngày: Ngày 2 3137 1007 3203 Ngày 1 3261 4115 3157 4156 4118 Ngày 3 186 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) Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK 187 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 / Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, ĐHBK 188 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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn 189 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 2. LÝ THUYẾT ĐỒ THỊ để tô e.môn Nguyễn Đứccạnh Nghĩa- Bộ Chương 2 BIỂU DIỄN ĐỒ THỊ Representations of Graphs Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 191 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 ? Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 192 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| Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 193 Ma trận kề của đồ thị vô hướng 2 3 1 6 4 A[u,v] = 5 1 nếu (u,v)  E 0 nếu trái lại Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 1 2 3 4 5 6 1 0 1 0 1 0 0 2 1 0 1 0 0 0 3 0 1 0 1 1 0 4 1 0 1 0 1 0 5 0 0 1 1 0 0 6 0 0 0 0 0 0 194 Ma trận kề của đồ thị có hướng 2 3 1 6 4 A[u,v] = 5 1 nếu (u,v)  E 0 nếu trái lại Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 1 2 3 4 5 6 1 0 1 0 1 0 0 2 0 0 1 0 0 0 3 0 0 0 1 1 0 4 0 0 0 0 1 0 5 0 0 0 0 0 0 6 0 0 0 0 0 0 195 Tính chất của ma trận kề – Gọi A là ma trận kề của đồ thị vô hướng: • A là ma trận đối xứng: A = AT (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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 196 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). Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 197 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, Ma trận liên thuộc đỉnh cạnh Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 199 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, +, -. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 200 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 v u w w u v x z y v z x t Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, y a b b e c b c d e b f f 201 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 C A F D E b Danh sách đỉnh kề A B D B A C C B D E D A C E E C D F Bộ nhớ = a |V| + 2 b |E| Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 202 Danh sách kề của đồ thị có hướng Với mỗi v  V, Ke(v) = { u: (v, u)  E } a B C A F D E b A B B C C D D E D E E F Bộ nhớ = a |V| + b |E| Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 203 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 204 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ề) Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 205 Chương 3 C¸c thuËt to¸n duyÖt ®å thÞ (Graph Searching, Graph Traversal) Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 206 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) Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 207 Ý 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). Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 208 Tìm kiếm theo chiều rộng Breadth-first Search (BFS) Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 209 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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 210 Procedure ProcedureBFS(s); BFS(s); (*(*Tìm kiếm Tìm kiếmtheo theochiều chiềurộng rộngbắt bắtđầu đầutừ từđỉnh đỉnhss*)*) begin begin color[s] color[s]gray; gray; d[s]  0; [s] d[s]  0; [s]nil; nil; QQ; enqueue(Q,s); ; enqueue(Q,s);(*(*Nạp Nạps svào vàoQQ*)*) while whileQQdo do begin begin uudequeue(Q); dequeue(Q); (*(*Lấy LấyuutừtừQQ*)*) for for vvAdj[u] Adj[u]do do ififcolor[v] = white color[v] = whitethen then begin begin color[v] color[v]gray; gray; d[v]  d[u] + d[v]  d[u] +1;1;[v] [v]u;u; enqueue(Q,v) enqueue(Q,v) (*(*Nạp Nạpvvvào vàoQQ*)*) end; end; color[u] color[u]black black end; end; end; end; BEGIN BEGIN(*(*Main MainProgram*) Program*) for for vv VVdo do(*(*Khởi Khởitạo tạo*)*) begin begin color[v] color[v]white; white; d[v] d[v]; ; [v] [v]nil; nil; end; end; for for vv VVdo do ififcolor[v]=white color[v]=whitethen then BFS(v); BFS(v); Trắng: chưa thăm xám: đã thăm đen: đã duyệt xong Q: hàng đợi các đỉnh được thăm color[v]: màu của đỉnh v d[v]: khoảng cách từ s đến v [u]: đỉnh đi trước v Ví dụ: xem minh hoạ END. END. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 211 Ví dụ (BFS) r  0  v  w s t  u    y x Q: s 0 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 212 Ví dụ (BFS) r s 1 0  v 1 w t  u    y x Q: w r 1 1 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 213 Ví dụ (BFS) r s 1 0  v 1 w t 2 u  2  y x Q: r t x 1 2 2 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 214 Ví dụ (BFS) r s 1 0 2 v 1 w t 2 u  2  y x Q: t x v 2 2 2 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 215 Ví dụ (BFS) r s 1 0 2 v 1 w t 2 u 3 2  y x Q: x v u 2 2 3 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 216 Ví dụ (BFS) r s 1 0 2 v 1 w t 2 u 3 2 3 y x Q: v u y 2 3 3 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 217 Ví dụ (BFS) r s 1 0 2 v 1 w t 2 u 3 2 3 y x Q: u y 3 3 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 218 Ví dụ (BFS) r s 1 0 2 v 1 w t 2 u 3 2 3 y x Q: y 3 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 219 Ví dụ (BFS) r s 1 0 2 v 1 w t 2 u 3 2 3 y x Q:  Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 220 Ví dụ (BFS) r s 1 0 2 v 1 w t 2 u 3 2 3 y x Cây BFS(s) Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 221 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ị. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 222 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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 223 BFS – Loang trên đồ thị • Thứ tự thăm đỉnh nhờ thực hiện BFS(A) L0 A B C E D F Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, L1 A B L2 C E D F 224 Ứ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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 225 Tìm kiếm theo chiều sâu Depth-first Search (DFS) Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 226 Ý 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µ ch­a ®­îc thăm th× ta sÏ thăm ®Ønh nµy (nã sÏ trë thµnh ®· thăm nhưng chưa duyệt xong) vµ b¾t ®Çu tõ nã ta sÏ tiÕp tôc qu¸ tr×nh t×m kiÕm. – NÕu nh­kh«ng cßn ®Ønh nµo kÒ víi v lµ ch­a thăm th× ta sÏ nãi r»ng ®Ønh nµy lµ ®· duyÖt xong vµ quay trë l¹i tiÕp tôc t×m kiÕm tõ ®Ønh mµ tr­íc ®ã ta ®Õn ®­îc ®Ønh v (nÕu v = s, th× kÕt thóc t×m kiÕm). • Cã thÓ nãi n«m na lµ t×m kiÕm theo chiÒu s©u 227 b¾t ®Çu tõ ®Ønh s ®­îc thùc hiÖn trªn c¬ së t×m Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 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ả. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 228 Depth-First Search: Code DFS(G) BEGIN for vV do begin color[v] = WHITE; [v] = NIL end; time = 0; for uV do begin if (color[u]= WHITE) then DFS(u); end; END. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, procedure DFS(u); begin color[u] = GRAY; time = time+1; d[u] = time; for v  Ke(u)do if (color[v]= WHITE)then begin [v] = u; DFS(v); end; color[u] = BLACK; time = time+1; f[u] = time; end; 229 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 230 Ví dụ: DFS Đỉnh xuất phát tìm kiếm (Source vertex) a g e 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 231 Ví dụ: DFS source vertex d[v] f[v] a e g 1 | | | f b | | | c Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, | d | h 232 Ví dụ: DFS source vertex a g e 1 | | b | f 2 | | | c Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, | d | h 233 Ví dụ: DFS source vertex a e g 1 | | b | f 2 | | 3 | c Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, | d | h 234 Ví dụ: DFS source vertex a e g 1 | | b | f 2 | | 3 | 4 c Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, | d | h 235 Ví dụ: DFS source vertex a g e 1 | | b | f 2 | | 3 | 4 c Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 5 | d | h 236 Ví dụ: DFS source vertex a e 1 | g | b | f 2 | | 3 | 4 c Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 5 | 6 d | h 237 Ví dụ: DFS source vertex a e 1 | 8 | b g | f 2 | 7 | 3 | 4 c Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 5 | 6 d | h 238 Ví dụ: DFS source vertex a e 1 | 8 | g | f b 2 | 7 | 3 | 4 c Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 5 | 6 d | h 239 Ví dụ: DFS source vertex a e 1 | 8 | g | f b 2 | 7 9 | 3 | 4 c Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 5 | 6 d | h 240 Ví dụ: DFS source vertex a e 1 | 8 | b g | f 2 | 7 9 |10 3 | 4 c Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 5 | 6 d | h 241 Ví dụ: DFS source vertex a 1 | e g 8 |11 b | f 2 | 7 9 |10 3 | 4 c Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 5 | 6 d | h 242 Ví dụ: DFS source vertex a 1 |12 e g 8 |11 b | f 2 | 7 9 |10 3 | 4 c Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 5 | 6 d | h 243 Ví dụ: DFS source vertex a 1 |12 e g 8 |11 b 13| f 2 | 7 9 |10 3 | 4 c Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 5 | 6 d | h 244 Ví dụ: DFS source vertex a 1 |12 g e 8 |11 b 13| f 2 | 7 9 |10 3 | 4 c Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 5 | 6 d 14| h 245 Ví dụ: DFS source vertex a 1 |12 e g 8 |11 b 13| f 2 | 7 9 |10 3 | 4 c Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 5 | 6 d 14|15 h 246 Ví dụ: DFS source vertex a 1 |12 g e 8 |11 b 13|16 f 2 | 7 9 |10 3 | 4 c Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 5 | 6 d 14|15 h 247 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) Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 248 Ví dụ: Rừng DFS source vertex a Cây DFS(g) a Cây DFS(a) 1 |12 8 |11 b 13|16 f 2 | 7 source vertex g 9 |10 3 | 4 Tree edges g e c Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 5 | 6 d 14|15 h 249 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) Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 250 Ví dụ: DFS Cạnh ngược source vertex a 1 |12 e g 8 |11 13|16 f b 2 | 7 9 |10 3 | 4 c Tree edges Back edges Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 5 | 6 d 14|15 h 251 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 252 Ví dụ: DFS Cạnh tới source vertex a 1 |12 e g 8 |11 b 13|16 f 2 | 7 9 |10 3 | 4 c 5 | 6 d Tree edges Back edges Forward edges Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 14|15 h 253 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 254 Ví dụ: DFS Cạnh vòng source vertex a 1 |12 e g 8 |11 b 13|16 f 2 | 7 9 |10 3 | 4 c 5 | 6 14|15 d h Tree edges Back edges Forward edges Cross edges Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 255 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 256 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. • Chứng minh bằng phản chứng: source F? – Giả sử có cạnh tới (forward edge) – Nhưng khi đó F phải là cạnh ngược (back edge)?! Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 257 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 đỉ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 source C? Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 258 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 259 Phân tích DFS (* (*Main MainProgram*) Program*) 1.1. for foruuVVdo do 2.2. color[u] color[u]white white 3.3. [u] [u]NIL NIL 4.4. time time00 5.5. for foruuVVdo do 6.6. ififcolor[u] color[u]==white white 7.7. then thenDFS-Visit(u) DFS-Visit(u) Các biến time, color,  là toàn cục . Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, DFS-Visit(u) DFS-Visit(u) 1.1. color[u] color[u] GRAY GRAY (* (*Thăm Thămđỉnh đỉnhuu*) *) 2.2. time time time time++11 3.3. d[u] d[u] time time 4.4. for foreach eachvvAdj[u] Adj[u]do do 5.5. ififcolor[v] color[v]==WHITE WHITE 6.6. then then[v] [v] uu 7.7. DFS-Visit(v) DFS-Visit(v) 8.8. color[u] color[u] BLACK BLACK(* (*Đỉnh Đỉnhuuđã đã duyệt duyệtxong xong*) *) 9.9. f[u] f[u] time time time time++11 260 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 261 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ị Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 262 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 263 DFS giải bài toán liên thông (* (*Main MainProgram*) Program*) 1.1. for foruuVVdo do 2.2. id[u] id[u]00 3.3. cnt cnt00 (*(*cnt cnt––số sốlượng lượngtplt tplt*) *) 4.4. for foruuVVdo do 5.5. ififid[u] id[u]==00 6.6. then thencnt cnt cnt cnt+1 +1 7.7. DFS-Visit(u) DFS-Visit(u) Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, DFS-Visit(u) DFS-Visit(u) 1.1. id[u] id[u] cnt cnt 2.2. for foreach eachvvAdj[u] Adj[u]do do 3.3. ififid[v] id[v]==00 4.4. then thenDFS-Visit(v) DFS-Visit(v) 264 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 265 DFS giải bài toán đường đi (* (*Main MainProgram*) Program*) 1.1. for foruuVVdo do 2.2. color[u] color[u]white white 3.3. [u] [u]NIL NIL 4.4. DFS-Visit(s) DFS-Visit(s) Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, DFS-Visit(u) DFS-Visit(u) 1.1. color[u] color[u] GRAY GRAY (* (*Thăm Thămđỉnh đỉnhuu*) *) 2.2. for foreach eachvvAdj[u] Adj[u]do do 3.3. ififcolor[v] color[v]==WHITE WHITE 4.4. then then[v] [v] uu 5.5. DFS-Visit(v) DFS-Visit(v) 266 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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 267 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 MainProgram*) Program*) 1.1. for foruuVVdo do 2.2. color[u] color[u]white white 3.3. [u] [u]NIL NIL 4.4. time time00 5.5. for foruuVVdo do 6.6. ififcolor[u] color[u]==white white 7.7. then thenDFS-Visit(u) DFS-Visit(u) Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, DFS(u) DFS(u) 1.1. color[u] color[u] GRAY GRAY (* (*Thăm Thămđỉnh đỉnhuu*) *) 2.2. time time time time++11 3.3. d[u] d[u] time time 4.4. for foreach eachvvAdj[u] Adj[u]do do 5.5. ififcolor[v] color[v]==WHITE WHITE 6.6. then then[v] [v] uu 7.7. DFS-Visit(v) DFS-Visit(v) 8.8. color[u] color[u] BLACK BLACK(* (*Đỉnh Đỉnhuuđã đã duyệt duyệtxong xong*) *) 9.9. f[u] f[u] time time time time++11 268 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. Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 269 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 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 270 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. 271 Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, Thuật toán kiểm tra tính liên thông mạnh a a d f c b e Đồ thị G Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, d f c b e Đồ thị GT 272 Đị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, Ví dụ: Định hướng đồ thị a a d f c b Đồ thị G Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, e d f c b e Đồ thị G() 274 Questions? Phần 2. LÝ THUYẾT ĐỒ THỊ Nguyễn Đức Nghĩa- Bộ môn KHMT, 275

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.