Bài giảng Toán rời rạc - Chương 4: Lý thuyết đồ thị

ChươngChương 4:4: LÝLÝ THUYTHUYẾẾTT ĐĐỒỒ THTHỊỊ ChChươươngng 44 4.1 MỞ ĐẦU 4.2 CÁC KHÁI NIỆM CƠ BẢN 4.3 ĐỒ THỊ EULER 4.4 ĐỒ THỊ HAMILTON BÀI TOÁN TÌM ĐƯỜNG ĐI 4.5 NGẮN NHẤT 4.6 CÂY 4.I MỞ ĐẦU Bài toán về những cây cầu ở Konigsber Năm 1736 Euler, cha đẻ của lý thuyết đồ thị, đã giải được bài toán hóc búa nổi tiếng thời đó về những cây cầu ở Konigberg. Thành phố Konigberg có hai hòn đảo nối với nhau và với 2 bờ sông bằng 7 chiếc cầu như hình vẽ. Tìm đường đi qua tất cả 7 cây cầu, mỗi cây cầu chỉ được đi qua một lần, sau đó quay về nơi xuất phát 4.2 CÁC KHÁI NIỆM CƠ BẢN 4.2.1 Đồ thị, đỉnh, cạnh, cung:  Đồ thị vô hướng G = (V, E) gồm tập V các đỉnh và tập E các cạnh. v w e Ví dụ: 4.2 CÁC KHÁI NIỆM CƠ BẢN  Đồ thị có hướng G = (V, E) gồm tập V các đỉnh và tập E các cạnh có hướng gọi là cung. v w e Mỗi cạnh e được liên kết với một cặp đỉnh (v, w) có thứ tự Ví dụ: 4.2 CÁC KHÁI NIỆM CƠ BẢN  Cho đồ thị G = (V, E). Cạnh e  E liên kết đỉnh v và w, ta nói e liên thuộc đỉnh v, w; đỉnh v và w gọi là kề nhau.  Cạnh song song:  Khuyên:  Đỉnh cô lập: 4.2 CÁC KHÁI NIỆM CƠ BẢN  Đồ thị hữu hạn: là đồ thị có số cạnh (cung) hữu hạn.  Đồ thị đơn: là đồ thị không có khuyên và không có cạnh song song.  Đồ thị đầy đủ: là đồ thị mà mọi cặp đỉnh đều kề nhau.  Bậc của đỉnh vV là tổng số cạnh liên thuộc với nó, kí hiệu d(v). Mỗi khuyên được tính cho 2 bậc. d(v) := Số cạnh + 2* Số khuyên 4.2 CÁC KHÁI NIỆM CƠ BẢN Đỉnh cô lập có bậc bằng 0  Đỉnh treo: là đỉnh có bậc bằng 1. Nửa bậc: Cho đồ thị có hướng G = (V, E). + Nửa bậc ra của đỉnh vV, kí hiệu dr(v) là số cung đi ra từ đỉnh v. + Nửa bậc vào của đỉnh vV, kí hiệu dv(v) là số cung đi vào đỉnh v MỘT SỐ TÍNH CHẤT * Tính chất 1: Cho đồ thị G = (V, E). Khi đó: i. Tổng bậc các đỉnh của đồ thị là số chẵn và d(v) = 2|E| ii. Nếu G là đồ thị có hướng thì: dv(v) = dr(v) = |E| * Tính chất 2: Cho đồ thị G(V, E). Khi đó số đỉnh bậc lẻ là số chẵn * Tính chất 3: Cho đồ thị đơn G = (V, E) có n đỉnh (n  2) có ít nhất hai đỉnh cùng bậc. * Tính chất 4: Cho đồ thị đơn G = (V, E) có n đỉnh (n > 2) có đúng 2 đỉnh cùng bậc thì 2 đỉnh này không thể đồng thời có bậc bằng 0 hoặc bằng n – 1. 4.2.2 Đường đi, chu trình, tính liên thông  Đường đi  từ đỉnh v đến đỉnh w là dãy các cạnh nối tiếp nhau bắt đầu từ đỉnh v và kết thúc tại đỉnh w. Số cạnh trên đường đi  là độ dài của đường đi . Đường đi  có độ dài n từ đỉnh v đến đỉnh w được biểu diễn như sau:  = (v, e1, v1, e2, v2, , vn-1, en, w) Trong đó: vi (i = 1, , n-1) là các đỉnh trên đường đi và ei (i = 1, , n) là các cạnh trên đường đi liên thuộc các cạnh kề trước và sau nó.  Chu trình là đường đi có đỉnh đầu và đỉnh cuối trùng nhau.  Đường đi đơn là đường đi không đi qua một cạnh quá một lần.  Chu trình đơn là chu trình không đi qua một cạnh quá một lần.  Đường đi sơ cấp là đường đi không đi qua một đỉnh quá một lần.  Chu trình sơ cấp là chu trình không đi qua một đỉnh quá một lần.  Đường đi có hướng trong đồ thị có hướng là dãy các cung nối tiếp nhau (e1, e2, , en) thỏa mãn đỉnh cuối của cung ei là đỉnh đầu của cung ei+1, i = 1, , n-1.  Chu trình có hướng là đường đi có hướng có đỉnh đầu và đỉnh cuối trùng nhau.  Đường đi đơn (chu trình đơn) có hướng là đường đi (chu trình) có hướng không đi qua một cung quá một lần.  Đường đi (chu trình) có hướng sơ cấp là đường đi (chu trình) có hướng không đi qua một đỉnh quá một lần. Ví dụ e v2 e v1 1 4 v3 e e2 9 e e8 3 e7 v e e 4 5 v5 6 v6 b a c d e  Đồ thị liên thông là đồ thị mà mọi cặp đỉnh của nó đều có đường đi nối chúng với nhau.  Đồ thị con: Cho đồ thị G = (V, E). Đồ thị G’ = (G’, E’) là đồ thị con của G nếu: (i) V’ V và E’ E và (ii) e = (v,w)  E: e  E’  v, w  V’  Thành phần liên thông: Là đồ thị con liên thông tối đại của G. 4.2.3 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY a. Ma trận kề  Đồ thị vô hướng Cho đồ thị vô hướng G = (V, E) có n đỉnh theo thứ tự v1, v2, , vn. Ma trận kề của đồ thị G là ma trận vuông A = (aij)n, trong đó aij là số cạnh nối vi với vj. Lưu ý mỗi khuyên được tính là 2 cạnh. Ma trận kề của đồ thị vô hướng luôn đối xứng qua đường chéo chính. v2 v1 Ví dụ: v3 Có ma trận kề là: v5 v4 v1 v2 v3 v4 v5 Tổng bậc v1 0 1 0 1 0 của v1 v2 1 0 1 1 0 v3 0 1 2 1 0 v4 1 1 1 0 1 v5 0 0 n 0 n 1 0 d(vi )  aij  a ji ,vi  V j1 j1  Đồ thị có hướng Cho đồ thị có hướng G = (V, E) có n đỉnh theo thứ tự v1, v2, , vn. Ma trận kề của đồ thị G là ma trận vuông A = (aij)n, trong đó aij là số cung đi từ đỉnh vi đến vj. Ví dụ: v2 v6 e4 e6 e1 e8 v e3 1 v e e 4 7 e2 5 v3 v5 v1 v2 v3 v4 v5 v6 tổng bậc ra v1 0 1 1 0 0 0 của v1 v2 0 0 1 1 0 0 v3 0 0 0 1 0 0 v4 0 0 0 0 1 1 v5 0 0 0 0 0 1 v6 0 0 0 0 0 0 tổng bậc vào của v1 Mệnh đề: Cho đồ thị có hướng G = (V, E) với ma trận kề (aij)n. Khi đó: n n d (v )  a v i  ij và dr (vi )  a ji , vi  V j1 j1 số bậc vào của số bậc ra của đỉnh vi = đỉnh vi = tổng tổng các số trên hàng vi các số trên cột vi b. Ma trận liên thuộc  Đồ thị vô hướng Cho đồ thị G = (V, E) có n đỉnh, V = {v1, v2, , vn} và m cạnh E = {e1, e2, , em}. Ma trận liên thuộc của đồ thị G là ma trận A = (aij)nm thỏa mãn: 1 nếu đỉnh vi liên thuộc cạnh ej aij   0  nếu đỉnh vi không liên thuộc cạnh ej Ví dụ: e1 v2 v1 e4 e e7 2 e3 v e 3 e 5 v 6 v Ma trận liên thuộc: 5 4 e1 e2 e3 e4 e5 e6 e7 Tổng bậc v1 1 1 0 0 0 0 0 của v1 v2 1 0 1 1 0 0 0 v3 0 0 0 1 1 0 1 v4 0 1 1 0 1 1 0 v5 0 0 0 0 0 1 0 Mệnh đề: Cho đồ thị đơn G = (V, E) với ma trận liên thuộc (aij)nm. Khi đó: n d(vi )  aij, vi V j1 Số bậc của đỉnh vi = tổng các số trên hàng vi  Đồ thị có hướng Cho đồ thị có hướng G = (V, E) có n đỉnh, V = {v1, v2, , vn}, m cạnh E = {e1, e2, , em} và không có khuyên. Ma trận liên thuộc của đồ thị G là ma trận A = (aij)nm thỏa mãn: 1 nếu đỉnh vi là đỉnh đầu của cung ej  aij  1 nếu đỉnh vi là đỉnh cuối của cung ej  0 nếu đỉnh vi không kề cung ej Ví dụ: v2 v6 e4 e6 e1 e e8 v1 3 v 4 e7 e2 e5 v3 v5 e1 e2 e3 e4 e5 e6 e7 e8 v1 1 1 0 0 0 0 0 0 v2 -1 0 1 1 0 0 0 0 V3 0 -1 -1 0 1 0 0 0 v4 0 0 0 -1 -1 1 1 0 v5 0 0 0 0 0 0 -1 -1 v6 0 0 0 0 0 -1 0 1 Chú ý Cho đồ thị có hướng G = (V, E) có ma trận liên thuộc (aij)n. Khi đó:  Số bậc ra của đỉnh vi = tổng các số dương trên hàng chứa vi  Số bậc vào của đỉnh vi = trị tuyệt đối của tổng các số âm trên hàng chứa vi 4.2.4 ĐỒ THỊ ĐẲNG CẤU Định nghĩa Hai đồ thị gọi là đẳng cấu nhau nếu có sự tương ứng 1 – 1 giữa các đỉnh và các cạnh (cung) với nhau. Định lý Cho G1 = (V1, E1), G2(V2, G2) là 2 đồ thị đẳng cấu. Khi đó: (i) G1, G2 có số cạnh và số đỉnh bằng nhau. (ii) Số đỉnh bậc k của G1 và G2 bằng nhau. (iii) Số chu trình đơn, sơ cấp có chiều dài k của G1 và G2 bằng nhau. Chú ý: Nếu các bất biến về đỉnh, cạnh, bậc, chu trình đều phù hợp thì G1 có thể đẳng cấu với G2. Để tìm phép đẳng cấu ta tìm đường đi qua tất cả các đỉnh sao cho các đỉnh tương ứng trong 2 đồ thị cùng bậc. Ví dụ Không đẳng cấu b 4 a c 1 3 5 e d 2 G H Đẳng cấu Đường đi: a, b, c, d, e Tương ứng: Tương ứng với đường a-1, b-2, c-3, d-4, e-5 đi: 1, 2, 3, 4, 5 ĐỒ THỊ LƯỠNG PHÂN Đồ thị lưỡng phân G = (V, E) là đồ thị mà tập các đỉnh được phân làm 2 tập rời nhau V1, V2 sao cho mỗi cạnh của đồ thị liên kết với 1 đỉnh thuộc V1 và 1 đỉnh thuộc V2. Kí hiệu: G = ({V1, V2}, E) Ví dụ a b c x y z 4.3 ĐỒ THỊ EULER 4.3.1 Định nghĩa Cho đồ thị vô hướng G = (V, E)  Đường đi Euler là đường đi đơn qua mọi cạnh và mọi đỉnh đồ thị.  Chu trình Euler là chu trình đơn qua mọi cạnh và mọi đỉnh đồ thị. Cho đồ thị có hướng G = (V, E)  Đường đi có hướng Euler là đường đi đơn có hướng qua mọi cung và mọi đỉnh đồ thị.  Chu trình có hướng Euler là chu trình đơn có hướng qua mọi cung và mọi đỉnh đồ thị. Đồ thị chứa chu trình Euler gọi là đồ thị Euler Ví dụ a b c d e f Đồ thị Euler Chu trình Euler: a, b, c, f, e, b, d, c, a Ví dụ Đồ thị về 7 cây cầu của thành phố Konigsberg 3 1 2 4 Không có chu trình và đường đi Euler 4.3.1 Điều kiện cần và đủ để đồ thị có chu trình và đường đi Euler Đồ thị vô hướng:  Đồ thị G có chu trình Euler khi và chỉ khi G liên thông và mọi đỉnh đều có bậc chẵn khác 0.  Đồ thị G có đường đi Euler khi và chỉ khi G liên thông và có đúng 2 đỉnh bậc lẻ. Đồ thị có hướng:  Đồ thị có hướng G có chu trình có hướng Euler khi và chỉ khi G liên thông mạnh và mọi đỉnh đều có nửa bậc ra bằng nửa bậc vào. dv(v) = dr(v) Chú thích: Đồ thị liên thông mạnh là đồ thị có hướng mà mọi cặp đỉnh của nó đều có đường đi có hướng nối chúng với nhau. Các thuật toán tìm chu trình Euler Đầu vào: Đồ thị G   , không có đỉnh cô lập Đầu ra: Chu trình Euler C của G, hoặc kết luận G không có chu trình Euler. Phương pháp: (1) Xuất phát: Đặt H  G, k 1, C  . Chọn đỉnh vC bất kì. (2) Xuất phát từ v, xây dựng chu trình bất kì Ck trong H.  Nếu tồn tại Ck nối Ck vào C, C  CCk  sang bước 3.  Nếu không tồn tại Ck thì kết luận không có chu trình Euler  Kết thúc (3) Loại khỏi H chu trình Ck. Nếu H chứa các đỉnh cô lập thì loại chúng ra khỏi H  sang bước 4. (4) Nếu H =  thì kết luận C là chu trình Euler  Kết thúc, ngược lại sang bước 5 (5) Nếu H và C không có đỉnh chung thì kết luận không có chu trình Euler H và C có đỉnh chung. Chọn v là đỉnh chung của H và C. Đặt k:= k+1. Quay lại bước 2. Ví dụ Cho G là đồ thị Thanh mã tấu Mohammed a j e i f b h g c d k Áp dụng thuật toán 1 để tìm chu trình Euler. (1) Đặt H := G, k := 1, C := , v := f. (2) Ta xây dựng chu trình C1 trong H: C1 := (f,g,k,h,i,e,b,c,d,f) Đặt C := C  C1 = (f,g,k,h,i,e,b,c,d,f) (3) Loại C1 ra khỏi H, ta được đồ thị H như sau a j e i f b h g c d k Các đỉnh c và k là các đỉnh cô lập, vì thế ta loại chúng ra khỏi H. (5) Chọn đỉnh chung của H và C là v := f. Đặt k := k+1 = 2. Quay lại bước (2) (2) Ta xây dựng chu trình C2 trong H: C2 := (f,i,j,h,g,d,b,a,e,f) Nối C2 vào C ta được chu trình C sau C := C  C2 = (f,g,k,h,i,e,b,c,d,f)  (f,i,j,h,g,d,b,a,e,f) = (f,g,k,h,i,e,b,c,d,f,i,j,h,g,d,b,a,e,f) (3) Loại C2 ra khỏi H, ta được đồ thị H gồm toàn các đỉnh cô lập. Loại các đỉnh cô lập ta có H = . (4) Vì H = , ta kết luận C là chu trình Euler, kết thúc.  Thuật toán 2 (Fleury) + Đầu vào. Đồ thị G  , không có đỉnh cô lập. + Đầu ra. Chu trình Euler C của G, hoặc kết luận G không có chu trình Euler. + Phương pháp. (1) Chọn đỉnh xuất phát bất kỳ vo. Đặt v1 := vo, C := (vo). H := G. (2) Nếu H = , thì kết luận C là chu trình Euler, kết thúc. Ngược lại sang bước (3). (3) Chọn cạnh đi tiếp: - Trường hợp đỉnh v1 là đỉnh treo: Tồn tại duy nhất đỉnh v2 kề v1 .Chọn cạnh (v1, v2). Sang bước (4). - Trường hợp đỉnh v1 không là đỉnh treo: Nếu mọi cạnh liên thuộc v1 là cầu, thì không có chu trình Euler, kết thúc Ngược lại, chọn cạnh (v1, v2) bất kỳ không phải là cầu trong H. Thêm vào đường đi C đỉnh v2. Sang bước (4). (4) Xoá cạnh vừa đi qua, và xoá đỉnh cô lập: Loại khỏi H cạnh (v1, v2). Nếu H có đỉnh cô lập, thì loại chúng khỏi H. Đặt v1 := v2. Quay lại bước (2) Chú thích: Cạnh v gọi là cầu nếu bỏ cạnh đó thì đồ thị không liên thông. Ví dụ v1 v2 v 4 v5 v3 v 6 v7 Đồ thị liên thông và có các đỉnh bậc chẵn. Ta có chu trình Euler sau (v6, v4, v7, v5, v1, v3, v4, v2, v1, v4, v5, v2, v3, v6) 4.4 ĐỒ THỊ HAMINTON 4.4.1 Định nghĩa Cho đồ thị G = (V, E)  Đường đi Haminton là đường đi sơ cấp đi qua mọi đỉnh đồ thị.  Chu trình Hamintơn là chu trình sơ cấp đi qua mọi đỉnh đồ thị. Định nghĩa tương tự đối với đồ thị có hướng Đồ thị chứa chu trình Hamintơn gọi là đồ thị Hamintơn 4.4.2 Điều kiện cần Giả sử đồ thị G có chu trình Hamintơn C. Khi đó: i. G liên thông. ii. Mọi đỉnh của G đều có bậc  2 và có đúng 2 cạnh kề thuộc chu trình C. iii. Nếu xóa đi k đỉnh bất kì cùng các cạnh liên thuộc chúng thì đồ thị còn lại sẽ có tối đa k thành phần liên thông. 4.4.3 Điều kiện đủ Định lí 1 Cho G là đơn đồ thị n đỉnh (n  3). Nếu: n d(v)  ,  vG 2 thì G có chu trình Hamintơn Định lí 2 Cho G là đơn đồ thị n đỉnh (n  3). Nếu: n 1 d(v)  , vG 2 thì G có chu trình Hamintơn Định lí 3 Nếu G là đồ thị có hướng liên thông mạnh và: n n d (v)  & d (v)  ,vG r 2 v 2 thì G có chu trình có hướng Hamintơn 4.5 TÌM ĐƯỜNG ĐI NGẮN NHẤT 4.5.1 Đồ thị có trọng số: Là đồ thị mà mỗi cạnh của nó được gán 1 số. Trong đồ thị có trọng số, độ dài trọng số của đường đi  là tổng các trọng số trên đường đi đó. 4.5.2 Phát biểu bài toán: Cho đồ thị có trọng số G = (V, E). Tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z của đồ thị 4.5.3 Thuật toán Dijkstra: Tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z trong đồ thị có trọng số. Trọng số của cạnh (i,j) là w(i,j) > 0 và đỉnh x sẽ mang nhãn L(x). Khi kết thúc thuật giải L(z) chính là chiều dài đường đi ngắn nhất từ a đến z. Đầu vào: Đồ thị liên thông G = (V, E) có trọng số w(i, j) > 0 với mọi cạnh (i, j), đỉnh a và đỉnh z. Đầu ra: Chiều dài đường đi ngắn nhất và đường đi ngắn nhất. Phương pháp: (1) Gán L(a)  0. Với mọi đỉnh x  a gán L(x) = . Kí hiệu T  V (2) Chọn v T sao cho L(v) có giá trị nhỏ nhất. Đặt: T  T – {v} (3) Nếu z  T  Kết thúc. L(z) là đường đi ngắn nhất từ a đến z. Từ z lần ngược theo các đỉnh được ghi nhớ ta có đường đi ngắn nhất. Ngược lại sang bước 4. (4) Với mỗi x  T kề với v gán: L(x)  min{L(x), L(v) + w(v, x)} Nếu L(x) này thay đổi thì ghi nhớ đỉnh v cạnh x để sau này xây dựng đường đi ngắn nhất. Quay về bước 2. Ví dụ: Tìm đường đi ngắn nhất từ đỉnh a đến z trong đồ thị sau: b 2 c 4 2 2 3 1 4 z a d e 3 7 1 6 f 5 g Phương pháp lập bảng ghi nhãn: Ta lập bảng tính toán các nhãn gồm các cột ứng với các đỉnh, và các hàng ứng với các các lần tính nhãn ở bước 4. Các nhãn gạch dưới ứng với nhãn nhỏ nhất ở bước 2 và đỉnh bị loại ghi bên phải. Sau khi đỉnh z bị loại, từ z ta lần ngược về đỉnh a theo nhãn ghi trên bảng ta có đường đi ngắn nhất. Ví dụ Tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z của đồ thị sau: b 4 f 1 1 10 2 5 c 4 g 10 2 a 1 5 z 6 4 8 d 3 h 3 5 2 6 3 e 8 k 4.5.4 Thuật toán Floyd: Thuật giải tìm độ dài đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị có hướng liên thông có trọng số. + Đầu vào: Đồ thị liên thông G = (V,E), V= {1, 2, ... , n}, có trọng số w(i,j) >0 với mọi cung (i,j). + Đầu ra: Ma trận D=[d(i,j)], trong đó d(i,j) là chiều dài đường đi ngắn nhất từ i đến j với mọi cặp (i,j). + Phương pháp: (1) Bước khởi tạo: Ký hiệu D0 là ma trận xuất phát D0 = [d0(i,j)] trong đó: d0(i,j) = w(i,j) nếu tồn tại cung (i,j) d0 (i,j) = + nếu không tồn tại cung (i,j) (đặc biệt nếu không có khuyên tại i thì d0 (i,i) = +). Gán k:=0 (2) Kiểm tra kết thúc: Nếu k = n, kết thúc. D = Dn là ma trận độ dài đường đi ngắn nhất. Ngược lại: k:=k+1  sang (3). (3) Tính ma trận Dk theo Dk-1 Với mọi cặp (i,j), i=1..n, j=1..n thực hiện: Nếu dk-1(i,j) > dk-1(i,k) + dk-1(k,j) thì đặt dk (i,j) := dk-1(i,k) + dk-1(k,j) ngược lại đặt dk(i,j) := dk-1 (i,j) Quay lại bước (2).  Định lý: Thuật toán Floyd là đúng.  Hệ quả (i) Nếu ma trận kết quả của thuật toán Floyd có phần tử hữu hạn trên đường chéo chính thì đồ thị chứa chu trình. (ii) Nếu ma trận kết quả chứa phần tử + ngoài đường chéo chính thì đồ thị không liên thông mạnh. Ví dụ Xét đồ thị sau 1 7 2 4 3 2 4 2 1 1 2 3 4 5 6 Áp dụng thuật toán Floyd: Ma trận khoảng cách xuất phát D0 là (các ô trống là ): Đỉnh 1 2 3 4 5 6 1 7 2 D0  2 4 1 3 3 4 4 5 2 2 6 1 Đỉn 1 2 3 4 5 6 h 1 7 2 D = 1 2 4 1 3 3 4 4 5 2 9 2 4 6 1 Đỉn 1 2 3 4 5 6 h 1 7 11 2 8 D = 2 2 4 1 3 3 4 4 8 5 5 2 9 2 4 10 6 1 5 2 Đỉ 1 2 3 4 5 6 nh 1 7 11 2 8 14 D = 3 2 4 1 7 3 3 4 4 8 5 11 5 2 9 2 4 10 5 6 1 5 2 8 Đỉn 1 2 3 4 5 6 h D = 4 1 6 10 2 7 13 2 4 1 7 3 3 4 4 8 5 11 5 2 8 2 4 9 5 Đỉn 1 2 3 4 5 6 h 1 9 6 9 2 7 12 D5 = D = 2 3 9 3 5 5 1 6 3 3 4 7 4 7 9 5 10 5 2 8 2 4 9 5 6 4 1 4 6 2 7 Đỉn 1 2 3 4 5 6 h 1 9 6 9 2 7 12 D = D = 6 2 3 7 3 5 1 6 3 7 4 7 9 5 3 4 7 4 7 9 5 10 5 2 6 2 4 7 5 Cuối cùng,6 D là ma4 trận kho1 ảng4cách ng6ắn nhấ2t giữa c7ác đỉnh. Theo hệ quả ta thấy đồ thị liên thông mạnh và chứa chu trình. 4.6 CÂY 4.6.1 Định nghĩa Cây là đồ thị liên thông không chứa chu trình. Gốc thường là đỉnh trên cùng. Mức của đỉnh là độ dài đường đi từ gốc đến đỉnh đó. Độ cao của cây là mức lớn nhất của cây Gốc v1 v2 v3 v2, v3: mức 1 v4 v5 v6 v7 v4, v5, v6, v7 mức 2 Độ cao là 2 Một số thuật ngữ: Cho T là cây có gốc vo. Giả sử x, y, z là các đỉnh của T và (vo, v1,..., vn) là đường đi trong T. Khi đó ta gọi:  vn-1 là cha của vn  vo,...,vn-1 là tiền bối của vn  vn là con của vn-1  y là hậu thế của x, nếu x là tiền bối của y  y và z là anh em nếu chúng đều là con của đỉnh x  x là đỉnh lá nếu nó không có con  x là đỉnh trong của cây nếu nó có con. v1 v2 v3 v4 v5 v6 v7 v2 là cha của v4&v5 v4 là con của v2 v1, v2 là tiền bối của v4. v4&v5 là anh em v4, v5, v6, v7: đỉnh lá v1, v2, v3: đỉnh trong Rừng là đồ thị mà mỗi thành phần liên thông là cây Rừng gồm 3 cây Định lí Cho T là đồ thị n đỉnh. Các mệnh đề sau tương đương (i) T là cây (ii) T không chứa chu trình và có n-1 cạnh (iii) T liên thông và có n-1 cạnh (iv) T liên thông và mỗi cạnh là cầu (v) Hai đỉnh bất kỳ được nối với nhau bởi một đường đi duy nhất (vi) T không chứa chu trình và nếu thêm một cạnh nối hai đỉnh thì ta thu được đúng 1 chu trình Ví dụ Cho đồ thị G là rừng có t cây và n đỉnh. Tìm số cạnh của G. Đs: (n – t) cạnh 4.6.2 Cây m-phân Cây m-phân là cây mà mọi đỉnh có tối đa m con và có ít nhất một đỉnh có m con. Cây m-phân đầy đủ là cây mà mọi đỉnh trong có đúng m con. Cây cân bằng là cây mà mọi đỉnh lá có mức là h hay h- 1, trong đó h là chiều cao của cây. Định lí Nếu cây m-phân đầy đủ có i đỉnh trong thì nó có n = m.i + 1 đỉnh Hệ quả  Cho T là cây m-phân đầy đủ có i đỉnh trong, l đỉnh lá và n đỉnh (n = i + l). Khi đó: a. l = (m – 1)i + 1 l 1 ml 1 b. i  & n  m 1 m 1 n 1 (m 1)n 1 c. i  & l  m m Ví dụ 1. Cây ngũ phân đầy đủ với 100 đỉnh trong có bao nhiêu đỉnh tất cả? 2. Cây nhị phân đầy đủ với 1000 đỉnh trong có bao nhiêu cạnh tất cả? 3. Cây tam phân đầy đủ với 100 đỉnh trong có bao nhiêu lá tất cả? Định lí Cho T là cây m-phân có l lá và chiều cao h. Khi đó: l  mh Nếu T là cây m-phân cân bằng đầy đủ thì: h = ]logml[ Trong đó: ]x[ kí hiệu số nguyên nhỏ nhất lớn hơn hoặc bằng x 4.6.3 Cây phủ Cho đồ thị G=(V,E). Cây T gọi là cây phủ của G, nếu T là đồ thị con chứa tất cả các đỉnh của G. a b c d e f g h G T1 T2 Các cây T1, T2 là cây phủ của G Định lí Đồ thị G = (V, E) có cây phủ  G liên thông Các thuật toán tìm cây phủ Duyệt cây theo chiều rộng Trong thuật giải này ta ký hiệu S là dãy các đỉnh. + Đầu vào. Đồ thị G=(V,E) với các đỉnh: v1, v2,, vn + Đầu ra. Cây phủ T hoặc kết luận đồ thị không liên thông. + Các bước. (1) Khởi tạo: Đặt S := {v1}. T là đồ thị gồm 1 đỉnh v1 và không có cạnh, v1 là gốc. (2) Thêm cạnh: Với mỗi xS theo thứ tự, thêm cạnh (x,y) và đỉnh y vào T sao cho không tạo thành chu trình. Nếu thêm được thì sang bước (3). Nếu không thêm cạnh được nữa thì kết thúc. Khi đó nếu T chứa hết các đỉnh của đồ thị T là cây phủ, ngược lại đồ thị không liên thông. (3) Cập nhật S: Thay S bởi các con (trong T) của các đỉnh trong S theo thứ tự. Quay lại bước (2) Ví dụ Dùng thuật toán duyệt cây theo chiều rộng tìm cây phủ với gốc a: a b c d e f g h G Duyệt cây theo chiều sâu + Đầu vào. Đồ thị G=(V,E) với các đỉnh v1, v2,, vn + Đầu ra. Cây phủ T hoặc kết luận đồ thị không liên thông. + Các bước. (1) Khởi tạo: Đặt w := v1. T là đồ thị cây gồm 1 đỉnh v1 và không có cạnh, v1 là gốc của T. Ký hiệu e là số cạnh của T. Đặt e:=0. Sang bước (2) (2) Kiểm tra số cạnh:  Nếu e = n-1, kết thúc: T là cây phủ.  Nếu e < n-1, sang bước 3. (3) Thêm cạnh: Chọn cạnh (w,vk) với chỉ số k nhỏ nhất sao cho thêm cạnh (w,vk) và đỉnh vk vào T không tạo thành chu trình. - Nếu không tồn tại cạnh như vậy thì đến bước (4); - Ngược lại thêm cạnh (w,vk) và đỉnh vk vào T, số cạnh e tăng lên 1, e:=e+1, đặt w:=vk và quay lại bước (2). (4) Kiểm tra điều kiện kết thúc:  Nếu w = v1 , Kết thúc. Đồ thị không liên thông.  Nếu w  v1 sang bước (5) (5) Quay lui: Giả sử x là cha của w (trong T) đặt w := x. Quay lại bước (3) Ví dụ Dùng thuật toán duyệt cây theo chiều sâu tìm cây phủ với gốc a: a b c d e f g h G