Chương 4: Lý thuyết đồ thị

Chương 4: LÝ THUYẾT ĐỒ THỊ Chương 4 4.3 ĐỒ THỊ EULER 4.4 ĐỒ THỊ HAMILTON CÂY4.6 BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT4.5 MỞ ĐẦU4.1 CÁC KHÁI NIỆM CƠ BẢN4.2 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 e w 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 e w Mỗi cạnh e được liên kết với một cặp đỉnh (v, w) có thứ tự Ví dụ:  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 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  Đỉ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 4.2 CÁC KHÁI NIỆM CƠ BẢN Đỉnh cô lập có bậc bằng 0 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| MỘT SỐ TÍNH CHẤT * Tính chất 1: * 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 đơ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.  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.  Đườ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.  Đườ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.  Chu trình có hướng là đường đi có hướng có đỉnh đầu và đỉnh cuối trùng nhau. c ba d e Ví dụ v6v5 v4 v3 v2v1 e8 e7 e6e5 e4 e3 e2 e1 e9  Đồ 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. v4v5 v3 v2v1 Có ma trận kề là: 01000v5 10111v4 01210v3 01101v2 01010v1 v5v4v3v2v1 Vv,aa)v(d i n 1j ji n 1j iji    Ví dụ: Tổng bậc của v1  Đồ 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ụ: v6 v5 v4 v3 v2 v1 e4 e3 e2 e1 e5 e8 e7 e6 000000v6 100000v5 110000v4 001000v3 001100v2 000110v1 v6v5v4v3v2v1 tổng bậc ra của v1 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 1j ijiv a)v(d và Vv,a)v(d i n 1j jiir   số bậc vào của đỉnh vi = tổng các số trên cột vi số bậc ra của đỉnh vi = tổng các số trên hàng 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:     0 1 aij nếu đỉnh vi liên thuộc cạnh ej nếu đỉnh vi không liên thuộc cạnh ej Ví dụ: v4v5 v3 v2v1 e5 e4 e3e2 e1 e6 e7 0100000v5 0110110v4 1011000v3 0001101v2 0000011v1 e7e6e5e4e3e2e1 Ma trận liên thuộc: Tổng bậc của v1 Vv,a)v(d i n 1j iji   Mệnh đề: Cho đồ thị đơn G = (V, E) với ma trận liên thuộc (aij)nm. Khi đó: 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:       0 1 1 aij nếu đỉnh vi là đỉnh đầu của cung ej nếu đỉnh vi không kề cung ej nếu đỉnh vi là đỉnh cuối của cung ej Ví dụ: v6 v5 v4 v3 v2 v1 e4 e3 e2 e1 e5 e8 e7 e6 -1-1000000v5 0 1 0 0 0 e7 1-100000v6 01-1-1000v4 0010-1-10V3 000110-1v2 0000011v1 e8e6e5e4e3e2e1 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 Đị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. 4.2.4 ĐỒ THỊ ĐẲNG CẤU 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 ab c de 1 2 3 4 5 Đẳng cấu Đường đi: a, b, c, d, e Tương ứng với đường đi: 1, 2, 3, 4, 5 Tương ứng: a-1, b-2, c-3, d-4, e-5 G H ĐỒ 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 1 2 3 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ị G có đường đi Euler khi và chỉ khi G liên thông và có đúng 2 đỉnh bậc lẻ.  Đồ 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ị vô 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. 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. Đồ thị có hướng: dv(v) = dr(v) 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: Xuất phát: Đặt H  G, k 1, C  . Chọn đỉnh vC bất kì. Xuất phát từ v, xây dựng chu trình bất kì Ck trong H. (1) (2)  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 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. 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 (3) (4) 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. (5) Cho G là đồ thị Thanh mã tấu Mohammed a b c d e f g h i j k Áp dụng thuật toán 1 để tìm chu trình Euler. Ví dụ (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 b c d e f g h i j 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 v3 v4 v5 v6 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ị. Đồ thị chứa chu trình Hamintơn gọi là đồ thị Hamintơn Định nghĩa tương tự đối với đồ thị có hướng 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 đủ Cho G là đơn đồ thị n đỉnh (n  3). Nếu: Gv, 2 n )v(d  thì G có chu trình Hamintơn Cho G là đơn đồ thị n đỉnh (n  3). Nếu: Gv, 2 1n )v(d    thì G có chu trình Hamintơn Định lí 1 Định lí 2 Định lí 3 Nếu G là đồ thị có hướng liên thông mạnh và: Gv, 2 n )v(d& 2 n )v(d vr  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: a f ed cb g z 2 1 2 14 3 4 2 67 5 3 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. hg f e d c b a k z 3 6 4 10 10 5 4 1 2 1 4 2 2 8 8 3 5 5 3 1 6 Ví dụ Tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z của đồ thị sau: 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) 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). (đặc biệt nếu không có khuyên tại i thì d0 (i,i) = +). (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ụ 1 2 3 4 5 6 7 4 2 1 3 2 4 1 2 Xét đồ thị sau 16 225 44 33 142 271 654321Đỉnh Á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à ): D0  D1 = 16 42925 44 33 142 271 654321 Đỉn h D2 = 2516 1042925 5844 33 142 821171 654321 Đỉn h D3 = 82516 51042925 115844 33 7142 14821171 654321 Đỉ nh 5942825 115844 33 7142 13721061 654321 Đỉn h D4 = D5 = D5 = 7264146 5942825 10597474 33 6153932 12729691 654321 Đỉn h D = D6 = 7264146 5742625 10597474 3597473 6153732 12729691 654321 Đỉn h Cuối cùng, D là ma trận khoảng cách ngắn nhất giữa cá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 Cây là đồ thị liên thông không chứa chu trình. v1 v2 v3 v4 v5 v6 v7 Gốc v2, v3: mức 1 v4, v5, v6, v7 mức 2 4.6.1 Định nghĩa 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 Độ 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 v1, v2 là tiền bối của v4. v4 là con của v2 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 m 1)n1(m l& m 1n ic. 1m 1ml n& 1m 1l ib.           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ụ a b c d e f g h G 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: 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).  Nếu w = v1 , Kết thúc. Đồ thị không liên thông.  Nếu w 