Bài giảng Toán rời rạc - Chương 1: Các khái niệm cơ bản

Chương 2Các khái niệm cơ bảnCá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). Các khái niệm về đồ thị (tt)Đồ 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)}.abedcĐỉnh / Cạnh kềĐỉ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).Cạnh kề: là hai cạnh có ít nhất một đỉnh chung.Ánh xạ kềĐị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).Ví dụ (ánh xạ kề)Á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} .abedcCạnh / CungCạnh: cặp đỉnh (x, y)  E không sắp thứ tự.Cung : cặp đỉnh (x, y)  E có sắp thứ tự.Đồ thị có hướng / vô hướngĐịnh nghĩa 1.3- Đồ thị chỉ chứa các cạnh được gọi là đồthị vô hướngĐồ thị chỉ chứa các cung đượ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 bằng hai cung tương ứng. Đơn / đ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ắt là đồ 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ị.Đường điĐị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. Đường đi (tt)Độ 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.Chu 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ị.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ó.Bậc và bán bậcBậc (Degree) của đỉnh:Giả sử G(V,E) là đồ thị vô hướng. Khi đó:Bậc của đỉnh v (kí hiệu là Deg(v)) là số cạnh kề với đỉnh đó.Bán bậc:Giả sử G(V,E) là đồ thị có hướng. Khi đó:Bán bậc vào Deg-(v) là số cung đi vào đỉnh v.Bán bậc ra Deg+(v) là số cung đi ra từ đỉnh v.Định lý bắt tayĐối với đồ thị vô hướng:“Tổng bậc của tất cả các đỉnh bằng 2 lần số cạnh”Đối với đồ thị có hướng:“Tổng bán bậc vào của mọi đỉnh bằng tổng bậc ra của chúng”.Tính liên thôngVô hướng:Hai đỉnh u, v được gọi là liên thông nếu tồn tại đường đi giữa u và v.Đồ thị là liên thông nếu mọi cặp đỉnh đều liên thông với nhau.Có hướng:Đồ thị là liên thông mạnh nếu giữa mọi cặp đỉnh đều tồn tại đường đi.Nếu đồ thị có hướng G(V,E) không liên thông mạnh nhưng đồ thị vô hướng “tương ứng” là liên thông thì ta nói G liên thông yếu.Nếu G(V,E) không liên thông khi đó G được tách thành k thành phần liên thông (k>1).Tính liên thông (tt)Đồ thị gồm 2 thành phần liên thôngĐồ thị vô hướng liên thôngĐồ thị con, đồ thị bộ phậnĐị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ị bộ phận (riêng) của đồ thị G. Đồ thị con, đồ thị bộ phận (tt)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.Đẳng cấu đồ thịSự đẳng cấu 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 cấu 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.Đẳng cấu đồ thị (tt)Hai đồ thị sau là đẳng cấu với song ánh: S(ai) = xi , i = 1, 2, 3, 4.a1a2a3a4x1x2x3x4Một số dạng đồ thị đặc biệt(SV tự đọc tài liệu)Đồ thị đầy đủ.Đồ thị vòng.Đồ thị bánh xe.Đồ thị 2 phía....