Bài giảng Toán rời rạc - Đồ thị (Phần 1) - Trần Nguyễn Minh Thư

1 TRƯỜNG ĐẠI HỌC CẦN THƠ KHOA CNTT & TRUYỀN THÔNG BỘ MÔN KHOA HỌC MÁY TÍNH TOÁN RỜI RẠC (DISCRETE MATHEMATICS) 08/2013 GV: Trần Nguyễn Minh Thư (tnmthu@ctu.edu.vn) 2 ĐẠI CƯƠNG VỀ ĐỒ THỊ ĐỒ THỊ VÔ HƯỚNG 3  G = (X,U), trong đó:  X: tập hợp các đỉnh  U: tập hợp các cạnh u=(i, j) = (j,i)  Đỉnh kề: chung cạnh (vd đỉnh 1,2)  Cạnh kề: chung đỉnh (vd cạnh u1, u3) u5 1 4 5 u6 u1 u3 Đỉnh cô lập 2 3 u 10 6 Đỉnh treo ĐỒ THỊ VÔ HƯỚNG 4  Đa đồ thị: tồn tại cặp đỉnh phân biệt (i,j) có nhiều hơn một cạnh và không có khuyên  Đồ thị đơn (đơn đồ thị): tất cả các cặp đỉnh (i,j) phân biệt có nhiều nhất một cạnh và không có khuyên u4 u1 2 4 u7 u 1 u3 6 6 u8 u5 u2 3 5 ĐỒ THỊ VÔ HƯỚNG  Đồ thị đầy đủ là đồ thị luôn tồn tại cung/cạnh nối hai đỉnh bất kỳ  Đồ thị con  A là tập hợp con của X  Đồ thị con GA của đồ thị G sinh ra bởi A có đỉnh là A có cung/cạnh là cung/cạnh của G mà đỉnh của chúng thuộc A. 5 ĐỒ THỊ VÔ HƯỚNG 6  Đồ thị bộ phận  V là tập hợp con của U  Đồ thị bộ phận sinh ra bởi V là đồ thị có đỉnh thuộc X và các cung/cạnh là V  Đồ thị bộ phận con là đồ thị vừa là đồ thị con vừa là đồ thị bộ phận Đồ thị đầy đủ G Đồ thị con của G Đồ thị bộ phận của G ĐỒ THỊ VÔ HƯỚNG  Đường đi và chu trình:  Đường đi (vô hướng): một dãy các cạnh kề nhau  Đỉnh đầu: đỉnh bắt đầu của đường đi  Đỉnh cuối: đỉnh kết thúc của đường đi  Độ dài: số cạnh trên đường đi  Đường đi sơ cấp: đường đi có các đỉnh khác nhau từng đôi một a b c    a - b - e - f - b - c: đường đi a - d - e - f - b: đường đi sơ cấp    d e f 7 ĐỒ THỊ VÔ HƯỚNG  Đường đi và chu trình:  Chu trình: một đường đi có đỉnh đầu và đỉnh cuối trùng nhau  Chu trình sơ cấp: một chu trình có các đỉnh khác nhau từng đôi một, trừ đỉnh đầu và đỉnh cuối a b c       d e f a - b - c - f - b - e - a: chu trình b - c - d - e - a - b: chu trình sơ cấp ĐỒ THỊ VÔ HƯỚNG  Xét đồ thị vô hướng G = (X, U)  Đồ thị liên thông: với mỗi cặp đỉnh i, j bất kỳ thì luôn tìm được đường đi từ i đến j Nhận xét: đồ thị vô hướng G = (X, U) 1. Đồ thị G là liên thông khi và chỉ khi G chỉ có một bộ phận liên thông 2. Mỗi bộ phận liên thông là một đồ thị liên thông 3. Mỗi đỉnh cô lập là một bộ phận liên thông ĐỒ THỊ VÔ HƯỚNG  Đồ thị vô hướng có 9 đỉnh, 6 cạnh và 4 bộ phận liên thông 4 1 6 9 2 3 5 7 8 ĐỒ THỊ CÓ HƯỚNG  Ví dụ: Đồ thị có hướng: G = (X,U) u8 Khuyên u5 u7 1 5 4 u9 u2 u6 u1 u4 2 3 u3 Đỉnh cô lập u 10 7 Cung treo Đỉnh treo 6 11 ĐỒ THỊ CÓ HƯỚNG  G = (X,U), trong đó :  X: tập hợp các đỉnh  U: tập hợp các cặp đỉnh có thứ tự u=(i, j) - cung  Khuyên: Cung u=(i, i)  Đỉnh treo: chỉ có một cung duy nhất (đi tới hoặc đi ra từ) đỉnh đó  Cung treo: cung duy nhất (đi tới hoặc đi ra từ) đỉnh treo  Đỉnh cô lập: không có cung nào từ đỉnh đó đi ra và cũng không có cung nào đi tới đỉnh đó 12 ĐỒ THỊ CÓ HƯỚNG  Đa đồ thị: tồn tại cặp đỉnh có thứ tự (i,j) có nhiều hơn một cung và có thể có khuyên  Đồ thị đơn (đơn đồ thị): tất cả các cặp đỉnh có thứ tự (i, j) có nhiều nhất một cung  Đồ thị có hướng: G = (X,U), cung u=(i, j)  U 13 ĐỒ THỊ CÓ HƯỚNG  Nửa bậc  Nửa bậc trong của đỉnh x, ký hiệu là d  (x) , là số cung có ngọn là x, là số cung đi vào x  Nửa bậc ngoài của đỉnh x, ký hiệu là d  (x), là số cung có gốc là x, là số cung từ x đi ra  Bậc là số cung/cạnh chứa x d(x)  d (x)  d (x) 14 ĐỒ THỊ CÓ HƯỚNG  Đường đi và chu trình  Đường đi (có hướng): một dãy liên tiếp các cung  Đỉnh đầu: đỉnh bắt đầu của đường đi  Đỉnh cuối: đỉnh kết thúc của đường đi  Độ dài: số cung trên đường đi  Đường đi sơ cấp: đường đi có các đỉnh khác nhau từng a b c đôi một       d e f a - d -15c - f - e: đường đi sơ cấp ĐỒ THỊ CÓ HƯỚNG  Đường đi và chu trình  Chu trình: một đường đi có đỉnh đầu và đỉnh cuối trùng nhau  Chu trình sơ cấp: một chu trình có các đỉnh khác nhau từng đôi một, trừ đỉnh đầu và đỉnh cuối a b c       d e f b - c - f - e - d - a - b: chu trình sơ cấp ĐỒ THỊ CÓ HƯỚNG  Đồ thị có hướng liên thông Xét đồ thị có hướng G = (X, U)  Đồ thị liên thông yếu: đồ thị vô hướng tương ứng với G là liên thông  Đồ thị liên thông một chiều: nếu với hai đỉnh i , j bất kỳ hoặc là tồn tại đường đi từ i đến j , hoặc là tồn tại đường đi từ j đến i  Đồ thị liên thông mạnh: nếu với hai đỉnh i và j bất kỳ tồn tại đường đi đi từ đỉnh i đến đỉnh j và ngược lại BIỂU DIỄN ĐỒ THỊ  Biểu diễn đồ thị bằng ma trận . Ma trận đỉnh – cung . Ma trận đỉnh – cạnh . Ma trận đỉnh – đỉnh . Ma trận trọng số BIỂU DIỄN ĐỒ THỊ Biểu diễn đồ thị bằng ma trận u4 . Ma trận đỉnh – cung u 1 2 4 u7 1 u3 u6 6 u8 u u 5 2 3 5 u1 u2 u3 u4 u5 u6 u7 u8 1 1 1 0 0 0 0 0 0 2 -1 0 1 1 0 0 0 0 3 0 -1 -1 0 1 0 0 0 4 0 0 0 -1 0 1 1 0 5 0 0 0 0 -1 -1 0 1 6 0 0 0 0 0 0 -1 -1 BIỂU DIỄN ĐỒ THỊ u u 4 Biểu diễn đồ thị bằng ma trận 1 2 4 u7 . Ma trận đỉnh – cạnh 1 u3 u6 6 u8 u u 5 2 3 5 u1 u2 u3 u4 u5 u6 u7 u8 1 1 1 0 0 0 0 0 0 2 1 0 1 1 0 0 0 0 3 0 1 1 0 1 0 0 0 4 0 0 0 1 0 1 1 0 5 0 0 0 0 1 1 0 1 6 0 0 0 0 0 0 1 1 BIỂU DIỄN ĐỒ THỊ u Biểu diễn đồ thị bằng ma trận 4 u1 u . Ma trận kề đỉnh – đỉnh 2 4 7 u 1 3 u6 6 u8 u u 5 2 3 5 1 2 3 4 5 6 1 0 1 1 0 0 0 2 0 0 1 1 0 0 3 0 0 0 0 1 0 4 0 0 0 0 1 1 5 0 0 0 0 0 1 6 0 0 0 0 0 0 BIỂU DIỄN ĐỒ THỊ u Biểu diễn đồ thị bằng ma trận 4 u1 u . Ma trận kề đỉnh – đỉnh 2 4 7 u 1 3 u6 6 u8 u u 5 2 3 5 1 2 3 4 5 6 1 0 1 1 0 0 0 2 0 0 1 1 0 0 3 0 0 0 0 1 0 4 0 0 0 0 1 1 5 0 0 0 0 0 1 6 0 0 0 0 0 0 BIỂU DIỄN ĐỒ THỊ Biểu diễn đồ thị bằng ma trận 4 . Ma trận trọng số 1 2 4 7 3 1 6 6 8 2 5 3 5 1 2 3 4 5 6 1 1 2 2 3 3 4 4 7 5 5 6 8 6 24 ĐỒ THỊ EULER, HAMILTON tnmtnhu@cit.ctu.edu.vn 8/2/2015 Đồ thị Euler và nửa Euler  Chu trình Euler: chu trình trong đồ thị G đi qua mỗi cạnh của đồ thị đúng một lần  Đồ thị Euler: Đồ thị có chu trình Euler  Đường đi Euler: đường đi đơn trong G đi qua mỗi cạnh của nó đúng một lần   Đồ thị nửa Euler: Đồ thị có đường đi Euler   Mọi đồ thị Euler đều là đồ thị nửa Euler Đồ thị Hamilton và nửa Hamilton 26  Chu trình bắt đầu tại một đỉnh v nào đó qua tất cả các đỉnh còn lại mỗi đỉnh đúng một lần sau đó quay trở lại v được gọi là chu trình Hamilton. => Đồ thị được gọi là đồ thị Hamilton nếu nó chứa chu trình Hamilton.  Đường đi qua tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần được gọi là đường đi Hamilton. => Đồ thị chứa đường đi Hamilton được gọi là đồ thị nửa Hamilton.  Như vậy, đồ thị Hamilton bao giờ cũng là đồ thị nửa Hamilton nhưng điều ngược lại không luôn luôn đúng. Đồ thị Hamilton và nửa Hamilton  Ví dụ. Xét các đồ thị G1, G2, G3 trong hình sau: a b c d G3 Ta có: đồ thị nửa Hamilton G2, Hamilton G1 và G3 27 28 ĐƯỜNG ĐI NGẮN NHẤT tnmtnhu@cit.ctu.edu.vn 8/2/2015 BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT 29  Đường đi ngắn nhất: Xét đồ thị có hướng G=(X, U)  Với mỗi cung u=(i,j)=l(u) hay lij  R: độ dài cung hay là trọng số của cung.  Độ dài l của đường đi (có hướng) đi từ đỉnh i đến đỉnh j là tổng của tất cả các độ dài của các cung nằm trên đường đi đó.  Bài toán đường đi ngắn nhất là: với hai đỉnh i và j của đồ thị hãy xác định đường đi ngắn nhất từ i đến j.  Ứng dụng thực tiễn: độ dài cung được hiểu cụ thể như là độ dài, chi phí, thời gian, lưu lượng . Giải thuật Moore – Dijkstra 30  Giải thuật Moore-Dijkstra tìm đường đi ngắn nhất từ một đỉnh chọn trước s đến các đỉnh còn lại.  G=(X,U) là đồ thị liên thông có trọng số dương  lij là độ dài của cung u= (i,j) với uU.  *(i) là độ dài đường đi ngắn nhất từ đỉnh s đến đỉnh i.  *(s)= 0  Giải thuật lặp n-1 lần (n: số đỉnh)  Với mỗi đỉnh iX người ta gán cho i nhãn (i) theo cách như sau:  iS thì (i) = *(i)  i  S thì (i) = min {(k) +lki , kS}. Giải thuật Moore - Dijkstra 31  Khởi tạo  Thực hiện bước lặp: S  {s} S  X \ S  (s)  0 lsi i s  (i)    is p(i)  s is Tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại của đồ thị sau: 4 2 4 7 5 2 1 5 1 5 3 1 7 3 6 2 Tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại của đồ thị sau 33 2 4 4 7 5  Khởi tạo : 2 1 5 1 5  S = {1} 3 1  S = {2, 3, 4, 5, 6} 3 7 6 2 G 1 2 3 4 5 6 i 2,3 4,6 2,5,6  2,4 5 (i) 0 7 1    p(i) 1 1 2 4 4 G 1 2 3 4 5 6 7 5 2 i 2,3 4,6 2,5,6  2,4 5 1 5 1 5 (i) 0 7 1    3 34 1 p(i) 1 1 3 7 6 2 G 1 2 3 4 5 6 1)- Với S  2,3,4,5,6  i 2,3 4,6 2,5,6  2,4 5 Chọn i có  (i) nhỏ nhất (i) 0 6 1  3 8 => i = 3 p(i) 3 1 3 3 Tập đỉnh cần cập nhật khoảng cách  S  S {i}  {2, 4, 5, 6} M  S 3 {2, 5, 6}  (2) = min {(2), (3) + l32} = min {7,1+5} = 6  (5) = min {(5), (3) + l35} = min {, 1+2} = 3  (6) = min {(6), (3) + l36} = min {, 1+7} = 8 2 4 4 G 1 2 3 4 5 6 7 5 2,3 4,6 2,5,6 2,4 5 2 i  1 5 1 5 (i) 0 6 1  3 8 3 35 1 p(i) 3 1 3 3 3 7 6 2 G 1 2 3 4 5 6 2)- Với S  2,4,5,6  i 2,3 4,6 2,5,6  2,4 5 Chọn i có  (i) nhỏ nhất (i) 0 5 1 8 3 8 => i = 5 p(i) 5 1 5 3 3 Tập đỉnh cần cập nhật khoảng cách  S  S {i} {2, 4, 6} M  S 5 {2, 4}  (2) = min {(2), (5) + l52} = min {6,3+2} = 5  (4) = min {(4), (5) + l54} = min {, 3+5} = 8 2 4 4 G 1 2 3 4 5 6 7 5  2,3 4,6 2,5,6  2,4 5 2 i 1 5 1 5 (i) 0 5 1 8 3 8 36 3 p(i) 5 1 5 3 3 1 3 7 6 2 G 1 2 3 4 5 6 3)- Với S  2,4,6  i 2,3 4,6 2,5,6  2,4 5 Chọn i có  (i) nhỏ nhất (i) 0 5 1 8 3 6 => i = 2 p(i) 5 1 5 3 2 Tập đỉnh cần cập nhật khoảng cách  S  S {i} {4, 6} M  S 2 {4, 6}  (4) = min {(4), (2) + l24} = min {8,5+4} = 8  (6) = min {(6), (2) + l26} = min {8, 5+1} = 6 2 4 4 G 1 2 3 4 5 6 7 5 2 i 2,3 4,6 2,5,6  2,4 5 1 5 1 5 (i) 0 5 1 8 3 6 3 37 1 p(i) 5 1 5 3 2 3 7 6 2 4)- Với S  4,6  Chọn i có  (i) nhỏ nhất => i = 6 Tập đỉnh cần cập nhật khoảng cách  S  S {i} {4} M  S 6   2 4 4 G 1 2 3 4 5 6 7 5 2 i 2,3 4,6 2,5,6  2,4 5 1 5 1 5 (i) 0 5 1 8 3 6 3 38 1 p(i) 5 1 5 3 2 3 7 6 2 5)- Với S  4  Chọn i có  (i) nhỏ nhất => i = 4 Tập đỉnh cần cập nhật khoảng cách  S  S {i}   M  S 4   2 4 4 7 5 G 1 2 3 4 5 6 2 1 5 5 1 i 2,3 4,6 2,5,6  2,4 5 39 3 1 (i) 0 5 1 8 3 6 3 7 6 2 p(i) 5 1 5 3 2 1 1 3 2 5 2 5 2 4 1 6 BÀI TẬP 40 Xét đồ thị vô hướng có trọng lượng, được cho bởi ma trận kề gia trọng như bảng sau, Tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại A B C D E F G H A 8 3 6 B 8 4 5 1 Đề thi năm 2012, lần 2 C 3 4 1 2 D 6 1 9 4 E 5 2 7 2 F 1 9 7 4 9 G 4 4 3 H 2 9 3 A B C D E F G H BÀI TẬP A 8 3 6 B 8 4 5 1 41 C 3 4 1 2 Đề thi năm 2012, lần 2 D 6 1 9 4 E 5 2 7 2  Khởi tạo F 1 9 7 4 9  S = {A} G 4 4 3  X = {A,B,C,D,E,F,G,H} H 2 9 3  S = X – S = {B,C,D,E,F,G,H} A B C D E F G H i B,C,D C,E,F B,D,E C, F, G B,C,F,H B,D,E,G,H D, F, H E,F,G (i) 0 8 3 6     p(i) A A A BÀI TẬP 42 A B C D E F G H i B,C,D C,E,F B,D,E C, F, G B,C,F,H B,D,E,G,H D, F, H E,F,G (i) 0 7 3 4 5 8 8 7 p(i) C A C C B D E A 3 C 4 B 1 F 1 D 4 G 2 E 2 H BÀI TẬP 43 1. Tìm đường đi ngắn nhất từ đỉnh A đến tất cả các đỉnh còn lại trong đồ thị được cho bởi ma trận trọng số sau: A B C D E F G H K A 1 1 4 B 9 2 3 C 7 2 D 1 5 4 3 E 2 F 9 3 G 5 H 7 Đề thi năm 2011, lần 1 K 1. Tìm đường đi ngắn nhất từ đỉnh A đến tất cả các đỉnh còn lại trong đồ thị được cho bởi ma trận trọng số sau: A B C D E F G H K BÀI TẬP A 1 1 4 B 9 2 3 44 C 7 2 Đề thi năm 2011, lần 1 D 1 5 4 3 E 2 F 9 3  Khởi tạo G 5  S = {A} H 7 K  X = {A,B,C,D,E,F,G,H,K}  S = X – S = {B,C,D,E,F,G,H,K} A B C D E F G H K i B,C, G, H, K D,K C,E, F, D,F D,E,G,H B, F, H B,D,F,G, B,C,D,H K H, K K (i) 0 1 1      4 p(i) A A A BÀI TẬP Đề thi năm 2011, lần 1 45 A B C D E F G H K i B,C, G, H, K D,K C,E, F, D,F D,E,G,H B, F, H B,D,F,G, B,C,D,H K H, K K (i) 0 1 1 6 7 6 8 3 3 p(i) A A K D H H B C 2 3 1 C K D E 1 A F 3 1 2 5 B H G BÀI TẬP Đề thi năm 2013, đợt 1 46  Tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị được cho bởi ma trận trọng số sau A B C D E F G H K A 2 1 7 B 2 6 3 1 C 6 3 7 4 D 3 4 9 E 4 8 7 6 F 1 8 6 3 G 7 3 6 2 H 1 7 7 3 2 3 K 4 9 6 3 A B C D E F G H K A 2 1 7 BÀI TẬP B 2 6 3 1 47 C 6 3 7 4 D 3 4 9 Đề thi năm 2013, đợt 1 E 4 8 7 6 F 1 8 6 3  Khởi tạo G 7 3 6 2 H 1 7 7 3 2 3  S = {A} K 4 9 6 3  X = {A,B,C,D,E,F,G,H,K}  S = X – S = {B,C,D,E,F,G,H,K} A B C D E F G H K i B,F,G C,G,H B,D,H,K C,E,K D,F,H,K E,G,H B, F, H B,C,E,F,G,K C,D,E,H (i) 0 2    1 7   p(i) A A A BÀI TẬP Đề thi năm 2013, lần 1 48 A B C D E F G H K i B,F,G C,G,H B,D,H,K C,E,K D,F,H,K E,G,H B, F, H B,C,E,F,G,K C,D,E,H (i) 0 2 8 11 9 1 5 3 6 p(i) A B C F A B B H 8 1 F E A 3 6 C D 2 3 B G 1 3 H K