Bài giảng Lý thuyết đồ thị

LÝ THUYẾT ĐỒ THỊ Giảng viên: PGS.TS. Hoàng Chí ThànhTrường Đại học Khoa học Tự nhiên, ĐHQG HN1MỞ ĐẦU	- Lý thuyết Đồ thị là một trong những ngành khoa học ra đời khá sớm.	- Lý thuyết Đồ thị giúp mô tả hình học và giải quyết nhiều bài toán thực tế phức tạp liên quan đến các khái niệm như: đường đi, chu trình, tập ổn định, chu số, sắc số, duyệt đồ thị, đường đi ngắn nhất, tâm đồ thị, luồng vận tải, đồ thị phẳng, cây bao trùm, cây biểu thức, cây mã tối ưu bằng các thuật toán ngắn gọn và lý thú.	- Lý thuyết Đồ thị đã gắn kết nhiều ngành khoa học với nhau.2MỞ ĐẦU (tiếp)	Bài giảng điện tử “Lý thuyết Đồ thị” này bao gồm: 	- 11 chương 	- phân thành 20 bài học 	trình bày những vấn đề cốt lõi nhất của lý thuyết đồ thị cùng các thuật toán tiêu biểu; giúp người học có thể cài đặt trên máy tính và ứng dụng trong thực tế.3CHƯƠNG 1ĐẠI CƯƠNG VỀ ĐỒ THỊ4NỘI DUNG Các khái niệm về đồ thị Biểu diễn đồ thị trong máy tính Một số tính chất về đường đi trên đồ thị Bậc của đỉnh và tính liên thông51.1. CÁC KHÁI NIỆM VỀ ĐỒ THỊ Định nghĩa 1.1	 Đồ thị là một cặp G = (V, E), trong đó:- V là tập hợp các đỉnh (vertex),- E  V  V là tập hợp các cạnh (edge). 6VÍ DỤ 1.1	Đồ thị G cho như hình vẽ.- Tập đỉnh V = {a, b , c, d, e}, - Tập các cạnh E = {(a, b), (a, c), (b, c), (d, b), 	(d, c), (e, a), (e, b), (e, d)}. 	Hình 1.1: Đồ thị hữu hạnabedc7TÍNH KỀ TRONG ĐỒ THỊ 	Đỉnh kề: 	Nếu (a,b) là một cạnh của đồ thị G thì: - Đỉnh b kề với đỉnh aHai đỉnh a và b cùng kề với cạnh (a,b).Hai cạnh kề nhau: là hai cạnh có ít nhất một đỉnh chung.8ĐỊNH NGHĨA ĐỒ THỊ (tiếp) Định nghĩa 1.2	 Đồ thị là một cặp G = (V, F), trong đó:- V là tập hợp các đỉnh, - F : V  2V , được gọi là ánh xạ kề. Sự tương đương của hai định nghĩa:	 x, y  V : (x, y)  E  y  F(x).9VÍ DỤ 1.2 Ánh xạ kề của đồ thị trên hình vẽ:F(a) = {b, c} , F(b) = {c} , F(c) =  , F(d) = {b, c} và F(e) = {a, b, d} . Hình 1.1: Đồ thị hữu hạnabedc10ĐỒ THỊ VÔ HƯỚNG VÀ CÓ HƯỚNG Cạnh vô hướng: cặp đỉnh (x, y)  E không sắp thứ tự. Cạnh có hướng: cặp đỉnh (x, y)  E có sắp thứ tự.11ĐỒ THỊ VÔ HƯỚNG VÀ CÓ HƯỚNG (tiếp) Định nghĩa 1.3- Đồ thị chỉ chứa các cạnh vô hướng được gọi là đồthị vô hướngĐồ thị chỉ chứa các cạnh có hướng được gọi là đồ thị có hướng.	Mỗi đồ thị vô hướng có thể biểu diễn bằng một đồ thị có hướng bằng cách thay mỗi cạnh vô hướng bằng hai cạnh có hướng tương ứng. 12ĐỒ THỊ ĐỐI XỨNGĐịnh nghĩa 1.4 Đồ thị G = (V, E) được gọi là đối xứng nếu:	  x, y  V : (x, y)  E  (y, x)  E.	- Các đồ thị vô hướng là đối xứng.13ĐƠN VÀ ĐA ĐỒ THỊ Định nghĩa 1.5	- Đồ thị G = (V, E) mà mỗi cặp đỉnh được nối với nhau không quá một cạnh được gọi là đơn đồ thị (gọi tắtlà đồ thị). 	- Đồ thị có những cặp đỉnh được nối với nhau nhiều hơn một cạnh thì được gọi là đa đồ thị.141.2. ĐƯỜNG ĐI VÀ CHU TRÌNH Định nghĩa 1.6: Cho G = (V, E) là một đồ thị. Đường đi trong đồ thị là một dãy các đỉnh: sao cho mỗi đỉnh trong dãy (không kể đỉnh đầu tiên) kề với đỉnh trước nó bằng một cạnh nào đó, nghĩa là: 	  i = 2, 3, ... , k-1, k : (xi-1, xi)  E. Ta nói rằng đường đi này đi từ đỉnh đầu x1 đến đỉnh cuối xk. 15ĐƯỜNG ĐI Độ dài của đường đi: là số cạnh của đường đi đó. Đường đi đơn: Các đỉnh trên nó khác nhau từng đôi một.16CHU TRÌNH Định nghĩa 1.7 Chu trình là một đường đi khép kín (đỉnh cuối trùng với đỉnh đầu của đường). [x1, x2,, xi, xi+1,, xk-1, xk] 	 	trong đó x1 = xk.	- Để cho gọn, trong ký hiệu của chu trình thường không viết đỉnh cuối:	[x1, x2,, xi, xi+1,, xk-1] 	Ký hiệu: n là số đỉnh, m là số cạnh của một đồ thị.17CHU TRÌNH (tiếp) Chu trình đơn: là chu trình mà các đỉnh trên nó khác nhau từng đôi. Đỉnh nút: là đỉnh kề với chính nó. 181.3. ĐỒ THỊ CON VÀ ĐỒ THỊ RIÊNG Định nghĩa 1.8 Giả sử G = (V, E) là một đồ thị. - Đồ thị G’ = (V’, E’) được gọi là đồ thị con của đồ thị G nếu:	 V’  V và E’ = E  (V’  V’).- Đồ thị G” = (V, E”) với E”  E, được gọi là đồ thị riêng của đồ thị G. 191.3. ĐỒ THỊ CON VÀ ĐỒ THỊ RIÊNG (tiếp) Một số kết quả- Mỗi tập con các đỉnh V’ của đồ thị tương ứng duy nhất với một đồ thị con.- Để xác định một đồ thị con ta chỉ cần nêu tập đỉnh của nó. - Đồ thị riêng là đồ thị giữ nguyên tập đỉnh và bỏ bớt một số cạnh.201.4. SỰ ĐẲNG HÌNH Sự đẳng hình của hai đồ thị dựa trên sự đẳng cấu của hai tập đỉnh sao cho sự đẳng cấu ấy bảo toàn được các cạnh của đồ thị. Định nghĩa 1.9 Hai đồ thị G1 = (V1, E1) và G2 = (V2, E2 ) được gọi làđẳng hình với nhau nếu tồn tại một song ánh S trêncác tập đỉnh bảo toàn các cạnh:  x, y  V1 : (x, y)  E1  (S(x), S(y))  E2. 211.4. SỰ ĐẲNG HÌNH (tiếp)Hai đồ thị đẳng hình chỉ khác nhau về tên gọi của các đỉnh và cách biểu diễn bằng hình vẽ.	Do vậy, ta không phân biệt hai đồ thị đẳng hình với nhau22VÍ DỤ 1.3Hai đồ thị sau là đẳng hình với song ánh: S(ai) = xi , i = 1, 2, 3, 4.Hình 1.3. Hai đồ thị đẳng hình a1a2a3a4x1x2x3x4231.5. BIỂU DIỄN ĐỒ THỊ TRONG MÁY TÍNH Biểu diễn bằng ma trận kề Biểu diễn bằng danh sách kề24BIỂU DIỄN BẰNG MA TRẬN KỀ Định nghĩa 1.10Cho G = (V, E) là một đồ thị có các đỉnh được đánh số là các số tự nhiên: 1, 2, ... , n. Ma trận vuông A cấp n được gọi là ma trận kề của đồ thị G nếu:  i, j  V, A[i,j] = số cạnh nối đỉnhi với đỉnh j trong G. Đồ thị G là đối xứng khi và chỉ khi ma trận kề A là đối xứng 25VÍ DỤ 1.4Ma trận kề của đa đồ thị có hướng: 	0 1 1 2	 A =	0 0 1 0	0 0 1 0	 0 0 1 0Hình 1.3. Đồ thị có hướng và ma trận kề124326BIỂU DIỄN BẰNG MA TRẬN KỀ (tiếp)Định lý 1.1Phần tử ở hàng i và cột j của ma trận luỹ thừa Ak chính là số các đường đi khác nhau có độ dài k nốiđỉnh i với đỉnh j trong đồ thị G.27BIỂU DIỄN BẰNG MA TRẬN KỀ (tiếp)Chứng minh:Quy nạp theo độ dài k của đường đi - k = 1: suy từ định nghĩa ma trận kề.- (k)  (k+1)Ký hiệu A = [aij], Ak = [bij], C = Ak.A = [cij] Khi đó cij =  biq aqjiqjHình 1.4: Các đường đi từ đỉnh i đến đỉnh j qua đỉnh q28BIỂU DIỄN BẰNG MA TRẬN KỀ (tiếp)Chứng minh:Theo giả thiết quy nạp, với q bất kỳ (1  q  n), biq chính là số đường đi từ đỉnh i đến đỉnh q có độ dài k.- Nếu aqj = d  1 thì có cạnh đi từ q đến j, do vậy có các đường đi từ i đến j qua q với độ dài k+1, mà số các đường đi đó chính là d * biq .29BIỂU DIỄN BẰNG MA TRẬN KỀ (tiếp)Chứng minh:- Nếu aqj = 0 thì không có cạnh từ q đến j, do đó cũng không có đường đi từ i đến j qua q với độ dài k+1.Vậy tính theo tổng trên, ta sẽ có tất cả các đường đi từ i đến j với độ dài k+1.  30BIỂU DIỄN BẰNG DANH SÁCH KỀ Với mỗi đỉnh của đồ thị ta xây dựng một danh sách móc nối chứa các đỉnh kề với đỉnh này: Danh sách này được gọi là danh sách kề. Một đồ thị được biểu diễn bằng một mảng các danh sách kề.31VÍ DỤ 1.5Đồ thị và danh sách kề biểu diễn đồ thị tương ứng:Hình 1.5. Mảng các danh sách kề biểu diễn đồ thịabedc32